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

Inverting Binary Trees Considered Harmful

jasq.org

Post reply on HN
Print view View original

181–190 of 225 posts

Re: Inverting Binary Trees Considered Harmful

#181

Post by xamuel »

pstrateman wrote: post #179
xamuel wrote: post #154

Earlier quoted context omitted.

Scenario: The file is a 100GB CSV file. The machine is a VPS with 500MB RAM. The task: Determine whether the value in the first column of the first row, is ever repeated in the first column of any subsequent row. An import solution is unlikely to work. Most import solutions would try to load the rows into memory, which doesn't work here. Maybe if the imported parser can be configured to run a user-supplied callback o…

import csv r = csv.reader(open('file.csv')) first_row = r.next() for row in r: if row[0] == first_row[0]: return True return False 287MB file 100m rows 15.804s peak memory usage 7MB

Thank you, that is beautiful. I've been proved decisively wrong and I've gained some greater appreciation for python's libraries.

Re: Inverting Binary Trees Considered Harmful

#182

Post by parados »

I know Google interviews generate a lot of traffic on HN but I thought that I'd add something that I haven't seen covered, that is, the job itself.

I interviewed twice successfully for Google and the interview experience was impeccable (interviewers were great, HR was completely on the ball etc.). The first time there was a hiring freeze so that didn't go anywhere, the second led to offers in several countries in Googles empire. Most of these I could not accept for family reasons but one I could although Google were quite secretive about what the job was.

I accepted thinking that, well they know me well enough by now and what I can do. A mistake. Upon arrival it turned out to be writing an Android app which is completely the wrong end of the spectrum for me - I have never even written Java. I was been benchmarked against people who seem only to have done only that. The other thing that made me realise that I had no long term future in Google is that it was made clear to me that any experience of working for other software companies or other industries was neither interesting or useful. If you have a lot on your C.V. like I have this is problematic.

So I left after a few months.

