Sorting And Search Screen

Problem

The first filter for the software and R&D roles is a written or online test followed by a basic data structures and algorithms interview. Reports are consistent about the content: sorting, binary search, and time complexity. It is not hard, and it is where a lot of people get eliminated anyway because they treated it as a formality.

The representative task: given a sorted array that has been rotated an unknown number of times, find a target in O(log n).

Examples

Example 1, nums = [4,5,6,7,0,1,2], target = 0 returns 4.

Example 2, nums = [4,5,6,7,0,1,2], target = 3 returns -1.

Example 3, nums = [1], target = 1 returns 0.

Example 4, nums = [3,1], target = 1 returns 1. The two element case is where most wrong implementations die.

Constraints

• 1 <= n <= 5000, distinct integers.
• O(log n) required. A linear scan passes the tests and fails the interview.
• Then state the complexity of what you wrote, and justify it rather than asserting it.

What they look for

A correct binary search with the invariant said out loud, because the mistake is almost never the idea and almost always the boundary. Decide up front whether your range is inclusive or half open and stay with it.

The follow ups are about complexity literacy, which the reports mention specifically:

• Time complexity of several named algorithms, on the spot. Quicksort average and worst, mergesort, heapsort, insertion sort on nearly sorted input.
• Why quicksort is the practical default despite the quadratic worst case, and what a library implementation does to avoid it.
• Which sort is stable and when you care.
• Space complexity, including the recursion stack, which people forget to count.
• Sorting a dataset larger than memory, which is a genuinely relevant question here because the tools routinely handle designs that do not fit.

There is often a logic puzzle at the end of the round, and it is a fixture of this company's loop rather than a one off. Treat it as a thinking out loud exercise and narrate your reasoning.