Pointless algorithm questions and cowardly interviewers

Jun 01, 2016 11:38

Tech interviews frustrate me.  Well, actually, interviews frustrate me.

I just had a phone interview (audio only).  The guy asked me a lot of questions about my background.  I answered them as honestly as I could, and I'm not sure if the result was positive.  The conversation went something like this:

Him:  What have you been doing recently?

Me:  I've been running a vanity publishing company, GreenDog Press.  I write for it, I automate publication, I write tools to manage it all.  I've also been doing various side projects to keep my hand in and my skills sharp.  Lately I've been doing some consulting work -- a guy hired me to do some web programming, which I did.  Now he's hired me to do a code review on his Java game, specifically wanting design review.  I've been going through, pointing out where I think he's decomposed things too far, where things should have been composed differently, and also offering tactical suggestions like "this code should be organized like this."  Finally, I'm talking with a friend of mine about the possibility of doing a startup.  [details]

Him:  Tell me about the companies you've founded.

Me:  [talks about companies and what I've learned from each one]

Now, the issue here is that the above could either be interpreted as "this guy is a flight risk who might bail to go start a company" or it could be interpreted as "this guy is a skilled and broad-based techie who also understands business issues."  I didn't get the chance to spin that one, because we moved on to...

Him:  Okay, let me ask you a tech question.  You have an array of data, and comparisons are expensive.  What's the smallest number of comparisons you can do to find the largest element of the array?

Me:  [thinks]  Well, assuming you have no context to simplify things, you're going to need to look at each element, so that's N comparisons.

Him: Really?  What about an array of two?

Me:  Ah, good point.  Okay, that only needs 1 comparison.  After that, though, it's going to be one additional comparison for each new element, so the correct answer is N-1.

Him:  How would you prove that that's the best answer, that no other algorithm could be better?

Me:  Well, I'd proceed inductively.  For one element, you need 0 comparisons.  For two elements you need 1.  For three elements you'd need 2.  In the case of N elements you need to do 1 comparison plus the number needed for N-1 elements.  One element requires zero comparisons, and you can proceed by induction from there.  In essence you're setting a pointer to the first element, then walking it up the array, updating it to the largest seen so far.

Him:  [more poking at the question]

Me:  ...Okay, I feel like I've answered this one already, so either I'm not explaining it well or there's a computer science trick that I'm not familiar with.  In either case, I don't think I can answer better than I have.  What's the correct answer?

Him:  Well, suppose we want to find the largest and the second largest?  How many would that take?

Me:  Hm.  Well, for one element you need 0 comparisons again -- the element is definitely the largest, and there is no second largest.  When you add another element you'll add 2 comparisons -- 1 to identify if the new element is larger than the largest, 1 to identify if it's larger than the second largest.  Proceed by induction from there.  (*)

Him: [more poking around, clearly not satisfied]

Me: Okay, I need to think this through visually.  [puts objects on the table, starts talking through what I'm doing]

Him:  Okay, I'm late for another meeting and need to jump off.  Let's let this go for now and we'll see about next steps later.

Me:  Are there going to be next steps, or have I already taken too long to answer your question?

Him:  Well, uh, um...we're going to talk about that.  I'll have [the HR person] contact you.

[we say goodbyes, we hang up]

Now, pretty obviously, they're not going to be following up.  The guy obviously wasn't satisfied with my answer, so I wish he'd just friggin' say so.  On the other hand, my experience at ChannelMeter is exactly what they need -- I wrote harvesters to pull in massive amounts of data, digest it into usable data, and then archive off the raw feeds in case we ever needed to regenerate the data or generate new types of results from it.  This is precisely what they're doing, except that they're doing it on store analytics instead of YouTube analytics.

I wish the guy just had the balls to say, "No, we were looking for someone with a stronger algorithmic knowledge.  Thank you, though."  But, no.  He's not going to say that to my face, he's going to have his HR person send me an email instead.

Now, on thinking about it about it after the fact, the "(Comparisons of N-1) + 2 for the new element" is correct only in the degenerate case.  [cf the (*) above]  If the new element is larger than the previous largest then you only need 1 comparison -- the largest is now the new largest element and the new second largest is the previous largest element.  Still, if you're designing an algorithm it's important to know the worst case, even though what you're looking for is the average case.  I figured out this error the minute I sat and wrote it down, which I could have done in front of him if I'd been in a face-to-face or if I were actually working on the project.  And, of course, if I were actually working on the project I wouldn't be figuring this out -- I'd be downloading a library that was optimized for the job instead of writing my own, because I'm not an idiot.

[EDIT:  Actually, I'm wrong, you can do it faster.  The second largest element of the total array has to be one of the largest from the subarrays, so you can find the largest by comparing only between the winners of each pairwise contest.  Having an odd number of elements adds some uncertainty -- it requires 1 compairson if the Nth item is larger than the largest from the winning pair, but 2 if it's smaller.  At each step you can carry an odd item along with 0 comparisons, and when you have another odd step you can combine the two odd elements into a pair that costs 1 comparison.]

So here's what I find frustrating:  this is a pointless question that has no relevance to the actual job, he doesn't have the guts to tell me to my face that I flunked his pointless test, and I'm probably not going to get the job even though my experience is very much in line with what they need.  The part that irritates me the most is the "not having the guts to say so" part, though.
Previous post Next post
Up