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....)
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.
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.
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?
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.
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.
If you've never seen the pattern before, there is a very good chance that you're hosed.
Edit: found it [1]
[1] https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoi...
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.
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.
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.
It is one that a lot of people will go "Aha, of course" when they hear about it but not figure out themselves.
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.
If you already know the answer, your main problem is acting like you're thinking it through.
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?
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.
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
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)
PS: At ~250 lb you can see why a less optimal shape might be a problem.
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".
These anti-skills will have been used quite regularly at Microsoft.
>(Note: I started at Microsoft when we were still asking questions about why manhole covers were round, how many ping pong balls would fill a 747, and how to reverse a linked list. In 20 years here, I’ve yet to have to write the code to reverse a linked list (copy-paste anyone?) or fill a 747 with any kind of ball.)
The manhole cover question is actually a valid industrial design or UX question even if it's not appropriate to ask for software interviews. The linked-list question is the equivalent of Fizzbuzz for data structures. And the 747 question is a valid Fermi problem. The exact number doesn't matter but the steps required to estimate the answer are similar to other estimation problems when mapping out a business strategy and trying to determine if it's profitable. Or maybe the company is interested in salvaging sunken planes: https://www.iusmentis.com/patents/priorart/donaldduck/