Debug Queues and Solve Arrays
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
During the coding rounds, the interviewer asked several implementation problems:
1. Debug a priority queue. You are given an array-backed min-heap. The buggy sift-down logic is:
left = 2*i + 1, right = 2*i + 2, smallest = left;
if right < n and heap[left] < heap[right]: smallest = right;
if heap[i] > heap[smallest]: swap(heap[i], heap[smallest]).
Explain the bug, fix it, and describe test cases that would expose it.
2. Implement a thread-safe queue for a web crawler. Multiple producer threads add URLs and multiple worker threads remove URLs. Support push, blocking pop, and graceful shutdown without losing work.
3. Given a binary array, return the maximum number of consecutive 1s. Follow-up: now treat the array as circular, so a run of 1s may wrap from the end of the array to the beginning.
4. Given an array of integers representing colors in the range 0 to k - 1, sort the array in place so equal colors are adjacent. The interviewer explicitly extended the classic three-color version to support more than three colors.
Quick Answer: This multi-part question evaluates competencies in data structures (heap invariants and in-place array manipulation), concurrent programming (designing a thread-safe queue with blocking operations and graceful shutdown), and algorithmic problem-solving for arrays (maximum consecutive ones including circular wrap and generalized k-color in-place sorting) within the Coding & Algorithms domain. Such problems are commonly asked to assess debugging and implementation correctness, understanding of synchronization and concurrency pitfalls, and algorithmic reasoning about space/time trade-offs, reflecting a mix of conceptual understanding and practical application-level implementation skills.