Retiring a Great Interview Problem • Hacker News Board

Re: Retiring a Great Interview Problem

#71

Post by [deleted] » Mon, Aug 08, 2011, 6:16 PM UTC

dxbydt wrote: post #30

patio11 wrote: post #2

A spiritually similar question at a previous employer resulted in many candidates attempting to iterate over the dictionary rather than iterating over the string. We hired them. At least they could iterate over a dictionary. That's a surprisingly rare skill in the hiring pool. Maybe I'm just getting cynical in my old age, but sometimes I think the world is awash in incompetence. We see so much of it in tech because o…

>sometimes I think the world is awash in incompetence. We see so much of it in tech because our incompetencies are (marginally) harder to hide. A very candid Philip Greenspun in Founders@Work( p341-2) : "In aviation, by the time someone's your employee, their perceived skill and actual skill are reasonably in line. JFK Jr is not working at a charter operation because he's dead. In IT,you have people who think 'I am a…

[deleted]

Re: Retiring a Great Interview Problem

#72

Post by nandemo » Mon, Aug 08, 2011, 6:51 PM UTC

someone13 wrote: post #22

skrebbel wrote: post #20

Earlier quoted context omitted.

I love it. You spark an (imho) much more interesting debate: that of raw smartness vs pragmatic productivity. A colleague of mine (now hired) was asked to code a string compare during her interview for a .NET function. She said "String.Compare()". This puzzled the interviewers for a while. They asked her whether she could write it out, she said she didn't see the point. They ended up hiring her for other reasons (not…

There's something to be said for NOT reinventing the wheel. Standard libraries are standard for a reason - the "String.Compare()" function is likely faster for just about every case, in addition to being already there.

I keep seeing this argument on threads about interview questions.

The principle of not reinventing the wheel has nothing to do with interview questions. Sure, if you're actually working on solving an actual problem at your job, then most of the time you'll be better off using a standard library function instead of rolling your own.

In the context of the job interview, however, it doesn't matter if the solution to the problem is well-known or whether it can be found in a standard library. The problem of the interviewer is not to find out how to compare strings, it's determining if the candidate will be able to write proper code if hired. And the string-compare question might be a good starting point for evaluating the candidate's level. In any case, the fact that a solution is in a standard library is irrelevant.

If I was the interviewer I'd create a new data structure Foo and then ask the candidate to implement Foo.compare(). The question remains essentially the same, so I wonder what the candidate would reply.

Re: Retiring a Great Interview Problem

#73

Post by mak120 » Mon, Aug 08, 2011, 6:59 PM UTC

Its a nice Dynamic programming problem. The beauty of DP is that simply memorizing one application of it does not guarantee you a solution to an entirely different problem that might have a similar Dynamic Programming solution. Look over the TopCoder SRM archives if you don't believe me.

So even though you are retiring this one, coming up with something similar that tests for basically the same things shouldn't be impossible.

Re: Retiring a Great Interview Problem

#74

Post by cema » Mon, Aug 08, 2011, 8:06 PM UTC

dtunkelang wrote: post #51

Shenglong wrote: post #47

With the exception of the last part of the question, you learn everything there in your first year of CS at university. Do people who can't write this really put the language on their resume? Can I get some stats? I really don't (want to) believe it. What percentage of people get this question wrong? Are they all some sort of eng/cs graduate? I'm not even a coder and I can solve this in a few minutes.

I don't have stats I can share, but I assure you that this problem has confounded many interview candidates with strong resumes. I agree with you that it's all basic material -- that's deliberate. I'm glad you think it's too easy. :-)

Yes, it's basic. But many people who are not fresh out of college may have spent recent years solving a completely different set of programming tasks, and do not have it loaded in their brains.

When applicants prepare for an interview, they do not often know what kind of knowledge to load in their heads. For example, just a couple of weeks ago I was asked to figure out a simple bit-flipping scheme, and bit string manipulations are something that I have not thought about in many years. So it took me about 10 minutes for a problem that I would have done in less than a minute when I was spending time thinking about similar things and my mind was full with them.

Being prepared for a technical interview does not mean to have memorized a few solutions to a few problems, but it means to have played with them sufficiently to have the brain loaded with the material. This helps with intuition as well as specific technical skills.

Re: Retiring a Great Interview Problem

#75

Post by cema » Mon, Aug 08, 2011, 8:09 PM UTC

jswinghammer wrote: post #57

dtunkelang wrote: post #43

Earlier quoted context omitted.

