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

91–100 of 122 posts

Re: A Google Interviewing Story

#91

Post by nl »

doosra wrote: post #54
ahilss wrote: post #16

Earlier quoted context omitted.

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…

A Bloom filter ( http://en.wikipedia.org/wiki/Bloom_filter ) might work well in this case.

Unlikely.

A Bloom filter is usually used where representation size is important, because it can be orders of magnitude smaller than a hashtable. It doesn't perform very quickly though, because of the hashing operations needed during insert.

A Bloom filter is great for P2P search applications for example. Then peers can pass Bloom filters around, and an initial search can happen locally. If it succeeds then the search can ask the remote host if the file actually exists. The frequency those remote requests will fail depends on the number of false positives the Bloom filter is configured to give (ie, a function of its size).

Re: A Google Interviewing Story

#92

Post by jerhewet »

unoti wrote: post #49
akeefer wrote: post #33

I 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…

Agreed. The prime-number-division thing is a great answer... FOR SPOCK. Who wants to read code that does that kind of stuff... converting strings in to prime numbers? How about: code it in a reasonable, readable way, and come back and optimize it if and when it needs optimizations. People that code things in the cleverest way, even when it's not needed, drive me batty. I'd far rather see a developer cross 10 items of…

Upvote ^10 if I could.

Re: A Google Interviewing Story

#93

Post by vilya »

zeraholladay wrote: post #34
nhashem wrote: post #18

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

I've interviewed a fair few people in my time. First impressions count, but they can and do get overturned in the course of the interview. With hindsight, although it was never a conscious choice, if someone made a good first impression I tended to give them an easier ride with the questioning and they were more likely to come out looking like a potential hire as a result.

Re: A Google Interviewing Story

#94

Post by jpeterson »

jakevoytko wrote: post #37
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 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: "ಠ_ಠ"

The array is a pretty obvious solution (to me, anyways).

Well, I guess not everyone is an amazing genius like you.

Re: A Google Interviewing Story

#95

Post by user24 »

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.

that's outside the scope of the problem. (which is why I really dislike these kinds of tests, because you can't win - if you don't consider unicode the interviewer says "ahh, but what about unicode" and if you do the interviewer says "ahh, but that's outside the scope of the problem".)

Re: A Google Interviewing Story

#96

Post by [deleted] »

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.

[deleted]

Re: A Google Interviewing Story

#97

Post by user24 »

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

that was a genuine question. I think I'm right, but I might not be. Judging by the upvotes it looks like I am, but I'd like someone to come forward and say "Yes, that's correct" explicitly.

Re: A Google Interviewing Story

#98

Post by mrud »

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

Yes, that's correct.

Re: A Google Interviewing Story

#99

Post by jdp23 »

mrshoe wrote: post #13

If 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…

A friend of mine interviewed at Microsoft sometime in the mid-90s. They offered him a job, but he declined it. They interviewed him again a few years later, and one of the questions had come up in his previous interview. He said "in fairness I have to disclose that I was asked this in my last interview -- and they must have liked my answer because they offered me the job." For some reason the interviewer was so flustered that the rest of the questions were all softballs :-)

Your mileage may vary.

Post reply on HN