Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to Rock an Algorithms Interview

blog.palantir.com

Post reply on HN
Print view View original

61–70 of 169 posts

Re: How to Rock an Algorithms Interview

#61

Post by T-hawk »

rcfox wrote: post #51
mcantor wrote: post #43

Earlier quoted context omitted.

Sorry, I should have been more specific: I understand the rules of Big O complexity, which you aptly summarized; the part I'm really curious about is " From there, you can pretty much combine these rules to analyze many algorithms. " It's not that the concepts are mysterious to me, but that making them a part of my learning habits has not come naturally.

> the part I'm really curious about is "From there, you can pretty much combine these rules to analyze many algorithms." I'm not sure if I'm still misunderstanding you, but here's an example of what I meant. Say, for whatever reason, you want to populate a binary tree with k items of random data: for(int i = 0; i The inside of the loop runs in O(log(n)) time because O(log(n)) > O(1). We're doing it k times, so the to…

We already know that the inner loop runs in O(klog(n)). Since we've just added a loop around that, it's easy to see that the whole thing runs in O(mklog(n)) time.

This is not necessarily true for all cases. (It is for yours.) It's possible for interaction to exist between a loop and its contents, such that the total time is not m times the running time of the interior of the loop.

  for (int i = 0; i
That's a trivial case but sufficient to prove the point. Bubble sort runs in O(n^2), and it looks like we're doing that n times, so the whole thing runs in O(n^3). But that's not true, since bubble sort runs in O(n) when the array is already sorted, so the whole thing is still O(n^2). In other words, the first iteration of the loop induces a side effect that affects all later iterations.

Re: How to Rock an Algorithms Interview

#62

Post by cpeterso »

praptak wrote: post #23
ohyes wrote: post #4

>Given a whiteboard and one hour, determine whether the person across from you is someone you’d like to work with, in the trenches, for the next n years. If we ignore the requirements of one hour... Brute force: Hire a random candidate that hasn't been hired by you before. Fire them when you get fed up with them. Hire a different candidate. Repeat. Greedy Algorithm: Develop the model for an ideal candidate, assign th…

Recursive: require the candidate to come up with the perfect hiring strategy.

As an interviewer, I have asked candidates what questions they like to ask when interviewing and then proceeded to ask them that question. :)

Or ask the candidate "when question should I ask you that I haven't?" These are somewhat softball questions, but they let the candidate drive the interview and highlight what they think is important about their experience.

Re: How to Rock an Algorithms Interview

#63

Post by regs »

va_coder wrote: post #56
mcantor wrote: post #21

FTA: You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) How does one achieve this? Not just being familiar with data structures and algorithms (I am), but being fluent in them, to the extent that you can produce the Big O complexity for different operations off the top of your head. I didn't have a tradition…

I agree. 2011 Programmer Cost/Benefit reality: 1) The chance my app will be so heavily used that it requires deep knowledge of many algorithms is pretty low. 2) The chance my app has serious marketing or business model problems is pretty high. 3) The extra cost of using a scalable platform (PaaS) like Appengine, Heroku or plain EC2 is less than both the cost of my time to learn or relearn all of those algorithms and…

I think you're correct that for certain types of apps, this sort of knowledge is pretty useless.

However, once the number of things you're dealing with gets up to, say, the millions, algorithmic complexity can really bite you in the ass and no matter how much hardware you throw at it (rented or otherwise), if the work that a single node needs to do is unreasonably complex, your whole app will be slow for every user, even if you have enough capacity to handle many simultaneous users.

In the mobile space, you can think of algorithmic complexity being a proxy for battery life - if you can make it cheaper to compute, you do less overall work, and the battery lasts longer.

Re: How to Rock an Algorithms Interview

#64

Post by haberman »

mcantor wrote: post #21

FTA: You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) How does one achieve this? Not just being familiar with data structures and algorithms (I am), but being fluent in them, to the extent that you can produce the Big O complexity for different operations off the top of your head. I didn't have a tradition…

