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

11–20 of 250 posts

Re: Google Tech Dev Guide

#11

Post by lwansbrough »

duality wrote: post #4
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'…

So you like the algorithms and data structures used to build a distributed collaboration system with event sourced data in Microsoft Orleans, but not the algorithms and data structures used for string search.

Honestly I don't care about the algorithms and data structures used for string search, or event sourcing for that matter. I use that code to build stuff. There's a vanishingly small portion of the population devoted to these problems, and indeed most of those people are probably working on search at Google or something similar. Calling them "foundational" is a joke. They're important, absolutely -- we all use them daily. But expecting every developer to be able to implement a search algorithm? That's the kind of dumb interview question I'd walk out on. Programming is much more than algorithms. Algorithms are the tools we use to build problems. You don't expect a tradesman to build his tools himself, do you?

Re: Google Tech Dev Guide

#12

Post by teraflop »

losvedir wrote: post #10
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'…

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.

Nope, that would find words that are substrings, not subsequences.

Re: Google Tech Dev Guide

#13

Post by chiefalchemist »

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 think it depends. Are you looking for someone who knows say the "perfect" answer? Or do you want to measure someones analysis / problem solving skills?

It's not always about the ends, sometimes it can be about the means. Maybe not the case in the context of Google, but still worth mentioning. I would think.

Re: Google Tech Dev Guide

#14

Post by lwansbrough »

fatjokes wrote: post #8
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'm glad you do cool stuff day to day and not need this. But I would disagree that what you do is foundational, whereas string matching is absolutely foundational.

String matching, like == or string.compare? Anything more complicated than that and you're not building anything that isn't already available.

Re: Google Tech Dev Guide

#15

Post by Waterluvian »

teraflop wrote: post #12
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.

Nope, that would find words that are substrings, not subsequences.

What is a subsequence then? I thought you are looking for words that show up in the long string. I visualize sliding each word across the string until it lines up with the same characters.

Re: Google Tech Dev Guide

#16

Post by MikeLui »

Is withgoogle.com a new subset of educational resources from google? Going directly to withgoogle.com just redirects me to google.com. My first instinct was suspicion when I saw the link.

Re: Google Tech Dev Guide

#17

Post by MikeLui »

lwansbrough wrote: post #11
duality wrote: post #4

Earlier quoted context omitted.

So you like the algorithms and data structures used to build a distributed collaboration system with event sourced data in Microsoft Orleans, but not the algorithms and data structures used for string search.

Honestly I don't care about the algorithms and data structures used for string search, or event sourcing for that matter. I use that code to build stuff. There's a vanishingly small portion of the population devoted to these problems, and indeed most of those people are probably working on search at Google or something similar. Calling them "foundational" is a joke. They're important, absolutely -- we all use them da…

What would you consider foundational?

Re: Google Tech Dev Guide

#18

Post by tylerhou »

Waterluvian wrote: post #15
teraflop wrote: post #12

Earlier quoted context omitted.

Nope, that would find words that are substrings, not subsequences.

What is a subsequence then? I thought you are looking for words that show up in the long string. I visualize sliding each word across the string until it lines up with the same characters.

The subsequences of a string X are any strings Y such that Y is X with zero or more characters dropped, with the condition that the original characters of X must remain in the same order. As an example, the string "help" has 16 subsequences: ["", "h", "e", "l", "p", "he", "hl", "hp", "el", "ep", "lp", "hel", "hep", "hlp", "elp", "help"]. Note that the set of subsequences are isomorphic to the power set (assuming repeated characters are unique), so for a string with n unique characters, there are 2^n subsequences.

Re: Google Tech Dev Guide

#19

Post by Waterluvian »

tylerhou wrote: post #18
Waterluvian wrote: post #15

Earlier quoted context omitted.

What is a subsequence then? I thought you are looking for words that show up in the long string. I visualize sliding each word across the string until it lines up with the same characters.

The subsequences of a string X are any strings Y such that Y is X with zero or more characters dropped, with the condition that the original characters of X must remain in the same order. As an example, the string "help" has 16 subsequences: ["", "h", "e", "l", "p", "he", "hl", "hp", "el", "ep", "lp", "hel", "hep", "hlp", "elp", "help"]. Note that the set of subsequences are isomorphic to the power set (assuming repe…

Okay gotcha. So for each word in the length-sorted set, walk the string "picking up" characters as you go. If you complete the word, that's your answer.

I'm sure there's a faster or more mathematical answer. But that would be my napkin python.

(Edits made)

Re: Google Tech Dev Guide

#20

Post by macspoofing »

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'…

>currently I'm building a distributed collaboration system with event sourced data in Microsoft Orleans

I know it's easy and fun to use frameworks that abstract all the gory low-level details (the equivalent of calling a built-in sort function on a list of numbers), but somebody has to write those frameworks at some point. Don't get me wrong, I'm certainly impressed with the work that the Orleans team did and it would be great to read a write-up on the design of this framework. I suspect a write up on your 'distributed collaboration system with event sourced data in Microsoft Orleans' would be less interesting because the best part would read 'and here I used Orleans to do all the hard parts'.

Post reply on HN