Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Google Interviewing Story

paultyma.blogspot.com

Post reply on HN
Print view View original

101–110 of 122 posts

Re: A Google Interviewing Story

#101

Post by bluesnowmonkey »

jamesaguilar wrote: post #80
bluesnowmonkey wrote: post #10

Earlier quoted context omitted.

Oh really? How much faster would that be?

As much faster as the length of the second string times the difference between an address lookup and a hash table lookup.

Which is how much? I wanted you to try and quantify the difference, because the process of doing so would lead to the flaw in your argument.

The hash table solution is O(n+m). 24 operations on the example. The array solution is O(n+m) and 24 operations. The same.

Your intuition tells you that the array is faster because subconsciously you're making assumptions about implementation details. What if you're in a language like PHP where arrays are implemented as hash tables? What if you're in C, but the hash table implementation uses a resizable array and happens to choose an initial size of 26?

Re: A Google Interviewing Story

#102

Post by tedunangst »

jamesaguilar wrote: post #70
tedunangst wrote: post #45

Earlier quoted context omitted.

If there are 3 As in the first string and 4 in the second, it fails. A boolean value can't count to 3.

Maybe in a different problem it would fail, but this is merely a presence test, so booleans are fine. At any rate, an array of int32s instead of bools would defeat the objection for reasonably long strings.

This is that different problem. The author's description is muddy, but you do need the counts.

Re: A Google Interviewing Story

#104

Post by lwhi »

I paused a bit before reading about the possible solutions, and actually thought of the (prime number) solution the interviewer came up with.

I realise that this is a bit of redundant post .. but, as a person who isn't a brilliant coder I surprised myself. But then again, after reading the comments here - I think maybe I just have an obtuse way of thinking about things.

Re: A Google Interviewing Story

#105

Post by alextp »

user24 wrote: post #19
jamesaguilar wrote: post #2

Angry 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 boolean array indexed by char effectively is a hashtable isn't it? where the hashing algorithm is index = ord(theChar).

This is not quite true. It's a mapping, but it's not a hash table because the mapping is bijective (while hash tables just project the keys into the table space). So there is no possibility of collision, the number of keys is fixed, etc. It's just a table, like any other, and most of what is implied when talking about hash tables does not necessarily apply here.

Re: A Google Interviewing Story

#106

Post by astrodust »

StavrosK wrote: post #68
ericd wrote: post #62

Earlier quoted context omitted.

Powers of two wouldn't work. If A = 2^1, B = 2^2 AA, B would evaluate to true. But you're right, the running times aren't any better, except that the constant factors of dealing purely in arithmetic might make it faster in real terms if dealing with a lot of this type of thing than creating hash maps. If response time matters for the application (high frequency trading, etc), it might make a difference.

Sorry, by "powers of two" I meant bitmasks, not actually dividing with powers of two. Let A = 2^1, Z=2^26, and then OR with 2^1 when you encounter an A, etc. If the integer is non-zero when you're done, you've exhausted all the characters in the original string.

This is exactly what I was thinking and I have no idea why it didn't come up. Given an "alphabet" of 26 characters, that neatly fits inside a long int, and that's just crying out for a bitmask.

Re: A Google Interviewing Story

#107

Post by antirez »

In my life I never got interviewed, even if it is 15 years I work as a programmer. Now I work at VMware thanks to Redis, and VMware did not requested an interview, and my only previous not-self-employed position 10 years ago was likewise triggered by my work on hping.

But, I'm sure, I would suck so much at this kind of interviews. If you are anything like me you'll understand what I mean, in topics where I work day by day I've pretty much the control of what the good solution can be in a few minutes, but for many things to find the best solution requires, at least for me, days of thinking, sleeping, possibly waking up with the solution in mind, to find it's wrong and you need to reiterate the process.

My design abilities are all there, in this days. I'm sure that in the five minutes race I would say many times something of super stupid. Now my question is, are the five-minutes performances really linked to the three days thinking about your problem solution?

Isn't it possible that at least a subset of guys that will get the few-days answer well, will instead provide a poor answer in little time, and sometimes the other way around?

If this can be somewhat true, there is a huge industry selecting runners for 100 meters, in order to run, most of the times, a maraton.

Re: A Google Interviewing Story

#108

Post by antirez »

tomerico wrote: post #77
jdoliner wrote: post #60

Earlier quoted context omitted.

I doubt that the interviewer mentioned the prime number solution due to insufficient cleverness in the original solution. The answered O(n+m) solution actually contains flaws beyond its lack of cleverness. 1) there's no good reason to use a hash map, hashing is useful in maps for mapping an unevenly distributed set from a large an arbitrarily large space to an evenly distributed set from an arbitrarily small space. T…

With your solution, I might have not accepted you to do job because it is obvious you don't have experience with Unicode and localization.

And I might have not accepted you for over-generalization that is one of the worst things ever you can do as a designer ;)

Re: A Google Interviewing Story

#109

Post by jdoliner »

irahul wrote: post #86
jdoliner wrote: post #60

Earlier quoted context omitted.

I doubt that the interviewer mentioned the prime number solution due to insufficient cleverness in the original solution. The answered O(n+m) solution actually contains flaws beyond its lack of cleverness. 1) there's no good reason to use a hash map, hashing is useful in maps for mapping an unevenly distributed set from a large an arbitrarily large space to an evenly distributed set from an arbitrarily small space. T…

> 15 seen &= mask( haystack); Shouldn't it be seen ^= mask( haystack); And a personal change would be to define all as: int all = ~(~0 EDIT: For some reasons, asterisk doesn't appear before haystack.

Right you are, fixed now.
Post reply on HN