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

Google Tech Dev Guide

techdevguide.withgoogle.com

Post reply on HN
Print view View original

111–120 of 250 posts

Re: Google Tech Dev Guide

#111

Post by keyanp »

SmirkingRevenge wrote: post #82
saulrh wrote: post #31

Earlier quoted context omitted.

Funny, I use this kind of thing all the time when I'm programming. I wrote a comment citing the pigeonhole principal to justify a test case not thirty minutes ago. And I'm not even doing anything wizardly or revolutionary, just improving some concurrency code in a random worker binary. As for your comment about "diversity of thought": These problems seem sterile when they're presented in the most general possible for…

It would be interesting to know how much time and practice it took the inventors of many of these algorithms, to actually create them. When you think about it... that's basically what candidates are being asked to accomplish in these kinds of interviews, unless they have the algorithm (or a very similar one) memorized already. Would we be surprised to learn that most of the smart guys behind these algorithms probably…

Good point!

I ran into this case studying for interviews a while ago. The "maximum subarray problem"[1] is a common interview question, you are generally expected to be able to come up with the O(n) solution.

Well has a great passage about the origins of the problem and how multiple excellent algorithmists could not improve on a O(n^2) run time[2]:

> Grenander observed that the cubic time of Algorithm 1 was prohibitively slow, and derived Algorithm 2. In 1977 he described the problem to Michael Shamos of UNILOGIC, Ltd. (then of Carnegie-Mellon University) who overnight designed Algorithm 3. When Shamos showed me the problem shortly thereafter, we thought that it was probably the best possible; researchers had just shown that several similar problems require time proportional to N log N. A few days later Shamos described the problem and its history at a seminar attended by Jay Kadane (a statistician at Carnegie-Mellon University), who designed the linear-time Algorithm 4 within a minute.

The solution is elegant and seemingly "obvious" after looking at it, but good luck coming up with it yourself :)

[1]: http://cricca.disi.unitn.it/montresor/wp-content/uploads/201... [2]: https://en.wikipedia.org/wiki/Maximum_subarray_problem

Re: Google Tech Dev Guide

#112

Post by kamaal »

nilkn wrote: post #74
saulrh wrote: post #31

Earlier quoted context omitted.

Funny, I use this kind of thing all the time when I'm programming. I wrote a comment citing the pigeonhole principal to justify a test case not thirty minutes ago. And I'm not even doing anything wizardly or revolutionary, just improving some concurrency code in a random worker binary. As for your comment about "diversity of thought": These problems seem sterile when they're presented in the most general possible for…

To offer an alternative viewpoint: I have a degree in pure mathematics from a highly ranked institution. I published research as an undergraduate. I went to multiple REUs. I participated in the Putnam and similar competitions. I read CLRS in 9th grade and didn't even bother taking an algorithms course in college. But even I find that these sorts of questions are more gatekeeping than anything else. That's not a persp…

>>You mention diff(1), but who's to say the author(s) of that tool would've necessarily solved this problem on the spot?

I think this is the gist of the all problems facing the current interview process.

There is a big difference between inventing a solution to a problem, and learning the solution to a problem which some one invented.

The latter shows nothing about the ability or even the way in which a person thinks or even works. It just shows the person was able to scale multiplication table memorization skills to other things as they grew up.

Re: Google Tech Dev Guide

#113

Post by onion2k »

m0zg wrote: post #36
akanet wrote: post #5

Earlier quoted context omitted.

That's certainly your opinion, but the subsequence problem is a very general, abstract question that offers the candidate a number of ways to arrive a progressively better solution by following their intuitions. It's not the greatest interview question, but it's certainly not the worst. This website appears to be for people who already know how to code, and offers many different paths as well.

It doesn't. This seems like a typical Google interview question. If you didn't know how to solve it before the interview started, you aren't going to figure out anything other than a brute force solution in 45 minutes. And brute force solution will not get you a good grade in a tech interview at Google. It's idiotic: once you do get hired by Google, easily 80% of your work is copying one proto buffer into another, an…

You're assuming that it's important to actually solve the problem. I'm not sure that's the case - it's really asking whether or not the candidate understands that brute forcing is a poor solution and determining whether they're capable of even looking for a better solution. A lot of developers find it very hard to look past the obvious first solution they find to a more efficient algorithm instead. Specifically companies like Google want to hire people who can do that deeper work.

The real issue with problems like this is when much smaller companies hiring a dev who'll be bolting together APIs and won't ever need to know an answer start to copy the technique believing "it's how you hire devs".

Re: Google Tech Dev Guide

#114

Post by raverbashing »

seanmcdirmid wrote: post #100
Apocryphon wrote: post #96

Earlier quoted context omitted.

> As long as it eliminates enough false positives, they’ll keep up with it. So Google is relying on a brute force approach to hiring?

Ya, but everyone is. Too many fakers in this industry.

And too many people that can't be bothered to think of easy ways of filtering them without something stupid like fizzbuzz

Who's the faker again?

Re: Google Tech Dev Guide

#115

Post by hesarenu »