> Maybe it's because none of my personal projects have gotten popular enough to be subjected to the kind of load that reveals such problems.

That's probably the case, and there's no shame in that. The companies who ask these questions do so because their engineers deal with these kinds of scaling challenges every day. They can't afford to have people casually slip in an O(n^2) algorithm when an O(n lg n) or O(n) algorithm would do. If you don't have the experience of working in this kind of environment it's not a dealbreaker, you just need to show an awareness of the big-O implications of your algorithms, which will most likely come from some combination of study and practice.

> Is my lack of fluency preventing me from understanding just how important it is

Probably not -- if you're working at a small scale, then big-O probably truly is one of your lesser concerns (unless you write an O(2^n) algorithm, which is less common to happen accidentally).

Re: How to Rock an Algorithms Interview

#65

Post by rcfox »

T-hawk wrote: post #61
rcfox wrote: post #51

Earlier quoted context omitted.

> the part I'm really curious about is "From there, you can pretty much combine these rules to analyze many algorithms." I'm not sure if I'm still misunderstanding you, but here's an example of what I meant. Say, for whatever reason, you want to populate a binary tree with k items of random data: for(int i = 0; i The inside of the loop runs in O(log(n)) time because O(log(n)) > O(1). We're doing it k times, so the to…

We already know that the inner loop runs in O(klog(n)). Since we've just added a loop around that, it's easy to see that the whole thing runs in O(mklog(n)) time. This is not necessarily true for all cases. (It is for yours.) It's possible for interaction to exist between a loop and its contents, such that the total time is not m times the running time of the interior of the loop. for (int i = 0; i That's a trivial c…

That is true, but one generally doesn't care about the best case. It's a good point though.

(Also, if data is a linked-list, length() could be an O(n) operation. That would make this O(n^3) or O(n^4) ;))

Re: How to Rock an Algorithms Interview

#66

Post by cpeterso »

Jun8 wrote: post #9
ohyes wrote: post #4

>Given a whiteboard and one hour, determine whether the person across from you is someone you’d like to work with, in the trenches, for the next n years. If we ignore the requirements of one hour... Brute force: Hire a random candidate that hasn't been hired by you before. Fire them when you get fed up with them. Hire a different candidate. Repeat. Greedy Algorithm: Develop the model for an ideal candidate, assign th…

Two more approaches: 1) There's the well-known Secretary (or Marriage, or Sultan's Dowry) Problem ( http://en.wikipedia.org/wiki/Secretary_problem ). It has three caveats, though: * Solution assumes that you have a lot of (e.g. ~20) candidates. * It is assumed that you can sum up each candidate's ability in a single number. This is the hardest part, since the human mind works relationally and assigning absolute numbe…

> Hire the engineer and HR person at the same time and have the HR candidates evaluate the engineering candidates.

Demetri Martin's "Important Things" TV show had a comedy sketch about two interview candidates inadvertently interviewing each other, each thinking the other candidate was the hiring manager. :)

http://www.comedycentral.com/videos/index.jhtml?videoId=2686...

Re: How to Rock an Algorithms Interview

#67

Post by jchonphoenix »

mcantor wrote: post #21

FTA: You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) How does one achieve this? Not just being familiar with data structures and algorithms (I am), but being fluent in them, to the extent that you can produce the Big O complexity for different operations off the top of your head. I didn't have a tradition…

Our interviews at Palantir test for these for two reasons:

We evaluate a lot of people coming straight out of school in CS. They don't have much experience in development. Thus, the best way to test if a candidate is smart is to see if he's learned his course material well. We do a lot of heavy algorithms and distributed systems, so we ask that, but it also happens to be what students learn.

Running time and Oh, however, in addition to systems knowledge, is extremely important to creating good software in general. If you can't determine how your software will scale with big data, and you can't understand why efficient code that runs quickly with small operations does so, you simply can't write good software.

