SDE - 1 Ameyo (Drishti Soft Solutions Pvt. Ltd.) interview experience

Interview rounds

Round

Easy

Face to Face

Duration60 minutes

Interview date8 Jun 2015

Coding problem3

Technical Interview round with questions on DSA.

1. Merge two sorted arrays

Moderate

15m average time

85% success

0/80

Asked in companies

Ninja has been given two sorted integer arrays/lists ‘ARR1’ and ‘ARR2’ of size ‘M’ and ‘N’. Ninja has to merge these sorted arrays/lists into ‘ARR1’ as one sorted array. You may have to assume that ‘ARR1’ has a size equal to ‘M’ + ‘N’ such that ‘ARR1’ has enough space to add all the elements of ‘ARR2’ in ‘ARR1’.

For example:

‘ARR1’ = [3 6 9 0 0]
‘ARR2’ = [4 10]
After merging the ‘ARR1’ and ‘ARR2’ in ‘ARR1’. 
‘ARR1’ = [3 4 6 9 10]

Problem approach

A simple approach would be to create a new arrays with size as sum of the sizes of both the arrays. Copy the elements of both the arrays in the new array and sort the array.
A space optimised approach also exists. While traversing the two sorted arrays parallelly, if we encounter the jth second array element is smaller than ith first array element, then jth element is to be included and replace some kth element in the first array.

Algorithm
1) Initialize i,j,k as 0,0,n-1 where n is size of arr1
2) Iterate through every element of arr1 and arr2 using two pointers i and j respectively
if arr1[i] is less than arr2[j]
increment i
else
swap the arr2[j] and arr1[k]
increment j and decrement k
3) Sort both arr1 and arr2

Try solving now

2. Print all permutations of a string

Easy

30m average time

80% success

0/40

Asked in companies

You are given an input string 'S'. Your task is to find and return all possible permutations of the input string.

Note:

1. The input string may contain the same characters, so there will also be the same permutations.

2. The order of permutation does not matter.

Problem approach

We can use the concept of backtracking.
According to the backtracking algorithm:
o Fix a character in the first position and swap the rest of the character with the first character. Like in ABC, in the first iteration three strings are formed: ABC, BAC, and CBA by swapping A with A, B and C respectively.
o Repeat step 1 for the rest of the characters like fixing second character B and so on.
o Now swap again to go back to the previous position. E.g., from ABC, we formed ABC by fixing B again, and we backtrack to the previous position and swap B with C. So, now we got ABC and ACB.
o Repeat these steps for BAC and CBA, to get all the permutations.
Algorithm
1. Define a string.
2. Fix a character and swap the rest of the characters.
3. Call the generatePermutation() for rest of the characters.
4. Backtrack and swap the characters again.

Try solving now

3. Sort a linked list

Easy

15m average time

85% success

0/40

Asked in companies

You are given a Singly Linked List of integers which is sorted based on absolute value.

You have to sort the Linked List based on actual values.

The absolute value of a real number x, denoted |x|, is the non-negative value of x without regard to its sign.

Example:

If the given list is {1 -> -2 -> 3} (which is sorted on absolute value), the returned list should be {-2 -> 1 -> 3}.

Problem approach

1) If the list contains only one node, return the head of the list.

2) Else, divide the list into two sublists. For this, we will take pointers ‘MID’ and ‘TAIL’ which will initially point to the head node. We will change ‘MID’ and ‘TAIL’ as follows until ‘TAIL’ becomes NULL:

‘MID = MID->next'
‘TAIL = TAIL->next->next’

3)The above operation will ensure that mid will point to the middle node of the list. ‘MID’ will be the head of the second sublist, so we will change the ‘next’ value of the node which is before mid to NULL.

4) Call the same algorithm for the two sublists.

5) Merge the two sublists and return the head of the merged list. For this, we will make a list ‘MERGE_LIST’ which will be initially empty. If the head of the first sublist has a value less than the head of the second sublist then we will add the head of the first sublist in the ‘MERGE_LIST’ and change the head to its next value. Else, we will add the head of the second sub list. In the end, if any of the sublists becomes empty and the other sublist is non-empty, then we will add all nodes of the non-empty sublist in the ‘MERGE_LIST’.

Try solving now

Round

Easy

Face to Face

Duration60 minutes

Interview date8 Jun 2015

Coding problem3

Technical round with questions on DSA and OOPS concepts.

1. Implement a specialStack class which should support O(1) push O(1) pop and should return minimum element in the stack in O(1) time

Moderate

15m average time

85% success

0/80

Asked in companies

Create a stack data structure that allows operations such as push (adding an element), pop (removing the top element), top (retrieving the top element), and also provides a way to retrieve the minimum element in constant time.

Implement the following public functions :

1. push(data) :
This function should take one argument of type integer. It pushes the element into the stack and returns nothing.

2. pop() :
It pops the element from the top of the stack and returns nothing.

3. top() :
It returns the element being kept at the top of the stack.

4.  getMin() :
It returns the smallest element present in the stack.

Operations Performed on the Stack:

Query-1(Denoted by an integer 1): Pushes integer data to the stack. (push function)

Query-2(Denoted by an integer 2): Pops the data kept at the top of the stack. (pop function)

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack. (top function)

Query-4(Denoted by an integer 4): Returns the smallest element present in the stack. (getMin() function)

Problem approach

Two stacks can be used to implement a min Stack. One stack can be used to store the actual stack elements and the other auxiliary stack is used to store minimum values. The top element of the auxiliary stack will always store the minimum at that point of time. Let us see how push() and pop() operations work.
Push(int x)
1) push x to the original stack (the stack with actual elements)
2) compare x with the top element of the auxiliary stack. Let the top element be y.
…..a) If x < y then push x to the auxiliary stack.
…..b) If x > y then push y to the auxiliary stack.
int Pop()
1) pop the top element from the auxiliary stack. This is necessary to update the auxiliary stack.
2) pop the top element from the original stack and return it.
int getMin()
1) Return the top element of the auxiliary stack.

Try solving now

2. OOPS Question

What are function pointers?

Problem approach

We can create a pointer of any data type such as int, char, float, we can also create a pointer pointing to a function. The code of a function always resides in memory, which means that the function has some address. We can get the address of memory by using the function pointer.
Syntax of function pointer
return type (*ptr_name)(type1, type2…);
For example: int (*ip) (int);

3. OOPS Question

Difference between Macros and Functions.

Problem approach

1. Macros are Preprocessed Functions are Compiled
2. No Type Checking is done in Macro Type Checking is Done in Function
3. Using Macro increases the code length Using Function keeps the code length unaffected
4. Use of macro can lead to side effect at later stages Functions do not lead to any side effect in any case
5. Speed of Execution using Macro is Faster Speed of Execution using Function is Slower
6. Before Compilation, macro name is replaced by macro value During function call, transfer of control takes place
7. Macros are useful when small code is repeated many times Functions are useful when large code is to be written
8. Macro does not check any Compile-Time Errors Function checks Compile-Time Errors

Round

Easy

HR Round

Duration30 minutes

Interview date8 Jun 2015

Coding problem1

Typical HR round with behavioral problems.

1. Basic HR Questions

1. Started with tell me about yourself
2. Then asked why my pointer are 7.8 only
3. From my extracurricular he said that I was not focused to study only
4. Then he started asking about my project and other technical stuffs I did in my college life
5. Major training, Future plans and all.

Problem approach

Tip 1 : The cross questioning can go intense some time, think before you speak.

Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.

Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round, like what are the projects currently the company is investing, which team you are mentoring. How all is the work environment etc.