1053. Zigzag Feed

Medium3.5 points estimatedDesignIteratorQueue3 hints
RPby Rohit Parihar

A news app merges two ranked lists of story ids, a from the sports desk and b from the politics desk, into a single scrolling feed. The feed alternates between the desks: first story of a, first story of b, second of a, second of b, and so on.

Implement ZigzagFeed. next() returns the following story id. If the desk whose turn it is has run out, the feed simply serves the other desk until nothing is left. hasNext() tells whether any story remains in either list. Each operation must take O(1) time and the class should not build a merged copy of the data.

Example 1

Input:
operations = ["ZigzagFeed","next","next","next","next","hasNext","next","hasNext"]arguments = [[[1,2,3],[10,20]],[],[],[],[],[],[],[]]
Output:
[null,1,10,2,20,true,3,false]
Explanation:

The feed alternates 1, 10, 2, 20 and, once the second list runs dry, keeps serving the leftover 3.

Example 2

Input:
operations = ["ZigzagFeed","hasNext","next","next","hasNext"]arguments = [[[],[6,7]],[],[],[],[]]
Output:
[null,true,6,7,false]
Explanation:

With an empty first list every item comes from the second list.

Example 3

Input:
operations = ["ZigzagFeed","next","hasNext","next","hasNext"]arguments = [[[5],[9]],[],[],[],[]]
Output:
[null,5,true,9,false]
Explanation:

One item is taken from each list in turn, starting with the first.

Constraints

0 ≤ a.length, b.length ≤ 1000

-109 ≤ a[i], b[i] ≤ 109

At most 4000 calls; next is only called while hasNext() would return true.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.
Time per case
Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms

Expected complexity

Time
O(1) per operation
Space
O(1) extra

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.