Microsoft Java Developer Interview Questions & Answers

I would use the Dutch National Flag three-pointer approach. I keep low, mid, and high pointers. Values before low are 0s, values from low through mid - 1 are 1s, and values after high are 2s. I inspect nums[mid]. For 0, I swap left and move low and mid. For 1, I move mid. For 2, I swap right and move high only. This sorts in O(n) time with O(1) auxiliary space.

The input is an array that contains only 0s, 1s, and 2s. We need to change the same array so every 0 comes first, then every 1, then every 2. We should not create another array for the result. The main idea is to use three moving positions to separate finished values from values that still need work. Each step looks at one unfinished value and places it into the correct part. When no unfinished values remain, the same input array contains the required sorted result.

1. Can I assume the array contains only 0s, 1s, and 2s?
2. Should I modify the input array in place instead of returning a new array?

The example input is [2, 0, 2, 1, 1, 0]. We need to modify that same array into [0, 0, 1, 1, 2, 2]. We are sorting only three possible values. We do not need to preserve the original order of equal values because equal values are identical for this problem.

I use the Dutch National Flag algorithm. The array is divided into four regions. Positions from 0 through low - 1 contain finished 0s. Positions from low through mid - 1 contain finished 1s. Positions from mid through high are still unknown. Positions from high + 1 through the end contain finished 2s.

This invariant tells us what every part of the array means during the loop. We only need to classify the value at mid.

For [2, 0, 2, 1, 1, 0], the indices are 0, 1, 2, 3, 4, 5. We start with low = 0, mid = 0, and high = 5. At this point, no value has been classified yet, so the whole range from mid through high is the unknown region.

The loop continues while mid <= high. When mid becomes greater than high, the unknown region is empty.

Step 1: low = 0, mid = 0, high = 5. nums[mid] is 2. A 2 belongs on the right. Swap indices 0 and 5. The array becomes [0, 0, 2, 1, 1, 2]. Decrease high to 4. Keep mid at 0 because the value that was swapped into index 0 has not been classified yet.

Step 2: low = 0, mid = 0, high = 4. nums[mid] is now 0. A 0 belongs on the left. Swap indices 0 and 0. The array stays [0, 0, 2, 1, 1, 2]. Increase low to 1 and mid to 1.

Step 3: low = 1, mid = 1, high = 4. nums[mid] is 0. Swap indices 1 and 1. The array stays [0, 0, 2, 1, 1, 2]. Increase low to 2 and mid to 2.

Step 4: low = 2, mid = 2, high = 4. nums[mid] is 2. Swap indices 2 and 4. The array becomes [0, 0, 1, 1, 2, 2]. Decrease high to 3. Keep mid at 2 so the new value at index 2 can be checked.

Step 5: low = 2, mid = 2, high = 3. nums[mid] is 1. A 1 already belongs in the middle region. Increase only mid to 3. The array remains [0, 0, 1, 1, 2, 2].

Step 6: low = 2, mid = 3, high =

3. nums[mid] is 1 again. Increase mid to
4. The array remains [0, 0, 1, 1, 2, 2].

Now mid = 4 and high = 3. Since mid > high, the unknown region is empty and processing stops. The final result is [0, 0, 1, 1, 2, 2].

The invariant is preserved after every operation. Everything before low is a

1. Everything from low through mid - 1 is a
2. Everything after high is a
3. The range from mid through high contains values that still need classification. Each iteration shrinks that unknown region by one position. When mid passes high, every value has been classified, so the array is sorted correctly.

The Java method creates low, mid, and high. It loops while mid <= high. If nums[mid] is 0, it swaps with low and advances both low and mid. If nums[mid] is 1, it advances mid. If nums[mid] is 2, it swaps with high and decreases high without advancing mid. A small swap method exchanges two array elements.

The running time is O(n). Every loop iteration shrinks the unknown range [mid..high] by one position, so there are at most n iterations. The algorithm uses only low, mid, high, and one temporary swap value, so auxiliary space is O(1). Relevant edge cases include an empty array, one element, an already sorted array, and an array where every value is the same.

