Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to Crack the Toughest Coding Interviews

gklst.tumblr.com

Post reply on HN
Print view View original

71–80 of 144 posts

Re: How to Crack the Toughest Coding Interviews

#71

Post by nandemo »

glaak wrote: post #62
nandemo wrote: post #46

Earlier quoted context omitted.

You seem to be disagreeing with something I haven't said. I'm simply describing my experience interviewing at Google: I didn't give an optimal solution to a couple of problems, and didn't get an offer. So I infer that the other items mentioned in the article don't matter as much for getting a job at Google .

You also did not wear a pink and blue striped hat, and did not get an offer. And yet, you seem to not connect your failure to wear a pink and blue striped hat with your failure to get an offer. I'd suggest you read the section in the article about how you're evaluated. Yes, how optimal your solution is matters -- of course it does. This doesn't mean that you have to get an optimal answer though. You have to do better…

> You also did not wear a pink and blue striped hat, and did not get an offer.

I don't understand the point of this quibbling.

Say I was asked 30 questions; I missed 3 of them and didn't get hired. It's a reasonable to assume that these 3 questions were considered important in the general assessment.

> You have to do better than the majority of candidates (maybe ~80% of candidates).

I know, I said I read your book. ;-)

But that doesn't substantially change the story, it means it's likely other candidates got the optimal solution or got closer to it.

Of course this is all based on my self-assessment, since Google doesn't provide any sort of feedback post-interview. But I'm pretty confident that I went well in the other questions. 4 out of 5 interviewers were pretty nice in giving feedback during the interview, even if indirectly. E.g. they'd ask progressively more involved questions on the same topic, so I more or less knew when I had answered the previous questions correctly.

> Additionally, you seem to assume that since (according to you) getting the optimal answer is necessary, that it must also be a sufficient condition. That's obviously false.

No, I haven't made any such assumption. I only assume that getting the optimal answer was the "high bit" in my case.

Apparently this works for Google, and unlike other people who have failed to get the grapes, I don't call them sour.

Re: How to Crack the Toughest Coding Interviews

#72

Post by Someone »

jsolson wrote: post #32
haberman wrote: post #17

> Given a cube with sides length n, write code to print all possible paths from the center to the surface. What is a path through a cube? This seems like some weird combination of graph theory and geometry.

Perhaps they're assuming that the cube is a set of integral points and they want you to count lattice paths. This is trivial in 2-space (e.g., give me the number of paths that go from (0,0) to (5,5) by going only up or right one point with each move (that is, each move is either (0,1) or (1,0))). However, I vaguely recall counting lattice paths in 3-space being a wickedly hard problem with no known polynomial time so…

"I vaguely recall counting lattice paths in 3-space being a wickedly hard problem with no known polynomial time solution."

I think you can easily write the recursion:

  p(x,y,z) = p(x-1,y,z) + p(x,y-1,z) + p(x,y,z-1)
Leave out the term with x-1, y-1, or z-1 for the edge cases for x, y, and/or z equal to zero.

With that in hand, it is easy to compute all values bottom up, starting with those where x+y+z = 0, 1, 2, etc.

Definitely fewer than (x+y+z)^3 values to compute, all of them in O(1) (disregarding cases where the numbers become bignums)

Generalization to any number of dimensions seems easy, too.

A closed form solution, that might be harder.

Re: How to Crack the Toughest Coding Interviews

#73

Post by timr »

shrughes wrote: post #60
timr wrote: post #56

Earlier quoted context omitted.

A hash table lookup is O(n), where n is the number of elements in the table. They have amortized constant time lookup (i.e. constant time in the average case).

Or it's O(log n). Depends on how collisions are handled.

If you use a balanced tree instead of chaining or probing, sure. But, of course, nobody ever does that in practice, because the complexity isn't justified by the theoretical gains.

Point was, worst-case time complexity isn't constant. I'd be happy to see more people get that right in interviews.

Re: How to Crack the Toughest Coding Interviews

#74

Post by lexandstuff »

ionwake wrote: post #19

Am in the only 30 year old coder here, who earns around £300 a day coding, but would fucking die in one of these interviews?

Well, I'm 25. But I'm also a well paid developer (early six-figures in Melbourne, Australia) who would be pretty hopeless in these interviews.

Re: How to Crack the Toughest Coding Interviews

#75

Post by haberman »

jhartmann wrote: post #38
Swizec wrote: post #8

