Software Developer Morgan Stanley interview experience

Interview rounds

Round

Medium

Face to Face

Duration60 minutes

Interview date11 Aug 2015

Coding problem3

Technical Interview round with questions based on DSA.

1. Duplicate In Array

Easy

15m average time

85% success

0/40

Asked in companies

You are given an array ‘ARR’ of size ‘N’ containing each number between 1 and ‘N’ - 1 at least once. There is a single integer value that is present in the array twice. Your task is to find the duplicate integer value present in the array.

For example:

Consider ARR = [1, 2, 3, 4, 4], the duplicate integer value present in the array is 4. Hence, the answer is 4 in this case.

Note :

A duplicate number is always present in the given array.

Problem approach

Concept of indexing can be used to solve this question.
Traverse the array. For every element at index i,visit a[i]. If a[i] is positive, then change it to negative. If a[i] is negative, it means the element has already been visited and thus it is repeated. Print that element.
Pseudocode :
findRepeating(arr[], n)
{
missingElement = 0

for (i = 0; i < n; i++){
element = arr[abs(arr[i])]

if(element < 0){
missingElement = arr[i]
break
}

arr[abs(arr[i])] = -arr[abs(arr[i])]
}

return abs(missingElement)

}

Try solving now

2. Sum root to leaf

Easy

10m average time

90% success

0/40

Asked in companies

You are given an arbitrary binary tree consisting of N nodes where each node is associated with a certain integer value from 1 to 9. Consider each root to leaf path as a number.

For example:

       1
      /  \
     2    3

The root to leaf path 1->2 represents the number 12.
The root to leaf path 1->3 represents the number 13.

Your task is to find the total sum of all the possible root to leaf paths.

In the above example,

The total sum of all the possible root to leaf paths is 12+13 = 25

Note:

The output may be very large, return the answer after taking modulus with (10^9+7).

Problem approach

This can be solved using recursion. The basic idea is to subtract the value of current node from sum until it reaches a leaf node and the subtraction equals 0, then we know that we got a hit. Keep checking for left or right child path sum equal to target sum – value at current node.
Time complexity : O(n)

Try solving now

3. Topological Sort

Easy

0/40

Asked in companies

You are given a directed acyclic graph. Your task is to find any topological sorting of the graph.

A directed acyclic graph is a directed graph with no directed cycles.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge from u to v, vertex u comes before v in the ordering.

For example-

For the given DAG-

One of the possible topological sort will be-
1  2  3

Problem approach

Backtracking can be used to solve this problem.
Steps :
1. Initialize all vertices as unvisited.
2. Now choose the vertex which is unvisited and has zero indegree and decrease indegree of all those vertices by 1 (corresponding to removing edges) now add this vertex to result and call the recursive function again and backtrack.
3. After returning from function , reset values of visited, result and indegree for enumeration of other possibilities.

Try solving now

Round

Easy

Face to Face

Duration60 minutes

Interview date11 Aug 2015

Coding problem3

Technical interview round with questions based on DSA.

1. LCA Of Binary Tree

Moderate

10m average time

90% success

0/80

Asked in companies

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

You may assume that given ‘X’ and ‘Y’ definitely exist in the given binary tree.

For example :

For the given binary tree

LCA of ‘X’ and ‘Y’ is highlighted in yellow colour.

Problem approach

The recursive approach is to traverse the tree in a depth-first manner. The moment you encounter either of the nodes node1 or node2, return the node. The least common ancestor would then be the node for which both the subtree recursions return a non-NULL node. It can also be the node which itself is one of node1 or node2 and for which one of the subtree recursions returns that particular node.

Pseudo code :
LowestCommonAncestor(root, node1, node2) {
if(not root)
return NULL
if (root == node1 or root == node2)
return root
left = LowestCommonAncestor(root.left, node1, node2)
right = LowestCommonAncestor(root.right, node1, node2)
if(not left)
return right
else if(not right)
return left
else
return root
}

Try solving now

2. Rotated Array

Moderate

10m average time

90% success

0/80

Asked in companies

You are given an array 'arr' of size 'n' having unique elements that has been sorted in ascending order and rotated between 1 and 'n' times which is unknown.

