Hacker News Reader

> e.g. If they ask you to merge sorted arrays and you don't know that Heap sort is the best way to do it, you've lost the interview no matter how clear your thought process is. Not because the interviewer is not watchful. But because your competition has solved it with Heap Sort. So even if both of you demonstrated a clear thought process, the other person gets the job, because s/he is more prepared.

Sadly, there's a ton of very qualified software engineers that make up this "competition" that you speak of, and still lose. Meanwhile, there's another group of people that realize how ridiculous proving yourself in that way every few years throughout the course of one's career is, become sales engineers, and make more money. They also don't have to have a whiteboard pissing contest anymore over such things.

I really wonder if lawyers who have been practicing for 7 years, or consultants from the Bain's and McKinseys of the world get asked questions about classes they took in junior year of undergrad when they interview.

Your frustration is justified. However, there is no flawless interview process. You could try and read this for more context: http://www.gayle.com/blog/2015/6/10/developer-interviews-are...

Having been on the other side for quite a long time, I can assure you that despite best efforts by some very well meaning and smart people, this is the only process that has stuck around (and is still growing). That's because it's the most convenient method to interview at scale.

When a company is very small and/or only hiring one or two engineers a quarter, choice of interviewing method doesn't really matter a whole lot. You will have enough time to interview people and any method you follow will give you a decent candidate.

But when you are a coveted company with a strong candidate pipeline and are tasked with hiring 25 engineers a quarter (which was the case with the leadership team I was a part of), or thousand at Google scale, you need a process that is fast, efficient and convenient. You don't necessarily need a process that's best for candidates; as long as the process filters in enough candidates, and doesn't waste much of your team's time, you're good.

There are some other reasons this process has stuck around, but that's one main reason. I don't see it going away any time soon.

This is a really awesome response, coming from an expert in the field.

It makes me a little sad to read some of this, since it runs a little counter to what I thought was becoming a more general understanding about how to and how not to interview candidates. I give search/social companies a pass because the algorithms and graph theory are core skills there, but in general it's well-known that any kind of closed question isn't all that valuable in an interview, tech or otherwise.

I don't see programming problems any differently. Looking for a "right" answer just means they know what you know and maybe think like you think. It's a very egocentric way to proceed, to be honest. I don't need a team of me!

But it does open my eyes a bit to the fact that new grads may have a pretty different experience than others. I'll try to keep that in mind in the future. I don't want to interview this way, but if I know someone has expected to interview this way it'll help me understand them better.

> e.g. If they ask you to merge sorted arrays and you don't know that Heap sort is the best way to do it

Sorry, I'm confused. I love heaps, but... what's wrong with this simple O(n+m) time and space solution, that I can easily prove is the theoretical limit (because the output size is O(n+m))?

    def merge_sorted(a, b):
        result = []
        la, lb = len(a), len(b)
        ia, ib = 0, 0
        while ia < la or ib < lb:
            if ib >= lb:
                result += a[ia:]
                break
            if ia >= la:
                result += b[ib:]
                break
            if a[ia] <= b[ib]:
                result.append(a[ia])
                ia += 1
            else:
                result.append(b[ib])
                ib += 1
        return result
    assert merge_sorted([], []) == []
    assert merge_sorted([1, 2, 3], []) == [1, 2, 3]
    assert merge_sorted([], [1, 2, 3]) == [1, 2, 3]
    assert merge_sorted([1, 3, 5], [2, 4]) == [1, 2, 3, 4, 5]
    assert merge_sorted([2, 4], [1, 3, 5]) == [1, 2, 3, 4, 5]
    assert merge_sorted([1, 2, 3], [1, 2, 3]) == [1, 1, 2, 2, 3, 3]

Ah, some googling got me here:

http://www.geeksforgeeks.org/merge-k-sorted-arrays/

Merge k sorted arrays. Obviously that's a job for a min heap (not heap sort though, just a heap to keep the values of the next item in each array).

Sorry I was not very precise there. Exact question is to merge K sorted arrays, size N each. A natural extension of that problem, is to have K streams.

First part can be solved with an extension of O(n+m) solution you proposed, but when it comes to streaming, Heap works better, with the same complexity, because you don't have to know the size of the arrays in advance: https://discuss.leetcode.com/topic/2780/a-java-solution-base...

> It takes a certain level of life-confidence to just go to an interview with what you know and take the rest head-on.

Apparently, I have that kind of confidence. In my experience, confidence is good for winging the personal questions and talking about my past projects, but at the end of the day technical interviews come down to being able to solve problems you'd never (or rarely) see on the job. If you walk in unprepared, you will fail. I usually fail the first 5-10 in my job search before I get a yes. Walking in unprepared is ridiculously suboptimal.

Just to clarify, I don't mean just the google style interviews where they ask you graduate level DS and algo questions. Thankfully, a lot of smaller companies are transitioning to asking questions about the tools, languages and techniques specific to the field. But, that still requires weeks of study because the level of detail most interviewers go into far exceeds what you see working on CRUD apps. Not to mention the difficulty of memorizing every CSS3 property available.

> With the plethora of prep material available for past several years, the bar for interviewing has just moved higher and higher at good companies. If you look at G and F (and some others), there is no way you can get away with just knowing the basics of trees and binary searches. It just takes time.

This is so idiotic. Asking about binary searches does not identify good candidates unless they're going to be doing a lot of binary searches.

If someone asks me stupid CS 101 questions in an interview it's a red flag to me.

I've been pretty seriously studying CS for a while, and there's a trillion things I don't know.

>If they ask you to merge sorted arrays and you don't know that Heap sort is the best way to do it, you've lost the interview no matter [...]

... no matter the fact that there are a hundred ways to sort an array, and you think you know the best one? Has it been proven the best, or is it just the best you know? How many ways do you actually know to sort an array? Has all research on array sorting ground to a halt because there's no better way to do it?

If someone asked me the best way to sort an array I'd say "probably radix sort." If you expected "merge sort," then you're the fool.

My point being, I study a lot, but that doesn't give you answers. I gives you a base from which further study can happen.

"Tell me more about the array you want me to sort" is the only valid initial response to "best way to sort an array." That said, the question posed had very little to do with sorting arrays and I'm not sure where your hostility came from.

My objections had nothing to do with the kind of question posed, only the expected response. Unless it's been proven that there can be no way to merge sorted arrays "better" than heap sort, it's flippant and erroneous to expect someone to give that answer. (And there are real reasons to not use heap sort for this.) Even if I don't know that this is the (supposedly) correct answer, they've learned little about my ability to actually merge sorted arrays, and even less about my general ability to solve problems.

Unless they're explicitly hiring me to merge sorted arrays, I'm not going to claim any expertise at at. There are probably hundreds of research papers on this topic, and I haven't read them all, and I know it. I understand that sorting is a big CS topic, but it's not the only CS topic, and I can go the rest of my carrier assuming someone else already solved it and never know how heap sort is implemented and still solve hard problems.

So they shouldn't ask that kind of question and expect such a casually incorrect answer. And they can't tell me "I've already lost the interview" if I don't see things this way, because then that might trigger some manner of hostility. I don't lose interviews when the interviewer expects careless and rote answers. The company loses.

His question was about merging pre-sorted arrays, not about sorting arrays. (Still, see my own disagreement in sibling)