Hacker News Reader

Google stopped asking brainteaser questions like that because they found no correlation in its hiring usefulness.

I think it's true for majority of questions (apparently leetcoding is the new thing at Google and also FB). IMHO interning for a few weeks is the best for both sides - unfortunately it doesnt scale.

Interning "for a few weeks" means that you miss out on candidates who already have perfectly good jobs. These are often the folks that you are trying to hire.

So imagine how a candidate reacts to, "Well, while we know you're happy where you are, what would you think about quitting your current job so you can try out a position at our company for a few weeks?" (Note that candidates can't use vacation time just to do a try-out, for legal reasons, and may be reluctant to use up all their vacation time in any event).

Having a trial period puts all the risk on the candidate, and guarantees you're filtering out people that you'd otherwise want.

I'll be the obligatory ex Googler claiming Google never did ask brainteaser questions, or at least they were long gone by 2006.

Puzzle questions were definitely against company policy and at least ones unrelated to coding were rare by that time at Microsoft, too.

Wouldn’t the current niche clever dynamic programming problems google asks you to work out on a whiteboard be classified as brain teasers? Sure, it’s much easier to prep for via the cracking code interview book, but is still not something you would encounter in the wild.

I was asked to estimate Pi using a unit circle (diameter = 1) inscribed in a unit square (side = 1) around 2012-2013. In a manner that would have a controllable amount of precision.

They wanted monte carlo (more darts, more precision), I went riemann sums (smaller delta x, more precision). It totally through me off my game for the rest of the interview as I was constantly thinking about it.

while not quite a traditional brain teaser, there are a couple of insights one has to get to solve it

1. ratio of circle area to square = pi/4 (but remember, you don't know pi yet, just that it exists, the point is to estimate it)

2. a way to make use of that ratio (i.e. monte carlo, pick a random 2d point (on both x,y from -0.5 to 0.5) if the distance from (0,0) is greater than 1, it is only added to the square, otherwise it gets added to both.

combine the 2 insights and you get pi ~ 4*circle/square

(as mentioned I went with riemann sums, where I calculated the area under the curve of the circle's arc in one quadrant, but same idea you get pi ~ circle_arc_area/.25)

those 2 points aren't quite obvious (I went riemann sums as area questions made me think calculus and went totally down that rabbit hole), and in 30-40 minutes of brainstorming (first 10-15 minute discussion about the person, then actual interview question, then 5+ minutes for any questions you have for the interviewer) can be difficult for many people to get.

The problem can then be, many people can't just stop thinking about a problem they struggled with and will continue to process it (hurting their following interview Qs),

i.e. even if that interviewer thought I did sufficiently, I believe it hurt me on the following Qs as I couldn't just let it go, which in the real world is how I think many people work. If they are struggling with how to solve something, they are dealing with it even when they are supposedly focused on other things (say in meetings, eating lunch....)

Unless you were interviewing for a mathematician position, I agree that's a garbage programming interviewing question. It's focused on your math skills far more than your programming skills.

If it's a "brainteaser" is I guess a matter of definition.

Look, I'm sure people are asked bad questions at all times in all companies, but the policy at Google was clearly to not do that. At least when I was there 2006-2009.

Manhole question is bad, because around half manholes im real world are squared. So the correct answer is that they are not in fact round and square works perfectly fine.

Of course I know right answer, but it has zero to do with me being smart and a lot to do with me being in right culture and thus having heard about it before. Which is exactly what it test along with other brain teasers - have you encountered this sort of question before?

Haha. That was exactly what I was thinking! I have yet to see a round one! Lol

The correct question, obviously, would be "why in some places they make manhole covers round and which advantages and disadvantages over square ones they have?" Which, as any good question does, already contains part of the answer.

It could be coupled with following question: "why in some places they make manhole covers square and which advantages and disadvantages over round ones they have?"

That is, essentially, the same question :) Except, of course, for triangular ones, which also exist.

Data point: There are triangular manhole covers on my street.

I've interviewed at MS a couple of times and I've never had a question as easy as "reverse a linked list".

There was a linked list interview question going around back then that went: In constant time, without allocating memory, given a pointer to the first element of a linked list, how can you tell if it eventually ends in a null or if it loops back on itself at any point? I actually ended up implementing the solution while tracking down a hang in a DCOM service I was working on...

In constant time? O(1)?

Isn’t that normally the 2 pointers (tortoise/hare) thing? If yes then I agree it’s not constant time.

I personally hate this kind of interview question. It’s one that is easily answerable when one heard the exact question before (in training for interviews). But super hard to answer if not. And it even does not have big applications in practice - in 20years of programming, I never encountered a problem like this. In the end the question just wastes time on both sides and won’t really tell a lot about the candidate.

He meant constant memory. It's to invalidate solutions marking items visited.

I too got this question at an interview once, and failed. For fun I asked everyone at work and predictably nobody came close to figuring it out.

No, I meant O(n) but used the wrong word for it.

Marking items visited can actually work, because on any(?) modern OS the memory for the elements in the list would be allocated at even addresses, meaning the low order bit of the Next pointer is always zero and can be reused as a marker.

Your solution isn't thread safe :)

It's in a critical section. (Which you pretty much have to do with the canonical one too, since it can run off the rails if another thread modifies the list.)

There was a blog post shared a while ago on HN where the author ranted that it was his least favorite interview question because the solution (fast/slow pointers) was - if I recall correctly - literally somebody's PhD thesis. There was a years-long window where anyone "clever enough" could have waltzed in with a one page paper.

If you've never seen the pattern before, there is a very good chance that you're hosed.

Edit: found it [1]

[1] https://news.ycombinator.com/item?id=7953725

The tortoise & hare algorithm [1] was not just discovered by some random PhD student, but by Robert Floyd, who won a Turing award.

[1] https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoi...

[2] https://en.wikipedia.org/wiki/Robert_W._Floyd

I used to ask this (cycles in linked list) question all the time, and I found it useful as a way to see how the candidate worked through an unfamiliar problem. No-one gave the 2-pointer answer, ever.

For me it wasn’t a pass/fail “do you know the right answer” question, it’s more of a “can I work with this person” question.

This is a pretty standard linked list question (called cycle detection) – one of the easiest questions on LeetCode. You can use the two-pointer method to just detect if there's a cycle. If you want to find the node that the cycle starts at, you can just walk the slow pointer from the slow/fast meeting point and a pointer to the head of the list 1 step at a time until they both meet (there's a simple explanation for this that I won't bother writing out).

I must admit I didn’t figure that one out till I saw the solution which was a “oh duh” moment. I don’t think i would have ever stumbled upon it without lots of hints during an interview.

The constraints, if correctly stated, can help a lot to figure what to do if you take a look at them closely.

In constant memory there's not that many things to do, a single pointer clearly won't be enough as you can't recall if you already visited the node or not, so `K>1` pointers must be used. If any two pointers moved at the same pace they would be duplicated and the second won't give any information. That and the fact that you can only move forward leaves a pretty constraint situation and acts as a guide.

It's not a bad thought problem, but I guess the fact that it's really unlikely to happen in a real world scenario plays against it (the memory on a hash table is probably way cheaper than the extra reasoning this takes). Also, knowing a bit about the answer is an unfair advantage, it might be more of a test on memory than on reasoning, which makes the problem bad for interviews.

I don't think it is a very good thought problem because I think very few would figure it out unless they have encountered the algorithm or a similar one before.

It is one that a lot of people will go "Aha, of course" when they hear about it but not figure out themselves.

I understand the reasoning now since I know the answer but I still don’t think I would arrive at the answer even with the reasoning. I don’t use it as an interview question so I don’t know if people ever genuinely solve it or just memorize the solution.

Isn't the round manhole covers just to make sure they can't fall in?

It’s actually several things. It’s stronger, cheaper, rolls, lighter, no need for alignment etc. You can make sure any shape does not fall in, but strength to weight ratio is important as you want people to open them with hand tools while supporting dump trucks.

PS: At ~250 lb you can see why a less optimal shape might be a problem.

It's also utterly irrelevant to the software engineering profession.

Less raw materials to produce, easier to transport by rolling, easier to place onto the manhole, easier to stack when transporting/storing in bulk, etc

Flies like a frisbee when Superman throws it...

Or better - Elastigirl! https://twitter.com/SamuelGavin/status/1008636415524171776

According to the Wikipedia [1]

Reasons for the shape might include:

* A round manhole cover cannot fall through its circular opening, whereas a square manhole cover might fall in if it were inserted diagonally in the hole. The existence of a "lip" holding up the lid means that the underlying hole is smaller than the cover, so that other shapes might suffice. (A Reuleaux triangle or other curve of constant width would also serve this purpose, but round covers are much easier to manufacture.)

* Round tubes are the strongest and most material-efficient shape against the compression of the earth around them.

* A round manhole cover of a given diameter has a smaller surface area than a square cover of the same width, thus less material is needed to cast the manhole cover, meaning lower cost.

* The bearing surfaces of manhole frames and covers are machined to assure flatness and prevent them from becoming dislodged by traffic. Round castings are much easier to machine using a lathe.

* Circular covers do not need to be rotated to align with the manhole.

* A round manhole cover can be more easily moved by being rolled.

* A round manhole cover can be easily locked in place with a quarter turn (as is done in countries like France), which makes them hard to open without a special tool. Lockable covers do not have to be made as heavy, because traffic passing over them cannot lift them up by suction.

[1] https://en.wikipedia.org/wiki/Manhole_cover

Ironically all the utility covers I see in the UK are square.

I also think the casting argument is a good one and its a lot easier to cast a round object than a square one (its to do with how molten metal flows)

Don't forget also: round manhole covers are a Schelling point.

Making a manhole cover round is one of the first intuitive shapes you'd think to make them (along with squares and rectangles); and so you'd guess, as a construction company gearing up to sell the concept of concrete manholes with removable iron-plate covers to a municipality (back in the 1800s or whenever we first got them) that what the municipality will ask you to make is round manhole covers. So you provisionally set up your tooling for round manhole covers, and build a few for the demo. And the municipality assumes you're the expert about good manhole-cover shapes, and so just goes with the flow, rather than trying to figure out the best shape themselves. So you end up with "the first intuitive thing that worked" spreading via network/"system compatibility" effects.

Same with road widths; same with screw drives.

Thanks for explaining why roads are round!

More like, why we got four-way intersections for so long before anyone tried roundabouts. It was intuitive to just drive one road through another, and then we added traffic laws and signalling on top to try to make it work, rather than anyone sitting down at the start to try to work out what intersection shape would optimize for traffic flow and [non-]accident rate.

Ok, that's actually an interesting (schelling) point!

> same with screw drives.

Which is why the "Robinson" screw head was invented (Canadians are immensely proud of this one)

https://en.wikipedia.org/wiki/List_of_screw_drives#Robertson

15 years ago I was interviewing for an engineering job and the VP of engineering at a company asked this question. I happened to have heard this question previously so spouted off a bunch of answers and impressed the heck out of the VP. And that is the real problem with this kind of questions. They largely depend on if you heard the question before or not.

I got into Oxford like that. Basically the interviews are a bunch of interesting questions like "How could I take the log of -1?" or "How is e defined?".

If you already know the answer, your main problem is acting like you're thinking it through.

When I interviewed for MIT I didn't get crazy puzzle questions. Is this pretty standard for Oxford?

Yeah for both Oxbridge unis the grades get you the interview but they could just fill the whole uni several times over with kids who got top grades.

So they reckon a 45 min quiz/chat is what will tell them who to admit.

Gets pretty open ended, favors people who can talk well.

I ended up not applying to MIT because you get your acceptance before Christmas and the US applications are huge. But my understanding is the US school interviews are more cultural fit?

The covers are round because the holes are round. :P

You’re hired!

That’s exactly why they’ve given up the brain teaser questions - all it checks is whether somebody’s told you the answer before.

I don't think the 747 problem is very predictive of how well someone can map out a business strategy.

I think a better question might be, "tell me how you've mapped out a business strategy in the past, and what are the strategies you've used to determine how profitable it would be".

But the real question is whether you can fill a 747 with internal policies and procedures!

^ this person is probably a PM at Microsoft. :-) When I worked there (over a decade ago) the place was so regimented you couldn't rip a fart without having to write a specification and estimating a schedule.

The manhole and 747 questions test for obedience and bikeshedding, not problem solving. Likewise the linked list reversal question tests for lack of planning and critical thinking.

These anti-skills will have been used quite regularly at Microsoft.

How does being able to reverse a linked list suggest that one lacks the ability to think critically?