?

Log in

No account? Create an account

Previous Entry | Next Entry

Sep. 12th, 2007

I found another blog post giving advice on how to pass a Silicon Valley interview. There is some good advice, some debatable advice, and some things to think about.

The sorting question was interesting for a number of reasons. One, it approaches the problem solving issue from another direction: how to translate a problem description into an effective algorithm (one that solves the problem well) but may seem like some other problem. I had commented on this some time ago, with regards to the Monty Hall problem, which even mathematicians answered incorrectly because of how it was phrased. I suspect that most people would get the "Mom's version" correct because the context within which is being asked is clear – a specific answer is expected. Whereas the "Engineer's version" may be misread by some (especially if they're nervous) to be a question about what is the best comparison sorting algorithm. So one needs to be careful not to answer the question too quickly.

"Mom's version" captures our "intuitive" notion of sorting objects into groups. The algorithm is similar to pigeonhole sort. My guess is the last time I thought about this was in 1989, when I took the algorithms class at Stanford that uses Cormen's text. But there may be people who are more likely to think about these things based on how often they do them (and whether they are worthy of consideration). This type of issue never came up at work, and I didn't really think much about this as a possible interview question until a few days ago, when I was thinking about the first time I ever encountered topics that are part of computer science. I "knew" what binary search was when I was a child, from a science fair exhibit at the site of the old 1964 World's Fair that guessed one's weight. This "stuck" in a way that enables it to come to the forefront when asked about it. However, sorting of clothing, socks, etc. that I do all the time does not "stick" in quite the same way, possibly because it's only efficient for very small numbers of items and categories. I was thinking that I never had to give consideration to a shortest-path algorithm until I got to MIT because I never had to solve anything like "find the shortest number of miles it takes to fly from one city to another, given a map of flight distances," even though I had flown before going to MIT and seen plenty of air route maps. I don't know much about high school curricula, especially for those people who are not planning to do computer science or software engineering, but if these issues are presented in classes such as AP computer science, those who don't take them (but decide to switch to CS or SE later) are at a disadvantage in the sense that certain problems are not "at the forefront" of what they usually think about, so they may not recognize all instances of these problems.

One of the responses to the post – that one may have a job that requires that APIs be glued together, so it is not necessary to implement a particular sorting algorithm, made a lot of sense to me. In fact, I find the notion that someone would be required to implement particular algorithms (without references) odd. Most of the standard algorithms are available in language libraries, so one can be productive, without needing to reinvent the wheel. The respondent goes on to question whether Google is attempting to identify candidates with proficiency in the areas covered (e.g. knowledge of algorithms), or those who (need to) study those areas to get to a level of proficiency. As I've noted, from a practical standpoint, most people don't spend a lot of time implementing all of the standard algorithms, either right before an interview or over the course of their careers and education. It's not productive. Also, this isn't the only thing a candidate would be expected to know.

Tags: