Queue Reconstruction by Height

Algorithms
Medium
Stripe
103K views

You are asked to reconstruct a queue of people based on their height and the number of people in front of them who are taller or the same height. Use a Greedy approach combined with sorting.

Why Interviewers Ask This

Stripe interviewers ask this problem to evaluate a candidate's ability to optimize sorting strategies and apply greedy logic under constraints. They specifically test whether you can recognize that processing elements in a specific order (tallest first) simplifies the insertion logic, transforming a complex O(N^2) simulation into an efficient solution. This assesses your capacity to reframe algorithmic problems by changing the perspective of data traversal.

How to Answer This Question

1. Analyze the constraints: Understand that 'k' represents people with height >= current person. 2. Sort strategically: Propose sorting primarily by height descending, and secondarily by k ascending. Explain why taller people should be processed first so their relative positions don't shift later insertions. 3. Define the Greedy Choice: Articulate that inserting each person at index 'k' is safe because all previously placed people are taller or equal, satisfying the condition immediately without affecting future shorter people. 4. Implement Simulation: Describe using a dynamic list where you insert the current person directly at index 'k'. 5. Validate Complexity: Conclude by analyzing time complexity as O(N log N) for sorting plus O(N^2) for insertions, noting that while insertion is costly, it is often acceptable for Medium difficulty unless N is massive.

Key Points to Cover

  • Explicitly state the dual-sort criteria: height descending, then k ascending.
  • Demonstrate understanding that inserting at index k works because prior elements are always taller.
  • Acknowledge the trade-off between O(N log N) sorting and O(N^2) insertion steps.
  • Walk through a concrete trace with a small dataset to validate the logic.
  • Explain why this greedy choice prevents backtracking or reordering later.

Sample Answer

To solve Queue Reconstruction by Height efficiently, I would start by clarifying the core constraint: each person needs exactly 'k' people in front who are taller or of equal height. A brute-force approach checking every…

Common Mistakes to Avoid

  • Sorting only by height without considering the secondary sort on k, which breaks the logic for equal heights.
  • Attempting to simulate the queue by scanning forward for every person instead of inserting directly at index k.
  • Failing to explain why processing tallest-to-shortest is necessary for the greedy property to hold.
  • Ignoring the time complexity implications of list insertions in languages with non-constant time shifting.

Sound confident on this question in 5 minutes

Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.

Try it free

Related Interview Questions

Search in Rotated Sorted Array

Medium
Salesforce

Merge Intervals

Medium
Google

Shortest Word Distance

Easy
Spotify
Browse all 145 Algorithms questionsBrowse all 57 Stripe questions
Try this question free