Microsoft interview prep
6 practice questions on the topics candidates reported from Microsoft interviews, with answers. The questions are ours; each one links to the interview report that names its topic.
DSA 6
-
You compute a to the power b by repeated squaring: a^b = (a^(b/2))^2, times one more a when b is odd. About how many multiplications does it take?
- O(b)
- O(log b)
- O(sqrt(b))
- O(b log b)
Show the answer
B. O(log b)
Each step halves the exponent, so there are about log2(b) steps with at most two multiplications each. a to the power 1,000,000 needs fewer than 40 multiplications instead of 999,999. The same idea gives fast modular powers.
This topic is named in a candidate’s interview report: SDE-1 on-campus interview, on GeeksforGeeks.
-
A number is stored as a singly linked list, most significant digit first: 9 -> 9 -> 9. What is the list after adding 1 to the number?
- 9 -> 9 -> 10
- 1 -> 0 -> 0
- 1 -> 0 -> 0 -> 0
- 0 -> 0 -> 0 -> 1
Show the answer
C. 1 -> 0 -> 0 -> 0
999 + 1 = 1000, so the carry runs through every digit and a new node is needed at the front. One way: reverse the list, add with a carry, then reverse it back. Another: recurse to the last node and pass the carry back up.
This topic is named in a candidate’s interview report: SDE-1 on-campus interview, on GeeksforGeeks.
-
You find the integer square root of n (the largest m with m * m <= n) by binary search over 0 to n. What do you do when m * m <= n?
- Return m at once
- Search the left half
- Keep m as the best answer so far and search the right half
- Restart the search from m
Show the answer
C. Keep m as the best answer so far and search the right half
m fits, but a larger value might too, so remember it and look right. When m * m > n, look left. It takes O(log n) steps. Compare m <= n / m, or use 64-bit numbers, so m * m cannot overflow.
This topic is named in a candidate’s interview report: SDE intern on-campus interview, 2023, on GeeksforGeeks.
-
A queue is built on a fixed-size array with front and rear indexes. Why is it usually made circular, so rear wraps around to index 0?
- So the queue can hold more items than the array size
- So dequeue becomes O(log n)
- So slots freed by dequeues at the front can be reused; otherwise rear reaches the end while the array still has room
- So the items stay sorted
Show the answer
C. So slots freed by dequeues at the front can be reused; otherwise rear reaches the end while the array still has room
Without wrapping, front and rear only ever move right, and the queue reports full once rear hits the end even if the front is empty. Moving with (index + 1) % size reuses that space. A linked-list queue has no fixed size but spends extra memory on each node.
This topic is named in a candidate’s interview report: SDE intern on-campus interview, 2023, on GeeksforGeeks.
-
Reverse a linked list in groups of k = 3 nodes, leaving a last group shorter than k in its original order. What does 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 become?
- 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7
- 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1
- 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
- 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7
Show the answer
C. 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
The first two groups of three are reversed. The last group, 7 and 8, has fewer than 3 nodes, so it stays as it is. In code, check that k nodes remain before reversing a group, then link the reversed group to the next one.
This topic is named in a candidate’s interview report: SDE intern on-campus interview, 2023, on GeeksforGeeks.
-
Why does an AVL tree keep search, insert and delete at O(log n)?
- It stores keys in a sorted array
- It hashes keys to buckets
- It never stores more than log n keys
- After each insert or delete it rotates nodes so that every node's left and right subtree heights differ by at most 1, keeping the height O(log n)
Show the answer
D. After each insert or delete it rotates nodes so that every node's left and right subtree heights differ by at most 1, keeping the height O(log n)
A plain BST fed sorted keys degrades to a linked list, O(n). AVL fixes imbalance with single or double rotations; red-black trees are a looser balance that rotates less often.
This topic is named in a candidate’s interview report: Software engineering intern interview, 2025, on Reddit.