SDE - 2 Morgan Stanley interview experience | Anonymous

Interview rounds

Round

Medium

Online Coding Test

Duration25 minutes

Interview date13 Mar 2023

Coding problem3

It was my 1st round and this round of data structures and algorithms code

1. Longest Increasing Subsequence

Moderate

30m average time

65% success

0/80

Asked in companies

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.

Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

For example:

[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.

Problem approach

Step 1: Create an array dp of size n, where dp[i] will represent the length of the longest increasing subsequence ending at index i.
Step 2: Initialize all the values in the dp array to 1.
Step 3: Iterate through the array from left to right. For each index i, iterate through all the indices from 0 to i-1. If arr[j] < arr[i], then update dp[i] as max(dp[i], dp[j]+1). Finally, return the maximum value in the dp array.

Try solving now

2. Binary Tree Maximum Path Sum

Moderate

20m average time

80% success

0/80

Asked in companies

You are given a binary tree with ‘N’ nodes.

Your task is to find the “Maximum Path Sum” for any path.

Note :

1. A ‘path’ is a sequence of adjacent pair nodes with an edge between them in the binary tree.
2. The ‘path’ doesn’t need to pass through the root.
3. The ‘path sum’ is the sum of the node’s data in that path.

Problem approach

DSA Medium Practice Problems

Naman Shah
Tell me 3 dsa medium question and provide 3 steps shot solution

Sure, here are three DSA medium-level questions along with their solutions:

Question 1: Given an array of integers, find the length of the longest increasing subsequence.

Solution:
Step 1: Create an array dp of size n, where dp[i] will represent the length of the longest increasing subsequence ending at index i.
Step 2: Initialize all the values in the dp array to 1.
Step 3: Iterate through the array from left to right. For each index i, iterate through all the indices from 0 to i-1. If arr[j] < arr[i], then update dp[i] as max(dp[i], dp[j]+1). Finally, return the maximum value in the dp array.

Question 2: Given a binary tree, find the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections.

Solution:
Step 1: Define a recursive function maxPathSumHelper(node), which returns the maximum path sum that can be obtained starting from the given node.
Step 2: In the maxPathSumHelper function, recursively call the function for the left and right children of the node.
Step 3: Calculate the maximum path sum passing through the current node as max(node.val, node.val + left_sum + right_sum), where left_sum and right_sum are the maximum path sums obtained from the left and right subtrees, respectively.
Step 4: Update a global variable max_sum with the maximum path sum obtained so far.

Try solving now

3. Longest Palindromic Substring

Moderate

20m average time

80% success

0/80

Asked in companies

You are given a string 'str' of length 'N'.

Your task is to return the longest palindromic substring. If there are multiple strings, return any.

A substring is a contiguous segment of a string.

For example :

str = "ababc"

The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome. 

There is another palindromic substring of length 3 is "bab". Since starting index of "aba" is less than "bab", so "aba" is the answer.

Problem approach

Step 1: Create a two-dimensional boolean array dp of size n x n, where dp[i][j] will represent whether the substring from index i to index j is a palindrome or not.
Step 2: Initialize all the values in the dp array to false.
Step 3: Iterate through the string from right to left, and for each index i, iterate through all the indices from i to n-1. If s[i] == s[j] and j-i < 2 or dp[i+1][j-1] == true, then set dp[i][j] to true.
Step 4: Keep track of the longest palindromic substring found so far, and return it at the end.

Try solving now

Round

Medium

Online Coding Test

Duration30 minutes

Interview date13 Mar 2023

Coding problem3

This was 2nd round of interview and it was some hard level of dsa questions.

1. Design a stack that supports getMin() in O(1) time and O(1) extra space

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

Step 1: Use a linked list to implement the stack.
Step 2: Keep track of the minimum value using a separate variable that gets updated during push() and pop() operations.

Try solving now

2. Delete Kth node From End

Moderate

15m average time

95% success

0/80

Asked in companies

You have been given a singly Linked List of 'N' nodes with integer data and an integer 'K'.

Your task is to remove the 'K'th node from the end of the given Linked List and return the head of the modified linked list.

Example:

Input : 1 -> 2 -> 3 -> 4 -> 'NULL'  and  'K' = 2
Output: 1 -> 2 -> 4 -> 'NULL'
Explanation:
After removing the second node from the end, the linked list become 1 -> 2 -> 4 -> 'NULL'.

Problem approach

Step 1: Traverse the linked list to get its length.
Step 2: Traverse the list again, stopping at the (length-N+1)th node, and remove the Nth node from the end.

Try solving now

3. Left Sum

Easy

10m average time

90% success

0/40

Asked in companies

Given a binary tree having ‘N’ number of nodes. Your task is to find the sum of all left nodes present in the input binary tree. That is, you need to take the sum of all nodes which are the left child of some node.

Note :

1. A binary tree is a tree in which each node can have at most two children. 
2. The given tree will be non-empty i.e the number of non-NULL nodes will always be greater than or equal to 1.
3. Multiple nodes in the tree can have the same values, all values in the tree will be positive.

Problem approach

Step 1: Define a recursive function that takes a node as input.
Step 2: Traverse the tree recursively, keeping track of whether each node is a left or right child of its parent. If a node is a left child and has no children of its own, add its value to the sum.

Try solving now

Round

Hard

Online Coding Test

Duration40 minutes

Interview date14 Mar 2023

Coding problem3

This was my 3rd round and it has question from system design and Operating system

1. Design Question

Design a distributed key-value store that can handle millions of requests per second.

Problem approach

Step 1: Use a hash function to shard the keys across multiple servers.
Step 2: Use a distributed consensus protocol like Paxos or Raft to ensure consistency across the nodes.

2. OS Question

Implement a deadlock detection algorithm for a resource allocation system with multiple processes and resources.

Problem approach

Step 1: Build a graph where each process is a node, and each resource is a node.
Step 2: Use a cycle detection algorithm to find cycles in the graph.

3. Design Question

Design a distributed system for real-time analytics of streaming data.

Problem approach

Step 1: Use a distributed messaging system like Kafka or RabbitMQ to ingest and buffer the streaming data.
Step 2: Use a distributed computing framework like Spark or Flink to process the data in real-time.
Step 3: Use a distributed database like Cassandra or HBase to store the processed data for later analysis.

Round

Easy

HR Round

Duration20 minutes

Interview date14 Mar 2023

Coding problem1

This was my final round and it was hr round.