Microsoft·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Microsoft coding round, one question on array duplicates but the constraint was the whole point. Not a bad experience, just needed to know your cycle detection.

Questions Asked (1)

You're given an array of n+1 integers where every value falls in the range 1 to n. There's exactly one duplicate. Find it without modifying the array, using constant extra space and linear time.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The naive approaches all fail the constraints.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the constraints and confirming that the array is read-only and that O(1) extra space and O(n) time are required. Then explain that this is a classic cycle detection problem, where the array values act as pointers to indices, and the duplicate value creates a cycle. Use Floyd's Tortoise and Hare algorithm to find the entrance of the cycle, which is the duplicate number.

Pro tip: Mention that this problem is equivalent to finding the start of a cycle in a linked list, and that the same algorithm can be applied. Also, note that while binary search on the value range is another approach, it requires O(n log n) time, so Floyd's algorithm is optimal.

1. Clarify constraints and edge cases

Confirm that the array is read-only, that values are in 1..n, and that exactly one duplicate exists. Discuss edge cases like n=1 or duplicate at the start.

2. Model as a linked list cycle

Explain that each element points to the index equal to its value, forming a linked list with a cycle. The duplicate value is the entry point of the cycle.

3. Apply Floyd's Tortoise and Hare

Use two pointers: slow moves one step, fast moves two steps. They meet inside the cycle. Then reset slow to start and move both one step until they meet again; that meeting point is the duplicate.

4. Analyze complexity and trade-offs

State that time is O(n) and space is O(1). Compare with other approaches like sorting (O(n log n)) or using a hash set (O(n) space), highlighting why this is optimal.

5. Test with an example

Walk through a small example (e.g., [1,3,4,2,2]) to demonstrate the algorithm and verify correctness.

Key Points to Mention

Floyd's cycle detection algorithm (tortoise and hare)
Mapping array values to indices as pointers
The duplicate value is the cycle entrance
Time complexity O(n) and space complexity O(1)
Comparison with alternative approaches (sorting, hash set, binary search)
Proof of correctness: why the meeting point after reset gives the duplicate

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.