FastPrepLazy K-Way Union Iterator

Lazy K-Way Union Iterator

MongoDB logoMongoDB● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Implement a lazy union iterator over strictly increasing input iterators. The initial exercise has two iterators; the follow-up permits k iterators. Return each distinct value once, in strictly increasing order, without materializing the merged sequence.

For the finite practice interface, each row of sortedIterators contains one iterator's values as strings. The selector valueType is int for homogeneous integer values encoded as canonical decimal strings, or string for homogeneous text values. Compare integer values numerically and text values lexicographically.

Process the ordered operations using one persistent union iterator:

  • has_next returns true if a distinct value remains, otherwise false. It must not consume any value.
  • next returns the least remaining value. If several iterator heads equal that value, return it once and advance all of those iterators.
  • For this exercise, next after exhaustion returns ERROR_EXHAUSTED without changing state.

Return one string result per operation, in order. Integer results use canonical decimal encoding. Keep at most one current head per input iterator: auxiliary iterator state is O(1) for two iterators and O(k) for the follow-up, excluding the provided input and required output. Do not sort or flatten the complete input.

Complete runUnionIterator. The string representation and operation batch adapt the reported integer-or-string iterator interface to deterministic practice; they do not replace its lazy state transitions.

Function

runUnionIterator(sortedIterators: String[][], operations: String[], valueType: String) → String[]

Examples

Example 1

sortedIterators = [["2","4","6","8","10"],["1","2","3","5","8","13"]]operations = ["next","next","next","next","next","next","next","next","next"]valueType = "int"return = ["1","2","3","4","5","6","8","10","13"]

The union is 1,2,3,4,5,6,8,10,13. Shared values 2 and 8 each appear once.

Example 2

sortedIterators = [["apple","banana","orange","tree"],["apple","tree","zoo"]]operations = ["next","next","next","next","next"]valueType = "string"return = ["apple","banana","orange","tree","zoo"]

The text union is apple,banana,orange,tree,zoo; matching heads advance together.

Example 3

sortedIterators = [["-10","-9","-5","-1","0","2","4"],["-9","-5","-3","-2","0","1","2"]]operations = ["next","next","next","next","next","next","next","next","next","next"]valueType = "int"return = ["-10","-9","-5","-3","-2","-1","0","1","2","4"]

Numeric comparison handles negative values. The result is -10,-9,-5,-3,-2,-1,0,1,2,4.

Example 4

sortedIterators = [["1","2","3"],[]]operations = ["next","next","next"]valueType = "int"return = ["1","2","3"]

An empty iterator contributes no head. The other iterator produces 1,2,3.

Constraints

  • 0 <= sortedIterators.length <= 200, with at most 200000 values across all rows.
  • 0 <= operations.length <= 2000.
  • Every row is strictly increasing under the selected comparison. Equal values may occur in different rows.
  • valueType is int or string; all values share that type.
  • Integer tokens use canonical base-ten encoding, with no leading plus or zeros except 0, and lie within [-2147483648,2147483647].
  • Text values contain 1 through 32 lowercase ASCII letters. Lexicographic order compares those characters and puts a proper prefix first.
  • Each operation is has_next or next. Repeated observations and exhausted requests are allowed.
  • The solution must preserve lazy iteration and the stated auxiliary-space bounds.

More MongoDB problems

See MongoDB hiring insights
public String[] runUnionIterator(String[][] sortedIterators, String[] operations, String valueType) {
    // Write your code here.
}
sortedIterators[["2","4","6","8","10"],["1","2","3","5","8","13"]]
operations["next","next","next","next","next","next","next","next","next"]
valueType"int"
expected["1", "2", "3", "4", "5", "6", "8", "10", "13"]
Checking account…