The key idea is to partition the array into four regions while processing it. The invariant is: [0..low-1] contains only 0s, [low..mid-1] contains only 1s, [mid..high] is still unknown, and [high+1..n-1] contains only 2s. We inspect nums[mid]. A 0 is moved to the left, a 1 stays in the middle, and a 2 is moved to the right. Every operation shrinks the unknown region by one position. This avoids a separate result array and gives an in-place linear-time solution.

Time complexity is O(n). The unknown region [mid..high] becomes smaller by one position on every loop iteration, so there are at most n iterations. Swaps are constant-time operations, so the total work stays linear. Auxiliary space is O(1). Auxiliary space means extra memory used by the algorithm. We only keep three pointer variables and one temporary value for swapping, so the extra memory does not grow with the input size.

A common mistake is incrementing mid after swapping a 2 with nums[high]. The new value at mid has not been checked, so mid must stay in place. Another mistake is moving only mid after finding a 0. Both low and mid must advance after that swap. Candidates may also use the wrong loop condition and stop before processing high. The correct condition is mid <= high. Another mistake is describing the runtime as more than O(n) because swaps occur. Each iteration still shrinks the unknown region by one position. Finally, the four pointer regions must stay consistent with the invariant throughout the loop.

State the four-region invariant before writing the loop. Then explain each branch by saying where the current value belongs and which boundary must move. Pay special attention to the 2 case and say clearly that mid does not advance because the swapped-in value still needs to be classified.

I would store each key in a hash map, and for each key I would keep a TreeMap of timestamp to value. On set, I write the value at its timestamp. On get, I use floorEntry to find the largest timestamp that is not after the query time, then return that value. I process each lookup in order, so the answer is correct and fast. The time is O(log n_k) per operation, and the extra space is O(N).

This problem asks me to remember a value for each key at different times and then answer with the newest value that is not later than the time I ask for. I keep the writes for each key in time order. That lets me find the right answer without checking every old value. When I set a value, I store it at its timestamp. When I get a value, I look for the largest timestamp that is still at or before the query time, and I return that value or null if there is none.

1. If the same key is written twice at the same timestamp, should the later write replace the earlier one?
2. Should I return null when no timestamp exists at or before the query time?

The input has a key, a value, and a timestamp for set. The input for get has a key and a timestamp. The output is the value with the largest timestamp that is less than or equal to the query time. If the key does not exist or there is no earlier timestamp, the answer is null.

I use a HashMap from key to TreeMap. The HashMap finds the right key quickly. The TreeMap keeps that key’s timestamps in sorted order. This is important because the query asks for the latest time that is still valid, not just any stored time.

At the start, the store is empty. For each new key, I create one TreeMap. The invariant is simple. For each key, the TreeMap stores timestamp to value pairs in sorted timestamp order. Only past writes for that key are inside that TreeMap.

The diagram uses the same example everywhere. For user1, we store A at 1, B at 5, and C at 10. Then we overwrite the value at timestamp 5 with D. After that, the stored history for user1 is {1 → A, 5 → D, 10 → C}. So get(user1, 6) returns D because 5 is the largest timestamp that is not after 6. get(user1, 1) returns A. get(user1, 10) returns C. get(user1, 11) also returns C.

The TreeMap keeps timestamps sorted. That means floorEntry(t) gives the entry with the largest timestamp that is less than or equal to t. That is exactly the rule for this problem. Because each key has its own TreeMap, the query never mixes values from different keys.

The set method uses computeIfAbsent to create the TreeMap when a key appears for the first time. Then it puts the timestamp and value into that TreeMap. The get method first reads the TreeMap for the key. If the key is missing, it returns null. Otherwise it calls floorEntry(timestamp). If that is null, it returns null. If it finds an entry, it returns the stored value.

Each set and get uses the TreeMap for one key, so the time is O(log n_k), where n_k is the number of timestamps stored for that key. The extra memory is O(N), where N is the total number of stored timestamp-value pairs. Important edge cases are a missing key, a query time before the first stored timestamp, duplicate writes at the same timestamp, and many timestamps for one key.

The key idea is to keep the data sorted by time for each key. The HashMap chooses the right key bucket, and the TreeMap keeps that key’s writes in timestamp order. The invariant is that each TreeMap contains only writes for one key, sorted by timestamp. Then floorEntry(t) returns the newest value that is still valid for time t. This matches the problem rule exactly, so we do not need to scan older values one by one.

