10+ Morgan Stanley Software Developer Intern Interview Questions and Answers

Find the length of the longest substring with at most K distinct characters in a given string.

• Use a sliding window approach to keep track of the characters and their counts within the window.

• Maintain a hashmap to store the characters and their frequencies.

• Update the window size and characters count as you iterate through the string.

• Return the maximum window size encountered for each test case.

Given a string, determine if it can be split into three non-empty substrings where one is a substring of the other two.

• Check if any substring of the string is a substring of the other two substrings.

• Iterate through all possible splits of the string and check for the condition.

• Use two pointers to find all possible substrings efficiently.

Convert a sorted singly linked list into a Balanced Binary Search Tree (BST) using the same data values.

• Create a function to convert the linked list to a BST by finding the middle element as the root and recursively building the left and right subtrees.

• Maintain a pointer to the head of the linked list and update it as nodes are processed.

• Use level order traversal to output the values of the BST nodes, representing NULL nodes with -1.

• Ensure the height difference of the subtree...read more

Implement a function to determine the total number of ways to make change for a specified value using given denominations.

• Use dynamic programming to keep track of the number of ways to make change for each value up to the target value.

• Iterate through each denomination and update the number of ways to make change for each value based on the current denomination.

• Return the total number of ways to make change for the target value.

• Example: For N=3, D=[1, 2, 3], V=4, the output sh...read more

Detect if a singly linked list forms a cycle by checking if a node's next pointer points back to a previous node.

• Use Floyd's Cycle Detection Algorithm to determine if there is a cycle in the linked list.

• Maintain two pointers, one moving at twice the speed of the other.

• If the two pointers meet at any point, there is a cycle in the linked list.

Find pairs of elements in an array that sum up to a given value, sorted in a specific order.

• Iterate through the array and for each element, check if the complement (S - current element) exists in a hash set.

• If the complement exists, add the pair to the result list.

• Sort the result list based on the criteria mentioned in the problem statement.

Validate if a binary tree is a Binary Search Tree (BST) or not.

• Check if the left subtree of a node contains only nodes with data less than the node's data.

• Check if the right subtree of a node contains only nodes with data greater than the node's data.

• Ensure both the left and right subtrees are also binary search trees.

• Traverse the tree in an inorder manner and check if the elements are in sorted order.

• Recursively validate each node's value against its parent's value range.

Determine if a binary string can be sorted in decreasing order by removing non-adjacent characters.

• Iterate through the binary string and check if it can be sorted in decreasing order by removing non-adjacent characters.

• Keep track of the count of '1's and '0's in the string to determine if it can be sorted in decreasing order.

• If the count of '1's is greater than the count of '0's, the string can be sorted in decreasing order.

Find the duplicate number in an integer array containing numbers from 0 to (N - 2).

• Iterate through the array and keep track of the frequency of each number using a hashmap.

• Return the number that appears twice in the array.

• The duplicate number is always present in the given array.