saulrh wrote: post #52
lwansbrough wrote: post #24

Earlier quoted context omitted.

Algorithms aren't foundational, in my opinion. Once you understand the syntax of programming, you can start learning about the applications of that syntax, which for 99% of developers rarely ends up in the shape of an explicit algorithm. It's not all bad, debugging is foundational for sure. I'd place a person's debugging skills, their ability to predict bugs, system design, knowledge of common (applicable) libraries…

> Having never needed to build my own sorting algorithm in 14 years of coding, Neither have I. What I have had to do is recognize when I could do what I needed to do without sorting the array, understand various requirements when I'm writing comparison functions, understand why std::list::sort exists when std::sort is right there, debug a stalling mapreduce job, recognize when a library I'm using has done a stupid an…

Depending on you work you don't need to use it again. I have not used it for a decade. I somewhat remember the theory. For interview i can just memorize it.

Re: Google Tech Dev Guide

#116

Post by arvinsim »

linza wrote: post #106
acroback wrote: post #91

I have been putting off a Google interview for a whole year now. I have real experience building Cluster Filesystems, Distributed Caches, TCP/IP Control plane software and low latency Ad platform for more than a decade. Sounds good on paper, but I can guarantee I cannot solve most of these puzzles without actually solving them beforehand. Why? Because I do not have cycles or time to solve these on my own. I have a sy…

I don't work for Google and i haven't interviewed with them. In our company (low level systems engineering) we ask similar question, with the following rationale: I don't want to test if you can build systems, your resume already says so and there is but enough time to assess this properly anyway. But, can you be bothered to try to solve problems outside of your comfort zone? Will you humor me as an interviewer for o…

I find this amusing because lots of people put bullshit on their resumes that one has to filter them out.

I already have my hands full trying to filter out the posers and assessing for culture fit. I don't have time to ask a candidate for some questions that aren't related to the role at hand.

But hey, you do you.

Re: Google Tech Dev Guide

#117

Post by jldugger »

lwansbrough wrote: post #2

"Given a string S and a set of words D, find the longest word in D that is a subsequence of S." Found under "Foundations of programming" -- this is exactly the type of problem I'd expect as question one under this section. When it's made by Googlers, that is. I make a lot of cool stuff day to day, and usually that requires a lot of code and knowledge about programming and topics that are rather advanced (currently I'…

> I make a lot of cool stuff day to day, and usually that requires a lot of code and knowledge about programming and topics that are rather advanced

I'm not entirely sure who this guide is written for. But if we're playing the 'nobody does this in real life' card, I wonder which would be a tighter filter for new CS grads: this dynamic programming questions or writing a regex with capture groups.

Re: Google Tech Dev Guide

#118

Post by sirpunch »

lwansbrough wrote: post #2

"Given a string S and a set of words D, find the longest word in D that is a subsequence of S." Found under "Foundations of programming" -- this is exactly the type of problem I'd expect as question one under this section. When it's made by Googlers, that is. I make a lot of cool stuff day to day, and usually that requires a lot of code and knowledge about programming and topics that are rather advanced (currently I'…

In case you think these questions are not actually asked in Google interviews, I should add that I was asked this very question in Google SDE interview just 6 days ago. I failed to answer this and was consequently rejected. Also, the interviewer asked me nothing other than this question. Nothing about the breadth of work that I have done in different sectors, my interest/passion, personal projects etc. I was so upset after the interview was over and I cried a lot after reaching home. :(

Re: Google Tech Dev Guide

#119

Post by raverbashing »

akanet wrote: post #5
lwansbrough wrote: post #2

"Given a string S and a set of words D, find the longest word in D that is a subsequence of S." Found under "Foundations of programming" -- this is exactly the type of problem I'd expect as question one under this section. When it's made by Googlers, that is. I make a lot of cool stuff day to day, and usually that requires a lot of code and knowledge about programming and topics that are rather advanced (currently I'…

That's certainly your opinion, but the subsequence problem is a very general, abstract question that offers the candidate a number of ways to arrive a progressively better solution by following their intuitions. It's not the greatest interview question, but it's certainly not the worst. This website appears to be for people who already know how to code, and offers many different paths as well.

Yes but Google wants the right answer, regardless of the way you think and regardless of the fact that you came up with a proof for P=NP on the interview

Re: Google Tech Dev Guide

#120

Post by thwy12321 »

onion2k wrote: post #113
m0zg wrote: post #36

Earlier quoted context omitted.

It doesn't. This seems like a typical Google interview question. If you didn't know how to solve it before the interview started, you aren't going to figure out anything other than a brute force solution in 45 minutes. And brute force solution will not get you a good grade in a tech interview at Google. It's idiotic: once you do get hired by Google, easily 80% of your work is copying one proto buffer into another, an…

You're assuming that it's important to actually solve the problem. I'm not sure that's the case - it's really asking whether or not the candidate understands that brute forcing is a poor solution and determining whether they're capable of even looking for a better solution. A lot of developers find it very hard to look past the obvious first solution they find to a more efficient algorithm instead. Specifically compa…

This is false.
Post reply on HN