The rotation involves shifting every element to the right, with the last element moving to the first position. For example, if 'arr' = [1, 2, 3, 4] was rotated one time, it would become [4, 1, 2, 3].

Your task is to find the minimum number in this array.

Note :

All the elements in the array are distinct.

Example :

Input: arr = [3,4,5,1,2]

Output: 1

Explanation: The original array was [1,2,3,4,5] and it was rotated 3 times.

Problem approach

On careful observation, it can be concluded that the number of rotations is equal to index of minimum element. So, the brute force solution is to find minimum element and returns its index.
Time Complexity : O(n)
Auxiliary Space : O(1)

An efficient approach can be built using Binary Search. We can find the index of minimum element using Binary Search. The idea is based on the below facts :

• The minimum element is the only element whose previous is greater than it. If there is no previous element, then there is no rotation (first element is minimum). We check this condition for middle element by comparing it with (mid-1)’th and (mid+1)’th elements.
• If the minimum element is not at the middle (neither mid nor mid + 1), then minimum element lies in either left half or right half.
1. If middle element is smaller than last element, then the minimum element lies in left half
2. Else minimum element lies in right half.

Try solving now

3. Maximum Binary Tree

Moderate

10m average time

90% success

0/80

Asked in companies

You have been given an array/list ‘TREE’ having ‘N’ unique integers. You need to make a maximum binary tree recursively from ‘TREE’ using the following conditions:

1. Create a root of the maximum binary tree whose value is the maximum value present in the ‘TREE’.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

For example:

For ‘TREE’ = [6, 1, 8, 2, 5],see the maximum binary tree in the below picture for reference:

As we can see the root of the maximum binary tree as shown in the picture is ‘8’ which is the maximum value in the ‘TREE’. The left subtree contains all the values which are present in the left of 8  in ‘TREE’ and the right subtree contains all the values which are present in the right of ‘8’ in ‘TREE’. Similarly, the maximum value in the left subarray of 8 is 6 so 6 becomes the root of the left subtree, 5 is the maximum value in the right subarray of the 8 so 5 becomes the root of the right subarray, and so on.

Problem approach

Every node has to be visited to figure out the maximum. So the idea is to traverse the given tree and for every node return maximum of 3 values.

1. Node’s data.
2. Maximum in node’s left subtree.
3. Maximum in node’s right subtree.

Pseudocode :
findMax(Node root)
{
// Base case
if (root is NULL)
return INT_MIN;

// Return maximum of 3 values:
// 1) Root's data 2) Max in Left Subtree 3) Max in right subtree
res = root->data;
lres = findMax(root->left);
rres = findMax(root->right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}

Try solving now

Software Developer

Interview preparation journey

Are you ready for your Dream Job?

Interview rounds

1. Duplicate In Array

You are given an array ‘ARR’ of size ‘N’ containing each number between 1 and ‘N’ - 1 at least once. There is a single integer value that is present in the array twice. Your task is to find the duplicate integer value present in the array.

For example:

Note :

2. Sum root to leaf

You are given an arbitrary binary tree consisting of N nodes where each node is associated with a certain integer value from 1 to 9. Consider each root to leaf path as a number.

For example:

Your task is to find the total sum of all the possible root to leaf paths.

In the above example,

Note:

3. Topological Sort

You are given a directed acyclic graph. Your task is to find any topological sorting of the graph.

A directed acyclic graph is a directed graph with no directed cycles.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge from u to v, vertex u comes before v in the ordering.

For example-

1. LCA Of Binary Tree

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

For example :

2. Rotated Array

You are given an array 'arr' of size 'n' having unique elements that has been sorted in ascending order and rotated between 1 and 'n' times which is unknown.

The rotation involves shifting every element to the right, with the last element moving to the first position. For example, if 'arr' = [1, 2, 3, 4] was rotated one time, it would become [4, 1, 2, 3].

Your task is to find the minimum number in this array.

Note :

Example :

3. Maximum Binary Tree

You have been given an array/list ‘TREE’ having ‘N’ unique integers. You need to make a maximum binary tree recursively from ‘TREE’ using the following conditions:

For example: