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

51–60 of 169 posts

Re: How to Rock an Algorithms Interview

#51

Post by rcfox »

mcantor wrote: post #43
rcfox wrote: post #39

Earlier quoted context omitted.

There aren't too many things to remember in order to be useful: - Operations that take the same amount of time regardless of the input are O(1). ie: 1+1 takes just as long as 10000+10000 (okay, not really, but it's a reasonable assumption.) - Doing a small sequence of operations runs in O(maximum of all operations). Doing 5 adds (which are O(1)) runs in O(1). Doing an O(n) operation followed by an O(k) (where k > n)…

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 total time is O(klog(n))

Now, if you wanted to do this for m trees:

    for(int j = 0; j
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.

Re: How to Rock an Algorithms Interview

#52

Post by rhizome »

MattLaroche wrote: post #6

Disclaimer: I work at Palantir Technologies. These are my own opinions and not my company's. The Palantir post is great for how to handle yourself when you are already there. Steve Yegge's "Get That Job at Google" is a great how-to-really-prepare piece. http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog... A couple other suggestions: * Find sample questions that similar companies use. Work through them. Dis…

You mean the anti-Wikileaks Palantir?

Re: How to Rock an Algorithms Interview

#53

Post by tikhonj »

mcantor wrote: post #30
tikhonj wrote: post #25

Earlier quoted context omitted.

What I've found is that I do not remember that, say, a tree map or heap have logarithmic insertion time, but rather have a vague mapping of general concepts to behavior: something like "tree" => logarithms, "list" => lines (linear), "array" => magic (constant). Then I think something like "a hashmap is like an array, so it can be accessed in constant time". If you're a visual thinker, the "shape" of an algorithm or d…

Thank you, this is a great answer that confirmed some of my suspicions. I'd be interested if anyone could recommend other good resources such as Project Euler. Perhaps the book Data Structures and Algorithms ought to be higher up on my reading list? I would feel a lot more enthusiastic about getting a copy and diving into it if someone with the context of my OP question could confirm that it's a relevant resource.

I haven't read Data Structures and Algorithms, but I can point you to a draft of the book for my current Algorithms class, creatively called Algorithms[1]. I think content-wise the draft is almost identical to the published versions; the main differences are in the exercises.

[1]: http://www.cs.berkeley.edu/~vazirani/algorithms.html

It's fairly in-depth but narrative in style and readable; I rather like it. One particularly nice touch is that it goes over the practical applications of the various algorithms at a high level, giving you a good idea of where they are used and why.

If you do not do much math and do not remember Linear Algebra/Discrete Mathematics, it might be best to skip the first couple of chapters and look at graphs first instead. That said, the first two chapters cover some math which is probably good to know.

The book is primarily about algorithms. It touches on data structures where needed to implement or describe an algorithm, but not much more besides (at least in the parts I've gotten through so far). I have not read any good data structures book, but have found Wikipedia to be a very good resource. I suggest avoiding overly language-specific books on the matter--I think that Java books in particular are insidious, but I am little biased in that regard.

The best approach would probably be to read through a section about some algorithm, look at what sorts of problems it can solve and then write a simple program to solve those problems. For example, when reading about path-finding algorithms, you could write a simple navigation program. I find this helps keep the material interesting and also aids retention.

Additionally, I have heard good things about Introduction to Algorithms[2] (another creative name)--it was suggested as a reference for the course, although I did not get it (Wikipedia is good enough for me).

[2]: http://en.wikipedia.org/wiki/Introduction_to_Algorithms

Re: How to Rock an Algorithms Interview

#54

Post by tikhonj »

adbge wrote: post #37
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…

Related: What books or other resources would HNers recommend for someone with limited algorithm and data structure experience who wants to beef up via self-study? I'm specifically interested in books/other resources that lend themselves to self-study. It's easy enough to look up what MIT is using for their Intro to Algorithms course, but it's harder to gauge if a book or other resource is suitable for usage outside o…

Another good option is Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. A draft is available at http://www.cs.berkeley.edu/~vazirani/algorithms.html.

I find this book readable and interesting; it does tie the algorithms to practical applications at a high level. It is language-agnostic, so it should be a good fit for almost anybody.

Re: How to Rock an Algorithms Interview

#55

Post by tom_b »

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…

For a significant number of gigs, you don't need to know algorithms and data structures. This continues to surprise me.

I think for interviewers, this approach to quizzing on algorithms and data structures is probably just a well-known practice and probably lacks correlation with the work of a specific job role most of the time.

If you aspire to work somewhere that has a demand for deeper algorithmic work, you do need to understand algorithms and data structures. I think this is probably a smaller number of potential jobs than many of us on HN would like to admit - there is simply a large number of mundane IT/dev jobs where the naive imperative solution will be just fine.

I would skip flash cards, but try to find small projects at work that require algorithmic and data structure thinking. Then you get some applied experience that will "tell a good story" at an interview plus build your analysis skills.

I think for a lot of jobs, even being able to talk about an algorithm and data structure design that you personally did will put you way out in front of a number of candidates.

Re: How to Rock an Algorithms Interview

#56

Post by va_coder »

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 the cost of setting up my own scalable platform.

I see far more business model/marketing problems than scalability/performance ones.

Re: How to Rock an Algorithms Interview

#57

Post by eric-hu »

dr_rezzy wrote: post #18

For me, this blog post represents a step backwards. They open up saying that the 1 hour interview provides absolutely no indication of how well a prospective candidate will perform. Hopefully most people will agree here. Then they go ahead and state that their staple interview will be an on the spot problem solving screening and then list the steps the expect the candidate to take in solving said problem. What does t…

That does seem to be an interview technique used at some companies. It comes with its own set of problems, though.

What if someone asks a friend for help or pays someone to solve the problem in its entirety? If your problems aren't unique enough, they could also google the answers.

With that said, I actually prefer your approach. Its pitfalls have to be weighed carefully; hiring someone who knew enough to fake it could be a costly setback for a small company. However, it does remove some unnecessary pressure from the interview process.

Re: How to Rock an Algorithms Interview

#58

Post by eru »

geoffschmidt wrote: post #42
praptak wrote: post #23

Earlier quoted context omitted.

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

I'm willing to believe that the ideal candidate is a fixed point under your operator, but I think it's going to be tricky to prove convergence :)

And there might be other fixed points, perhaps with even greater catchment areas.

Re: How to Rock an Algorithms Interview

#60

Post by reginaldo »

mcantor wrote: post #47
reginaldo wrote: post #44

Earlier quoted context omitted.

The standard reference (in the "That's what MIT uses" sense) is Introduction to Algorithms[1], as you probably know. It is a wonderful book and I have a copy that is wearing of because I use it so much. As for "outside of a classroom setting", the best book I can recommend is "The Algorithm Design Manual" [2]. It is worth its weight in gold. Very user friendly, as I never though an algorithms book could be. It contai…

For anyone trying to buy "The Algorithm Design Manual" (or at least add it to their Amazon wish-list with a dreamy sigh), It seems like the "correct" version is here: http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/... I was a bit flummoxed at first because algorist.com doesn't tell you how to buy the thing, and the Kindle edition appears to be out of date (based on the first edition, obsoleted by the sec…

Sorry about that.

I should have linked to the Amazon page in the first place (who am I kidding?). You linked to the correct version.

Post reply on HN