1053. Zigzag Feed
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.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor 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