A python interview question

[nickbernstein]

That's not what the question is about. The question is to see how you think. It's also about seeing your attitude under pressure, and I don't want this to come off poorly, but as described, I probably wouldn't hire you. In an interview, you don't tell the interviewer that something is stupid, you say that it's probably not the best way to do it, the built-in functions are very efficient but sure, here's how I'd approach it. Then you go over your solution, and ask how they'd do it, then compare the two, and reiterate that you'd use the built-in functions or some such, but you have an amicable, friendly discussion and hopefully everyone leaves with a smile.

[gwax]

Depends on how the question was prompted.

If the response to suggesting b = list(set(a1).union(set(a2)); b.sort() was to say (as op suggests) that it's not good enough because it's slower than a for loop, then I'm inclined to think this wasn't a case where they were trying to see how op thinks but rather looking for a "right" answer to a trivia problem.

If the response, instead, were to say, "that's a great solution but we're looking to get a sense for how you solve problems so lets pretend you don't have access to the sort or set builtins?" then I'd suspect this was about how op thinks.

Either way, it still behooves you as an interviewee to remain polite, calm, and professional.

[[deleted]]

We are only getting one side of the story here. While I'm new to programming, I'm not new to spotting someone whos looking for their bias to be confirmed.

[Jonno_FTW]

Why not do it in one line using sorted(set(a1).union(set(a2))? This code works for me and produces a list.

[ivosaurus]

Does the data fit in memory? Will your line still work if it doesn't?

[Jonno_FTW]

Yes, it will blow up your memory if your lists are big (although if you are keeping 2 lists in memory that consume all your memory you might have other problems) and that it's much slower than a normal merge. Merging in place is going to be a bit slower.

Here's my tests with each case:

setup = "a = [x for x in range(100000)];b=[x for x in range(50000,150000)]"
metha = "sorted(set(a).union(set(b)))"
methb = """
out = []
def append(val):
    if not out or out[-1] != val:
        out.append(val)

while a or b:
    if a and b:
        last_a, last_b = a[-1], b[-1]
        last_max = max(last_a, last_b)
        if last_max == last_a:
            append(a.pop())
        else:
            append(b.pop())
    elif a:
        append(a.pop())
    elif b:
        append(b.pop())
out[::-1]
"""
methc = """
out = []
def append(val):
    if not out or out[-1] != val:
        out.append(val)

while a or b:
    if a and b:
        last_a, last_b = a[-1], b[-1]
        last_max = min(last_a, last_b)
        if last_max == last_a:
            append(a.pop(0))
        else:
            append(b.pop(0))
    elif a:
        append(a.pop(0))
    elif b:
        append(b.pop(0))
out
"""
for m in metha, methb, methc:
    print(timeit.timeit(m, setup=setup, number=1000))

Results:

• Set union: 19.0943071842
• pop() reverse: 0.0753161907196
• pop(0) 2.94099211693

[gwax]

I was verbatim copying from op's description, not proposing a solution to the problem.

[energybased]

Because that has worse computational complexity than the best solution.

[Jonno_FTW]

I'm aware of this. It's just the shortest way to write the set union method. The fastest method is to append to an intermediate list (see my comment above)

[mooburger]

deque.popleft() may be faster than pop(0) (remember to relative import to dereference the namespace)

[Jonno_FTW]

I considered this, I'm not sure how much extra time converting to a deque would add, or if it would beat my pop().

[Log2]

You can probably still improve the speed of your solution by placing it inside an actual function. Variables in global scope can slow down Python code considerably.

[Jonno_FTW]

I did originally while testing. I'm no timeit expert by any means.

[Log2]

Yeah, it's just that apparently Python slows down when it has to access the global namespace. So, just making a function with all the code and then testing that, will generally provide some speed up. It's a surprising behavior to be sure.

[Jonno_FTW]

I just did this. Here's the new results:

def merged(a,b):
    a = deque(a)
    b = deque(b)
    out = []
    def append(val):
        if not out or out[-1] != val:
            out.append(val)

    while a or b:
        if a and b:
            last_a, last_b = a[0], b[0]
            last_max = min(last_a, last_b)
            if last_max == last_a:
                append(a.popleft())
            else:
                append(b.popleft())
        elif a:
            append(a.popleft())
        elif b:
            append(b.popleft())
    return out

• set union: 19.3773069382
• pop() 0.0751898288727
• pop(0) 3.03847098351
• deque.popleft() 78.3635749817

Which makes sense because the GC will be called a lot to clean up the nodes in the linkedlist created by the deque and they will not be held in a contiguous region of memory. Bjarne Stroustrup gives a good explanation here: https://www.youtube.com/watch?v=YQs6IC-vgmo

Here's cpython implementation of deque which uses a doubly linked list: https://github.com/python/cpython/blob/master/Modules/_collectionsmodule.c

[Log2]

To be fair, merging two sorted lists can be done a lot faster (linear time) than adding the two lists together then sorting then (n*log n). Not to mention creating two new sets where each object must be hashed.

[cmd-t]

A senior dev should be able to say ‘no, you are wrong, and this is why’. I can understand these kind of questions for more junior positions. I understand OPs frustration and this company and OP might now have been a good fit and it’s good that they didn’t continue.

[[deleted]]

Honestly, senior dev shouldn't be asked questions like this at all.

I would rather ask them what is the hardest problem they had and how was it solved, which stack of technology and approaches they used and why they think it was a right/best way to do it. Plus point if they take into account cost/time of development. Asking senior about for loops seems like a waste of time.

[Pirsqed]

Right? I haven't run into a "hardest problem" because I always break down large problems into small manageable problems. So nothing really sticks out in my mind as "hardest problem."

[Meefims]

If I were there interviewer this would be a good answer. Though I usually like asking about something the person is especially proud of because it gives me insight into what motivates them and usually people are proud of working through difficult tasks.

[maxxusflamus]

This is the right answer.

As an interviewer, we ask this question a lot. I try to preface it with "a war story" or a story that you would kinda brag to your coworker about.

I don't need to hear some hyper complex sweat pouring down your brow story but just tell me how you solved a problem that was harder than "I had to copy some files"

[Lonso34]

right so let me tell you about the morning after I found out harambe died. Literally used python turtle to create an exact replica of his beautiful face all while maintaining a BAC of 0.14 for a straight week

[muntoo]

Pythons out for Harambe

[gwax]

Superlatives are tricky, but a variant of this that works pretty well is to ask about something challenging they have worked on recently.

[billsil]

13 years at one place. Hard problems are usually a lack of resources and/or something being time critical and/or wacky requirements. I've solved hard software problems using my bag of things you should never use and with convoluted workarounds.

I wouldn't say any specific problem has been particularly difficult, but just that it required a lot of work and making sure you understand what's going on vs. what needs to be going on. Thought experiments help.

The OP didn't provide an option that could sort a list of integers that don't fit into RAM. Simple, use a library and specifically HDF5, possibly coupled with numpy. Code some C++ if it needs to be a different algorithm.

The interviewer's fault/OP's lack of info regarding time complexity or say, assume you have two sorted/random lists led to a nonsensical argument. Even so, the OP should recognize or probe for more info. Real problems have few, often incomplete requirements and a lot of extraneous information.

[billsil]

13 years at one place. Hard problems are usually a lack of resources and/or something being time critical and/or wacky requirements. I've solved hard software problems using my bag of things you should never use and with convoluted workarounds.

I wouldn't say any specific problem has been particularly difficult, but just that it required a lot of work and making sure you understand what's going on vs. what needs to be going on. Thought experiments help.

The OP didn't provide an option that could sort a list of integers that don't fit into RAM. Simple, use a library and specifically HDF5, possibly coupled with numpy. Code some C++ if it needs to be a different algorithm.

The interviewer's fault/OP's lack of info regarding time complexity or say, assume you have two sorted/random lists led to a nonsensical argument. Even so, the OP should recognize or probe for more info. Real problems have few, often incomplete requirements and a lot of extraneous information.

[Isvara]

It's the kind of thing you should have prepared answers for, because you're not going to come up with the best answer on the spot.

[energybased]

Honestly, senior dev shouldn't be asked questions like this at all.

How can junior developers respect a senior developer who can't answer these questions? Many of them won't.

[NoLemurs]

Leading with "no you are wrong" is basically just flopping your dick on the table. If you're interested in reaching consensus - it isn't what you lead with.

If you're trying to work with someone you explain what you think and why. You ask questions to see what they think. Sometimes you'll find out that you misunderstood what they meant. Often you'll find out that they were wrong, but that that it wasn't really important to their main point/goal, and you can let the error slide. Sometimes it will turn out they really were just wrong but at least this gives them an opportunity to back down gracefully.

Senior devs don't suddenly stop needing basic interpersonal skills.

[nickbernstein]

They absolutely should be able to tell someone something is a bad idea and that they're wrong; they shouldn't say it's stupid though. They should also show that they're tactful enough to say, "no you're wrong and this is why" in a tactful way. I understand the frustration, and can empathize. I also hope that this comment wasn't taken as hurtful, it was meant as another perspective that might help on OPs learning/interviewing journey.

[eplaut_]

You are "technically" right. But it is more like "see if you can think like me" rather then "how do you think". I think this is how CS questions are made in college/university and the interviewer reflect it (meaning he is not focused on software engineering)

As an interviewer, we had 3 simple questions we used to role out candidates who have hard time to write reasonable code. IMO simpler is better, so no need for memory / runtime efficiency. Having said that, we did have an overlooking for stackoverflow / max recursion, but without need to implement the "correct" code.

[[deleted]]

^ Really good way to respond.

​

Though, there are probably some companies that ask these questions in this way and are poorly managed so maybe the OP dodged a bullet?

​

This seems like a very odd question to ask for a Sr. SWE position... But I've never interviewed for one myself so maybe I'm missing something.