Hacker News Reader

Comment by exabrial | Hacker News Reader

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.

View on HN

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

Yeah, 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.

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

Doesn'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.

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.

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

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

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

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

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

This 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.)

You sound like a guy that quite openly harbor grossly ignorant stereotypes of what you think is an unacceptable culture.

Drat, I knew someone would say that. Thwarted again.

> young skinny-jeans-wearing progressives

> cartoonish, caricatured views of these groups are stereotypes

I cannot tell if this is satire.

Maybe he was referring to the fact that it's O(M) in the worst case where M is the length of the collision list?

The 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

Wouldn'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).

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.

Like 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....) 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).

Totally 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).

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

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

You don't need hash codes to be unique for items in the table so there doesn't need to be any relation between the size of the hash and the size of the table. The time taken by the hash function depends on the size of the keys not the size of the table.

If they're not unique, it will have to linearly search through items with duplicate keys. This situation will begin to approach O(n) time, which isn't good.

Unless you're using an Open addressing scheme like cookoo which ensures constant lookup time in the worst case

If the cost of a hash function is related to anything, it is more usually the number of bits in the input.

I've always used the assumption that objects have pre-calculated/stored hashes

The reason hash computation is traditionally called constant time is because it doesn't change while the hash table grows. Big O describes how run time or memory consumption grows as input grows, and with a hash table, the hash computation typically does not grow.

Calling a hash table O(log2(N)) gets misleading when you measure a hash function's performance, and it doesn't change as the table grows.

So you're right about your technicality, but you're using big-O slightly differently than how everyone else is using it.

The implications are interesting, in that if the hash computation did grow as O(log2(N)), then it would (theoretically) outperform the current typical O(1) hash table implementation, and they would meet only when the table is full.

Another way to see O(1) is that hash computation is always implemented not as a log2(N) function, but is log2(MAX_N), where MAX_N is the size of a full table, and since MAX_N is a constant, the complexity is O(1).

A side note is that not all hash tables are implemented using an array that can hold N items. Some hash tables use linked lists instead of re-hashing for collisions, meaning that your array can be arbitrarily less than N in size, meaning that it is definitely possible to have a hash function that takes less than log2(MAX_N) time. In that case, insertion time becomes explicitly greater than O(1).

I'm not following your logic here:

"The implications are interesting, in that if the hash computation did grow as O(log2(N)), then it would (theoretically) outperform the current typical O(1) hash table implementation, and they would meet only when the table is full."

How would O(log n) ever out perform constant time, O(1)? Could you elaborate?

This is and always has been an important part of understanding what big-O notation actually means. O(1) means constant time, it does not tell you what the constant is. The constant can be large.

In this case, if your hash always takes 64 bit values and always produces 64 bit values, it is O(1). If your hash were O(log2(N)), then your hash function with an empty table would do 1 bit worth of work, and would do only one operation. But when the table grew to contain 1,000 elements, it would do 10 bits worth of work.

The O(log2(N)) algorithm with N < 2^64 is always faster (in theory) than the O(1) algorithm that does a constant 64 bits of work.

The O(1) algorithm pays off in spades for N >> 2^64, it will become much faster than the logarithmic one, but for small N, log(N) is smaller than 64.

Right, a constant i.e unchanging amount of work.

I usually think of hashtables though as being O(1) in referring to the look up(amortized) and not the hash code itself.

Yep, and a hash table's get is O(1) amortized even when you include the hash function itself, simply because the hash function doesn't change as the hash table grows. @rand_r is right that the hash function is doing C * log2(MAX_N) operations, but that doesn't actually affect the big-O metric, it only affects the run time. :P

Indeed, thanks for the clarification.

> 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

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

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

Reply on news.ycombinator.com