Each operation works on one key. The HashMap finds that key quickly, and the TreeMap keeps the timestamps in order. TreeMap put and floorEntry both take O(log n_k) time, where n_k is the number of timestamps for that key. So set and get are O(log n_k) time each. The extra memory is O(N), where N is the total number of stored timestamp-value pairs across all keys.

A common mistake is to use only a HashMap and lose the timestamp order. Another mistake is to return the first time that is close enough, instead of the latest time that is not after the query time. A third mistake is to use ceilingEntry instead of floorEntry. That gives a future value, which is wrong here. People also forget to return null when the key is missing or when no earlier timestamp exists. Finally, some candidates forget that a later write at the same timestamp must replace the earlier value.

Say the invariant out loud: each key points to a sorted TreeMap of its past writes. Then say why floorEntry matches the phrase “latest at or before the query time.”

I would first build a position array so pos[x] tells me where value x appears in the permutation. Then I process k from 1 to n and keep the minimum and maximum positions seen for values 1 through k. Those values are contiguous exactly when maxPos - minPos + 1 equals k. If that condition is true, I record k. This takes O(n) time and O(n) auxiliary space.

The input is a permutation containing each value from 1 to n exactly once. For every k, we want to know whether the values 1 through k appear together in one continuous part of the array, in any order. We return every k for which this is true. The key idea is to store where each value appears. As we add values in the order 1, 2, 3, and so on, we track the leftmost and rightmost positions. If those positions cover exactly k slots, the values must be consecutive.

1. Can I assume the input is always a valid permutation of values 1 through n?
2. Should I return the balanced k values themselves, as shown in the example?

The input is a permutation. This means every value from 1 to n appears exactly once. For each k, we check whether one contiguous subarray contains exactly the set {1..k}. The values can appear in any order inside that subarray. We return every k that satisfies this condition.

For the example p = [4, 1, 3, 2, 5], the balanced k values are [1, 3, 4, 5]. The corresponding answers for k = 1 through 5 are [true, false, true, true, true].

I build pos[value] = position of that value. I use 1-based positions to match the walkthrough.

For p = [4, 1, 3, 2, 5]:

• pos[1] = 2
• pos[2] = 4
• pos[3] = 3
• pos[4] = 1
• pos[5] = 5

Now I can find the position of each next value in constant time using an array lookup.

I initialize minPos to positive infinity and maxPos to negative infinity. Then I process k from 1 to n.

After processing k, minPos and maxPos describe the smallest and largest positions occupied by the values {1..k}. This is the main invariant.

For each k, I read pos[k]. I update minPos and maxPos. Then I calculate:

span = maxPos - minPos + 1

If span equals k, the k distinct positions must fill every position in that interval. Therefore the values 1 through k form one contiguous subarray.

For k = 1, pos[1] = 2. The state changes from no positions to minPos = 2 and maxPos = 2. The span is 2 - 2 + 1 = 1. Since 1 equals k, record 1. The result is [1]. The matching subarray is p[2..2] = [1].

For k = 2, pos[2] = 4. Before this step, the span is [2,2]. After adding position 4, minPos = 2 and maxPos = 4. The span is 4 - 2 + 1 = 3. Since 3 is not equal to 2, do not record 2. The result stays [1]. Positions 2 and 4 leave a gap at position 3, so values {1,2} are not contiguous.

For k = 3, pos[3] = 3. minPos stays 2 and maxPos stays 4. The span is 4 - 2 + 1 = 3. Since 3 equals k, record 3. The result becomes [1,3]. The subarray p[2..4] = [1,3,2] contains exactly {1,2,3}.

For k = 4, pos[4] = 1. minPos becomes 1 and maxPos remains 4. The span is 4 - 1 + 1 = 4. Since 4 equals k, record 4. The result becomes [1,3,4]. The subarray p[1..4] = [4,1,3,2] contains exactly {1,2,3,4}.

For k = 5, pos[5] = 5. minPos remains 1 and maxPos becomes 5. The span is 5 - 1 + 1 = 5. Since 5 equals k, record 5. The final result is [1,3,4,5].

After processing k, minPos and maxPos are the minimum and maximum positions of the values 1 through k. Because the input is a permutation, those k values occupy k different positions.