I realize a lot of people on HN take offense at these claims because they've written programs without this knowledge and claim they are self taught. The reality, however, is that they aren't good programmers. You don't need a good programmer to write a prototype that works and determines market fit. You do need good programmers to scale your product, add features efficiently, and architect solutions without making a crippling mess of your code.

Edit: I realize the above comment sounds a little condescending. It wasn't meant to be. I have met self taught programmers that are amazing. Most people just don't have the self discipline to fully learn a subject matter (I many times don't). So a lot of "self taught" programmers have only taught themselves 10% of what they need to know and never bother learning the other 90%.

Re: How to Rock an Algorithms Interview

#68

Post by va_coder »

regs wrote: post #63
va_coder wrote: post #56

Earlier quoted context omitted.

I agree. 2011 Programmer Cost/Benefit reality: 1) The chance my app will be so heavily used that it requires deep knowledge of many algorithms is pretty low. 2) The chance my app has serious marketing or business model problems is pretty high. 3) The extra cost of using a scalable platform (PaaS) like Appengine, Heroku or plain EC2 is less than both the cost of my time to learn or relearn all of those algorithms and…

I think you're correct that for certain types of apps, this sort of knowledge is pretty useless. However, once the number of things you're dealing with gets up to, say, the millions, algorithmic complexity can really bite you in the ass and no matter how much hardware you throw at it (rented or otherwise), if the work that a single node needs to do is unreasonably complex, your whole app will be slow for every user,…

I think you're correct as well.

I'm just saying most paid programmers are not dealing with the problem of how to handle processes that involve millions of users, but they do have problems with marketing their app or monetising it. Therefore spending their weekend learning something like Dijkstra's Algorithm may not be the best use of their time, but finding ways to better understand the needs of their paying users probably would be time well spent.

Re: How to Rock an Algorithms Interview

#69

Post by mcantor »

VladRussian wrote: post #48
alain94040 wrote: post #36

Earlier quoted context omitted.

I'm an engineer. I'll worry about the time my code takes once it's notieably slow. If everything I write runs in a fraction of a second, why would I waste my brain optimizing it to make it faster, when all I'd achieve is introduce tricky bugs. Coding is an engineering discipline: it's all about tradeoffs. Bugs and reliability. Performance. I know to focus on what is important to get a working product.

>I'll worry about the time my code takes once it's notieably slow. the Dunning-Kruger is exactly about ability to notice >If everything I write runs in a fraction of a second, where are different fractions of a second out there. Some are slow, some aren't. One either knows which are which or he doesn't. >why would I waste my brain optimizing it to make it faster, when all I'd achieve is introduce tricky bugs. that is…

>I'll worry about the time my code takes once it's notieably slow.

the Dunning-Kruger is exactly about ability to notice

It seems like you are saying that every programmer ought to go out of his way to become fluent in algorithms, because without fluency he or she will never notice when their code is running slowly.

If so, I disagree. It requires no skill to notice whether code is running slowly--you needn't look further than my techno-skeptical dad muttering, "Jeez, this thing takes forever to boot up" as he regards his desktop with disappointment. I think this is what the grandparent commenter was talking about: if I'm not fluent in algorithms, but my dad doesn't think it's slow, then where's the problem?

"Premature optimization is the root of all evil."

Re: How to Rock an Algorithms Interview

#70

Post by steve8918 »

The interview process at this point, at least in Silicon Valley, is broken.

There's an arms race between interview "gamers" that memorize all the answers to every single question out there, vs interviewers that are asking increasingly ridiculous questions. It's naive to think these days that not knowing the answer to a common question, but coming up with the answer will work. It won't. If 9 candidates know the answer right away, and you don't, but you figure it out, do you honestly think the interviewer will care? I've talked to plenty of interviewers at my company and that's the unwritten rule.

For example, over the phone, one of my friends was asked to design and give an algorithm to solve a maze. It took 10+ mins just to understand exactly what the interviewer wanted, and at that point, time was up, the interviewer was frustrated, and my friend didn't get the job, even though he's better than me, technically.

The only way to interview these days, it to know everything.

Post reply on HN