So first I'd google and use someone else's implementation.
February 16, 2011 6:36 PM Subscribe
I have an interview that includes an algorithm test with a financial services firm. This is for a "Senior Developer" type of position. Perusing through GlassDoor's interview questions for a lot of firms (Amazon.com in particular) has me nervous. What's the best way to prepare for this? I've been out of school for awhile and never use the language "breadth-first search" or "find the intersection of a linked list" in my day-to-day life.
I picked up "Introduction to Algorithms" and Donald Knuth's Art of Programming series to brush up. I was a bit foolish, as these aren't the type of texts you just brush up with. I'm confident I'd be able to pass any sort of FizzBuzz test, but a lot of data structures are already implemented in the language frameworks I use, so it is not like I'm ever finding myself implementing a hash table from scratch.
I thought that going through Project Euler would jog my brain, but I'm finding that a lot of these interview questions are rather CS centric and involve search through trees and graphs, etc.
Compound with this that I haven't interviewed in almost a decade (I've had the fortunate luck of positions being offered to me without formal interviews).
So someone that's been through a lot of these, will simply going through GlassDoor's brain dumps get me to where I need to be? Again, my firm isn't listed but there's a lot of other firms are.
Also, I've contributed to quite a few open source projects of high notoriety. I've aggressively highlighted this on my resume. If I bomb and can only talk my way through an algorithm test, will having a strong record of submitting good code alleviate this?
Working in a high level language (Java & C#) with strong supporting frameworks have turned my brain into a lazy mush. Any advice would be great.
I picked up "Introduction to Algorithms" and Donald Knuth's Art of Programming series to brush up. I was a bit foolish, as these aren't the type of texts you just brush up with. I'm confident I'd be able to pass any sort of FizzBuzz test, but a lot of data structures are already implemented in the language frameworks I use, so it is not like I'm ever finding myself implementing a hash table from scratch.
I thought that going through Project Euler would jog my brain, but I'm finding that a lot of these interview questions are rather CS centric and involve search through trees and graphs, etc.
Compound with this that I haven't interviewed in almost a decade (I've had the fortunate luck of positions being offered to me without formal interviews).
So someone that's been through a lot of these, will simply going through GlassDoor's brain dumps get me to where I need to be? Again, my firm isn't listed but there's a lot of other firms are.
Also, I've contributed to quite a few open source projects of high notoriety. I've aggressively highlighted this on my resume. If I bomb and can only talk my way through an algorithm test, will having a strong record of submitting good code alleviate this?
Working in a high level language (Java & C#) with strong supporting frameworks have turned my brain into a lazy mush. Any advice would be great.
I've gone through quite a few interviews like this during the past few years. I think I've improved my interviewing skills dramatically by NOT trying to cram in a review of my entire CS degree's coursework, but trying to nail the basics of data structures and algo runtime.
A lot of it can come down to understanding data structures, and knowing O(n) runtimes of various algorithms, including those core algorithms that allow your favorite data structures to exist. You should be able to get a rough estimate of any new algorithm's runtime once it's been described to you.
I've had a few interviews in which unusual (to ME, anyhow) data structures have been described to me, and I've been able to figure out their strengths and weaknesses just by imagining how their various methods are implemented and determining runtime.
Know at least one or two sorting algorithms by heart. Understand their runtimes in best-, worst- and average-case scenarios.
Know how much space (in bytes) various solutions require. On disk and in memory.
YMMV, but I seem to get a lot of mileage out of giving answers that I know will work but are inefficient, and then IMMEDIATELY explaining the inefficiency and proposing a modification. For instance, a lot of interviewers love to ask you to write the algorithm for determining the Nth number in the Fibonacci sequence. The most obvious solution to most people involves recursion, but it can actually be done quite cleanly with a simple loop, and won't blow up the stack for large values of N.
Umm... what else? Talk out loud. A lot. Practice talking your way through problems with friends or colleagues, or just ranting to your dog... whatever. This is not the time for classic nerdish introspection, even if that's how you typically work at your desk. This isn't a formal exam where you have twenty minutes to write an answer on a piece of paper. Treat it as a conversation. Describe assumptions that you're making, even if they're wrong. If you're going off course and you're being vocal about it, the person conducting the interview has a chance to jump in and put you back on course. If you sit there staring at an empty whiteboard, you're sunk.
If the specifics of a problem are giving you trouble, try to rewrite the problem in terms of something you do know. For example, I've been given questions which start out with "Assume we have the following data in a MySQL database...". At the time, MySQL was not my strong suit, and I was tempted to waste precious time thinking about MySQL specifics instead of the problem at hand. I said "First, let me explain how I'd solve the problem if the data was in flat CSV files...". Solved the problem that way, and then addressed the MySQL specifics after I had the problem solved in the more general sense.
I hope my rambling helps you. Good luck!
posted by adamk at 7:13 PM on February 16, 2011 [6 favorites]
A lot of it can come down to understanding data structures, and knowing O(n) runtimes of various algorithms, including those core algorithms that allow your favorite data structures to exist. You should be able to get a rough estimate of any new algorithm's runtime once it's been described to you.
I've had a few interviews in which unusual (to ME, anyhow) data structures have been described to me, and I've been able to figure out their strengths and weaknesses just by imagining how their various methods are implemented and determining runtime.
Know at least one or two sorting algorithms by heart. Understand their runtimes in best-, worst- and average-case scenarios.
Know how much space (in bytes) various solutions require. On disk and in memory.
YMMV, but I seem to get a lot of mileage out of giving answers that I know will work but are inefficient, and then IMMEDIATELY explaining the inefficiency and proposing a modification. For instance, a lot of interviewers love to ask you to write the algorithm for determining the Nth number in the Fibonacci sequence. The most obvious solution to most people involves recursion, but it can actually be done quite cleanly with a simple loop, and won't blow up the stack for large values of N.
Umm... what else? Talk out loud. A lot. Practice talking your way through problems with friends or colleagues, or just ranting to your dog... whatever. This is not the time for classic nerdish introspection, even if that's how you typically work at your desk. This isn't a formal exam where you have twenty minutes to write an answer on a piece of paper. Treat it as a conversation. Describe assumptions that you're making, even if they're wrong. If you're going off course and you're being vocal about it, the person conducting the interview has a chance to jump in and put you back on course. If you sit there staring at an empty whiteboard, you're sunk.
If the specifics of a problem are giving you trouble, try to rewrite the problem in terms of something you do know. For example, I've been given questions which start out with "Assume we have the following data in a MySQL database...". At the time, MySQL was not my strong suit, and I was tempted to waste precious time thinking about MySQL specifics instead of the problem at hand. I said "First, let me explain how I'd solve the problem if the data was in flat CSV files...". Solved the problem that way, and then addressed the MySQL specifics after I had the problem solved in the more general sense.
I hope my rambling helps you. Good luck!
posted by adamk at 7:13 PM on February 16, 2011 [6 favorites]
If you have a lot of good experience on your resume we'll be excited to bring you in and interview you. When you get here, we'll stick you in a room with a whiteboard, and send a series of interviewers to ask you questions. They will do things like "design a JSON library in C++" and expect you to come up with a reasonable class hierarchy for an object-oriented design. If you come up with some other solution, they'll try to steer you toward the one they wanted. If you can't come up with it *at all*, even after much prodding, it will not look good. We aren't particularly interested if you can remember the names of specific API calls, but we might want you to be able to tell us why you might use an STL list vs a vector.
Writing the code isn't really the hard part, designing solutions is. If we throw out a problem like "assume you have two separate threads that both need to access the same data without corrupting it" We want you to be able to say "I'd use a mutex and let each thread wait to lock it". Then we'd ask you something about deadlocks.
We also might ask you to do some sort of construction of a network service with standard unix APIs. We won't really care if you accidentally call 'recv()' 'read()' instead, but we will expect you to know that you can read data off the socket. Similarly, if we ask how you might read from several sockets at once, we're going to want you to mention 'select()' or 'poll()'. If you answer with threads or 'fork()', that's not a good sign. We'll ask you why you chose that and see if you can think of another solution, possibly by saying "What if you want to handle 5000 connections at once?"
So I don't know what you want exactly. People want you to be able to solve problems, and to know why the solutions you propose would work. If you answer some question with "i'd use a hashtable", expect a follow-up with something like "what are the properties of a hashtable that made you choose it?" (especially if your answer was less than ideal). We're probably not going to ask you to come up with a good string hashing algorithm, or even ask how many buckets are in your hash, or how you'll resolve collisions, but we might want you to at least know that these things exist and what sort of overhead or advantages they come with.
I don't work at a financial firm, but we hire people to write software all the same.
posted by tylerkaraszewski at 8:16 PM on February 16, 2011
Writing the code isn't really the hard part, designing solutions is. If we throw out a problem like "assume you have two separate threads that both need to access the same data without corrupting it" We want you to be able to say "I'd use a mutex and let each thread wait to lock it". Then we'd ask you something about deadlocks.
We also might ask you to do some sort of construction of a network service with standard unix APIs. We won't really care if you accidentally call 'recv()' 'read()' instead, but we will expect you to know that you can read data off the socket. Similarly, if we ask how you might read from several sockets at once, we're going to want you to mention 'select()' or 'poll()'. If you answer with threads or 'fork()', that's not a good sign. We'll ask you why you chose that and see if you can think of another solution, possibly by saying "What if you want to handle 5000 connections at once?"
So I don't know what you want exactly. People want you to be able to solve problems, and to know why the solutions you propose would work. If you answer some question with "i'd use a hashtable", expect a follow-up with something like "what are the properties of a hashtable that made you choose it?" (especially if your answer was less than ideal). We're probably not going to ask you to come up with a good string hashing algorithm, or even ask how many buckets are in your hash, or how you'll resolve collisions, but we might want you to at least know that these things exist and what sort of overhead or advantages they come with.
I don't work at a financial firm, but we hire people to write software all the same.
posted by tylerkaraszewski at 8:16 PM on February 16, 2011
Specific questions and more general study tips from Yegge based on his experience interviewing candidates for, among others, Google and Amazon.
posted by d. z. wang at 10:15 PM on February 16, 2011 [1 favorite]
posted by d. z. wang at 10:15 PM on February 16, 2011 [1 favorite]
It is no substitute for a real, working knowledge of algorithms, but if you want a book that is oriented towards rigorous but practical "brushing up", I highly recommend The Algorithm Design Manual. It is perhaps the best book I've ever read on algorithms. Don't expect miracles, but any time you can spend with this (nontrivially-sized) volume would probably help immensely.
Prioritizing your studying, I would focus on:
- Basic data structures: linked lists, trees, hash tables.
- Sorting: be sure that you can explain to yourself how (at least) quicksort, mergesort and bubble sort work. You will need the latter to contrast a good vs. bad sort
- All kinds of graph algorithms. The number of problems that can be generalized to graphs is astounding (and, as a bonus, mentioning graphs make you seem 10 times smarter). Understand basic graph traversals, shortest path finding, minimum spanning trees, cycle detection. If you have time, dive into bipartite matching type of problems.
- Shore up on basic operating system concepts, if you don't deal with those much normally. Think about different concurrency primitives: locks, mutexes, semaphores. At your level of experience, things like memory allocation (stack, heap, garbage collection behaviors) should be a given. As is explaining the difference between threads and processes.
Finally, not algorithm related, but I would make sure you remember (and understand) as many numbers from http://surana.wordpress.com/2009/01/01/numbers-everyone-should-know/ as you can. They can sure come in useful...
Good luck!
posted by blindcarboncopy at 10:41 PM on February 16, 2011 [2 favorites]
Prioritizing your studying, I would focus on:
- Basic data structures: linked lists, trees, hash tables.
- Sorting: be sure that you can explain to yourself how (at least) quicksort, mergesort and bubble sort work. You will need the latter to contrast a good vs. bad sort
- All kinds of graph algorithms. The number of problems that can be generalized to graphs is astounding (and, as a bonus, mentioning graphs make you seem 10 times smarter). Understand basic graph traversals, shortest path finding, minimum spanning trees, cycle detection. If you have time, dive into bipartite matching type of problems.
- Shore up on basic operating system concepts, if you don't deal with those much normally. Think about different concurrency primitives: locks, mutexes, semaphores. At your level of experience, things like memory allocation (stack, heap, garbage collection behaviors) should be a given. As is explaining the difference between threads and processes.
Finally, not algorithm related, but I would make sure you remember (and understand) as many numbers from http://surana.wordpress.com/2009/01/01/numbers-everyone-should-know/ as you can. They can sure come in useful...
Good luck!
posted by blindcarboncopy at 10:41 PM on February 16, 2011 [2 favorites]
When I do technical interviews I ask questions for which I have ulterior motives. I want to assess critical thought, communication, problem-solving, and passion. Our prescreen weeds out those who can't code their way out of a paper bag. You give me someone who can do that and if I get a good sense of those 4 things, then I know I have someone who can learn to do what we need. If we have to have specific problem domain knowledge, that's another beast.
So I make it clear to my candidates that we're not playing a trivia game here. I ask my candidates to ask me specific questions and I'll either answer or we'll agree on an answer/convention. I don't care that a candidate knows or doesn't know all the format options in printf. I do care that a candidate would understand how printf works and why and what's both great and wrong with it.
So why am I telling you this? I'm telling you because the people you're interviewing with may not be as methodical as I am when I interview. So you should talk a lot. You should at least mentally question the motives of any request. You can also question them out loud, especially if you don't know the answer. "If you're trying to find out if I know how to implement shell sort off the top of my head, I can't, but if you want to me to contrast it with quick sort..."
Sometimes when I interview, after a subjective question, I will ask the metaquestion, "why do you think I asked that question?" to see if the candidate is thinking in those terms.
Also don't ever assume the inputs to any function. Ask about expected values. Always. This lets you do things like deciding if memoization of the function makes sense (ie, table driven results), which very often can put a slow function into the realm of O(1) at runtime.
posted by plinth at 9:05 AM on February 17, 2011
So I make it clear to my candidates that we're not playing a trivia game here. I ask my candidates to ask me specific questions and I'll either answer or we'll agree on an answer/convention. I don't care that a candidate knows or doesn't know all the format options in printf. I do care that a candidate would understand how printf works and why and what's both great and wrong with it.
So why am I telling you this? I'm telling you because the people you're interviewing with may not be as methodical as I am when I interview. So you should talk a lot. You should at least mentally question the motives of any request. You can also question them out loud, especially if you don't know the answer. "If you're trying to find out if I know how to implement shell sort off the top of my head, I can't, but if you want to me to contrast it with quick sort..."
Sometimes when I interview, after a subjective question, I will ask the metaquestion, "why do you think I asked that question?" to see if the candidate is thinking in those terms.
Also don't ever assume the inputs to any function. Ask about expected values. Always. This lets you do things like deciding if memoization of the function makes sense (ie, table driven results), which very often can put a slow function into the realm of O(1) at runtime.
posted by plinth at 9:05 AM on February 17, 2011
This thread is closed to new comments.
posted by phunniemee at 7:02 PM on February 16, 2011