How to Rock an Algorithms Interview • Hacker News Board

Re: How to Rock an Algorithms Interview

#91

Post by strlen » Mon, Sep 26, 2011, 9:44 PM UTC

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 work predominantly with server-side, interpreted languages, and I just don't run into the bottlenecks and performance problems that Big O-knowledge seems to mitigate.

Algorithmic complexity isn't about performance, it's about scalability. A hand-written implementation in assembly that's O(N^2) will be slower than an implementation in Basic that's O(N) (or even O(N log N)) for a sufficiently large N.

I suggest picking up Programming Pearls, they had an example of a BASIC program on C64 vs. a Fortran program on a mainframe (the book is from the 80s) demonstrating this.

That said, if building basics web apps is all you want to do (e.g., internal enterprise applications) then you don't need this knowledge. However, the harder stuff (whether algorithmic, systems, etc...) like (but not limited to) what Palantir works is what I find more interesting.

Re: How to Rock an Algorithms Interview

#92

Post by mcantor » Mon, Sep 26, 2011, 9:53 PM UTC

pavelludiq wrote: post #85

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'll give you my point of view. I'm young(21), I'm in my third year as an informatics student, and I feel greatly intimidated by all these hard stuff. I can barely write a working web app, even with all the hand-holding modern frameworks give me. I don't consider myself smart(i'm bright enough to be a programmer, but nothing more). Recently I sat down and thought about where I want to be in 5-10 years. I don't want t…

Thank you for such a candid post! I know how you feel.

I'm only a little farther along in my journey than you; at 26, I finally feel confident in my abilities, but am still humbled by how much I don't know. Last month I spent hours poring over Linux network programming resources so I could implement a performant, scalable, thread-safe game server [1]. After weeks, I finally got it working--replete with tests, sane coding practices and other Good Things--and it felt so good.

Like you said: "All hard stuff that I'll never need to know in order to build a web store site..." I didn't need to reinvent the wheel--there are tons of pre-existing solutions and frameworks out there that I could pick up and use to hit the ground running. But, like most people on this site, you and I were bit by the same bug: the desire to understand how and why it works.

For me, the hard part isn't dedication to learning or writing dime-a-dozen web apps to pay the bills. The hard part is finding the right balance. I think that's probably something I'll keep learning more about until I finally kick the bucket.

If I can presumptuously offer advice, from barely a half-decade down the line: Don't give up, and learn to see the intimidation for what it is: thrill! Do as the sagacious Derek Sivers commands: whatever scares you or excites you, go do it [2]. If you come upon something that seems insurmountably complex; it could be anything: compilers, emulators, algorithms, low-level network programming... do it. You don't have to learn it in a day, a month, or even a decade, but never fool yourself into believing that it's too hard. It isn't. Take breaks to keep yourself sharp, but never give up.

[1] - http://stackoverflow.com/questions/6849239/how-should-i-arch...

[2] - http://sivers.org/scares-excites-do-it

Re: How to Rock an Algorithms Interview

#93

Post by mcantor » Mon, Sep 26, 2011, 10:03 PM UTC

VladRussian wrote: post #86

mcantor wrote: post #69

Earlier quoted context omitted.

>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 fur…

>"Jeez, this thing takes forever to boot up" this "forever" consists of myriad of "a fraction of a second"-s, with each fraction individually not being "notieably slow" and thus not "prematurely optimized". And if not optimized "prematurely" (ie. written efficiently from the start), then after-the-fact optimization, if happens at all, would shave only a fraction out of the "forever" - thus it frequently doesn't happe…

> And if not optimized "prematurely" (ie. written efficiently from the start), then after-the-fact optimization, if happens at all, would shave only a fraction out of the "forever" - thus it frequently doesn't happen at all because of such low projected ROI.

My personal experience completely contradicts what you're saying.

Despite the cushy comforts of server-side scripting languages, I have experienced the occasional performance or scalability problem, and in every single case, I wrote inefficient code on the first pass, discovered unacceptable slowness at a later date, then found the bottleneck and optimized it.

Perhaps I am a brilliant super-coder (unlikely), but I have never ignored a performance problem because I didn't think I could improve it enough to be worth the effort.

Re: How to Rock an Algorithms Interview

#94

Post by scott_s » Mon, Sep 26, 2011, 10:04 PM UTC

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…

Rather, I think his point aligned with points Jonathan Blow makes in this presentation: http://the-witness.net/news/2011/06/how-to-program-independe...

One of his points - with which he uses an id game as an example - is that sometimes the naive implementation is the best implementation. His example has to do with loading levels at startup. The written code was, from an algorithmic perspective, inefficient. It was written in such a way to optimize for developer time. His point was that in this circumstance, that was the correct thing to do because this was not a performance critical part of the code, and naive implementations are easier to maintain.

Re: How to Rock an Algorithms Interview

#95

Post by groby_b » Mon, Sep 26, 2011, 10:14 PM UTC

mcantor wrote: post #80

jchonphoenix wrote: post #67

Earlier quoted context omitted.

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, howe…

I upvoted you for the good explanation (and the refreshingly self-aware edit). However, I think it is rather presumptuous to paint the broad strokes of "good" and "bad" without adding so many caveats that it would no longer be germane to this conversation. By your definition, I am currently a "bad programmer" because I do not have fluency in algorithms. (I will leave the objective truth of this statement as an exerci…

Based on 20 years of experience, lack of fluency in algorithms _is_ a surefire indicator of bad architecture skills. Yes, it gives a few false positives, but the amount of false negatives is pretty much 0.

And since actually getting a new person on-board is an expensive process, you aim for criteria that are a bit too stringent, if you can afford it.

There's also the issue that making a bad algorithmic decision at the center of the problem turns scaling into an insanely hard problem, sometimes. It's not so much about learning about it when you need it, but about avoiding issues in the first place.

True, there are many places where it truly doesn't matter - but if scaling/performance matter for your company, you don't want to head down the garden path because your developers didn't know better.

Not knowing algorithms won't exclude you from all jobs (or even many of them), but there are some jobs where it _will_ bite you. It's your choice if you want to go for those jobs. Personally, I think they are where the cool stuff is happening, but YMMV.

Re: How to Rock an Algorithms Interview

#96

Post by prodigal_erik » Mon, Sep 26, 2011, 10:16 PM UTC

mcantor wrote: post #80

jchonphoenix wrote: post #67

Earlier quoted context omitted.

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, howe…

I upvoted you for the good explanation (and the refreshingly self-aware edit). However, I think it is rather presumptuous to paint the broad strokes of "good" and "bad" without adding so many caveats that it would no longer be germane to this conversation. By your definition, I am currently a "bad programmer" because I do not have fluency in algorithms. (I will leave the objective truth of this statement as an exerci…

The thing is, it's very easy to end up using a bad algorithm without noticing. If you're doing a linear search over a collection of n elements, fine, but if you end up having to do it n-ish times, suddenly you're up to O(n^2), and if n is ever a few million in reality, your app will enter a loop that's practically infinite. Meanwhile, sorting them would be O(n log2 n) and intersecting two sorted lists is O(n), and n hash table searches is only O(n) if you have enough memory to avoid collisions.

Re: How to Rock an Algorithms Interview

#97

Post by HardyLeung » Mon, Sep 26, 2011, 10:25 PM UTC

groby_b wrote: post #95

mcantor wrote: post #80

Earlier quoted context omitted.

I upvoted you for the good explanation (and the refreshingly self-aware edit). However, I think it is rather presumptuous to paint the broad strokes of "good" and "bad" without adding so many caveats that it would no longer be germane to this conversation. By your definition, I am currently a "bad programmer" because I do not have fluency in algorithms. (I will leave the objective truth of this statement as an exerci…

Based on 20 years of experience, lack of fluency in algorithms _is_ a surefire indicator of bad architecture skills. Yes, it gives a few false positives, but the amount of false negatives is pretty much 0. And since actually getting a new person on-board is an expensive process, you aim for criteria that are a bit too stringent, if you can afford it. There's also the issue that making a bad algorithmic decision at th…

I agree with jchonphoenix and groby_b. I'm sure there are a lot of great self-taught genius who don't have the formal training but does a much better job than most, but there are orders of magnitude more in the camp of "half-taught" mediocre programmers, with shiny formal training, that can easily be filtered out using this approach.

Re: How to Rock an Algorithms Interview

#98

Post by MattGrommes » Mon, Sep 26, 2011, 10:25 PM UTC

If you're struggling with algorithms I'd suggest reading the book Programming Pearls (2nd edition). It's a little dated but not enough to matter too much. The big thing it helps with is what I think of as "algorithmic thinking". The various chapters go through different approaches to solving problems and help you get a handle on why a particular approach might be O(n^2) versus O(logn) and why that's important. It's very helpful stuff.

Re: How to Rock an Algorithms Interview

#99

Post by sampsonjs » Mon, Sep 26, 2011, 10:27 PM UTC

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…

Just read the lecture notes for a CS course that covers this already. It will almost always be a course that also covers the sorting algorithms and basic data structures(what is a linked list, tree, graph, etc.) It won't take that long. As for coming up with the Big-O omplexity for a routine on the spot, most job interveiws will throw something at you where it should be intuitive if you know the canonical algorithms. I have yet to read about someone having to solve a recurrence relation on the spot(everyone's already forgotten the cook book approach they learned in school, if they ever learned it at all). It's not a lot to remember, so no big deal if the only thing you use if for is to impress someone. If you want true "Who gives a shit?" material from academia, try Automata Theory, or whatever the course where you learn about the pumping lemma is called. Never read about that coming up in an interview.

Re: How to Rock an Algorithms Interview

#100

Post by pjscott » Mon, Sep 26, 2011, 10:31 PM UTC

pavelludiq wrote: post #85

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'll give you my point of view. I'm young(21), I'm in my third year as an informatics student, and I feel greatly intimidated by all these hard stuff. I can barely write a working web app, even with all the hand-holding modern frameworks give me. I don't consider myself smart(i'm bright enough to be a programmer, but nothing more). Recently I sat down and thought about where I want to be in 5-10 years. I don't want t…

Such moments of clarity are rare and brief, but to a surprising extent they define our lives. I would bet on your success.

Back on topic: it's actually pretty easy to intuitively estimate the asymptotic time performance of most data structures if you sit down with a good algorithms book for a while and read through until you understand it. If you don't find everything simple the first time, go back to the beginning a few days later and read it again. This will give you big-O-estimation skills for things that aren't mentioned in the book, plus thorough understanding of the things that are mentioned.

I prefer Robert Sedgewick's Algorithms books, because the pictures are amazingly useful and abundant, but there are other good options. After a while it just starts to make sense.