Interviews requiring genius-level capabilities for doing boring daily trivial stuff. Quite deceptive. There is a rush in SAT and automated tests (e.g. hackerrank) stuff that is getting crazy. Anyway, no matter how good you do in SAT/programming tests, you may be discarded because of your personality, political views, or even because of plain xenophobia. Brave new world! :-D
Inverting Binary Trees Considered Harmful
171–180 of 225 posts
Re: Inverting Binary Trees Considered Harmful
#172I'm only a rising junior in CS on my second internship and I completely agree. I did really well in my Data Structs & Algorithms class (A+...) and I just hate these types of problems. I bombed Google and Dropbox's interviews, and am ready to never go through another process like that again if I can. I've been exceedingly lucky landing gigs at great companies that don't filter with these questions. I worked for LeadGe…
It's not just CS, but probably more common with CS. There are two kinds of engineers. 1. Those that love love love solving Puzzles. 2. Those that question whether solving this or that puzzle is going to bring in any money for the company. For a places like google or deranged YC startups, whether what you are assigned has any bearing on cash flow is something way above the typical engineers paygrade. There are a lot o…
BTW: Bit of advice for anyone going into a technical fields.
Learn to write, English. Learn it well. How to clearly explain idea's and requirements. How things work, how they are broken. Justify what you did, or cover your butt. Where you are in twenty years will depend mostly on this.
Learn to speak fluently in front of a group of people.
Or whatever the locally appropriate language is.
Re: Inverting Binary Trees Considered Harmful
#173I 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…
Of course they know that writing code on a whiteboard under stress isn't the same thing as sitting at a desk grinding out code. The problem is that it's pretty hard to sit down all the applicants for a position for a few weeks and work with them long enough to actually get a sense of how they work, and it's quite wasteful for the 95% who don't get the job.
Some companies actually do this, eg. Coinbase requires that you take a week off from work and work with them (I think unpaid, but perhaps you get contractor wages) on a project. They've been widely criticized as exploitative here, with many people saying "Why should anyone who has any choice at all agree to that?" They also open up a rats nest of legal & IP issues.
The best way to get a full-time position at Google - or most companies, really - is to get an intern or contractor position and then convert to FTE at the end. Hiring rates are way higher for successful interns (and the interview process is shorter), because they have lots of people inside with first-hand experience grinding out code with them that goes directly into Google's systems. But getting that internship or contract itself often requires an interview...
Re: Inverting Binary Trees Considered Harmful
#174Earlier quoted context omitted.
The correct way to write a CSV parser is to import one.
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…
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();
Re: Inverting Binary Trees Considered Harmful
#175Earlier quoted context omitted.
And then the author writes: > Now, in his defense, computing the dot product of the string with a random prime vector is a well known Universal Multiplicative Hash Function, but forgive me, father, for I did not pay much attention to this invaluable nugget in my Algorithms 101. Well, I didn't pay much attention in such a class either, but isn't that just intuitively obvious? Dot-product a vector `x` with a vector `p`…
The question was explain the exact approach Java uses to hash strings, not come up with a way to hash string or explain why does this particular approach work for hashing strings. Much like hashes themselves going one direction is much harder than the other.
Meanwhile, my actual Google interviewer asked me how I might do it. He then explained why my Gödel numbering scheme was bad, showed me how Java does it, was seemingly satisfied enough and offered me a job on his team.
Google has a bad rep, but it is possible to sort it out.
Re: Inverting Binary Trees Considered Harmful
#176Earlier 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…
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 agree, but a naive imported solution would likely try to store all the rows at once, possibly in some sort of list or vector or array or whatever. This is what would cause the memory failure, not the file read itself.
Re: Inverting Binary Trees Considered Harmful
#177Earlier 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…
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…
please note that according to https://www.ietf.org/rfc/rfc4180.txt
this is a valid record definition from a csv file: "b CRLF bb","ccc" CRLF zzz,yyy,xxx
Your code will fail on this case. CSV parsing is not as simple as it sounds. Given that the format is also not well-defined, it's even worse. (is the first line a header or not for example)
Re: Inverting Binary Trees Considered Harmful
#178Earlier quoted context omitted.
The question was explain the exact approach Java uses to hash strings, not come up with a way to hash string or explain why does this particular approach work for hashing strings. Much like hashes themselves going one direction is much harder than the other.
Meanwhile, my actual Google interviewer asked me how I might do it. He then explained why my Gödel numbering scheme was bad, showed me how Java does it, was seemingly satisfied enough and offered me a job on his team. Google has a bad rep, but it is possible to sort it out.
That sounds eminently reasonable.
Re: Inverting Binary Trees Considered Harmful
#179Earlier quoted context omitted.
The correct way to write a CSV parser is to import one.
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
Re: Inverting Binary Trees Considered Harmful
#180I'll be the contrarian and claim that inverting a binary tree is a perfectly reasonable interview question. (Although not anymore now that it's famous). It combines basic background knowledge (what is a binary tree and how is it structured?), ability to reason logically (binary tree algorithms are often recursive, "inverting" a tree with no children is a no-op, otherwise you want to swap the children, and the childre…
In your daily programming activities, how many times do you have to implement a binary tree? I'm genuinely interested.
Quite a few times. If you are doing things related to computer vision, machine learning, maps, language processing, compilers, speech etc - you are going to use all these CS stuff fairly regularly. You are even going to need stats, linear algebra and probabilities (I'd to literally do bunch of math quite a few times at work on whiteboard).
Most of the crowd here seems to be doing CRUD, JS, iOS stuff. You won't need much of CS/Algorithm skills there and I understand their statements like "I have never needed to touch binary trees in 15 years". Unfortunately they are trying to make case that this is same everywhere. Sure not all jobs at GOOG/FB/MS require strong CS skills but lot of projects at these companies do. It's not reasonable expectation to walk in to these companies who literally thrive just because of their algorithms and say I don't give a damn about CS but look at this package manager I built. In my opinion, people who can't work with something as simple as binary trees won't last a day in many of the projects at these companies. Learning frameworks and languages are easy, problem solving using CS primitives is hard earned skills.