A Google Interviewing Story • Hacker News Board

Re: A Google Interviewing Story

#21

Post by exit » Sat, Nov 20, 2010, 1:32 AM UTC

nl wrote: post #15

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.

Your anger is misplaced. Characters can repeat, so a boolean array doesn't work. Plus, the story says I mumbled awhile that given the characters were limited to alphabetic (his original specification) that I could use an array instead of a hashtable for some constant time savings but that was about it.

sorry, i don't get how characters repeating affects things

Re: A Google Interviewing Story

#22

Post by mavelikara » Sat, Nov 20, 2010, 1:32 AM UTC

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…

And somehow setting up a "trap" for a future colleague to walk right in to shows great "integrity".

Re: A Google Interviewing Story

#23

Post by exit » Sat, Nov 20, 2010, 1:35 AM UTC

> "Given that our range of characters is limited."

i think what matters is that characters are enumerable, not finite?

Re: A Google Interviewing Story

#24

Post by Oxryly » Sat, Nov 20, 2010, 1:37 AM UTC

jamesaguilar wrote: post #20

Oxryly wrote: post #5

Earlier quoted context omitted.

Even faster is to fill a 32-bit mask with "seen" characters for each string. AND them together and compare result to the mask from the second string.

Maybe. You need 256 bits for all the possible chars, and this solution is perhaps a little less intuitive. Also, the shift + and + cmpz is not necessarily going to be significantly faster than an address lookup + cmpz because of the latency of getting the array from memory or cache. Though it will use less cache space compared to the size of modern caches that's not enough of a win to matter much I would guess.

I was assuming a 26 letter alphabet. At that point the shifting, anding and comparing would take place in registers.

Re: A Google Interviewing Story

#25

Post by dennisgorelik » Sat, Nov 20, 2010, 1:38 AM UTC

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…

There is a limit to how open employee should be. Google actually wants employees to keep things to themselves and not to talk about internal stuff to outside world. 100% honesty would make prospective candidate leak internal Google stuff to the outside world. So it's unlikely that interviewers would set up "integrity traps".

Re: A Google Interviewing Story

#26

Post by firebones » Sat, Nov 20, 2010, 1:38 AM UTC

Oxryly wrote: post #8

lacker wrote: post #7

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

Yeah, I don't get the interest in this answer. It's neat-but-useless.

It's just one anecdote, but it also seems like the kind of thing that happens in companies that grow fast and have trouble maintaining quality in their hiring process. Instead of hiring true cleverness, they hire for someone who feigns the trappings of cleverness (smart enough to regurgitate a "clever" solution that turns out not to be practical in the real world.)

Re: A Google Interviewing Story

#27

Post by Oxryly » Sat, Nov 20, 2010, 1:40 AM UTC

huhtenberg wrote: post #17

Oxryly wrote: post #5

Earlier quoted context omitted.

Even faster is to fill a 32-bit mask with "seen" characters for each string. AND them together and compare result to the mask from the second string.

It would depend on the hardware used. Standard counter-intuitive example (from the game development domain) is how to check if an array of integers has a zero in it. The answer, when all things are considered, is to scan through an entire array making a simple arithmetic for each item and one comparison at the end rather than compare each element. The same may happen with your example. Filling up 32-bit mask might be…

Early termination is the biggest advantage of the array version. The 32-bit mask is probably the fastest possibility since it will reside in a register.

Re: A Google Interviewing Story

#28

Post by extension » Sat, Nov 20, 2010, 1:44 AM UTC

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…

How much are you ever deriving on the fly when answering programming questions? You aren't goint to reinvent computer science on the spot, you're going to apply the vast knowledge and experience you hopefully have. The problem in the story is so basic that I would assume anyone who got it right had run into a similar problem before.

Re: A Google Interviewing Story

#29

Post by rapind » Sat, Nov 20, 2010, 2:00 AM UTC

Stories like this and the comments that follow just reinforces my belief that I am no where near smart enough to work with most of you guys.

Plus I'll never wear leather pants. That can't be comfortable.

Re: A Google Interviewing Story

#30

Post by cletus » Sat, Nov 20, 2010, 2:01 AM UTC

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…

I couldn't disagree more.

Where do you draw the line? What if you'd spent the previous two days reading about graph theory and in doing so had come across a neat network flow problem that co es up almost verbatim in the interview? What's the difference?

Interviews are a filter and not necessarily always accurate or fair. This can go both ways. You can have bad days when your brain freezes. You can have good days when you're asked something you know in your sleep. It doesn't really matter how you know it.

Besides just knowing the solution to something doesn't mean you can give the answer, discuss the solution and analyze other solutions, all of which may come up.