> "Given that our range of characters is limited." i think what matters is that characters are enumerable, not finite?
Yes, if your code is going to run on an Turing Machine that actually has infinite tape.
A Google Interviewing Story
61–70 of 122 posts
Re: A Google Interviewing Story
#62Earlier quoted context omitted.
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…
Okay, how was it a great answer? Unless I'm miscounting from all the jet lag, it's still O(n+m), only much more convoluted (not to mention slower, since you have a constant factor from all the multiplications/divisions). And seriously, primes? Why not powers of two? Gah, so much fail in that answer, but the worst thing is that the guy proposed it as a better alternative, and the interviewee admired it !
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.
Re: A Google Interviewing Story
#63Earlier quoted context omitted.
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".
100% honesty would make prospective candidate leak internal Google stuff to the outside world. That doesn't make any sense. open != honest. Two different things. It's not dishonest to obey a Non Disclosure Agreement, and so you can be perfectly honest person and still not be "open" about matters which you are not authorized to reveal.
You forgot about context of my comment.
I used "100% honesty" in the sense of "never lie and AND be open".
Please re-read original context:
"If you are ever asked an interview question which you've already answered in a previous interview, you should tell the interviewer immediately."
"Not talking about your past interview experience" has about the level of openness as "not talking about your corporate experience".
Re: A Google Interviewing Story
#64Angry 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: "ಠ_ಠ"
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.
Re: A Google Interviewing Story
#65Earlier quoted context omitted.
Okay, how was it a great answer? Unless I'm miscounting from all the jet lag, it's still O(n+m), only much more convoluted (not to mention slower, since you have a constant factor from all the multiplications/divisions). And seriously, primes? Why not powers of two? Gah, so much fail in that answer, but the worst thing is that the guy proposed it as a better alternative, and the interviewee admired it !
Powers of two wouldn't actually work there. Using primes lets you use division as a test for presence in the original set. The task is 'detect presence in the set', and integers are uniquely identified by their prime factorization. Powers of two would just give you another power of two. That wouldn't actually preserve the information you're looking for. Consider an original string 'bb', and a test string 'c'. With po…
If using powers-of-two, you'd bitwise-OR rather than multiply the values-per-character. Simpler op, and your accumulated value per string never rises (in the 26-letter case) above 2^26.
Re: A Google Interviewing Story
#66The 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.
i think it is a joke, you guys here already mentioned multiplication/division are expensive operations, so a simple hash just works well. and who care the complicated way if the simple way just makes the job done nicely. programming is an art.
Re: A Google Interviewing Story
#67Earlier 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.
I haven’t tried a Bloom filter, but I think for my application, the simple bit array might give better performance. The nice thing about the bit array is it works great on the worst-case. After the user has typed in 3 or 4 characters of their query, the search space has been narrowed enough where the performance isn't an issue. It’s that first or second character when the search space is large that gives problems. Using the bit array in the single character case, the 1 to 1 mapping of characters to bits gives the result directly.
Re: A Google Interviewing Story
#68Earlier quoted context omitted.
Okay, how was it a great answer? Unless I'm miscounting from all the jet lag, it's still O(n+m), only much more convoluted (not to mention slower, since you have a constant factor from all the multiplications/divisions). And seriously, primes? Why not powers of two? Gah, so much fail in that answer, but the worst thing is that the guy proposed it as a better alternative, and the interviewee admired it !
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.
Re: A Google Interviewing Story
#69Earlier quoted context omitted.
Powers of two wouldn't actually work there. Using primes lets you use division as a test for presence in the original set. The task is 'detect presence in the set', and integers are uniquely identified by their prime factorization. Powers of two would just give you another power of two. That wouldn't actually preserve the information you're looking for. Consider an original string 'bb', and a test string 'c'. With po…
If using powers-of-two, you'd bitwise-OR rather than multiply the values-per-character. Simpler op, and your accumulated value per string never rises (in the 26-letter case) above 2^26.
Yep, that's what I meant, thanks. Powers-of-two is just for getting the correct bits.
Re: A Google Interviewing Story
#70Earlier quoted context omitted.
sorry, i don't get how characters repeating affects things
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.