# Microsoft DSA Questions with Answers

8 previously-asked dsa questions from Microsoft's hiring process, each with the correct answer and a worked explanation. Written against the company's actual test pattern.

_Source: Astra (https://useastra.in). Updated 2026-09-05._

### 1. Reverse the order of words in a string.

**Answer:** Split the string on spaces, reverse the list of words, and join with single spaces. Handle multiple spaces. Time O(n).

**Explanation:** Split, reverse, join.

### 2. Find the middle node of a singly linked list.

**Answer:** Use slow and fast pointers; when fast reaches the end, slow is at the middle. Time O(n), space O(1).

**Explanation:** Slow and fast pointers.

### 3. Check whether a binary tree is height balanced.

**Answer:** Recurse returning subtree heights; a tree is balanced if for every node the left and right heights differ by at most 1. Return early on imbalance. Time O(n).

**Explanation:** Bottom-up height check with early exit.

### 4. Clone a linked list where each node has a next and a random pointer.

**Answer:** Interleave copied nodes with originals, set the random pointers using the interleaving, then separate the two lists. Alternatively use a hash map from original to copy. Time O(n).

**Explanation:** Interleave or hash-map mapping.

### 5. Find the maximum depth of a binary tree.

**Answer:** Recurse: the depth is 1 plus the maximum of the left and right subtree depths, with 0 for a null node. Time O(n).

**Explanation:** Recursive max of subtree depths.

### 6. Design a stack that returns its minimum element in O(1).

**Answer:** Maintain a second stack of current minimums (or store pairs). On push, record the min of the new value and the previous min; on pop, pop both. getMin returns the top of the min stack. All operations O(1).

**Explanation:** Auxiliary min stack.

### 7. Merge a list of overlapping intervals.

**Answer:** Sort by start; iterate, extending the last interval when it overlaps, else appending a new one. Time O(n log n).

**Explanation:** Sort by start, merge overlaps.

### 8. Search for a target in a rotated sorted array.

**Answer:** Modified binary search: determine which half is sorted, check if the target lies in it, and narrow accordingly. Time O(log n).

**Explanation:** Binary search on the sorted half.

More Microsoft preparation, including the full recruitment process: https://useastra.in/campus/microsoft