9 ms·
A Google Interviewing Story
- jamesaguilar 16y agoAngry 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.
- ajays 16y agoExactly. When your domain is restricted (characters or small ints), then why use a hashtable? Use an array. If initializing an array is a concern, use a smartarray.
- Oxryly 16y agoEven 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.
- huhtenberg 16y agoIt 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 more expensive than to flip an element in a boolean array. That's not even considering that the array option allows for early termination of the second loop.
- Oxryly 16y agoEarly 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.
- jamesaguilar 16y agoMaybe. 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.
- Oxryly 16y agoI was assuming a 26 letter alphabet. At that point the shifting, anding and comparing would take place in registers.
- jamesaguilar 16y agoTrue, 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.
- Oxryly 16y agoYeah, the registers will only be faster than manipulating some sort of bool array. Reading the original string (with associated cache stalls) will certainly be necessary.
- TheNewAndy 16y agoDoing 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.
- bluesnowmonkey 16y agoOh really? How much faster would that be?
- jamesaguilar 16y agoAs much faster as the length of the second string times the difference between an address lookup and a hash table lookup.
- bluesnowmonkey 16y agoWhich 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?
- nl 16y agoYour 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.
- exit 16y agosorry, i don't get how characters repeating affects things
- tedunangst 16y agoIf there are 3 As in the first string and 4 in the second, it fails. A boolean value can't count to 3.
- jamesaguilar 16y agoMaybe 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.
- tedunangst 16y agoThis is that different problem. The author's description is muddy, but you do need the counts.
- bfung 16y agoit doesn't matter if characters are repeated. Let's assume ascii characters, so 'A' = 65 in decimal. If you make an array, T[], where T[65] = 1 if 'A' exists and 0 if 'A' didn't exist in the first string, you can run through the 2nd string to check if T[65] was true (1) or false (0), telling you if the character in the 2nd string appeared in the first. Same thing as the hashtable. I think that's what was meant by boolean array.
- ahilss 16y agoI 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 it through this filter.
- ssp 16y agoThat's pretty clever. It can be tempting in such a situation to immediately go for the big guns (patricia trees or whatever), but often a simple hack like that gives a lot more bang for the buck.
- doosra 16y agoA Bloom filter (http://en.wikipedia.org/wiki/Bloom_filter http://en.wikipedia.org/wiki/Bloom_filter) might work well in this case.
- ahilss 16y agoI 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.
- nl 16y agoUnlikely. 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).
- user24 16y agothe boolean array indexed by char effectively is a hashtable isn't it? where the hashing algorithm is index = ord(theChar).
- user24 16y agothat 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.
- mrud 16y agoYes, that's correct.
- user24 16y agothanks :)
- alextp 16y agoThis 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.
- jakevoytko 16y agoThe 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: "ಠ_ಠ"
- blinks 16y agoNote: "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.
- barrkel 16y agoI 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.
- TheNewAndy 16y agoYes, 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).
- jpeterson 16y agoThe array is a pretty obvious solution (to me, anyways). Well, I guess not everyone is an amazing genius like you.
- ajays 16y agoI have been in a similar situation, where one interview's curveball ended up being asked in a subsequent interview. I went through the same emotions as the author (including resisting the urge to grin from ear to ear). But like an idiot, I answered with the trick answer right away (though I was calm about it). I then told the interviewer that I had learnt it in a previous interview. It turned out he was looking for the clever answer too; and he was disappointed that I knew it. Maybe he felt I wasn't sufficiently "excited" about the clever answer, but I never got the job. Which is not too bad, since that outfit wasn't my first choice anyways.
- kabdib 16y agoMultiplication and division are o(log n) operations.
- lacker 16y agoThe 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.
- Oxryly 16y agoYeah, I don't get the interest in this answer. It's neat-but-useless.
- firebones 16y agoIt'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.)
- deleted 16y ago[deleted]
- psadauskas 16y agoYeah, seems like dividing ints would be a much more expensive operation than comparing them.
- jules 16y agoCan you explain what representation you use to get multiplication by a constant in O(log n)? Wouldn't it be at least O(n) for the standard bignum representations, making the algorithm O(n^2). Multiplying n primes together creates an O(n) digit number. Multiplying an O(n) digit number by a constant is an O(n) operation. So essentially we're doing an O(n) operation n times, hence O(n^2). The smartest representation that I can think of for the numbers would be to store the prime factor exponents in an array, which would essentially transform the algorithm into the array based version. For example 120 = 2^3x3x5 would be represented as {3,1,1,0,0,...}.
- aaronbrethorst 16y agoMy last internship in college involved working on thermostat systems for Honeywell with a bunch of people who had been there their entire professional careers. I didn't have much interest in becoming a lifer and ended up interviewing with a couple other companies, including Microsoft. I interviewed for a Program Management position in the Visual Studio group. My first interview was with the Design Manager for the VS product line. Her final question for me was about building an effective temperature control system for a new house. I launched into a 5 minute analysis of the advantages and disadvantages of a wide range of HVAC systems, obvious ramifications from open floor plans, and so on. A month later, we sat down for lunch as co-employees for the first time, and I told her the whole story. She got a big laugh out of it. I guess she didn't realize that's what I'd spent the last few months working on.
- philwelch 16y agoYour interviewer didn't read your resume?
- aaronbrethorst 16y agoShe did, but I hadn't been super-specific about what I'd been working on.
- aaronbrethorst 16y agoShe did, but I hadn't been super-specific about what I'd been working on.
- mrshoe 16y agoIf 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 you know. So, more importantly than the risk of getting caught, if you recite an answer from memory and pretend that you're deriving the solution on the fly, you're lying to your future coworker.
- mavelikara 16y agoAnd somehow setting up a "trap" for a future colleague to walk right in to shows great "integrity".
- dennisgorelik 16y agoThere 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".
- dotBen 16y ago100% 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.
- dennisgorelik 16y agoYou 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".
- TARMAP 16y agoI 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.
- nhashem 16y agoI 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 subset of questions over and over again. Am I being hired because they've made a true evaluation of my technical skills, or was I just serendipitously lucky to have heard the answer to how those 5 pirates are going to split those 100 gold pieces?
- zeraholladay 16y agoProbably 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.
- firebones 16y agoNever 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 a team of people fitting a core profile--5'10" 30-something males from second tier colleges, or taller-than-average mustachioed conservatives.) Most large company hiring practices are not so much a selection of specific traits as they are a filter for ensuring a lack of negative traits. When you factor in the bias of narcissism in interviewers, you'll get competent people who are skillful at reflecting the interviewers' traits back at them (such as the author, who didn't demonstrate incompetency with his first answer, but aced the interview by reflecting the cleverness the interviewer must have self-identified with as "Google material".) After a certain point, four or seven or nine layers of interview will certainly guarantee the incompetent ones don't get through, but at the same time it will also select for the kind of highly adaptable social personality that is often found in political operators.
- exit 16y ago> "Given that our range of characters is limited." i think what matters is that characters are enumerable, not finite?
- endtime 16y agoYes, if your code is going to run on an Turing Machine that actually has infinite tape.
- rapind 16y agoStories 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.
- hardik988 16y agoWell, look at the bright side. You're now smarter 'by this question' - You can be rest assured that if you're ever asked this question, you'll be able to answer it.
- zeraholladay 16y agoPersonally, I would be more inclined to hire a person picking the "throw it in a hash and look it up" solution over any more complex solution. My reasoning is that bad programmers tend to get lost in nuance, or don't understand a problem. Good programmers tend to reason through the proportionate value of a problem. I'm not saying nuance is always a bad thing, but it's probably not what your company is developing unless you work for a math department.
- akeefer 16y agoI 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, and that other competent engineers will understand. If there's no other good solution, or if every bit/cycle matters, then you get to try to be clever, but that happens pretty rarely. I've seen way, way too many problems caused by people using clever solutions for problems that had straightforward-but-less-fun solutions. (And as has been pointed out plenty of times already here, the clever solution in this case is less optimal than a more straightforward one would be). If an interviewer seemed intent on proving they were more clever than me, or on trying to get me to throw out unnecessarily-clever solutions to straightforward problems, it would be a pretty big turnoff.
- baguasquirrel 16y agoThe 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.
- jemfinch 16y agoThe 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.
- baguasquirrel 16y agoSure 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.
- ronnier 16y agoI was asked that exact same question over a phone interview. One of the most interesting questions given to me was, write an algorithm such that given four colors and a rectangle, fill the rectangle with a gradient using a color in each corner. After the fact it wasn't very hard, but having never thought about such a problem, it was pretty difficult white boarding it out. It was a pretty good question because I think that most people aren't thinking or preparing for such a problem, instead opting to study arrays, linked lists, trees, sorting algorithms and running time. You really get to see how a person thinks with it.
- wazoox 16y agoHum, Guy's solution is really terrible, division, multiplication and modulo are very expensive operations, and completely unnecessary here. This is basically a case of "I'm clever and you must think like me to be in my team". Uh no thanks.
- ibagrak 16y agoI've had something similar happen to me at a Microsoft interview. The interviewer asked me a question I explicitly knew the answer to, and it too wasn't "my" answer to the problem but the one I've heard in another interview. So I just told him: "I know this one. Can you ask me something else?" He told me he appreciated my honesty, and didn't have any other questions. I got the job.
- Charuru 16y agoI kind of wish that he didn't emphasize the 'women engineer', would've kinda gotten the picture when he starts using she. Maybe we'll get there someday...
- wingo 16y agoLeather pants turn a good story into a great story.
- random42 16y agoThe point of the story is not the actual problem that author had to solve, which we have been discussing (but again, its _hacker_ news, after all :-)), but basically to tell how interviewing experience, even at which you fail, prepare you for better.
- lwhi 16y agoLeather pants in an academic setting always makes me think of Jeff Goldblum in Jurassic Park.
- lwhi 16y agoI 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.
- antirez 16y agoIn 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.
- deleted 16y ago[deleted]
- Aleran 16y agoIt is strange how every time someone interviews at Google they feel compelled to write "their" story and share it with the internet. How many stories like this are out there now? Hundreds?
- skybrian 16y agoI'm guessing that the guy in the leather pants probably got the idea from reading about Godel numbering. If you're interested in this, you might like this book: http://www.amazon.com/Godels-Proof-Ernest-Nagel/dp/0814758169 http://www.amazon.com/Godels-Proof-Ernest-Nagel/dp/081475816...