Yes, that is true. Memorization doesn't necessarily mean rote memorization - for me at least, the algorithms are too complex to memorize by rote, I have to understand them to "memorize them". But yeah, if you are able to implement certain data structures and algorithms "in your sleep", then this does imply, as you said, a kind of memorization.
I didn't get past the technical interview at google or amazon, so you might want to take advice from someone else, but here's what I think I'd need to pass the algorithm section of the technical entrance exam at google.
You must be able to do the following in about 5 minutes or less at a whiteboard with no errors:
1) print all permutations of a set
2) build and print a binary tree (preorder, postorder).
3) create a hashing function
4) quicksort and mergesort
(I'm leaving out linked lists, arrays, stacks and so forth because you won't be able to do 2 or 3 without them anyway).
The reason you need to memorize these (yes, I'll go ahead and use your word now, I agree with you that this is memorization) is that you can't be dealing with how to implement these if you're going to do enough in 45 minutes to pass the exam. I think that these three things form the foundation for most variants on recursion, sorting, traversal, combinatorics, and so forth.
Next, you need to be able to identify when something is a variant of these algorithms and solve it very quickly at the whiteboard. "Cracking the coding interview" is good practice for this, but in this case, I don't think "memorizing" these questions and answers would be especially helpful, because you're unlikely to get that exact question.
Here are a few of questions I've invented on the spot (not from my interview, not from cracking the coding interview) that you'd probably want to get close to solving in 45 minutes or so. In other words, if a buddy wanted to apply to a top tech company and asked me to give him some practice, I'd give him 45 minutes at a whiteboard for each of the following questions.
"In a binary tree with positive and negative integers, find and print all paths with a positive sum. Now assume the tree is ordered, and make your code more efficient."
"In an nxm matrix, find all sub square matrices with a positive determinant."
This might just be me, but I was kind of struck with just how much progress and accuracy you are expected to achieve at the whiteboard. And like I said, I am kind of blown away that people are able to do this. While I can pose those questions and develop a mental model for how to approach it, I just couldn't solve them at a whiteboard in 45 minutes to anything approaching what I believe is the standard.
Again, whether this is a good way to filter people out isn't something I'm discussing here, this is just my advice if you are planning to apply and want to be prepped. Also, there will be more than just data structures and algorithms on the exam.
> This might just be me, but I was kind of struck with just how much progress and accuracy you are expected to achieve at the whiteboard. And like I said, I am kind of blown away that people are able to do this. While I can pose those questions and develop a mental model for how to approach it, I just couldn't solve them at a whiteboard in 45 minutes to anything approaching what I believe is the standard.
That is why I stress its memorization because without memorizing things you've long since abstracted to libraries, you really can't perform in the stressful interview situation to the level the interviewer expects.
If, however, you take something the interviewee implemented in the past 6 months as the "standard problem" they could probably do it without much trouble.
I didn't get past the technical interview at google or amazon, so you might want to take advice from someone else, but here's what I think I'd need to pass the algorithm section of the technical entrance exam at google.
You must be able to do the following in about 5 minutes or less at a whiteboard with no errors:
1) print all permutations of a set 2) build and print a binary tree (preorder, postorder). 3) create a hashing function 4) quicksort and mergesort
(I'm leaving out linked lists, arrays, stacks and so forth because you won't be able to do 2 or 3 without them anyway).
The reason you need to memorize these (yes, I'll go ahead and use your word now, I agree with you that this is memorization) is that you can't be dealing with how to implement these if you're going to do enough in 45 minutes to pass the exam. I think that these three things form the foundation for most variants on recursion, sorting, traversal, combinatorics, and so forth.
Next, you need to be able to identify when something is a variant of these algorithms and solve it very quickly at the whiteboard. "Cracking the coding interview" is good practice for this, but in this case, I don't think "memorizing" these questions and answers would be especially helpful, because you're unlikely to get that exact question.
Here are a few of questions I've invented on the spot (not from my interview, not from cracking the coding interview) that you'd probably want to get close to solving in 45 minutes or so. In other words, if a buddy wanted to apply to a top tech company and asked me to give him some practice, I'd give him 45 minutes at a whiteboard for each of the following questions.
"In a binary tree with positive and negative integers, find and print all paths with a positive sum. Now assume the tree is ordered, and make your code more efficient."
"In an nxm matrix, find all sub square matrices with a positive determinant."
This might just be me, but I was kind of struck with just how much progress and accuracy you are expected to achieve at the whiteboard. And like I said, I am kind of blown away that people are able to do this. While I can pose those questions and develop a mental model for how to approach it, I just couldn't solve them at a whiteboard in 45 minutes to anything approaching what I believe is the standard.
Again, whether this is a good way to filter people out isn't something I'm discussing here, this is just my advice if you are planning to apply and want to be prepped. Also, there will be more than just data structures and algorithms on the exam.