I was also told that it is usually the guys that come fresh out of varsity that nail interviews because data structures and the rest are still fresh in their mind compared to some guys that have been developing in the industry for years, like at banks where there isn't really any growth.
I would say that is partially true. If someone goes into a job after they graduate that uses no CS, and they don’t study anything externally to compensate, then it will decay over time, and it will be harder for them to pass the interview. They may still get a job, but it would be for a team that does not require the same level of CS background.
If, however, the job that they do do, involves a fair amount of CS, engineering, and careful software engineering practices, this too will be evident in their answers and will also put them in line for a more senior position.
E.g., I don’t currently have Quick-Sort memorized, but just knowing that it involves selecting a pivot and moving data to either side means that I could:
1) Derive it on a board and cover all edge cases.
2) Observe that it is
a divide and conquer style algorithm.
3) Observe they it is a
randomized algorithm with O(nlogn)
expected complexity, and O(n^2) worst case complexity.
4) Observe that it is in-place.
5) Observe that it can be stable.
6) Observe that it would typically be faster than O(nlogn) worst case in place algorithms such as heap sort because it has coherent memory access patterns.
7) Suggest a strategy to parallelise it.
8) Suggest a strategy to implement it on an FPGA.
9) Suggest a strategy to implement it on a GPU, or parallel CPU.
10) Suggest better algorithms for 7-9 that are more suited for the type of hardware (eg sorting networks, or Bitonic sorting)
11) Suggest hybrid algorithms (when the memory footprint is small enough due to the division a heap sort of insertion sort may be better for the lower nodes). Small sorts can be written as a SIMD sorting network.
12) Write a statistical proof of E[O(nlogn)] complexity, and show how a median selection change it could be made to make it an O(nlogn) worst case.
13) Show how this could be done out of core or distributed over a supercomputer grid.
14) Describe the real algorithmic complexity in terms of time, space, number of nodes, cores bandwidth and die area.
15) Talk about lower bounds in sorting.
16) Consider whether or not partial sorting is better for the problem being solved.
17) Explain the motivation for every line of code I write and every algo result I consider.
18) Explain how it can be implemented recursively or via a stack (and why they are essentially the same).
19) Use indexed data to avoid expensive swap operations.
20) And off course, a
lot of soft skills, such as communication, response to criticism, etc., while explaining the above.
The above is what we (I can’t speak for Amazon, but image it is similar) typically look for when asking an algo question of a very senior engineer. If one just regurgitated QS Code without showing any of the sophistication above, the interviewer will know.
