Introduction

In this blog post, we'll share the most commonly asked coding interview questions at Morgan Stanley. If you don't have months to study for your interviews, you can use AI tools like Chatmagic to generate solutions quickly and efficiently - helping you pass the interviews and get the job offer!

Problem #1: Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. Example 1: Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. Example 2: Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0. Constraints: 1 <= prices.length <= 105 0 <= prices[i] <= 104

Topics: Array, Dynamic Programming

Problem #2: Count Subarrays With Fixed Bounds

You are given an integer array nums and two integers minK and maxK. A fixed-bound subarray of nums is a subarray that satisfies the following conditions: The minimum value in the subarray is equal to minK. The maximum value in the subarray is equal to maxK. Return the number of fixed-bound subarrays. A subarray is a contiguous part of an array. Example 1: Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5 Output: 2 Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2]. Example 2: Input: nums = [1,1,1,1], minK = 1, maxK = 1 Output: 10 Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays. Constraints: 2 <= nums.length <= 105 1 <= nums[i], minK, maxK <= 106

Topics: Array, Queue, Sliding Window, Monotonic Queue

Problem #3: Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Can you solve it without sorting? Example 1: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 Example 2: Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4 Constraints: 1 <= k <= nums.length <= 105 -104 <= nums[i] <= 104

Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect

Problem #4: Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list. For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y. Return the head of the copied linked list. The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where: val: an integer representing Node.val random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node. Your code will only be given the head of the original linked list. Example 1: Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]] Example 2: Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]] Example 3: Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]] Constraints: 0 <= n <= 1000 -104 <= Node.val <= 104 Node.random is null or is pointing to some node in the linked list.

Topics: Hash Table, Linked List

Problem #5: Subarrays with K Different Integers

Given an integer array nums and an integer k, return the number of good subarrays of nums. A good array is an array where the number of different integers in that array is exactly k. For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3. A subarray is a contiguous part of an array. Example 1: Input: nums = [1,2,1,2,3], k = 2 Output: 7 Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2] Example 2: Input: nums = [1,2,1,3,4], k = 3 Output: 3 Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4]. Constraints: 1 <= nums.length <= 2 * 104 1 <= nums[i], k <= nums.length

Topics: Array, Hash Table, Sliding Window, Counting

Problem #6: Stamping The Sequence

You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'. In one turn, you can place stamp over s and replace every letter in the s with the corresponding letter from stamp. For example, if stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can: place stamp at index 0 of s to obtain "abc??", place stamp at index 1 of s to obtain "?abc?", or place stamp at index 2 of s to obtain "??abc". Note that stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s). We want to convert s to target using at most 10 target.length turns. Return an array of the index of the left-most letter being stamped at each turn. If we cannot obtain target from s within 10 target.length turns, return an empty array. Example 1: Input: stamp = "abc", target = "ababc" Output: [0,2] Explanation: Initially s = "?????". - Place stamp at index 0 to get "abc??". - Place stamp at index 2 to get "ababc". [1,0,2] would also be accepted as an answer, as well as some other answers. Example 2: Input: stamp = "abca", target = "aabcaca" Output: [3,0,1] Explanation: Initially s = "???????". - Place stamp at index 3 to get "???abca". - Place stamp at index 0 to get "abcabca". - Place stamp at index 1 to get "aabcaca". Constraints: 1 <= stamp.length <= target.length <= 1000 stamp and target consist of lowercase English letters.

Topics: String, Stack, Greedy, Queue