If maxPos - minPos + 1 equals k, the interval contains exactly k positions. Since we already have k distinct tracked positions inside it, there can be no gaps. The interval therefore contains exactly the values {1..k}.

If the span is larger than k, at least one position inside that interval is not occupied by one of the tracked values. That position contains another value from the permutation, so {1..k} does not form one contiguous subarray.

The Java code first builds the pos array in one loop. It then creates the result list and initializes minPos and maxPos. The second loop processes k from 1 through n. Each iteration updates the current minimum and maximum position. It computes the span and adds k to the result only when the span is exactly k. After all k values are processed, it returns the result list.

Building the position array takes O(n) time. Processing k from 1 through n also takes O(n) time. Therefore the total time is O(n).

The position array uses O(n) auxiliary space. The returned result list can also contain up to n values.

For any valid permutation, k = 1 is always balanced because one value occupies one position. Also, k = n is always balanced because all n values occupy the entire permutation. The reasoning depends on the input being a true permutation with unique values.

The key insight is to change the problem from checking subarrays to checking positions. Store pos[x], the position where value x appears. Then add values in increasing order: 1, 2, 3, and so on. Keep only the smallest and largest positions seen so far. The invariant is that after processing k, the interval [minPos, maxPos] covers every position belonging to values {1..k}. Since these are k distinct positions, they are contiguous exactly when the interval length maxPos - minPos + 1 is also k. If the interval is longer, at least one position in the interval belongs to a value larger than k, so k is not balanced.

Building the position array takes O(n) time because every permutation element is processed once. The second loop processes every k from 1 through n once, so it also takes O(n) time. The total time is O(n). The pos array has n + 1 entries, so it uses O(n) auxiliary space. The result list can contain up to n balanced k values. Array lookup, minimum, maximum, and arithmetic operations are constant-time operations.

A common mistake is to track the values themselves instead of their positions. The condition is about whether their positions form one continuous interval. Another mistake is forgetting the +1 in maxPos - minPos + 1, which gives the inclusive span length. Candidates may also reset minPos and maxPos for every k instead of carrying the state forward as k grows. Another mistake is recording k when the span is only less than or equal to k instead of exactly equal to k. Finally, claiming O(1) extra space is incorrect because the position array grows with n.

State the invariant early: after processing k, minPos and maxPos bound the positions of exactly the values 1 through k. Then the test maxPos - minPos + 1 == k becomes easy to justify and the rest of the implementation follows directly.

I would use BFS to find the shortest transformation level, then DFS to rebuild every shortest sequence. The BFS queue processes words level by level. I keep a remaining-word HashSet and a parents map from each child to all parents that reach it at the same shortest level. I remove discovered words only after the whole level finishes, so valid shortest parents are not lost. The diagram's expected time is O(N * L * 26 + outputSize), with O(N + outputSize) auxiliary space.

We need to change beginWord into endWord by changing exactly one letter at each step. Every transformed word after the start must appear in wordList. We must return every sequence that uses the minimum number of changes. For the example, "hit" reaches "cog" in four transformations through two different shortest paths. BFS fits because it explores shorter paths before longer paths. We also keep each shortest previous word so that all minimum-length sequences can be rebuilt after BFS.

1. Should I return an empty list when endWord is not present in wordList?
2. Can the shortest sequences be returned in any order?
3. Should all parents that reach the same word at the same shortest level be preserved?

The input is beginWord, endWord, and wordList. In the approved example, beginWord is "hit", endWord is "cog", and wordList is ["hot", "dot", "dog", "lot", "log", "cog"]. Each move changes exactly one character. We must return all shortest transformation sequences. One valid result order is [["hit", "hot", "dot", "dog", "cog"], ["hit", "hot", "lot", "log", "cog"]]. The order of those two returned ladders may vary.

I use BFS because every transformation has the same cost of one step. BFS processes words one distance level at a time. The queue therefore discovers minimum distances before longer distances. I use a HashSet called remaining for words that can still be discovered at a new shortest level. I also use a parents map with the direction child -> list of shortest parents. A child may have several parents when different words reach it during the same BFS level.

The central invariant is: BFS visits levels in increasing transformation distance, so the first level that reaches a word gives that word its shortest distance. The parents map keeps all predecessors that reach that word at that same shortest distance.

