Personally, I would be more inclined to hire a person picking the "throw it in a hash and look it up" solution over any more complex solution. My reasoning is that bad programmers tend to get lost in nuance, or don't understand a problem. Good programmers tend to reason through the proportionate value of a problem. I'm not saying nuance is always a bad thing, but it's probably not what your company is developing unless you work for a math department.
A Google Interviewing Story
31–40 of 122 posts
Re: A Google Interviewing Story
#32The prime multiplication is a pretty bad solution. It's actually O(n log n) rather than O(n), since you have to use some form of big integer, and multiplying a size-n number by a constant is O(log n). It is also needlessly complicated.
Can you explain what representation you use to get multiplication by a constant in O(log n)? Wouldn't it be at least O(n) for the standard bignum representations, making the algorithm O(n^2).
Multiplying n primes together creates an O(n) digit number. Multiplying an O(n) digit number by a constant is an O(n) operation. So essentially we're doing an O(n) operation n times, hence O(n^2).
The smartest representation that I can think of for the numbers would be to store the prime factor exponents in an array, which would essentially transform the algorithm into the array based version. For example 120 = 2^3x3x5 would be represented as {3,1,1,0,0,...}.
Re: A Google Interviewing Story
#33I enjoy clever ways of approaching problems as much as the next guy, but I would never ding someone in an interview for not coming up with a clever-enough solution. Good software engineering is maybe 99.7% failure-avoidance and 0.3% cleverness. On very rare occasions you need a clever solution, but most of the time you need to solve the problem in a way that you're 100% sure will work, has no nasty failure conditions, and that other competent engineers will understand. If there's no other good solution, or if every bit/cycle matters, then you get to try to be clever, but that happens pretty rarely. I've seen way, way too many problems caused by people using clever solutions for problems that had straightforward-but-less-fun solutions. (And as has been pointed out plenty of times already here, the clever solution in this case is less optimal than a more straightforward one would be). If an interviewer seemed intent on proving they were more clever than me, or on trying to get me to throw out unnecessarily-clever solutions to straightforward problems, it would be a pretty big turnoff.
Re: A Google Interviewing Story
#34I feel like most engineers rarely have to try too hard to get a decent job, but I wonder if it's because of stories like this. I've been on the interview circuit a handful of times so far in my life, and aside from the first time when I was mostly clueless ("So where do you want to be in 5 years?"; "Man, I never think that far ahead."), I feel like interviews have become a very routine process of answering a similar…
Probably none of the above. I've heard the interviewer makes up their mind to hire you in the first few seconds of meeting you. Psychology is a strange, strange thing ... but reality is better than fiction.
Re: A Google Interviewing Story
#35If you are ever asked an interview question which you've already answered in a previous interview, you should tell the interviewer immediately. I know some coworkers who will intentionally ask a question they know you were asked in a previous interview to test your integrity. (Edit: Not that I would condone this practice either.) These types of interview questions are about evaluating how you think far more than what…
> If you are ever asked an interview question which you've already answered in a previous interview, you should tell the interviewer immediately.
That's sort of like saying you won't shot a man in the back during a war.
Re: A Google Interviewing Story
#36Angry because neither the hash table or the prime multiplication would be as fast as a boolean array indexed by the char value. As an added bonus, the boolean array actually makes the most intuitive sense.
I recently used this algorithm for speeding up an iTunes style search function. Originally I did a strstr over every item in the database, but it wasn't quite fast enough. I precomputed a 32-bit mask - 1 bit per alphabetic char, 5 bits per digits, and the last bit for special characters - for every database item, and used that as an initial search filter. I only needed to use the more costly strstr on items that made…
That's pretty clever. It can be tempting in such a situation to immediately go for the big guns (patricia trees or whatever), but often a simple hack like that gives a lot more bang for the buck.
Re: A Google Interviewing Story
#37Angry because neither the hash table or the prime multiplication would be as fast as a boolean array indexed by the char value. As an added bonus, the boolean array actually makes the most intuitive sense.
The array is a pretty obvious solution (to me, anyways). But the hash table has an added benefit.
Consider the following string, where   is a non-breaking space:
Main string: "Counter example:  _à²"
Shorter string: "ಠ_ಠ"Re: A Google Interviewing Story
#38If you are ever asked an interview question which you've already answered in a previous interview, you should tell the interviewer immediately. I know some coworkers who will intentionally ask a question they know you were asked in a previous interview to test your integrity. (Edit: Not that I would condone this practice either.) These types of interview questions are about evaluating how you think far more than what…
This is right. In my experience, when you tell interviewers that you already know the answer to their favorite interview question (and can explain the answer) they are just as impressed as if you had solved it yourself, and you don't feel like you've deceived them.
Re: A Google Interviewing Story
#39The prime multiplication is a pretty bad solution. It's actually O(n log n) rather than O(n), since you have to use some form of big integer, and multiplying a size-n number by a constant is O(log n). It is also needlessly complicated.
Especially since they're using the primes to encode N = 26 independent variables within a single number. On any modern CPU, you already have 32 (or more) independent variables in each number, they just happen to be called bits. And you can test them and set them in much simpler and faster ways than integer multiplication and mod.
Re: A Google Interviewing Story
#40The prime multiplication is a pretty bad solution. It's actually O(n log n) rather than O(n), since you have to use some form of big integer, and multiplying a size-n number by a constant is O(log n). It is also needlessly complicated.
Can you explain what representation you use to get multiplication by a constant in O(log n)? Wouldn't it be at least O(n) for the standard bignum representations, making the algorithm O(n^2). Multiplying n primes together creates an O(n) digit number. Multiplying an O(n) digit number by a constant is an O(n) operation. So essentially we're doing an O(n) operation n times, hence O(n^2). The smartest representation tha…
It's O(n) in the number of bits. The number of bits is O(log n) in the value of the number. Multiplying n primes together, where the primes are taken from a restricted set of numbers, creates a number whose value is O(n) (it has n factors, but each factor is bounded by a constant).
BTW, I would've used a bitvector. For lowercase letters only, you could fit it into a 32-bit value (add mixed-case and numbers and you can fit it into 64 bits), then it's just an OR to set a bit and an AND to read if a bit has been set, both fast machine-level operations.
Edit: Didn't see the footnote on the problem. A bitvector doesn't work if counts must be kept, but you can still do this pretty simply with the table solution.