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

71–80 of 122 posts

Re: A Google Interviewing Story

#71

Post by jamesaguilar »

Oxryly wrote: post #24
jamesaguilar wrote: post #20

Earlier quoted context omitted.

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.

True, although if there are lower case letters too it could become a problem. At any rate, I'm not sure that the register aspect would improve speed significantly because of the latency of getting the string from main memory. You're still going to get pipeline stalls as you reach portions of the string that are not in the cache.

Re: A Google Interviewing Story

#72

Post by baguasquirrel »

jemfinch wrote: post #58
baguasquirrel wrote: post #43

Earlier quoted context omitted.

The dinging people for not-clever-enough solutions feels like hazing. It's less about competence than about ego. The most important thing in an interview is to make sure the person's level of skill is at least as big as their conception of their skill.

The most important thing in an interview is to make sure the person's level of skill is enough to be your coworker. Their conception of their skill doesn't matter. Programmers who know they're bad programmers are still bad programmers.

Sure but you at least have a chance at helping them out and moving them up. To some extent is culture and happenstance. Sometimes you get off on the wrong foot and you're on each other's nerves. But attitude and work ethic are like multipliers that can go negative.

Re: A Google Interviewing Story

#73

Post by _cbsz »

mdwrigh2 wrote: post #42
TARMAP wrote: post #14

I hate such stupid tricks, frankly a hash table or an array for a restricted domain is way faster, since the whole data structure gets cached on the L1. I can solve the same problem by using statistical thermodynamics, and show its only o(1), since each string is a configuration of the system and finding common alphabets is like finding degenerate states.

How could you do this in O(1)? Or are you saying you can get a probably right answer in O(1)?

It's impossible to do in O(1) in the worst case, because you have to at least examine all the input (e.g., if the input matches the regex AA*B.)

Re: A Google Interviewing Story

#74

Post by ericd »

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.

Ahh, sorry, good answer. Much simpler than finding an arbitrary number of primes.

Re: A Google Interviewing Story

#75

Post by barrkel »

blinks wrote: post #64
jakevoytko wrote: post #37

Earlier quoted context omitted.

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: "ಠ_ಠ"

Note: "Say you have one string of alphabetic characters" The array of bools, bitmap (remember 32-bit int!), hash map; all are the same basic deal, easy to understand code, etc. Any would probably be fine, imho. Hash map would be my initial implementation, though, if only because I don't know where it would be used, and the map will be immediately understood.

I come from a compiler background. When I hear "alphabet" I don't think a-z - I think of an arbitrary set of distinct symbols that can be arranged into a string.

Re: A Google Interviewing Story

#76

Post by TheNewAndy »

barrkel wrote: post #75
blinks wrote: post #64

Earlier quoted context omitted.

Note: "Say you have one string of alphabetic characters" The array of bools, bitmap (remember 32-bit int!), hash map; all are the same basic deal, easy to understand code, etc. Any would probably be fine, imho. Hash map would be my initial implementation, though, if only because I don't know where it would be used, and the map will be immediately understood.

I come from a compiler background. When I hear "alphabet" I don't think a-z - I think of an arbitrary set of distinct symbols that can be arranged into a string.

Yes, but even in compiler land, you don't say "alphabetic" to mean a symbol taken from your particular alphabet (since that is practically a given... a symbol outside the alphabet might as well not exist).

Re: A Google Interviewing Story

#77

Post by tomerico »

jdoliner wrote: post #60
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…

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.

Re: A Google Interviewing Story

#78

Post by TheNewAndy »

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.

Doing it this way will use the optimal amount of memory (in the worst case) (assuming an O(n+m) answer). There are exactly 26 bits of state that need to be tracked (where "bit" is used in the information theoretic sense of the word). If you choose to store this state as 26 actual bits, then you win.

Multiplying together the first 26 primes requires that you can store a number up to 232862364358497360900063316880507363070. log2 of that number is about 127.5. So you need 128-bits of storage.

Essentially, the correct solution is to sort both lists, and then do a single pass through checking for unique items in one list. Once you have this solution, you can do some micro-optimizations: - note that the set of symbols is limited, so you can use a counting sort (or other non comparison based "sort") - note that the sorting function doesn't need to be an actual sorting algorithm, and may discard duplicates.

If you apply these two optimizations, you should end up with the bit-field approach (or maybe a slightly more memory hungry one that doesn't store stuff in individual bits... but algorithmically it doesn't bring anything new to the table).

For some reason, a minority of people are then thinking that a further optimization is to use a more inefficient data structure in the sorting algorithm for storing whether or not a letter has been seen. This has the effect of a more expensive read operation, write operation, more memory usage and provides no other benefits.

Re: A Google Interviewing Story

#79

Post by enjo »

firebones wrote: post #56
zeraholladay wrote: post #34

Earlier quoted context omitted.

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.

Never underestimate the influence of narcissism in hiring, manifested as the kind of blink decision you describe. Teams in a large company develop a personality and culture that more often than not extends to attributes that have less to do with skill and competence and more to do with similarity of physical characteristics and outside interests. (The degenerate case is flat out nepotism, but the more typical case is…

My go to story to describe this involves a guy who was a EMT. He spent his interviews describing his life as an EMT, and rarely dealing with any meaningful technical discussions. He was offered a ton of jobs....

I saw something similar with a badly underqualified sys-admin who had been in marine recon before embarking on a technical career. He had zero issues finding a high paying job.

Re: A Google Interviewing Story

#80

Post by jamesaguilar »

bluesnowmonkey wrote: post #10
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.

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.
Post reply on HN