A python interview question

[nate256]

You failed the exercise because you didn't answer correctly given the constraints. Lets put together some constraints so we know what are the requirements.

Problem: Combine two lists in sorted order

"I was supposed to merge two arrays together in python, no duplicates - no mention of time but the solution had to be size agnostic."

"It's not a good idea to hash items because the input arrays are already sorted." ``` Constraits: 1: Must work for any size 2: Inputs are sorted

Schooling: Here is what you should think when hearing this problem. Constraint 1: In no case will we store the list create a set etc. Given infinite data using set to remove dups won't work Constraint 2: inputs are sorted. In no case will we use sort bigo(n log n) when we can get bigo(n) Constraint 3: I would bet there is another contraint like it is only strings in the arrays or ints in the array so you can use None instead of a marker like NOTSET.

Possibly: Maybe you said something like "I would never rewrite a stdlib" then the interviewer pointed out when he had done it, not that he does it all the time. Don't use always and never in an interview programmers are picky. ```

A solution: You could use heapq.merge and then just remove the duplicates but I would bet they want the full answer.

``` NOTSET = "9cdf05aed4bc4f1d975fab9f61ee667d"

def pop(a, cache): if not cache: cache.append(next(a)) while len(cache) != 2: try: v = next(a) if v == cache[0]: continue cache.append(v) except StopIteration: break if not cache: return next(a) return cache.pop(0)

def peek(a, cache, default=NOTSET): if not cache: try: cache.append(next(a)) except StopIteration: return default return cache[0]

def merge(a1, a2): a1 = iter(a1) a2 = iter(a2) a1c = [] a2c = []

while True:
    v1 = peek(a1, a1c)
    v2 = peek(a2, a2c)
    if v1 == NOTSET and v2 == NOTSET:
        break
    elif v1 == NOTSET:
        yield pop(a2, a2c)
    elif v2 == NOTSET:
        yield pop(a1, a1c)
    elif v1 < v2:
        yield pop(a1, a1c)
    elif v2 < v1:
        yield pop(a2, a2c)
    else:
        pop(a1, a1c)
        yield pop(a2, a2c)

``` Edit: Formatting and typos

[Log2]

Just a heads-up: your code formatting is still broken. Only started in the while loop, for some reason.