How to: Pass a Silicon Valley Software Engineering Interview
paultyma.blogspot.com
paultyma.blogspot.com
http://en.wikipedia.org/wiki/Counting_sort
When you're trying to get nice low asymptotic time bounds on things, it can really help to remember counting sort, radix sort, and tries. Counting and radix sort are O(n), and tries are a really handy data structure with the same worst-case asymptotic time as the expected amortized time of hash tables. They also support in-order key traversal and prefix/range queries.
To illustrate, consider sorting 32 bit integers. If the radix is one bit (i.e. radix=1 bit and k=2 * 32 [32 "digits" and 2 possible values for each "digit"]) then radix sort is O(64n) = O(n). Now consider, cutting up the 32-bit int into byte size chunks (i.e. radix=8 bits and k=4 * 256 [4 "digits" and 256 possible values for each "digit"]). In which that case radix sort is O(1024n). Note that we are able to determine the value of k without any idea of what n may be.
In practice even for small n (n>200), a straight forward implementation of radix sort is faster than any O(nlogn) sort.
In the interviews we do we include a written exercise you have to complete before you come in the door so that we can sit and talk about a problem you've been able to solve at your own pace - instead of seeing how well you think on your feet. Even then people try to come up with the fastest solution instead of something that represents them well.
Remember that the interviewer is always more impressed with a right answer than a fast answer.
Hah! When I interviewed at Google, I turned down the invite to the next round because it felt more like a cult than an engineering organization.
if Google stopped paying me tomorrow, I'd still come to work
Exactly.
Is there any other professional career where it's common practice to expect candidates to practice their profession in their spare time? My CPA ex never came home and crunched numbers for fun. My doctor never mentioned diagnosing his neighbors to relax.
This seems like a self-deluded way to weed out people who have families, physical limitations or injuries that prompt them to get away from their computer, etc.
The test probably does weed out good engineers, but I would rather have a test for employees that yields more false negatives than false positives. I know plenty of people with families that also code in their spare time as a hobby.
People like to pretend that keeping up with the latest trends in computing takes a lot of time. But, mostly it's new people falling in love with old ideas. Consider, from a C background Ruby would seem extremely innovative, less so if you know C and python, and if you know C, python, and Lisp it's just not that novel.
PS: Sometimes people are not exceeded about bulb because they have never heard of it. Other times they know more about it than you do and are simply not impressed by yet another remix of really old ideas.
I don't think so. I think programming is a weird mix because it is largely populated by somewhat awkward introverts. Writers I know do like to write, and write each day, but they're very scheduled. One of my friends says he writes six hours a day, if he wants to more or less.
In part, I think other "creatives" value time among other humans. Whereas programmers tend not to value that as much.
Plus programming had a weird dynamic where staying up late (or not sleeping) is something to have pride in. For other creatives -- inspiration and elegance seems to be something they take much more pride in, over brute hours on a task.
OTOH, my neighbor who plays in the symphony (and is probably one of the best for her instrument in the US), plays music part time, because it can't pay the mortgage (at least not where she lives). She is a lot more into the lifestyle.
It just seems like in other creative fields there's kind of a line between the pros vs the amateurs or hobbyists -- and how they spend their down time.
Also, many professional symphony musicians I know are in multiple side groups. (jazz bands, quartets, etc) I think there are actually some parallels with coding, though I don't believe orchestras take extra-curricular activities into account during auditions.
My dad works in the aerospace industry. Specifically outer space. His company builds rockets. And you know what? He LOVES outer space. He watches the ISS when it's visible over head, records the shuttle launches, and he browses the NASA app on his iPad, FOR FUN. You know what else? He's VERY good at his job.
But then, some professions aren't necessarily fun. CPAs exist to remove a problem. It might not be the most glorious job, but it's a tough job that not everybody can do, so they are compensated well. I doubt they crunch numbers for fun. But you know what I'll bet they will do for fun, check up on the latest financial news.
Your dad seems to be engaging in activities which are relevant to his interest in aerospace, without actually involving what he does as 'work' each day.
As I mentioned elsewhere, this is more on par with browsing /r/programming, skimming a book on a new programming language, or meeting with other tech-minded folks. In my opinion, this is very different from completing a software project.
Sometimes I have clients with interesting projects but 90% of the time my day job is stirring enterprise soup. I fix bugs, write documentation and make responsible engineering decisions.
My side projects have no tests, no documentation and no comments. I write fun stuff like chat bots that mess with 419 scammers or p2p chat protocols. I get to enjoy all the fun parts of programming without the real-world constraints and responsibilities.
1) I don't know much about doctors' scheduling, but I've known a few that seemed to schedule a batch of patients, then hours for paperwork, document review, and peer review/help. So I wonder how much of this happens in their "free time".
2) There's a difference between reading up on new technologies versus creating a project and seeing it through to completion. Similarly, there is a difference between reading medical journals (study) versus seeing patients (practice).
would you trust an auto mechanic who didn't change the oil on her own car?
Absolutely. That's a very simple job, and if my mechanic can have it done for $20 at Walmart while he shops, it's well worth his time. If he's a good mechanic, he bills at, what, $70+ per hour? By the way, the mechanics I've known tend to drive inexpensive, late-model cars, and get rid of them after a few years. Why? Because they don't want to fix cars in their spare time.
I'm sure a mechanic would be able to do the replacement if they had the part, but I imagine that takes a lot of the enjoyment out of being a mechanic. You could probably get around that by only buying cars that predate mass computerization (now 20+ years old), but then you're trading one problem for a potentially much larger set of problems. It's not that they might not want to fix cars - it's that it might not be worth it to indulge that activity as a hobby.
I waste time fixing a 30 year old vehicle because it's a fun pastime for me. They don't do it because it's just more of what they do all day.
I simply hate spending my weekends and evenings sitting indoors. I would probably get rejected by many interviewers for simply not spending my spare time doing lots of coding, even though solving problems and/or doing challenging activities is one of my favorite past times. I love learning new things and mastering (attempting to master) my favorite outdoor hobbies like golf, snowboarding, hunting, fishing, etc.
If you are someone like me, then I suppose you should keep this in mind during an interview, and stress your enjoyment for more soft skills such as working with people and solving different types of problems outside the programming area.
Other professions have more formal, expensive, and rigid requirements for certification and continuing education. Programming does not. Consider spare time projects as one potential proxy for the former.
The whole column and its approach and values are wrong. If Silicon Valley and Google are recruiting that way, and I suspect that they are, then GOOD because it means that competing with them should be easy. Basically the author just nearly totally fails to understand what's important in computing or what qualifications are important.
It's an old story: In a well run technology company, HR is absolutely, positively forbidden to engage job candidates in any meaningful sense whatsoever on threat of immediate reassignment to the toilet squad. All HR can do is push paper and keep records, smile, bring coffee, tea, soda, or donuts, make travel arrangements, etc.
Radix sort? I read it as a trick question where the answer is 'hash table with numberOfYearsOld as the key'.
I suggested that as the solution to an almost identical question when interviewing with Google - and it got rejected by the interviewer. Ah, the arbitrariness of it all!
Second, assuming that numberOfYearsOld takes on at most 100 unique values (which I think is reasonable), the best you can hope for is for every hash table insertion and lookup to require you to traverse an average of 5000 students (because on average you will have to look through half of a list of 10,000 students). If you used this as an intermediate step in a real sorting algorithm, your sort would take O(n^2) time.
Once you've scanned the list, why do you have to traverse the 100 lists at all (unless you want to further sort them on 'name')? You just need to merge all the lists (In the mom case, simple concatenate all the stacks). This is a constant time operation.
The 'trick' here is to think about how would you implement a sort if you had no memory constraints. As the blogger rightly says, engineers will usually pick one of the standard ones without thinking (I would surely do the same).
- What do you mean by uniqueness of elements? There's no mention of sorting by a secondary criterion, if that's what you mean. Which 'standard' sorting algorithm removes duplicates?
- What do you mean by 'unique key maps to a different bucket'? You'd only have to worry about this if you're designing a hashing algorithm, clearly that's not the problem here. You're hashing on age (hence guaranteeing partition on age), and simply adding objects to a list in the hash. Are you implying we'll have to invent a new hash map to solve this problem?
This is literally less than 10 LoC in any high-level language. That 'complexity' surely seems worth O(n) running time?
// TODO enforce! see also: soylent green
#define MAX_AGE 100
struct student {
const char *name;
int age;
};
struct students {
long n_students;
struct student *students[10e6];
};
struct students all_students[MAX_AGE];
void insert(struct student *s) {
struct students *ss = &all_students[s->age];
ss->students[ss->n_students++] = s;
}
I tried to argue that my solution was a fair bit faster and simpler to boot. That's probably why I didn't get a follow-up interview - no-one likes a smart arse. :-)
There's no hash table here, this is just bucket sort. I don't think anyone should care about the difference between counting sort and bucket sort, though. The only thing I would mind about this is that it allocates 100x the necessary memory, but I'm sure you wouldn't actually do that when it matters.
Radix sort? Take a deck of punch cards with a non-negative integer in base 10 right justified in some three columns. Run the cards through the sorter sorting on the least significant digit. The sorter puts each of the cards into the right one of 10 pockets, one for each of 0-9. Or just imagine that it builds 10 'linked lists'. Then move the cards back to the input, 0 pocket first, then the 1 pocket, etc. Then sort on the 10s digit column. Then repeat on the 100s digit column. Done. Just did the work in time proportional to 3*n for n cards.
If have a sorter with 1000 pockets, then can do the sorting in one pass. For the ages, such a sorter would sort all the input in just one pass.
Also cute, radix sort is 'stable' which means if card A starts before card B and if these two cards have the same value on the sort key then at the end card A will still be ahead of card B. Stable sorts are nice because they can permit sorting on several keys separately and, then, have the whole list of records in sort on the 'hierarchical key' made from 'concatenating' the separate keys.
Again, can do it all playing with pointers and linked lists.
It remains, for short keys, radix sort is faster than the (n)ln(n) sorts.
The obvious way to implement radix sort, just think punch cards, is stable with no extra effort.
(seriously asking. New grad in about a weeks time, been keeping track of different peoples opinions)
(Disclaimer: I work for Google. I didn't overlap with Paul Tyma, but I know people who worked closely with him, and he's generally quite highly regarded. He also has built something that people want, unlike most of us: he wrote Mailinator single-handedly and ran it off a single box. So despite NY_USA_Hacker's questioning of his competence, I think he's actually a far better source of advice than anyone on this thread, including myself.)
I wish I knew more of:
Statistics. Hypothesis testing, and confidence intervals. I wish I knew everything that could go wrong when analyzing data, because we analyze a lot of data, and it's really easy to let biases creep in. I wish I understood better how to slice & dice data by conditions - "these are the samples that exhibit some particular trait, and that trait affects this other variable in this way, and so our overall result will be biased by..." I wish I could data-mine large quantities of data and pick out the trends automatically.
Neuroscience. So much of what we do relies upon understanding how people perceive things. There's been a lot of research in that area lately, and it turns out that people's biases are actually quite predictable. I wish I knew how. I wish I knew why.
Trade sense. There's this soft skill called "trade sense" that basically refers to knowing what people will be willing to pay for. Steve Jobs is a master at it. I suck at it. It is a fundamental skill for an entrepreneur, because there is no company if people will not pay you for your product.
Statistical machine learning. Basically, the past decade of AI research has discovered that trying to encode a whole bunch of rules into a computer just doesn't work, because the real world doesn't function like that. Instead, what does work is to feed the computer a lot of data, and then notice patterns like "if this term appears, this article is most likely X". There're a bunch of techniques for this in the literature, they typically aren't taught in undergrad, and they are wonderfully useful.
Image, audio, and video algorithms. More and more data is taking the form of multimedia these days; plain text just doesn't cut it. Processing multimedia is an order of magnitude more difficult than processing text, because there's an order of magnitude more data. But this is largely virgin territory. Well, sorta. Basic multimedia algorithms have been around since the 60s, but the environment has changed massively in the last decade.
Getting along with people. Almost everything worthwhile these days is too big for one person to handle. You need co-conspirators and allies if you want to get anywhere. Don't be a jerk; you need people if you want to accomplish anything.
http://lesswrong.com/lw/he/knowing_about_biases_can_hurt_peo... is a decent prelude and a taster of LessWrong's peculiarities; http://wiki.lesswrong.com/wiki/Category:Biases is a long list of references.
Your first point is fully correct. The 'expert system rules' didn't work very well.
On your second point, "what does work", actually doesn't work very well either. You can use such things okay for first-cut, say, what J. Tukey called 'exploratory data analysis', then, to be followed by 'confirmatory data analysis'. The first part is okay, but the solid stuff is the second.
Then there's more: See what assumptions hold in the practical problem. Use these assumptions as the hypotheses of theorems with proofs. Use the conclusions of the theorems as results you now know about your real problem.
In real problems with a significant role for uncertainty, look for cases of probabilistic independence. For this, learn the high-end version of what a random variable is from, say, Cinlar, Breiman, Shreve, or Diaconis. Then for random variables X and Y, if knowledge of X doesn't help predicting the value of Y, then X and Y are independent, and can often come to this conclusion just intuitively.
Cases of independence can partition your problem into 'independent' pieces.
For more, look for some good examples of how to apply math in physics, chemistry, electrical engineering, and operations research. For statistics, sure, look at what agriculture did with the general linear model or, if you will, analysis of variance.
You will have little hope of making progress in using applied math just within CS or computing. For the progress, have to look to other fields that have made good progress with applied math. Eventually it will be crucial to have a good background in math, say, Halmos 'Finite Dimensional Vector Spaces', Rudin, 'Principals', measure theory and functional analysis, and then probability, stochastic processes, and statistics based on these.
Here's 'programming' in a nutshell: (A) Look at the problem and see what data is needed. Allocate appropriate 'chunks' of main memory for the data and give the chunks some names, usually mnemonic. (B) Manipulate the data with assignment statements from expressions, If-Then, and Do-While. (C) Otherwise use divide and conquer and call functions, subroutines, APIs, etc. So, that's the ABC's of programming.
For these ABC's all the common languages Algol, Cobol, Fortran, PL/I, C, C++, Rexx, Visual Basic .NET, C#, etc. are all very similar, more similar than English, French, Spanish, and Italian. 'Object oriented' programming? People did essentially this in Fortran and PL/I, likely also Algol, long before C++. IBM had object oriented programming in microcode in the early 1970s. Exceptional condition handling? Throw-Catch or Try-Catch are nowhere nearly as powerful as On Conditions in PL/I. Concurrency? We have mutex, semaphores, and actors and maybe more -- it's time for more: E.g., with lots of object instances and lots of threads, run into the same problems solved via transactional integrity in relational database with automatic deadlock detection and resolution, and basically, at least first cut, need the same solution.
Net, 'programming' as practiced and as in the article hasn't changed much in 40 years. In particular in recruiting no sense in getting all picky about some 40 years old material. The picky guy in the article didn't know enough to know how silly he was being. E.g., the corresponding guy at Google asked me what my favorite programming language was. I said PL/I. Of course he wanted C++. But, net, PL/I is a much better designed language than C++. My mention of PL/I ended the conversation.
Second, let's talk about what is important: Broadly, the future is important, and about that what is important is making it. So, how to do that? Here's by far the most powerful, broad 'paradigm': Have operations with powerful, known properties.
Now, considering how abstract computing is, to have some properties known is basically to have a theorem and a proof. Sorry 'bout that, but that remains the situation. Or, if we are going to build a large, complicated system where at each step all we have is "I think so, usually, maybe", then don't ask for much reliability for the resulting system.
Or, think like a mechanical engineer designing a Boeing 767: Start with some very well known engineering properties of the materials. From those properties use, say, finite element calculations, to determine the properties of various larger pieces of the airplane. Same for building bridges, buildings, cars, etc.
So, generally in building things, need to know the properties of what are working with. Also in computing.
Now, so far in computing, the more important 'pieces' were the now traditional topics in algorithms and data structures from Knuth's TACP, etc. Or we read about DeRemer's LALR parsing from Ullman. Or we read about k-D trees from wherever. Now ancient, but fine for 40 years ago and still good for the original purposes.
But for the future, we want more. Here's where computer science (CS) ran out of gas and got off track: CS wanted to move closer to the real problems. So, CS ran into 'information', 'knowledge', manipulating information, etc. and started borrowing ugrad texts in applied math, optimization, statistics, stochastic processes, graph theory, control theory, etc. These fields are based on theorems and proofs, but CS set those aside. Bummer since the theorems and proofs are the main way we know what we have, that is, the properties we need to depend on.
In particular, long the main criterion of artificial intelligence (AI) was just to program it and 'play with it and see if it seems intelligent'. So, the criterion was not that start with some assumptions that hold in the real problem, use the assumptions to justify some theorems, and use the theorems to construct the system so that we know what we have. Similarly there is 'machine learning' which also is working just empirically on the results and largely ignoring the assumptions, theorems, and proofs. Then there is the respect for heuristics, that is, guesses with no known properties except what we can see empirically. Basically CS and AI are becoming C- students in applied math, and that is NOT good.
My view is that the future of computing will have to borrow closely from the 'paradigm' of applied math, with a lot of careful attention to assumptions, theorems, and proofs. Then we will have 'pieces' with known properties we can assemble into the larger systems we need.
In a nutshell, CS and Silicon Valley know very well how to program at the level of ABC above but are very short on what to program. E.g., at Stanford, f'get about CS and listen to, say, P. Diaconis. At Berkeley, listen to L. Breiman. At Princeton, listen to E. Cinlar. At CMU, S. Shreve. At MIT, D. Bertsekas. Alas, none of these professors and none of their students would make it past the first-cut interview of the article!
Here's an example: Recently yet again we had a large server farm with lots of parallelism and redundancy go big time belly up. I mean, they had this backing up that, and when this got too full it got more from there, etc. Intuitively, it all looked really good. Intuitively. A proof? Nope. Was it good? Nope. It sucked. Terrible design that made the Titanic look good. Not nearly the first time for such a thing!
Let's just take the first, simplest part of this problem, near real-time detection that something is sick instead of well. So, we have two ways to be wrong, false alarms and missed detections. From Diaconis, we can learn about Neyman-Pearson (Neyman was long at Berkeley) where we see how to get the lowest rate of missed detections for whatever false alarm rate we are willing to tolerate. Now we are at the level of a junior course in mathematical statistics but already way, WAY past essentially all of the system monitoring community in both computer science and practical computing. NOT good.
Next, what we want, and we can't escape that, is essentially a statistical hypothesis test. So, we have data on each of several variables and with no reasonable chance of knowing the probability distribution. So, we need a multi-variate, distribution-free statistical test.
Now we are into reseach-level computer science. Just ain't going to get there with intuitive, heuristic, or empirical methods. Instead, notice where have some exchangability and a finite group of data transformations that are 'measure preserving' and derive a new class of hypothesis tests.
'Computer science'? Nice progress on an important problem in computing, but several chaired profs of computer science at top research universities and editors in chief of top computer science journals confessed that neither they nor anyone on their board of editors could review such math. Out'a gas.
For more on how to design a reliable server farm, need some more applied math, likely beyond essentially all of CS. Instead, for the right stuff as prerequisites, start with some good applied math people such as I mentioned. For CS, f'get about it. Right: For the future of CS, largely f'get about CS -- it's out'a gas.
The guy in the article doesn't have even as much as a weak little hollow hint of a tiny clue about this situation. The people he recruits are guaranteed to hold his company back to 40 years ago. He thinks he's a tough recruiter looking for the best of the best of the best, but he will only take people 40 years out of date. How 'bout that!
- Recruiting. They'll reach out and arrange your interview. They might also have some basic questions towards you just to ensure your resume is not a complete work of fiction.
- Engineering. They'll interview you, and make a hiring decision.
- HR. They'll greet you on your first day of your becoming a "human resource", set you up with benefits, and ask you to fill in some basic paperwork.
If engineering wants an ad run, then HR can help as long as they don't touch the real content of the ad. When resumes come in, they can hold them up to the light, read them upside down, wave them with a magic wand, but under no circumstances should they make any significant decisions on the content. HR couldn't tell the next Turing award winner from a grade school video game player.
Who does college scouting for the NBA? College cheerleaders? Not exactly.
E.g., there's Gleason. That's A. Gleason. Since he never got a Ph.D., he shouldn't be a college prof, right? I mean, ask any college cheerleader! Instead, early in his career, maybe before he finished his Ph.D., he knocked off one of Hilbert's problems and was made a Fellow at Harvard and remained at Harvard for the rest of his career.
Just cannot hope to find Michelangelo to paint the ceiling if have house painters doing the first cuts on the applications.