I shared my experience in a blogpost: http://swizec.com/blog/inside-a-google-onsite-interview/swiz... A few days ago I finally realized why they said I'm not good enough at big-O to play with them (despite saying my coding was excellent). For some reason I had a mental block that day and wanted to implement hash tables as prefix trees every single fucking time . I have no idea why. Of course I know a hash table is O(…

Just my two cents, Well hash tables might be O(1), but depending on the circumstance they are used in, how they handle collisions, implementation details and the quality of the hashing algorithm they can see real world performance that is not O(1). Inserting into a hash table can cause the hash table to expand, if the hash table is too small you will get collisions, etc. etc. Some choices of hash functions are actual…

> Some choices of hash functions are actual O(n) instead of O(1)

I think you're getting your n's confused. O(n) in the context of a collection applies to the size of the collection, not the size of the keys. Nearly all hash functions for strings are O(n) in the size of the string. This doesn't mean the hash table is O(n) for lookups.

Re: How to Crack the Toughest Coding Interviews

#76

Post by arjn »

haberman wrote: post #17

> Given a cube with sides length n, write code to print all possible paths from the center to the surface. What is a path through a cube? This seems like some weird combination of graph theory and geometry.

The first thing I thought was , this may be a trick question, since there are an infinite number of paths from the center to the surface. I think the problem statement needs a bit more detail.

Re: How to Crack the Toughest Coding Interviews

#77

Post by haberman »

timr wrote: post #56
Swizec wrote: post #8

I shared my experience in a blogpost: http://swizec.com/blog/inside-a-google-onsite-interview/swiz... A few days ago I finally realized why they said I'm not good enough at big-O to play with them (despite saying my coding was excellent). For some reason I had a mental block that day and wanted to implement hash tables as prefix trees every single fucking time . I have no idea why. Of course I know a hash table is O(…

A hash table lookup is O(n), where n is the number of elements in the table. They have amortized constant time lookup (i.e. constant time in the average case).

Hash tables, in general, have average constant time lookup. Only some hash tables have amortized constant time lookup.

An amortized bound is a bound on the total cost of a sequence of operations. Loosely speaking, it guarantees that you can't keep hitting the worst case indefinitely. An average bound is averaged over all possible inputs, but doesn't protect you against hitting the worst case over and over.

Re: How to Crack the Toughest Coding Interviews

#78

Post by gutnor »

suyash wrote: post #53
ionwake wrote: post #19

Am in the only 30 year old coder here, who earns around £300 a day coding, but would fucking die in one of these interviews?

you get paid daily..what kind of company is this?

Contracting in the UK. You are either paid per day or per hour. You bill per month typically.

Re: How to Crack the Toughest Coding Interviews

#79

Post by famousactress »

Zenst wrote: post #5

Interviews work both ways - what questions do you ask them? One I used to ask was do you have IS9002/BS5750, but that was 15 years ago and there are better questions to ask. A good question is also sometimes better than a good answear as it shows you understand things from another perspective and have the ability to ask questions instead of blindly accepting what you are told all the time if your unsure. So what are…

I ask some questions about test coverage, coding standards, code reviews.. I'm sometimes more interested in whether I get the same answers from different people or not than the particulars.

I always ask for an example of a technical or tools decision that was made. I'm usually looking to see whether decision-making is well distributed or things get bottlenecked by a manage or lead.

Probably most of all I pick at how the organization decides what to build. I'll ask about features or products that have been sunset or rehashed, how requirements are discovered and communicated. How prioritization works. One of the easiest ways to get red flags here when applying for a spot on a team is to ask everyone I interview with what the team is currently working on. A large variety of answers makes me nervous.

Oh, and also big points off for "Yes" to the following: - Do you have an exchange server? - Do you have a sales team? - Is the person who makes the purchase decision for your product your primary user?

Re: How to Crack the Toughest Coding Interviews

#80

Post by Zenst »

hkmurakami wrote: post #47
kami8845 wrote: post #22

Earlier quoted context omitted.

You have to be more sneaky. Rather than asking something as generic as >What's it like working here? ask them >What do you like the most about working here? If they give you something like "the stability" or "the high pay" those are generally bad signs. Better signs would for example be "the great people I get to work with every day" or "the autonomy to get to choose what I work on".

You can probably throw the "If you could change one thing about the company, what would it be" type question as well.

Or you can ask it along the lines of, what changes good and bad have you experienced in your working enviroment over your time here. If they can't list something in either then I'm usualy wary, most will at least complain about the canteen or some change, even if cheaper coffee. Though if there is no good changes and no bad changes they can think of then it does sound like it could be a boring company.
Post reply on HN