Sure Google is a fabulous company, does some amazing stuff and has some great people (perhaps not as uniformly great as they'd like you to believe). If you fit the mould tightly enough you will have a lovely time.

TL;DR - They should not have hired someone like me, I should not have accepted.

Re: Inverting Binary Trees Considered Harmful

#183

Post by sytelus »

wyager wrote: post #3

>You are then ushered into a room with the programmer's worst nightmare - a blank whiteboard. Am I the only one who enjoys programming interviews? Even if you screw it up, it's still fun to try your hand at whatever problem they give you. They also don't expect you to do it perfectly; you're allowed to have sub-superhuman performance.

Most posts complaining about interview process are being made by people who failed those interviews. There is a ton of reverse-survivorship bias here. It's certainly not the case that companies like GOOG/FB/MS are filled with all bozzos. If anything their interview process have been rather successful considering above average quality of talent at these companies and non-trivial products they work on.

I also sense lot of "entitlement" in OP's post and comments on this thread. It's like "oh I can't answer your interview questions but I'm so good that if I don't get the job, it would be only because your interview process sucks". Most company's HR would let you know what to expect at these interviews. If you are not comfortable with CS whiteboarding questions then you should just decline at that point. It's unprofessional to blame their process after you accepted to go through it, failed and then shit all over it because you didn't get the job.

This is not to say all interviewers are good and many could be downright assholes. But that feedback should be between you and their HR. It's just professional courtesy considering that these companies don't post on Internet how badly you performed on interviews compared to their other candidates to tell other side of your story.

Personally I like solving computational challenges whether I get job or not. As a programmers we are supposed to be loving these kind of CS puzzles. If nothing else, you walk out with few CS things you didn't knew before which would have taken same amount of time to learn anyway. I'm not saying interview questions shouldn't be job related but the fact is that many of these companies are doing LOTs of things and they need to hire more generally because they give you relatively more freedom to move around once you are in. So large companies have to keep things general at some level unlike startups with one project. In any case, if you complain about having to write code and design algorithms at developer interviews then you are probably applying for the wrong job.

Re: Inverting Binary Trees Considered Harmful

#184

Post by CHY872 »

xamuel wrote: post #176
CHY872 wrote: post #174

Earlier quoted context omitted.

The trivial Java solution BufferedReader r = new BufferedReader(new File(filename)) String line = r.readLine(); if (line != null) { String first = line.split(",")[0]; while ((line = r.readLine()) != null) { if (first.equals(line.split(",")[0])) { return true; } } return false; } throw new RuntimeException(); would work just fine, and very quickly, too. This sort of question simply is not hard to solve; it's far more…

In other words, you write your own CSV parser, in this case using Java. Btw, CSV files can contain values with commas and even newlines inside of them. So if your point was that you don't have to write an _entire_ CSV parser, only a partial one, unfortunately that isn't true. https://en.wikipedia.org/wiki/Comma-separated_values#Example >I very much doubt that any CSV parser would try to load the file all at once I ag…

Possibly, but unlikely (most csv libraries will be based around iterators). In any case, the problem is stupidly underspecified. For example, what if the 100GB CSV is 100 1GB rows? What if the input is UTF16, UTF32? How do you deal with the 10 Unicode line separators?

It just tests how well the interviewee knows CSV, which is an ill specified format anyway. It's a fake problem as no sane person would parse 100GB CSVs on 500MB VPS', and in real life, you'd just try the naive solution, see why it didn't work and iterate.

Re: Inverting Binary Trees Considered Harmful

#185

Post by jbdigriz »

chrisseaton wrote: post #130
zbyte64 wrote: post #100

Earlier quoted context omitted.

The correct way to write a CSV parser is to import one.

Someone has to write that CSV parser though, don't they? And sometimes you actually need to write things like sort algorithms. I implemented an insertion sort from scratch recently, because it needed to be done in a particular way to take advantage of the capabilities of a specific JIT compiler. People do actually do this stuff - it's not all academic.

Did you have to do this on a whiteboard or paper as part of the interview process for your job? The point: not being able to do this on a interview in completely contrived circumstances with all the anxiety that comes with close scrutiny of a person who had the power to determine your future career is not a good gauge of your ability to do so when matters, given all the resources we as developers generally afford ourselves.

My biggest problem is that the vast majority of these tests is they only test two skills, neither of which is all that critical to software development beyond a certain minimum threshold: recollection and pattern matching known solutions to familiar problems. In my current level of competency with a decade of tenure in software development is this: if you're asking me to solve problems which I can easily "solve" with a few minutes of searching the web, you probably don't want or need someone like me whose spent the majority of their career on big projects which require a multitude of disciplines from being creative to quantifying results to forethought of future use to systematically testing and releasing at a minimum of risk....

What I find ironic is that I've never been tested on some of the few rote tasks which I find most developers struggle with: committing/branching/merging/commenting code, producing post release documentation, developing robust API functions, etc etc

Re: Inverting Binary Trees Considered Harmful

#186

Post by TylerE »

zbyte64 wrote: post #100
TylerE wrote: post #52

I recently interviewed for (and got) a new job. The interview process took about two weeks and on the whole was pretty reasonable for both sides. There was a short phone screen (~30 minutes) Then I had two technical exercises to do. For each, I was given a reasonable time period (4 hours) that started when I visited a special link to the get the problem description, and then used whatever tools I wanted to get it don…

The correct way to write a CSV parser is to import one.

Well, sure, and that's what I did, but the meat of the problem was the validation. E.g. couldn't assume that required fields would be present.

Re: Inverting Binary Trees Considered Harmful

#187

Post by TylerE »

MrBuddyCasino wrote: post #170
zbyte64 wrote: post #100

Earlier quoted context omitted.

The correct way to write a CSV parser is to import one.

Sure, but I think its actually a reasonable interview task. You're just being asked to implement a simple state machine.

No, sorry, I was unclear, using an existing parser was fair game. The meat of the problem was on the validation/actually get data into the DB side.

Re: Inverting Binary Trees Considered Harmful

#188

Post by wyldfire »

asuffield wrote: post #77
wyldfire wrote: post #17

I enjoy the challenge of programming interviews. When I interviewed in Mountain View, I thought it was just super cool to have been invited. It was like the mother ship had summoned me home! I was mega-underwhelmed when I botched the last session, though. And after doing so poorly, no one escorted me out or summed things up. Efficient, I suppose -- I'd met with the recruiter at the beginning of the day and there was…

To fill in one gap - our hiring process has an extra layer of insulation to better control individual biases. Your interviewers all submit feedback and an independent hiring committee makes the decision, on a different day, with all due deliberation. The reason nobody has anything to say to you at the end of the day is because none of that has happened so nobody knows what to say at that point, and I don't think it's…

> The reason nobody has anything to say to you at the end of the day is because none of that has happened

I just meant typical American (or global?) politeness stuff -- escort your guest to the door, thank them for coming, you'll hear from us soon, etc.

Re: Inverting Binary Trees Considered Harmful

#189

Post by TylerE »

xamuel wrote: post #181
pstrateman wrote: post #179

Earlier quoted context omitted.

import csv r = csv.reader(open('file.csv')) first_row = r.next() for row in r: if row[0] == first_row[0]: return True return False 287MB file 100m rows 15.804s peak memory usage 7MB

Thank you, that is beautiful. I've been proved decisively wrong and I've gained some greater appreciation for python's libraries.

It's not even a library thing. Reading a file in this way does reads in approximately optimal (for the FS) sized blocks. The CSV parser just rides on top of stdio.

Re: Inverting Binary Trees Considered Harmful

#190

Post by vladaionescu »

IMHO, I feel like people who are not up to it don't agree with coding interviews. Also, in my experience, the employers that didn't check coding skills at the interview had the worst engineers I met (surprise!).

Now I can see why it's easy to disagree with interviews that check your algorithms 101 knowledge: that stuff is really really rarely used in real-life and you can just google it if you ever need it. But! Keep these in mind:

- Can you come up with a better process that scales with the number of interviewers in your company, but also maintains reasonable consistency and keeps reasonable costs? Maybe you think you can, but keep in mind that the tech giants have data-crunched their interview stats over and over and this process is what they stuck with. (Of course, with scale there's also the problem you occasionally have arrogant interviewers - but I think that problem should be decoupled from the coding/non-coding interviews problem).

- In places where they look for A* engineers, the point of the interview is often not to test what you know best, but how you get along with problems you have never seen before. An algorithm or data structure question often fits the bill.

- Geeks love geeky puzzles (like inverting binary trees). Companies often look for geeks in love with abstract stuff.

Also, IMHO, knowing only one language is a red flag for me too at 10+ years experience level.

Post reply on HN