Hacker News Reader

> His grandmother knew radix sort.

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!

First, 'hash table' isn't a sorting algorithm. If you apply 'hash table' to an array the result is not a sorted array.

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.

Using a hash table as auxiliary storage is a perfectly reasonable 'sorting algorithm'. He's not asking you to name one of the common sorting algorithms. He's asking you to solve a sorting problem, with a loosening of the usual limited memory constraint.

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).

I guess a candidate could say "I would solve this problem by making a hash table keyed on the number of years, except that unlike the hash table that ships with my language, this hash table will expose its constituent linked lists to me directly, guarantee that each unique key maps to a different bucket, and not enforce uniqueness of elements (so as to avoid performing a linear scan of the element's bucket upon insertion)." I probably wouldn't reject someone who said that, but I would wonder what prompted such a complex answer.

- Which programming language 'complicates' storing list objects in a hash map? Downright trivial in all languages I can think in (Java, C++, Perl, Ruby, Python)

- 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?

My understanding of bnoordhuis' proposed was that the elements of the hash table would be students, rather than lists of students.

The language was C and my solution (adapted to the article) was something like this:

    // 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;
    }

So O(1) insertion and O(n) post-processing to stitch the arrays together again. Seems like pretty acceptable performance to me but the Google guy thought otherwise, the answer he was looking for was (probably) a counting sort.

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. :-)

Thanks, I'm sorry I misunderstood your brief description.

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.

Now, the good answer, and essentially what the grandmother gave, is essentially just old radix sort like punch cards were sorted.

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.

Technically the sort algorithm from the article is called counting sort, not radix sort. While both radix sort and counting sort are O(n) they are fundamentally different algorithms. In practice radix sort can be used for larger domains of values than is feasible with counting sort. Furthermore care must be taken if you want a stable sort since only certain variants of radix sort are stable.

What the grandmother did with ages, say, 0-99, would be radix sort if the sorter had 100 pockets. Then the sort was done in just one pass. I don't recall counting sort, but in this case it sounds like the same thing.

The obvious way to implement radix sort, just think punch cards, is stable with no extra effort.

What would you say is important if those things aren't

(seriously asking. New grad in about a weeks time, been keeping track of different peoples opinions)

First, let's talk about 'computer science' much as viewed via 'programming' and, indeed, as in the article.

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!

This should be a blog post so it can be linked to, every interviewer ought to read it.

Don't really disagree with NY_USA_Hacker, but I think his perspective is biased toward what he happens to know about. This is quite natural: everybody thinks that what they already know about is important, because that means that they know Important Things. So I'm going to go the other route and tell you things that I don't know about that I wish I did.

(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.

I can't really help with the others, but LessWrong has some pretty readable, if scattered, treatment of cognitive biases.

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.

"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."

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.

For what it's worth, statistical machine learning and other CS people have recently "discovered" classical convex analysis - for the last few years papers have been full of stochastic subgradients and the like. The next big thing has got to be the material on decompositions from the 50s and 60s.

I was trying to parse the last part. Interviewing practice with technology companies would generally involve three departments:

- 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.

What you are calling "recruiting" I was assigning to HR.

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.