The initial queue is [hit]. The initial remaining set is {hot, dot, dog, lot, log, cog}. The parents map is empty. found is false. The word length L is 3. The code first puts wordList into a HashSet. If endWord is missing from that set, it immediately returns an empty result because no valid ladder can end at endWord.

At level 0, the queue is [hit]. The valid next word is hot. We record hot <- hit and put hot into the next BFS level. Its shortest distance is 1.

At level 1, the queue is [hot]. We discover dot and lot. We record dot <- hot and lot <- hot. The next queue is [dot, lot]. Their shortest distance is 2.

At level 2, the queue is [dot, lot]. From dot we discover dog, so we record dog <- dot. From lot we discover log, so we record log <- lot. The next queue is [dog, log]. Their shortest distance is 3.

At level 3, the queue is [dog, log]. Dog reaches cog, so we record cog <- dog and set found to true. We do not stop in the middle of this level. We continue processing the same level. Log also reaches cog, so we record cog <- log. After the whole level finishes, BFS stops. The shortest distance to cog is 4 transformations, or 5 words in each ladder.

The final parent links used by the example are hot <- hit, dot <- hot, lot <- hot, dog <- dot, log <- lot, cog <- dog, and cog <- log.

A newly discovered word is not removed from remaining immediately. Instead, it is also stored in nextLevel. Other words in the current BFS level may still reach that same child. This is how cog can keep both dog and log as shortest parents. After the entire level finishes, nextLevel is removed from remaining. That prevents a deeper level from adding a longer path to the same word.

After BFS stops, DFS starts at endWord and follows the parents map backward. From cog, one branch follows dog -> dot -> hot -> hit. The other follows log -> lot -> hot -> hit. The path is being built backward. When DFS reaches beginWord, it copies that path, reverses the copy, and adds the forward ladder to the result. After each recursive branch returns, the last parent is removed from the current path. This backtracking step restores the path before the next branch is explored.

BFS processes states in increasing distance order. Therefore the first BFS level that reaches a word gives its minimum transformation distance. Finishing the whole level before removing its discovered words preserves every shortest parent. Once the first level containing endWord is complete, any deeper path would be longer and is ignored. DFS then follows exactly those shortest-parent links, so it returns all shortest ladders.

The diagram reports expected time O(N * L * 26 + outputSize), where N is the number of words and L is the word length. HashSet and HashMap operations are O(1) on average. The diagram reports O(N + outputSize) auxiliary space for the BFS structures, parent information, reconstruction state, and returned ladders. Relevant edge cases are endWord missing from wordList, duplicate words being collapsed by the set, several shortest parents reaching one child in the same level, and preventing longer paths after endWord's first level is found.

The key insight is to use BFS only to build the shortest-path structure, rather than storing full transformation sequences in the BFS queue. BFS processes the unweighted word graph level by level. The invariant is that the first level that reaches a word gives its shortest distance. The parents map stores child -> every predecessor that reaches that child at the same shortest level. Words discovered during a level stay available through nextLevel until that whole level ends. This preserves multiple shortest parents such as cog <- dog and cog <- log. After the first level containing endWord finishes, DFS follows those parent links backward to generate every shortest ladder.

Let N be the number of words and L be the length of each word. The approved diagram uses expected time O(N * L * 26 + outputSize). For each processed word, the algorithm tries each of its L character positions and each of the 26 lowercase letters. HashSet and HashMap lookup and insertion are O(1) on average, so this is an expected-time statement rather than a guaranteed worst-case hashing bound. outputSize is the work needed to produce the returned ladders. The diagram gives O(N + outputSize) auxiliary space for the remaining set, BFS queue, parents information, DFS reconstruction state, and returned results.

One common mistake is removing a discovered word from remaining immediately. That can lose another valid parent that reaches the same child during the same BFS level. Another mistake is stopping as soon as dog first reaches cog. The rest of that level must still run so log can also become a shortest parent of cog. Candidates may also enqueue the same child more than once in one level, allow deeper levels to add longer parent links after a shorter distance is known, or forget path.removeLast() when DFS backtracks.

Explain the visited timing before writing the DFS. Use cog as the concrete example: dog finds cog first, but cog stays available to the current level so log can also be recorded as a shortest parent. Then remove all next-level words only after that level finishes.