Debug Queues and Solve Arrays
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
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.
Part 1: Fix Array-Backed Min-Heap Sift-Down
Constraints
- 0 <= len(heap) <= 100000
- -10^9 <= heap[j] <= 10^9
- If 0 <= i < len(heap), the left and right subtrees of i are valid min-heaps.
- The operation should mutate or construct the corrected heap and return it.
Examples
Input: ([], 0)
Expected Output: []
Explanation: An empty heap has no node to sift down.
Input: ([1], 0)
Expected Output: [1]
Explanation: A single-node heap is already valid.
Input: ([5, 2, 3], 0)
Expected Output: [2, 5, 3]
Explanation: The smaller child is 2, so 5 must swap with 2. The buggy code would choose 3.
Input: ([10, 4, 7, 5, 6], 0)
Expected Output: [4, 5, 7, 10, 6]
Explanation: The value 10 must move down multiple levels.
Input: ([1, 2, 3], 0)
Expected Output: [1, 2, 3]
Explanation: The heap property already holds, so no swap is needed.
Hints
- Compare the current node with both existing children, not just the left child.
- After a swap, the moved value may still violate the heap property farther down the tree.
Part 2: Simulate a Gracefully Shutting Down Thread-Safe Queue
Constraints
- 0 <= len(operations) <= 200000
- Each operation is ['push', url], ['pop'], or ['shutdown'].
- URL strings are non-empty and are not equal to NO_WORK.
- After shutdown, pushes are ignored.
- Queued URLs must be returned in FIFO order.
Examples
Input: ([],)
Expected Output: []
Explanation: No operations means no pop results.
Input: ([['push', 'a'], ['push', 'b'], ['pop'], ['pop'], ['shutdown'], ['pop']],)
Expected Output: ['a', 'b', 'NO_WORK']
Explanation: The first two pops receive queued URLs in FIFO order; after shutdown and drain, there is no work.
Input: ([['pop'], ['push', 'u1'], ['push', 'u2'], ['pop'], ['shutdown'], ['pop']],)
Expected Output: ['u1', 'u2', 'NO_WORK']
Explanation: The first pop blocks and is satisfied by the later push of u1.
Input: ([['pop'], ['pop'], ['shutdown']],)
Expected Output: ['NO_WORK', 'NO_WORK']
Explanation: Both workers are blocked on an empty queue and are released by shutdown.
Input: ([['push', 'a'], ['shutdown'], ['push', 'b'], ['pop'], ['pop']],)
Expected Output: ['a', 'NO_WORK']
Explanation: The queued URL a survives shutdown, but the later push of b is rejected.
Hints
- Use one FIFO queue for available URLs and another FIFO queue for blocked pop result positions.
- When shutdown happens, do not clear queued work; only release currently blocked pops and reject future pushes.
Part 3: Maximum Consecutive Ones in a Binary Array
Constraints
- 0 <= len(nums) <= 1000000
- nums[i] is either 0 or 1.
Examples
Input: ([],)
Expected Output: 0
Explanation: There are no 1s in an empty array.
Input: ([0, 0, 0],)
Expected Output: 0
Explanation: No element is 1.
Input: ([1],)
Expected Output: 1
Explanation: The single element forms a run of length 1.
Input: ([1, 1, 0, 1, 1, 1],)
Expected Output: 3
Explanation: The longest run is the final three 1s.
Input: ([1, 1, 1],)
Expected Output: 3
Explanation: The entire array is one run.
Hints
- Scan from left to right while maintaining the length of the current run of 1s.
- Reset the current run length to 0 whenever you see a 0.
Part 4: Maximum Consecutive Ones in a Circular Binary Array
Constraints
- 0 <= len(nums) <= 1000000
- nums[i] is either 0 or 1.
- A circular run cannot exceed len(nums).
Examples
Input: ([],)
Expected Output: 0
Explanation: An empty array has no run of 1s.
Input: ([0, 0],)
Expected Output: 0
Explanation: There are no 1s.
Input: ([1, 1, 1],)
Expected Output: 3
Explanation: All elements are 1, but the answer cannot exceed the array length.
Input: ([1, 0, 1, 1],)
Expected Output: 3
Explanation: The run wraps: the two trailing 1s plus the leading 1.
Input: ([0, 1, 1, 0, 1],)
Expected Output: 2
Explanation: Wrapping does not improve the best linear run of length 2.
Hints
- The best wrapping run is the suffix of 1s at the end plus the prefix of 1s at the start.
- Handle the all-ones case carefully so you do not count the array twice.
Part 5: Sort K Colors In Place
Constraints
- 0 <= len(colors) <= 1000000
- 1 <= k <= 100000
- 0 <= colors[i] < k
- The returned list must contain the same multiset of values as the input.
Examples
Input: ([2, 0, 1, 2, 1, 0], 3)
Expected Output: [0, 0, 1, 1, 2, 2]
Explanation: The three colors are sorted in increasing order.
Input: ([3, 1, 2, 0, 3, 2, 1], 4)
Expected Output: [0, 1, 1, 2, 2, 3, 3]
Explanation: The method supports more than three colors.
Input: ([], 5)
Expected Output: []
Explanation: An empty array is already sorted.
Input: ([0, 0, 0], 1)
Expected Output: [0, 0, 0]
Explanation: Only one color exists.
Input: ([4, 0, 2, 4, 1], 5)
Expected Output: [0, 1, 2, 4, 4]
Explanation: Missing colors do not need to appear in the output.
Hints
- For arbitrary k, counting how many times each color occurs is often simpler than repeated partitioning.
- After counting, overwrite the original array from left to right.