SDE - Intern Unthinkable Solutions interview experience | Abhishek Chand Jha

Interview rounds

Round

Medium

Online Coding Interview

Duration90 minutes

Interview date4 Oct 2019

Coding problem2

We have been assigned 2 coding problems 1 easy and one medium-level question.
As I submitted all three questions I was selected for direct technical interview round but some of my friends got second round test they needed to clear that second round to get an interview call so try to submit all the questions.

1. Min Jumps

Easy

15m average time

85% success

0/40

Asked in companies

You live in a Ninja town which is in the form of a N * M grid. In this town, people travel from one place to another by jumping over the buildings which are present in each cell of the grid. It is Christmas eve, and Santa wants to give gifts and chocolates to the kids who live in the building which is present at the cell (N - 1, M - 1). Initially, Santa is present on cell (0, 0). Since Santa is in a hurry, help him find a path from starting point to the endpoint with the least amount of time.

The Santa may go only from one building to any of its adjacent buildings which is present either to the right or to the bottom or bottom right cell i.e. if the current position is (x, y), he may go to (x + 1, y + 1) or (x + 1, y) or (x, y + 1) given that the new coordinates are in the grid. The time taken to reach from one building to another is equal to the absolute difference between the heights of buildings.

Note:

1. The heights of the buildings are positive.
2. Santa starts from the cell (0, 0) and he has to reach the building (N - 1, M - 1).
3. Santa cannot leave the grid at any point of time.

Problem approach

Since each element of our input array (N) represents the maximum jump length and not the definite jump length, that means we can visit any index between the current index (i) and i + N[i]. Stretching that to its logical conclusion, we can safely iterate through N while keeping track of the furthest index reachable (next) at any given moment (next = max(next, i + N[i])). We'll know we've found our solution once next reaches or passes the last index (next >= N.length - 1).

The difficulty then lies in keeping track of how many jumps it takes to reach that point. We can't simply count the number of times we update next, as we may see that happen more than once while still in the current jump's range. In fact, we can't be sure of the best next jump until we reach the end of the current jump's range.

So in addition to next, we'll also need to keep track of the current jump's endpoint (curr) as well as the number of jumps taken so far (ans).

Since we'll want to return ans at the earliest possibility, we should base it on next, as noted earlier. With careful initial definitions for curr and next, we can start our iteration at i = 0 and ans = 0 without the need for edge case return expressions.

Try solving now

2. Replace Each Element Of Array With Its Corresponding Rank

Easy

10m average time

90% success

0/40

Asked in companies

Given an array of integers 'ARR’ of size ‘N’. Replace each element of this array with its corresponding rank and return the array.

The rank of an element is an integer between 1 to ‘N’ inclusive that represents how large the element is in comparison to other elements of the array. The following rules can also define the rank of an element:

1. It is an integer starting from 1.

2. The larger the element, the larger the rank. If two elements are equal, their rank must be the same.

3. It should be as small as possible.

For Example:

'ARR' = [4, 7, 2, 90]

Here, 2 is the smallest element, followed by 4, 7, and 90. 

Hence rank of element 2 is 1, element 4 is 2, element 7 is 3, and element 90 is 4.

Hence we return [2, 3, 1, 4].

Problem approach

A Simple Solution is to create an auxiliary array, copy contents of given array to auxiliary array. Finally traverse the auxiliary array and update given array using copied values. Time complexity of this solution is O(n), but it requires O(n) extra space.
An efficient solution can solve the problem in O(n) time and O(1) space. The idea is to keep track of previous element in loop.

Try solving now

Round

Easy

Online Coding Test

Duration50 minutes

Interview date3 Oct 2021

Coding problem3

He asked me to tell me about yourself and then started talking about my project which technologies you used what challenges you faced while working on this project, what was role in this project and all then he asked me about how good you are with OOPs concept I said I’m pretty much familiar with oops so he started asking about oops like what is oops how it could be useful while writing the code, what is encapsulation and interface, how you can obtain multi-Inheritance in OOPs.

1. Pattern: Triangle of numbers

Moderate

0/80

Asked in companies

Print the following pattern for the given number of rows.

Pattern for N = 4

The dots represent spaces.

Problem approach

Well this can be done easily done if you observe the pattern there all you need to take a count of stars and space variable to keep track of what is used in previous step now keep increasing your star and decrease you space while printing for each row from bottom to top.
problem will be solved using two for loop and 2 variables.

Try solving now

2. Is SubSequence

Easy

10m average time

90% success

0/40

Asked in companies

You have been given two strings ‘STR1’ and ‘STR2’.

Your task is to find if ‘STR1’ is a subsequence of ‘STR2’.