Point taken. But it's hard to come up with good interview questions, as my colleagues here, at Google, and at Endeca can attest. In contrast, it's much easier to post solutions. That's why I'm working on an approach that assumes the candidate does of prior knowledge of the problem. But not there yet.

One thing that I've noticed over the years is that almost no one prepares for an interview in any way so you'll still keep out the worst candidates with this question.

I think Google etc are exceptions, people do prepare for technical interviews there.

Re: Retiring a Great Interview Problem

#76

Post by btilly » Mon, Aug 08, 2011, 8:55 PM UTC

mason55 wrote: post #56

SoftwareMaven wrote: post #52

Earlier quoted context omitted.

I wouldn't feel bad. The advanced answers to this question require spending a lot of time understanding string processing. It's like having a CSS question that can be implemented multiple ways: a simple, obvious, slow way and a complicated, "deep knowledge required", fast way. If you have lots of experience with CSS, you might get the fast way, but it doesn't really say how good a programmer you are. (Yes, not a perf…

The advanced answers to this question require spending a lot of time understanding string processing. Really? Seems like a standard DP question to me

Indeed. The only detail that surprised me was that you could only do exact lookups in the dictionary. That makes it O(n*n). If you had the dictionary stored in a trie it would be O(n) on long strings. (With a maximum constant whose size depends on the length of the longest word in the dictionary.)

Re: Retiring a Great Interview Problem

#77

Post by eru » Mon, Aug 08, 2011, 9:36 PM UTC

sur wrote: post #67

SoftwareMaven wrote: post #50

Earlier quoted context omitted.

Well, yours does iterate over the dictionary twice and generates a temporary list in the meantime. If you have a huge dictionary, this would explode. The equivalent Java code wouldn't do that (due to lack of list comprehensions).

He is using parentheses instead of square brackets, so the code is actually using a generator expression which will produce each value lazily.

Is mydict.items() also lazy?

Re: Retiring a Great Interview Problem

#78

Post by eru » Mon, Aug 08, 2011, 9:42 PM UTC

saucetenuto wrote: post #35

qntm wrote: post #21

Earlier quoted context omitted.

This was actually going to be my solution as well. Regex engines are optimised for exactly this sort of problem, why duplicate the work manually?

rfumani gave one reason: it won't produce the right answer. Here's another: your regex engine will probably fall over dead if you ask it apply a million-word alternation.

grep could be fine. I wouldn't trust backtracking regex engines, though.

Re: Retiring a Great Interview Problem

#79

Post by eru » Mon, Aug 08, 2011, 9:45 PM UTC

NY_Entrepreneur wrote: post #49

rfurmani wrote: post #14

Earlier quoted context omitted.

The "obvious" selection of stages does work. When you are at position j you check all i<j until you find one where there is a segmentation up to i, and the substring [i,j) is a word. Memoization is just syntactic (semantic?) sugar on top of this and he provides the code that basically implements the above. In programming competition circles it's common to just say "it's dynamic programming" when the stages are semi-o…

Yes, from a fast reading, your solution appears to be correct, and so does 'memoization', but, still, in spite of common practice in computing, it's not a dynamic programming algorithm because what 'dynamic programming' is goes back to R. Bellman and his student Dreyfus and the book Dreyfus and Law. There may be a problem with what you outline: That substring [i, j) is a word is not so impressive! In addition we need…

At university we defined dynamic programming as reducing a problem to finding paths in directed acyclic grahp. By that definition, there's a simple way to map the problem to dynamic programming. And yes, it's sloppy, if you don't mention the `stages' or equivalently, how you'd (lazily) construct the graph.

Re: Retiring a Great Interview Problem

#80

Post by logic » Mon, Aug 08, 2011, 9:48 PM UTC

dtunkelang wrote: post #39

pkteison wrote: post #25

Bit of a tangent, but a real question: If a writer doesn't approve of a site's behavior (in this case, Glassdoor is desribed as "a site that does not seem to mind when interview candidates violate NDAs"), why does the writer still link to them? Inbound links (w/o a nofollow) help sites, why help sites you don't like?

Point taken. I thought of not linking to them, or even not mentioning them. But they do play an important part in the story of the post, and I don't think I'm helping them so much as I'm raising employees' and employers' awareness of their existence. At least now a few more interviewers might check to see if their questions are posted there. From my limited data, interviewees are already more aware of Glassdoor than…

> interviewees are already more aware of Glassdoor than interviewers

My first amusing thought when reading this was to assume a correlation; ie. that interviewees who lean heavily on Glassdoor prior to interviewing do not eventually become intervewers.