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

81–90 of 250 posts

Re: Google Tech Dev Guide

#81

Post by dbt00 »

lwansbrough wrote: post #41
ascar wrote: post #38

Earlier quoted context omitted.

I agree with you that a non significant number of developers need this kind of problem-solving ability for their daily work, but I would disagree that they never need it. And when they do it can have huge impact. There are many applications of these fundamental problems in system building. They are usually not as obviously in your face as the coding interviews and it is often not possible to let a library do that stu…

My thought process: 1.) this is an intersection problem, 2.) what does a quick search have to say about efficiently solving an intersection problem in $language? That thought process does not require any algorithm knowledge. That knowledge is already out there in abundance, and there are enough people smarter than me focused on those problems that I am wasting everyone’s time by implementing a solution myself. (Btw t…

The problem with "just use a damn library" is that software is full of abstractions and they leak. If all you know is libraries, and you don't invest in knowing how underlying technologies and algorithms work, you're going to get destroyed and look completely lost at some point. Sooner than you think.

Re: Google Tech Dev Guide

#82

Post by SmirkingRevenge »

saulrh wrote: post #31
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'…

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 didn't come up with them in 40-ish minutes on a chalk/white board?

Re: Google Tech Dev Guide

#83

Post by panda88888 »

ascar wrote: post #27
losvedir wrote: post #10

Earlier quoted context omitted.

Huh. I was thinking it seemed like a fairly reasonable question. You sort D by length, and then iterate through it doing a kind of string matching. Both of those operations are pretty "foundational" in programming, right? I'd be curious what you think a better question would be. It's not for brand new programmers - it says the pre-req is a couple of previous computing courses.

Maybe I'm off here, but sorting of D should not be necessary. You add O(|D| log(|D|)) to the runtime complexity (with |D| being number of elements in D) while a single linear run through D is sufficient. The complexity of checking if a single word d in D is a subsequence of S is lienar, thus O(|S|). While sorting might work out in the best case for a long String and a few words of different length so you can terminat…

Sorting D is a one time operation of n log n, so the overall complexity is n log n + n * m, which reduces to O(n * m) where n is number of words in D and m is length of S.

Re: Google Tech Dev Guide

#84

Post by SmirkingRevenge »

seanmcdirmid wrote: post #76
nradov wrote: post #75

Earlier quoted context omitted.

This seems related to Goodhart's law: "When a measure becomes a target, it ceases to be a good measure." If the hiring process for some tech companies has become so dysfunctional that they actually consider brain teaser coding questions to be meaningful then we should expect that competitors with more results oriented hiring processes will eventually beat them in the market.

Perhaps the tenacity and work ethic needed to study a couple of months for an interview selects for people who would do the job well anyways? Maybe that is what it means to be Googly as a culture fit? Anyways, practicing solving clever small programming problems at least isn’t boring (though I’m beginning to burn out on it), it reminds me of prepping for a high school or ACM programming contest. As long as it elimina…

I love to hate on these interview practices, but I have to admit, the brain teaser problems have actually improved my programming, I think.

Re: Google Tech Dev Guide

#85

Post by jakebasile »

dbt00 wrote: post #80
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…

As someone who's done a ton of tech interviewing for a blue chip silicon valley firm, viewing this as a homework problem to which there is one correct answer is exactly not what I'm looking for. I want to see your problem solving skills and I'm curious about your knowledge base, but if you don't know any of the specific techniques and/or don't get to the specific optimal solution I'm looking for I really don't give a…

Everyone says "it's not about the solution but how you go about solving it", but it's never been my experience as an interviewee. Every time I've been interviewed with one of these godawful trivia questions I've been denied even though I do my best to work with the interviewer to solve it. On the rare occasion I get feedback it has been because I didn't solve the problem optimally or some other nonsense.

Re: Google Tech Dev Guide

#86

Post by m0zg »

SamReidHughes wrote: post #64
m0zg wrote: post #51

Earlier quoted context omitted.

The problem here is the only non-bruteforce solution worth pursuing here involves DP with less-than-straightforward memoization rules, which the engineer is unlikely to actually use before or after the interview. So she has to waste a month studying _specifically for the interview_ and "refreshing" the skills she won't actually need on the job. It's like you're hiring a welder, but you want them to be good at jugglin…

Actually looking at their "brute force" solution, what I was referring to as brute force was their "greedy" algorithm, and the first optimization I came up with was the most optimal solution. I'd call that a very natural strategy to take -- try doing the words simultaneously instead of separately, and you see it. I don't even see that as DP. Not everybody will be as quick as me, but there are plenty of people that do…

That's not the point. I just automatically assumed a subsequence problem will involve DP. I only know this because I studied for interviews in the past, not because I ever had to solve a subsequence problem at work, and I've done some _very_ advanced stuff.

I posit that ability to solve such problems is completely irrelevant to one's job performance, at Google or anywhere else. Google's own test of this hypothesis (hiring a control group of people irrespective of their interview scores) seems to bear it out.

Re: Google Tech Dev Guide

#87

Post by Alex3917 »

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…

As an anecdote, Dr. Krebs had no idea what the Krebs cycle was without looking it up, even though students are expected to memorize it.

Re: Google Tech Dev Guide

#89

Post by ascar »

panda88888 wrote: post #83
ascar wrote: post #27

Earlier quoted context omitted.

Maybe I'm off here, but sorting of D should not be necessary. You add O(|D| log(|D|)) to the runtime complexity (with |D| being number of elements in D) while a single linear run through D is sufficient. The complexity of checking if a single word d in D is a subsequence of S is lienar, thus O(|S|). While sorting might work out in the best case for a long String and a few words of different length so you can terminat…

Sorting D is a one time operation of n log n, so the overall complexity is n log n + n * m, which reduces to O(n * m) where n is number of words in D and m is length of S.

You are right, I was off.

On another note: I absolutely do not understand why we substitute the international mathematical symbol for cardinality (|A|) with variables we have to explain.

Computer science has a math background, so we all know set theory. At least I also learned using cardinality with Big O notation in university. But for some reason industry prefers to use variables here.

Re: Google Tech Dev Guide

#90

Post by EnderWT »

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…

I interview for my company, too, and don't ask these kinds of algorithm questions because the reality is these problems aren't typical of day-to-day work for the positions we are hiring for.

I'm interested to know what your interview process is. If you wouldn't mind sharing, how does the interview process work at your company?

Post reply on HN