MSFT

Question 1

Find Median from a data stream

Answer 1

implement one max heap and one min heap on either side of the median value

Question 2

Implement LRU (Least Recently Updated) Cache

Answer 2

Use a doubly linked list where each node also sits inside of an unordered map. Dictionary. The actual integer value is stored in the key, the node is stored at the value.
Node Head
Node Tail
Dictionary

1) When adding something new to the cache, add it to the head of the cache
2) when getting an existing element from the cache,
2. 1) index into the dictionary to get in O(1) time, to access the node i.e. the exact location of the node within the linked list.
2. 2) slice the node out by bypassing the node via its neighbors, then move the node to the head since we just accessed it.
3) when adding a something new to the cache and the cache is too big, add the new element to the Head and remove whatever is at the tail

Question 3

Number of islands

Answer 3

BFS algorithm inside of a doubly nested for loop. inside of the BFS algorithm, change each node visited to 0 or False to prevent visiting it again. We count the number of islands by the number of times we executed the BFS algorithm.

Question 4

Water Trap Problem given an array of heights representing the hights of blocks

[0,1,0,2,3,2,4,1]

Answer 4

Dynamic programming solition

1) Starting from the left, build an array of water levels where the water level = the max(leftArr[i, height[i - 1]])
2) Starting from the right, build an array of water levels where water level = max(rightArr[i], height[i + 1])
3) now starting from the left, compute the water height for each index as min(leftArr[i], rightArr(i)) - height[i]

Question 5

Longest string with no repeating characters

Answer 5

O(n2), use a dicitoinary to store the index where we saw each character.

As we move from left to right, once we come across a character whch already exists in the dictionary, jump back to the last index where we saw that character.

Question 6

Given an array of numbers, return an array where each answer[i] = the product of all numbers in array num[] EXCLUDING num[i]

Answer 6

O(1) complexity, two passes.

First pass:
starting from answers[1], for each answer[i] = nums[i - 1] * answers[i - 1]. This builds out the left hand side of all of the cumulative sums.

intialize rProd to store the product of the righthand side of the nums array
second pass: starting from i = answers.Length - 1, answers[i] = rProd * answers[i].

Then rProd = rProd * nums[i].

return answers[i]

Question 7

Given two sorted arrays, find the median of the two sorted arrays combined in O(log(m+n))

Answer 7

1) add the length of the arrays together and divide by 2 to get the number of elements desired on the left and right hand sides.

halfLen = (large + small + 1) / 2

2) if the answer to step 1 was odd, we will have more on one or the other side
3) the starting index for the larger array = largeIdx = Math.floor(larger.Length / 2)
4) the starting index for the smaller array halfLen - largeIdx is a good guess

smallidx = halfLen - largeIdx

5) if small[smallIdx - 1] < large[largeIdx] && small[smallIdx] > large[largeIdx - 1]