5 ms·

His grandmother knew radix sort. It's well known that, on sufficiently short keys and sufficiently many records, radix sort beats the (n)ln(n) sort algorithms

His grandmother knew radix sort. It's well known that, on sufficiently short keys and sufficiently many records, radix sort beats the (n)ln(n) sort algorithms such as heap sort and, thus, beats the Gleason bound. How? The Gleason bound is only for sorting by comparing pairs of keys, and radix sort doesn't do that. Maybe his grandmother had a job with punch cards: The old punch card sorter used radix sort. Of course Knuth covers radix sort in TACP. However I've always thought that his claim that radix sort was especially good for a pipelined processor was wrong. 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.

wh-uws 15y ago
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)
- nostrademons 15y ago
  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.
  - JoachimSchipper 15y ago
    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_people/ 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 http://wiki.lesswrong.com/wiki/Category:Biases is a long list of references.
  - NY_USA_Hacker 15y ago
    "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.
- NY_USA_Hacker 15y ago
  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!
bnoordhuis 15y ago
> 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!
- anonymoushn 15y ago
  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.
  - anxrn 15y ago
    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).
    - anonymoushn 15y ago
      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.
prostoalex 15y ago
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.
- NY_USA_Hacker 15y ago
  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.

wh-uws 15y ago

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)

nostrademons 15y ago
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.
- JoachimSchipper 15y ago
  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_people/ 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 http://wiki.lesswrong.com/wiki/Category:Biases is a long list of references.
- NY_USA_Hacker 15y ago
  "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.
NY_USA_Hacker 15y ago
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!

bnoordhuis 15y ago

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

anonymoushn 15y ago
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.
- anxrn 15y ago
  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).
  - anonymoushn 15y ago
    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.

prostoalex 15y ago

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.

NY_USA_Hacker 15y ago
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.