7 ms·
I once really wanted to work for Google, but after my in person interviews I realized I would never fit in. I was instantly judged for my soft Midwestern accent
by exabrial 10y ago
I once really wanted to work for Google, but after my in person interviews I realized I would never fit in. I was instantly judged for my soft Midwestern accent and dress shirts, while the guy in skinny jeans and explained to me that Java's HashMap.get() was not 0(1) and asked if I was taught that in my non-Stanford education. (It is btw, feel free to analyze the implementation)
For a place that claims to be culturally diverse, I realized there was a hidden list of acceptable cultures, and mine was not one of them. I politely declined the offer and decided to stay a bit closer to home.
- whack 10y agoI live in NYC and most of the Googlers I meet are from the Midwest or East Coast. It sounds to me like you happened to end up with an idiotic interviewer. I would personally chalk that up to bad luck more so than company culture.
- ianlevesque 10y agoYeah, I'm not a Googler but the only one I know had no formal CS education and wore a full suit to his interview. Just study algorithms like mad and go for it if it's what you want. Technical merit will get you in.
- justinhj 10y agoWhen a company selects someone to interview a candidate they're also choosing that person to represent and sell the company. If that person turns out to be rude and condescending then I chalk that up to more than bad luck.
- walshemj 10y agoDoesn't Google train its interviewers I worked for a large company and before you could interview anyone there was a 2/3day course you had to pass.
- kmicklas 10y agoIn my experience Google NYC attracts a lot of people who are very cynical about the stereotypical bay area tech culture. I get the impression there is a lot less cool-aid being drunk here but then again I've never lived in the bay so I can't really compare.
- dragonwriter 10y ago> In my experience Google NYC attracts a lot of people who are very cynical about the stereotypical bay area tech culture. I get the impression there is a lot less cool-aid being drunk here but then again I've never lived in the bay so I can't really compare. Maybe its just a different flavor of Kool-Aid. Cynicism about X is often as much of an irrational orthodoxy as X is.
- beisner 10y agoNot to be pedantic, but while the computational complexity of the map.get() function is O(1), meaning that the number of computational steps executed is constant with the size, the runtime complexity is often O(f(N)), because cache fetches and disk fetch latency increase with the number of items stored, meaning that the amortized time of get() might be longer for larger datasets. This doesn't invalidate your experience at all - the interviewer may or may not have been talking about this, and there may well be cultural issues there - but I learned this interesting distinction recently, figured I would pass it on.
- UK-AL 10y agoI thought the whole point of O Notation is that your not thinking about low level operations like Disk io or caching.. Just the growth of the operations performed.
- pjlegato 10y agoComputational complexity vs. runtime complexity: while the details are irrelevant for computational complexity, as you say, the runtime complexity is a different matter, because the execution environment (disk, cache, etc.) has been optimized to deliver better performance for certain types of operations. In the real world, it may thus be better to use a computationally more complex algorithm than a computationally simpler one in certain cases, if you happen to have a system that delivers big enough optimizations for the complex algorithm.
- cableshaft 10y ago> ...asked if I was taught that in my non-Stanford education... Anyone who said that to me would seriously risk a sock to the jaw from my non-Stanford educated fist, interview or no. That is an incredibly rude and condescending thing to say. Thankfully that guy didn't interview me during my interview at Google, and my fist remained wrapped around my dry-erase marker instead.
- rand_r 10y agoTotally pedantic, but no HashMap.get function is O(1). In order do a look-up, you have to compute the hash, whose size is at least log2(n).
- conjectures 10y agoNot being funny, I actually don't know: Is the n in log2(n) the size of thing you're hashing? AFAIK the O(1) statement is referring to how many things you have hashed.
- rand_r 10y agoIn context, n is the number of things in the hashmap. You need log2(n) bits per item to store n unique items. So the hash function is operating on an input of log2(n) bits. There's no way the hash function takes less than log2(n) time to work on log2(n) bits of input.
- relics443 10y agoMaybe he was referring to the fact that it's O(M) in the worst case where M is the length of the collision list?
- pjlegato 10y agoThis sounds more like a feature of the SF Bay area tech scene rather than Google in particular. Many young skinny-jeans-wearing progressives here quite openly harbor grossly ignorant steroetypes of a wide variety of unacceptable cultures: the south, the midwest, Republicans, Christians, and conservatives, among others. When challenged, they typically deny that their cartoonish, caricatured views of these groups are stereotypes, and insist that that's simply the way it is. Just wearing a button-down shirt (or, God forbid, a tie) is more than enough to stigmatize you as "one of them" and get you instantly ostracized (while they simultaneously loudly trumpet the value of diversity and tolerance.)
- cc81 10y agoYou sound like a guy that quite openly harbor grossly ignorant stereotypes of what you think is an unacceptable culture.
- pjlegato 10y agoDrat, I knew someone would say that. Thwarted again.
- ng12 10y ago> young skinny-jeans-wearing progressives > cartoonish, caricatured views of these groups are stereotypes I cannot tell if this is satire.
- kt9 10y agoThe reason the Java HashMap get() is not O(1) is because of separate chaining. The HashMap handles hash collisions by adding all colliding entries to a Linked List and lookups have to hash to the correct bucket and then iterate over the linked list in that bucket. So the complexity of a get() is O(1)+O(k) where k is the number of items in the LinkedList. https://en.wikipedia.org/wiki/Hash_table#Separate_chaining https://en.wikipedia.org/wiki/Hash_table#Separate_chaining
- jschmitz28 10y agoWouldn't this just simplify to O(n)? Consider a case where the keys are objects whose hashcode() is overridden to return a constant (while equals() still uses reference equality from Object.equals).
- justinhj 10y agohttp://stackoverflow.com/questions/4553624/hashmap-get-put-complexity http://stackoverflow.com/questions/4553624/hashmap-get-put-c... It's a dumb question to be authoritative about because there are different implementations of hashmap and hashcode meaning that you can't guarantee the runtime complexity. According to the SO answer above Java8 will be mostly O(1) but full buckets may be stored as trees meaning that they will be O(log n). But as the answer says "So no, O(1) certainly isn't guaranteed - but it's usually what you should assume when considering which algorithms and data structures to use." The interviewer could have explored the candidates knowledge of how hashmap is implemented, or could be implemented, which would be more rewarding than insulting and gloating.
- rb808 10y ago> Java's HashMap.get() was not 0(1) and asked if I was taught that in my non-Stanford education. (It is btw, feel free to analyze the implementation) It is O(1) if the hashmap is sparsely populated but if there are hash collisions the items are stored in a list (tree from 8) so is not O(1) in worst case
- dragonwriter 10y ago> It is O(1) if the hashmap is sparsely populated With a finite number of buckets (which is inherent to hashmap), asymptotic performance will never conform to the "sparsely populated" constraint, so its O(n). (That its concrete performance is roughly constant-time within certain size bounds in non-pathological cases is important knowledge, too, though.)
- Klockan 10y agoHashmap operations are O(n) and there is no way to reduce it since it is impossible to get a collision free hash. Being ignorant about this is a good reason not to hire someone since they likely have similar knowledge holes everywhere.
- exabrial 10y agoLike I said, feel free to analyze the implementation (Or just look in the JavaDoc (https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html https://docs.oracle.com/javase/8/docs/api/java/util/HashMap....) Given the hash function was known (it was a String) his answer of O(n) is incorrect, it is indeed O(1). If you violate the API and put something like "return 1" as your hashcode() you will get O(n), but this was not the case for this interview question. I think the big misunderstanding in most of these answers is assuming a fixed amount of buckets are used in Java's implementation. That is not correct, the put() method will rehash your table if it grows too big. (meaning that on average put() is O(1) but has a very real possibility of being O(n).