Abstracting away the specific content about algorithms, these suggestions are helpful for any kind of technical oral exam, e.g. qualifying exams in grad school. The more clearly you can communicate your thought process to your interviewers, the more accurately they can assess your work.
How to Rock an Algorithms Interview
41–50 of 169 posts
Re: How to Rock an Algorithms Interview
#42>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.
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 :)
Re: How to Rock an Algorithms Interview
#43FTA: 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…
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.
Re: How to Rock an Algorithms Interview
#44FTA: 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…
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 contains dense material, but at the same time reading it feels like reading a good fiction book. I first heard of it while reading Steve Yegge's post "get that job at google"[3], bought a copy and, wow, what an amazing book.
[1] http://mitpress.mit.edu/algorithms/ [2] http://www.algorist.com/ [3] http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog...
Re: How to Rock an Algorithms Interview
#45Earlier quoted context omitted.
I didn't do CS as a major in undergrad (I found it too easy... that sound pretentious, but the program at my college simply wasn't difficult enough for me), but I did do a MS in CS afterwards. It helped a lot with basis for algorithms (terminology so you can understand what you are reading), but it didn't really teach me all of the data-structures and algorithms that I know. (There are really too many to cover everyt…
Thank you for the Wikipedia suggestion; I hadn't really considered using it as a learning resource because I've had bad experiences trying that with other fields. (For example, I think Wikipedia is an abhorrent place to learn mathematics, though it clearly functions well as a reference for people who already know what the hell is going on.) Perhaps being already fluent in the fundamental concepts of programming and c…
To be clear, Wikipedia is really just a jumping off point. You can only put so much information on a topic into a Wikipedia article.
You really start learning when you read the references, and have 5 or 6 browser windows open with web searches to things that either interested you and weren't referenced, or to terms that you didn't understand.
>That meshes with my empirical experience that the best way to learn is to "play".
It has actually been shown in educational studies that this is one of the best ways to learn; so social science seems to match up with your experience as well.
Re: How to Rock an Algorithms Interview
#46FTA: 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…
How about the obvious thing, which is to look at the curriculum of undergrad and grad level algorithms courses, pick up some textbooks, and learn it on your own? Flashcards won't help, because it's not a problem of memorization. You need to own the knowledge that lookup in a balanced binary tree is a logarithmic operation.
Re: How to Rock an Algorithms Interview
#47Earlier quoted context omitted.
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…
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 second edition from 2010).
Re: How to Rock an Algorithms Interview
#48Earlier quoted context omitted.
>My main problem is that I don't seem to need this information to do what I do. 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. Maybe I've been lucky. if you don't know the time it really should take, then you just don't know what you have a performance problem. Dunning-Kruger in application to sof…
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 one of the main points where effective implementation knowledge [incl. algorithms] comes to play. Typical "blackmail" in the industry - if performance then 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.
man, you sound like a typical PM when schedule is pressing and the things are started to be pushed out of release, and a pile of slow sh!t is released as result.
Re: How to Rock an Algorithms Interview
#49FTA: 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…
The good thing is that most operations on most data-structures (as well as many of the more common algorithms) don't require solving recurrence equations to determine their asymptotic growth, usually our intuition based on counting tends to be pretty close.
Sketch out your basic data structures on a piece of paper, then just use your finger to trace out how you could do insert, delete, search, etc you can usually tell if something is taking O(lg n), O(n), O(n lg n), etc just by counting the steps you take. After you're comfortable with this, sketch it in your head. You can't forget something that you understand.
The point is that if figuring what out Big O is seems like something you have to memorize to recall quickly, then you very likely don't really understand the underlying data structure/algorithm (and as such you rightfully should do poorly on algorithms interviews). Take the time to make sure you really understand what's going on, and everything else should fall into place.
Re: How to Rock an Algorithms Interview
#50FTA: 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 didn't do CS as a major in undergrad (I found it too easy... that sound pretentious, but the program at my college simply wasn't difficult enough for me), but I did do a MS in CS afterwards. It helped a lot with basis for algorithms (terminology so you can understand what you are reading), but it didn't really teach me all of the data-structures and algorithms that I know. (There are really too many to cover everyt…
I've been doing this exact same thing to learn. I read an interview question that asked how to sort a linked list. I tried implementing it on my own. Later I looked online to see other implementations and compared with my version. I was a little bummed to see my solution wasn't ideal but it only made me dig deeper.
Later on I found some Stanford lectures, particularly Programming Abstractions by Julie Zelenski (around lecture 14). After watching that lecture I was able to classify my linked list sorting attempt as a selection sort. I was pretty excited that I wrote a selection sort without even knowing what kind of sorting I was doing. I have yet to use my newly acquired knowledge at work but I'm now confident I can spot certain sorting algorithms and I'm much more aware of when to use each.
If anyone is aware of any other resources like books, online tutorials or videos I would love to hear about them!