A subsequence of a string is a new string that can be derived from the original string by deleting some characters (can be none) without changing the relative ordering of other characters.

Example:

‘ACE’ is a subsequence of ‘ABCDE’ because ‘ACE’ can be formed by deleting ‘B’ and ‘D’ without changing the relative order of characters. ‘ADB’ is not a subsequence of ‘ABCDE’ because we can get ‘ABD’ from ‘ABCDE’ but not ‘ADB’ and in ‘ADB’ relative order of ‘B’ and ‘D’ are different from original strings.

Note:

1.Strings ‘STR1’ and ‘STR2’ consists only of English uppercases.

2.Length of string ‘STR2’ will always be greater than or equal to the length of string ‘STR1’.

Example:

For example, the given ‘STR1’ is ‘BAE’ and ‘STR2’ is ‘ABADE’. 
String ‘STR1’ is a subsequence of string ‘STR2’ because ‘BAE’ can be formed by deleting ‘A’ and ‘D’ from ‘ABADE’ and the relative ordering of the characters of the string ‘ABADE’ persists.

Problem approach

All you need to find is LCS of both the string if LCS == target.size() return true else false
By LCS I mean longest common substring.

Try solving now

3. Number Pattern

Easy

15m average time

85% success

0/40

Asked in companies

Ninja wants to build a number pattern.

Example For ‘N’ = 4 

Pattern:

4444
3444
2344
1234

Your task is to make a program that prints a similar pattern for a given 'N'.

Problem approach

The idea is that we can use a stack to keep track of previous min-max intervals.

Here is the principle to maintain the stack:

For each number num in the array

If stack is empty:

push a new Pair of num into stack
If stack is not empty:

if num < stack.peek().min, push a new Pair of num into stack

if num >= stack.peek().min, we first pop() out the peek element, denoted as last

if num < last.max, we are done, return true;

if num >= last.max, we merge num into last, which means last.max = num.
Once we update last, if stack is empty, we just push back last.
However, the crucial part is:
If stack is not empty, the updated last might:

Entirely covered stack.peek(), i.e. last.min < stack.peek().min (which is always true) && last.max >= stack.peek().max, in which case we keep popping out stack.peek().
Form a 1-3-2 pattern, we are done ,return true
So at any time in the stack, non-overlapping Pairs are formed in descending order by their min value, which means the min value of peek element in the stack is always the min value globally.

Try solving now

Round

Medium

Coding Test - Pen and paper

Duration40 minutes

Interview date2 Oct 2021

Coding problem3

After this, under 5-10 minutes I got call for the second technical interview and it’s occurred just after 5 minutes the first interview now in this interview he gave me 3 medium level DSA problems.

1. Spiral Matrix

Easy

0/40

Asked in companies

You are given a N x M matrix of integers, return the spiral path of the matrix

Example Of Spiral Path

Problem approach

Traverse the matrix in the spiral order by keeping four variables: u for the uppermost row, d for the downmost row, l for the leftmost column and r for the rightmost column.

Try solving now

2. Longest Common Subsequence

Moderate

39m average time

0/80

Asked in companies

Given two strings, 'S' and 'T' with lengths 'M' and 'N', find the length of the 'Longest Common Subsequence'.

For a string 'str'(per se) of length K, the subsequences are the strings containing characters in the same relative order as they are present in 'str,' but not necessarily contiguous. Subsequences contain all the strings of length varying from 0 to K.

Example :

Subsequences of string "abc" are:  ""(empty string), a, b, c, ab, bc, ac, abc.

Problem approach

Bottom-up DP
For every i in text1, j in text2, we will choose one of the following two options:

If two characters match, length of the common subsequence would be 1 plus the length of the common subsequence till the i-1 andj-1 indexes
If two characters doesn't match, we will take the longer by either skipping i or j indexes

Try solving now

3. Count characters

Easy

0/40

Asked in companies

Write a program to count and print the total number of characters (lowercase english alphabets only), digits (0 to 9) and white spaces (single space, tab i.e. '\t' and newline i.e. '\n') entered till '$'.

That is, input will be a stream of characters and you need to consider all the characters which are entered till '$'.

Print count of characters, count of digits and count of white spaces respectively (separated by space).

Problem approach

Well Interviewer asked me to solve this question without using hashmap, so I've used a constant size array to store the frequency of each character in my string then I've easily counted the frequency of each character.

Try solving now

Round

Easy

HR Round

Duration20 minutes

Interview date2 Oct 2021

Coding problem1

After this, I got a call for my HR interview which was smoothest one out of all the rounds she discussed the salary structure and job hours how to reach the office, and all that’s it and she said take your time to accept this offer and finally got the congratulation mail from the HR department of unthinkable solution whole interview process was smooth.