One time a company I interviewed with asked me obscure algorithm questions about playing card shuffling. As a former professional magician I knew the optimal answers instantly and could jot them down straight away. They had allocated an hour for answers I wrote in a few minutes. I could have told them I had a massively unfair advantage, but I did not bother.
They were visibly impressed and told me I was moving on to the final interview stage right away. I declined, as I hate companies that select for algorithm puzzle skill instead of real world problem solving experience.
On the flip side, we questioned a candidate the usual way with pertinent technical challenges and so on. Then when driving in a van to lunch (our habit was to do a social segment as well as technical) I asked some puzzle questions - add 6 feet to a rope around the world, stretch it out and how far off the ground would it be? and suchlike. He was charmed, we brainstormed some answers and had a fun lunch.
Years later, now a senior Engineer at our place, he admitted he had been going to give us a miss that day, until that conversation in the car.
The rope question is more of a Fermi question[1]. Not that they aren't commonly called [2] puzzlers, but I think the distinction is useful. Fermis are about estimating, and that's an actual skill - innumeracy[3] is real.
What I would call puzzle problems usually involve some trick to getting the answer. If you can't figure out the trick, you're stumped. If you know the trick, you barely have to think to crank out the answer. Optimally solving the example in the article is one of those.
They weren't widely banned because they were too novel and charming. They were banned because "time to aha!" in any given instance doesn't tell you much about how someone solves problems. Also, because the bulk of the work at most jobs doesn't really resemble seeking "aha moments," these questions tend to select for people who thrive most on doing something other than the job at hand.
To me it definitely seems to be in the puzzler category based on those descriptions. The trick is realizing it's "just" asking you to solve the well known formula for radius to circumference, 2*pi*r=c, for c=6 would give r≈1 while you can ignore the rest of the information worded to trick you into thinking it's a complicated problem which would require a fancy solution. Of course if you're not dealing with geometry every day of your adult life it's more likely it leads to seeing what your general thought process is, such as "I'll fall back to Fermi Estimation to get a ballpark going".
I asked some puzzle questions - add 6 feet to a rope around the world, stretch it out and how far off the ground would it be?
I can only imagine being "charmed" by a question like if I was much younger in my career, eager to be seen as smart and in the company of like-minded folk.
Nowadays... my focus is on solving problems... as in real problems, not made-up ones. Thankfully I haven't heard questions like this in years. But when I do, I take it as a sign that they probably don't have actual, meaty problems to work on, that is, requiring higher-level cognitive skills (and actual experience). Not to mention that this was supposed to be lunch, and here they are asking filter questions, but pretending it's just "casual conversation" when obviously it isn't.
And so would probably pause for a second, and think of a way to tactfully end the interview, and thank the interviewer for their time.
Yeah it's easy to act all butt-hurt and be too good to even try. But how outrageous is it to imagine that folks who can solve such problems might be able to solve other problems?
Also, it's not about being too good to even try but about being old enough to no longer put-up with corporate non-sense; too much bullshit in a job to put up with as it is. Once you get to a certain age, you learn to prioritize real stuff rather than appearances.
A lot of people will find your questions obnoxious and irrelevant. Ask questions about the candidate's experience in past problems. Asking abstract questions to satisfy your own ego is a narcissistic trait.
That's not the point or context; No one likes "creative" interview questions is what people are saying like this is just a variation of brain teasers from 1990's Microsoft interviews.
I think you've got it backwards. Lots of people who could solve your real world problems with a computer might not have a background in maths or physics and so may not be able to solve your puzzles. They may just feel anxious about appearing stupid in front an interviewer, and annoyed they weren't allowed any downtime in the day.
This is about empathetically understanding the stress levels between both of you would have been miles apart. Unless the candidate had brought up the subject somehow it'd have been nicer to just try to relax them and get to know them informally by asking about them - or better yet letting them do their own thing for lunch if they wanted.
add 6 feet to a rope around the world, stretch it out and how far off the ground would it be
is this a technical puzzle/question? to me it reads like a middle school geometry question. it would be fun to discuss it with friends/colleagues but I wouldn't expect it during a software engineering interview
> Although finding the answer requires only basic geometry, even professional mathematicians find the answer strangely counter-intuitive.
I guess the more a visual person you are the more counter-intuitive it is. That only 6 feet of rope is needed to widen the radius of Earth at every place at continents and oceans ect at a whole 1 feet seems crazy to me.
sure, the answer might seem counter-intuitive but the method to find the answer is not, as long as you know the connection between a circle's circumference and its diameter
I still fail to see how this is relevant for a technical interview, assuming that we're trying to hire a software engineer. Fun, but not relevant.
Hah, I just did the math on this myself, found the answer to be 0.955 feet, and assumed I had done something wrong, or was off by a factor (or two or three) of ten.
It helps me to think about it in opposite terms. You're increasing the radius by ~1ft (radius around the whole earth), and 2pi is the linear relationship with circumference, so you'll get six ft. Thinking about it this way kind of ignores the fact the circle is huge. I'm not too visual of a person though.
I think that's perhaps a naive interpretation. At the core of this question are a number of assumptions, and concepts to think about:
- What is the rope made of? How stretchy is it? How strong is it to tensile stresses?
- What model of the earth are we using? A sphere (circular cross-section?) ellipsoid? Which axis of the ellipsoid? Does it take terrain into effect, or just gravitation? How does the rope avoid hitting terrain?
- How does the rope stay suspended? how does it resist gravity? are there uniform thrusters on it? How are they fueled?
- How is length added to the rope? Is it stretched somehow? Material added? How is the added material, if applicable, inserted?
Ultimately, I think we need to know what project requirement is driving the question to be able to answer this. It would shed light on most of these assumptions. If it sounds like I'm being pedantic or overthinking the question, I'd disagree: These considerations are critical to giving a meaningful answer; otherwise the question doesn't make sense. Unless we're talking platonic forms or w/e.
It does sound like overthinking to me, but context is king. Without context/requirements we're just guessing.
Maybe the job interview is for Space X and they're working on some new system of mini-satellites-on-a-rope called Hyper-rope, or maybe google is trying to pivot their failed Loon project into some kind of air-born connectivity solution, and the rope is actually a very long fiber-optic cable.
Or the interview could be for an online eCommerce platform and the person being interviewed will most likely have to work in a huge heterogeneous codebase with all the important technical decisions already made.
otherwise the question doesn't make sense
Well that is my point. I love these types of subjects, but when I'm having a beer with friends and we find a puzzle like this one and we try to take it as far as possible without going into fiction/bullshit territory.
So it could be useful to check/signal for culture fit, and in OP's case it actually worked like that
OP: "We value people that love to get into this type of discussions/arguments"
Interviewee: "Gosh, you guys bored me to death during the technical interview but it seems like we have similar tastes when it comes to theoretical puzzles so I'll give you another chance"
Nothing wrong with this though. It just proves that interviewing is a complex process and actual merit and success are highly subjective.
The follow-on is, if you add 6 feet and put your finger under the rope and pull up until it's tight again, how far have you raised your finger? 1ft? 10ft? 100ft? 1000 miles?
The answer to that is very difficult. There are several approaches.
Yes, but that's still a geometry problem. Don't get me wrong, geometry was my favorite branch of mathematics in school, but I don't see how this is relevant for most software engineering jobs.
I guess this type of question might serve the purpose of finding like-minded people with similar interests (in your case geometry or puzzles) but it might alienate others.
I solved a very similar problem (in the context of a pathfinding and obstacle avoidance sim) 25 years ago, and I can probably describe the thought process and geometry in very digestible terms, but if I had to code it in a whiteboard I'd likely fail.
An issue is that one person's trick question is another's straightforward problem. My college algebra students thought that every problem was a trick question, and that the only strategy for passing exams was memorization.
Was this a situation in which you were asking the candidate while everybody else either already knew the answer and was listening to the candidate think?
Or was it more like everybody was discussing (and explicitly or implicitly through discussion) admitting that they don't necessarily know the answer (while assumedly is an engineer in good standing on the team), and the group is working together to solve it?
Because both situations seem equally plausible based on what you wrote, and if it's the first one then I agree with your detractors below that it's messed up. If it's the second situation then I would have loved it and been excited to join your team.
It's very possible that the ambiguity of the situation is why there's such variance in reactions.
Really? You don't like to socialize with peers, with puzzles or tricky problems? Enough to make you refuse to join a company?
Discussion has gone off the rails here. Maybe I didn't make it clear - the puzzles were during casual conversation at lunch. Rebutting something I didn't say, is not fair.
Would have been a huge negative to me. I'm fine to chat with peers and discuss little riddles.
That is not what's happening when you're interviewing me for a job position. You're not my peer. We're not having fun. There's a non-subtle implication that my ability to answer the riddle will impact whether or not I get the job. I would be very annoyed if someone asked a puzzle like this too. It's not a novel puzzle. It's mostly a gotcha where intuition meets math. I could blurt out the answer. But I would instead feel it more important to slowly reason out the answer and appear to discover it on the fly. Which is pretty bullshit. And I would think you're not very smart for thinking this is worth anyone's time.
If I didn't know the puzzle and I failed to get the job I would be mad and it would stick out as something that penalized me unfairly.
In every interview I've done, lunch was explicitly bracketed by "this is a free, casual lunch that won't affect your interview at all".
And as an interviewer, I've never been asked to report on lunch chats.
> You're not my peer. We're not having fun.
Actually, most interviewers are your peers, and they typically know that you're under interview stress and are trying to help. If you can't take a break and de-stress during lunch, you're just hurting yourself.
The power dynamics at play makes someone spending time with me during an interview process where they have nothing to lose and can exert influence in the selection of me for a full time job offer decidedly _not_ my peer in that situation.
Every time I interviewed someone, I ALWAYS asked myself if I would want to work with this person.
Not just, can they do the job? Not just, are they technically competent? But, is this someone I would be comfortable going to, asking for help? Are they someone I can build rapport with, brainstorm new approaches and products with? Do they pass the "have a beer together" test?
Someone who explicitly has an attitude of, "You're not my peer, we're not having fun" doesn't sound like a good collaborator. Doesn't sound like someone who can be an approachable. Doesn't seem like a good mentor to newer members of the team.
> Someone who explicitly has an attitude of, "You're not my peer, we're not having fun" doesn't sound like a good collaborator. Doesn't sound like someone who can be an approachable. Doesn't seem like a good mentor to newer members of the team.
Interviewing is a high stress situation where the person performing the interview ultimately has power. What you're discussing here is how well I can socially fit in - regardless of pressures/stress on my side of the table etc.
It's 100% performative - if I am an interviewee I'm showing you the professional version of myself which is positive attitude and politeness. I'm upholding a social contract.
---
> Do they pass the "have a beer together" test?
I'm not here to have beers with you - I'm here to work. And, I think this is pervasive in regards to hiring. This can be incredibly discriminatory and I would appreciate you interview me on the value I can add with my labor vs. "can I have a beer with this guy?" That's weird to me, and as someone who interviews I work hard to not think this way... "Who I like" isn't necessarily who is going to perform in the role - I have to keep my personal preferences out of my professional decisions in my world... and I think that's fair.
---
Idk - interviewing is not fun for most people. I defend op's "we're not peers, we're not having fun" perspective both as an interviewer, and interviewee. I think it's a reasonable stance to take as long as they're outwardly presenting as professional and polite as that's what actually matters... not "beers"
Neither have I, but unless I was asked to deliver my interview evaluation before the lunch, you can bet any particularly good or noticeably bad flags during lunch would go into it.
Conversely, the couple times I had those "casual" lunches as a candidate, "I'm jetlagged" was a graceful way to lie out of the question why I wasn't eating much.
I feel like everyone here is missing OPs point. It seems like they had a mostly typical interview, which the candidate had probably been through a bunch of but for whatever reason wasn't to intrigued by the company. Maybe the candidate thought it was too boilerplate... I don't know. But then during lunch, when a handful of collegues are casually throwing around brain teasers, the candidate realized he would like the atmosphere. This doesn't seem too wild to me. But then again, software engineers are some of the most sensitive people I've ever worked with.
One reason for the lunch is to try and relax a bit and test “cultural fit”, which is more like a blind date between two people to see if there is any spark. Ideally it is a two way conversation, where the candidate and the interviewers get to judge each other.
There is a problem where cultural fit “tests” are heavily biased against minorities - for example most any sports discussion is dominated by your social class.
Enjoying brain teasers matches a particular type of geek, and the discussion likely veered or was encouraged in that direction by the candidate. It wasn’t Machiavellian, which perhaps you are more responsive to?
Asking puzzle questions during lunch interview is absolutely not just socialization. In fact I remember as a kid my dad explaining how lunch interviews are culture tests and how to succeed them- but it's very unpleasant for me. Best lunch "interview" I ever had was at Noname at Google some 15 years ago, it was just a relaxed conversation where we discussed the fact that Google's chefs made and served consomme.
I absolutely don't like solving puzzles with other people. On the other hand, I do enjoy writing code on my own, solving problems (not puzzles) and then sharing the results in a readable way with others.
I do like to socialize with peers, but never playing games (I prefer to play games on the computer against NPCs).
THe reason I don't like this is there are people who've asked me ludicrous puzzle questions before and they are proxies for 'people I wouldn't want to work with'.
I think there's a pretty clear difference between chatting about interesting puzzles between friends and asking annoying puzzle questions in a job interview. The power dynamic is very different, although honestly I don't often like those socially either. They can be deployed to trip other people up, make them feel small, etc. Can cause social anxiety.
As with most things, it depends a lot on the history you have with those people and the psychological safety you feel, so it depends? Definitely not with someone I just met and is interviewing me for a job.
And FWIW I also don't interview anywhere there are questions like this.
Happy to chat about puzzles when we really are peers. In an interview setting that’s not the case. For some candidates there could be a lot riding on the outcome of that interview and grading them based on puzzles that don’t really reflect day-to-day work is IMO kind of rude.
imho this is really negative. Early in my career I would have been self-browbeaten into answering such an interview question disguised as “fun” lunch conversation, but I would have hated it and thought badly of your company. Power dynamic, not subtle implications about getting the job, gaslighting, etc. all lead to a bad look.
At least normally when someone takes you out to the XYZ company “not part of the interview” lunch halfway through your eight hour interview loop and you chat small talk and background, there aren’t actual interview questions being thrown your way.
Imagine going to lunch and the interviewer striking up a conversation with “how many manholes do you suspect there are in New York.”
Well, I would have enjoyed that discussion. If the interviewer is capable of taking a break and having an engaging conversation about literally anything during an interview, that's a massive bonus in my mind. I don't need to hear about your plan to shake things up for the 10th time. If you can't see me as a person and not just a potential cog to make your department look better so that you get your bonuses, I don't want to work for you.
No, I go to work for an employer and work with my peers. My peers are not my friends in most situations. Maybe for you that is the extent of your social life so you think peers have to be friends, but you mixing the two together is your work/life balance limitation being applied to those you want to hire.
Are managers that naive with regards to power imbalances with their peers/colleagues?
I have seen people with similar insensitivity fail to understand why people in their teams dont like them: "but I treat them as if we are peers!! I like playing on the 'you are doing it wrong'games"!!
Agree that the amount of entitlement in this thread is wild. People, ostensibly respected principal engineers, will turn down jobs because they are asked a puzzle question during lunch. I _hope_ we are fortunate enough for this attitude to be a possibility in the next decade.
> "You don't like to socialize with peers, with puzzles or tricky problems?"
You have to remember that, after about 2010, the software industry is mostly comprised of people who are after a paycheck and their actual interest in computers, STEM, and other nerd activates is kind of minimal. It came as a shock to me too when I realized that the old shibboleths of being a hacker had become largely absent in the software industry.
Well, if you're thinking I said what I said because I'm not a pre-2010 hacker with an interest in STEM or other nerd activities, you'd be completely wrong. I started hacking on UNIX systems in the late 1980s, got a PhD because I wanted to be a scientist, and only went to work at Google to get access to their computer farm (where I built what was the world's largest idle cycle harvesting system, for science, at the time) although the pay was quite nice!
No, I said what I said because it's hard enough to be "on" during the coding interviews and also "on" during the culture tests, to also be "interested" in your puzzle. Wrong time, wrong place, wrong signal to send. Lunch interview (and the transport to it) is about learning about other people in a fairly non-competitive way.
When stretched, the length of the rope will be two straight lines plus part of the circle. The length of the segment can be calculated using a formula for horizon. Then we can create an equation: (s arc distance to horizon for h)*2 + delta = (d straight Distance to horizon for h)*2, or d-s-delta/2=0.
I think I found a small typo, where you have delta (instead of delta/2) in the third line. I believe it should be
sqrt(h(2R+h))-R * arccos(R/(R+h))-delta/2 = 0
This can be solved for h given delta numerically, such as with a spreadsheet. Use caution here because this formula leads to a loss of significant digits from cancellation of nearly identical terms.
For example, given R = 6378000 meters and trying h = 193 meters: the first (d) term is 49618.0 meters and the second (s) term is 49617.0 meters. The difference is 1.0 meter, which is the half delta we wanted. But there's been a loss of 4 significant digits (because the first 4 digits in each value are the same: 4961). The smaller the arc distance, the smaller the angle, the worse the relative error becomes.
It's possible to analytically factor out sqrt(2hR) from both the d and s terms. In the first case,
d = sqrt(2Rh+h^2) = sqrt(2Rh) * (1+h/4R) using Taylor series for (1+h^2/2Rh)^0.5
In the second case, I can derive one formula, but the coefficients aren't the same as my numerical best fit, which is
s = sqrt(2Rh) * (1-5h/12R)
Combining the two series versions for d and s, gives us this for delta,
delta = 4h/3 * sqrt(2h/R)
Finally, solving for h given delta, take the cube root of h^3:
h^3 = (9R/32) * delta^2
Thus for a delta of 2 meters, I get height h = 192.88 meters.
If companies told candidates why their applications were denied, sure, I'd be inclined to share my side. They don't, so fuck 'em. Play stupid games, win stupid prizes.
Previous company, I was a principal IC and I used to interview people. I was warned by HR never to discuss how the interview went or why the candidate bombed.
Their notion was:
1) We're there to find candidates, not improve people.
2) Time spent on someone you've eliminated is a loss. Cut your losses.
3) Think like you're talking to the police. Are you 100% sure you're not going to say anything that could be even remotely construed as illegally discriminatory?
4) Most states are 1-party-consent for recording, and even if it's an inadmissible recording, them having an interaction recorded can come back to bite you if they use it to jog their memory to perfection.
I think it's gross, but it's a litigious race to the bottom so I kind-of see their point. Really happy not to be an interviewer anymore.
I mean, I've been on the other side too, I know why companies don't share that information. But, given that they won't, why should I waste my time and energy?
I had a bit similar story, though it went a different way, and prompted a few other thoughts...
Earlier in my career (a few years before Google seemed to start the current techbro rituals), I went to an interview at a big-name CS dept. spinoff company which had the same problem: CS students and professors with no professional software engineering experience deciding what's most important for professional software engineers to know.
The interviewer and I were both senior engineers at well-regarded companies, but he gave me a coding exercise (this was not usual, at the time), and it was a CS101 tree traversal coding exercise in C. I'd happened to remember that day of class from community college, and I just did the exercise. Nothing to brag about.
Then he said "no one ever did it that fast before". So, feeling very confident and a bit disappointed/surprised, I started telling him what I thought was a better way to do interviews for software engineers. (Spoiler: it didn't involve regurgitating CS101 algorithms a person randomly happened to recall.)
I got the offer, and accepted the job, partly because we had a collegial discussion about the interview methods. Very smart and likeable people. But there were a lot of people who arrived from top university departments not knowing how to do software engineering nor even how to do non-homework computer programming, but they apparently passed the interview of the CS undergrads' idea of what's important to software engineering.
(Actually, the person from there who I noticed on LinkedIn many years later as eventually most accomplished from there, was the only one I knew came from a commuter state school, rather than from a big-name CS department. I don't know whether he would've gotten in, once techbro rituals took over. Maybe he would've, if his school's department had switched to teaching to the techbro interview; though, then, maybe that would've been at the cost of whatever skills development later helped him be so successful.)
As someone who's never interviewed at FAANG and only ever gotten either relevant (paid!) take-home programming assignments or the CS101 bullshit the author talked about, what do you mean by that?
This is what happened at my Oxford interviews. They asked me stuff that I knew the answer to, thinking it would be one of those see-how-he-thinks things.
Biggest problem was acting like I didn't know and getting it really fast.
Total lottery, they could have asked any number of things that I didn't understand.
Ya, this is hard. I bombed an Amazon interview because the interviewer asked me Alien Dictionary, a well known LeetCode problem that I already worked out while practicing. I told her outright that this was a problem everyone practiced, but she still dinged me for already knowing the answer and not going through the “figure this out flow” (admittedly, I could have handled that better, but it is actually difficult to work through something that you know the answer to but forgot how you got the answer).
At least it was for a job I probably wouldn’t have taken.
Is the answer to convert the letters to integers, then compare that list of integer strings before/after alphabetizing it? I haven’t studied leetcode (never needed to), but this is the first thing that occurred to me…
> it is actually difficult to work through something that you I am the answer to but forgot how you got the answer
Well, yeah. That's a big part of the point of the question. Anybody can Google the answer. Do you understand it well enough to explain it, and if you don't, can you walk through your thought process as you figure it out.
I failed to practice answering questions that I already knew the answer to. I also think the interviewers style had something to do with putting me off balance (it became adversarial after I pointed out this was just alien dictionary, I probably would have had a better result pretending not to have seen the problem before). Or maybe that’s just how things are at Amazon?
My Google and Facebook interviews went much better in comparison. None of their questions were top ten LeetCode ones.
> I failed to practice answering questions that I already knew the answer to.
You failed for the same reason you would have failed if you had never heard the problem before. Knowing the answer has nothing to do with why you were dinged.
The interviewer turned really adversarial when I told her this was a common LeetCode problem. I guess you really had to have been there. Alien dictionary isn’t that hard otherwise, if I were allowed to work through it rather than explaining how it worked, things would have gone much better.
I’ve had this happen to me before and disclosed it during the interview. Consistently, the response was the interviewer telling me they were impressed that I was well prepared, and to go ahead with the answer.
The vast majority of your coworkers will have gone through a similar if not identical interview process. Do you prefer to work with people that pretend they've never seen a question before when they have? Then do that. Do you prefer to work with people that admit they have seen the question before but are not directly penalized for it? Then do that. If you somehow are penalized for it... you dodged a bullet.
As an interviewer, I would prefer (in this order):
1. The candidate has actual domain experience matching the question and can rattle off the answer in their sleep. We can use the remaining time to go deeper into the question and probe the boundaries of candidate's knowledge. [maybe 1 out of 200 candidates actually deliver this]
2. The candidate came prepared, studied the question ahead of time, can rattle off the answer from memory. As above, with the question out of the way, we could use time to explore around the topic and find areas the candidate didn't study but still can work their way through. It's rare that you see someone who memorized a perfect answer, but then can't go further purely because they have no canned response.
3. The candidate doesn't know the question ahead of time, and legitimately "thought hard" and solved it on the spot. We may or may not have time to probe further, but candidate has shown the ability to reason through a problem outside their domain.
[above this line is my "hire" bar, below is unfortunately the vast majority of candidates]
4. The candidate doesn't immediately get there, but can be guided through with hints and can follow the bread crumbs I'm laying.
5. The candidate tries but, for many possible reasons, struggles, goes off down wrong-way roads, and doesn't make any progress.
6. The candidate freezes up, deer in headlights, won't produce anything.
7. The candidate talks and talks with a prepared speech about his background and skills, but doesn't actually do or solve anything [yes, I've seen this multiple times]
I usually asked as an interviewer if you had seen the material before. If you were honest, it was very impressive, you could give your solution, and we could also cover other material.
Can you elaborate on what made the question obscure? I'm asking because I used the question "print out the first 52 numbers in random order"in interviews before, and the answers seemed to give a good hint about understanding of basic CS concepts.
It might be the difficulty of actually getting it right (if by "right" we mean that all 52! permutations are equally likely. Or perhaps it is more accurate to say the ease of not getting it right.
Something like this:
10 pick a number from 1 to 52
20 if not already printed it
30 print it
40 if we have printed 52 numbers
50 halt
60 goto 10
works, but could take arbitrarily long time. Most people prefer bounded run time.
Most people seem to come up with something like this:
array = [1, 2, ..., 52]
for i = 0 to 51
j = random(0,51)
swap(array[i], array[j])
print(array)
That has bounded time (constant time assuming random and swap are constant time). Unfortunately not all permutations are equally likely.
We can see that all permutations are equally likely by noting that there are 52 iterations of the loop, and each iteration has 52 possible outcomes. That gives us a total of 52^52 possible outcomes. 52! does not divide 52^52, so it is not possible for each of the 52! possible outcomes to be equally represented in the 52^52 outcomes.
To fix this, you can use the same basic idea of going through all 52 places in your array [1, 2, ..., 52] and swapping each with a random location, but instead of swapping the Nth location with a random location in the whole array, swap with a random location that is not earlier in the array.
Then you still have 52 iterations, but now the number of outcomes varies by iteration. The first iteration has 52 outcomes. The second has 51 outcomes. The third 50 outcomes and so on down to that last having only 1 outcome. That gives 52! possible outcomes, all equally likely. We just then have to show that every one of the 52! permutations is among those outcomes which is easy to do, and then we have shown that this is a correct shuffle.
What’s nice about this example is it provides lots of scope for discussion (as you did) without requiring much domain experience.
If the person can’t program their way out of a paper bag you’ll find out right away.
If they are a junior hire, any working answer is fine.
If they have more experience they can start to talk about why they chose the approach they did.
If they are quite senior you could talk about the benefits and limitations of different strategies, as you did.
In my case (if I still applied for programming jobs, which I don’t), I’d most likely do a naive shuffle and then discuss how problems using random numbers involve corner cases that require thought and domain knowledge I don’t have at my finger tips, so we could talk more about the (pseudo in this case) application needs so I could (in the real world) focus on the most important constraints.
As an interviewer I’m as happy, or even more happy, when the candidate knows their domain limitations and where they are important and where they are not.
If I was interviewing people what I'd probably do is pick 3 or 4 LeetCode problems, but not ask the person to actually solve them.
Instead, we'd pick whichever of the problems they find most interesting discuss the problem specification, and how we might approach it. We'd discuss what difficulties and special cases we anticipate. Then we'd look at the answer together and see if it seems to make sense. In these discussions I'd try to let them take the lead but would contribute enough to get things moving if they are getting hung up on something.
Finally, we'd go to the most valuable part of LeetCode, the discussion forum for the problem. In the discussion many people post their solutions and a lot of them are wrong. We'd look at a few of those and review them, again with me letting the candidate take the lead.
The great thing about the discussions is that the answers people post contain a wide variety of mistakes. Some don't solve the right problem. Some do get the right answer but don't meet the time or space constrains from the spec. Some miss edge cases. Some fall apart if the problem is too big (e.g., if an input array is big enough that every unsigned integer the language supports is a valid index).
Before we started I'd tell them we are going to do that, so when they hear the word "LeetCode" they don't have to worry even for a moment that I'm going to spring some hard trick question on them and expect to solve it under pressure. I'd probably even ask them if they have any LeetCode problems they have seen or did before and would like to use for this discussion. Since I'm not asking them to solve them, it doesn't matter if they've already seen them.
I agree, but there is a reason for having the candidate write some code: some people can talk a good talk but can’t actually write a line of code. That’s a phone screen fail, but yes, some people pass the phone screen, so the sooner you figure it out the better.
When I say “some code” I mean no more than ~20 lines and who cares about missed semicolons or such.
And only one or two interviews need this, the subsequent interviewers can do more of the important stuff you’re talking about.
Another important point about these discussions: train your interviewers. I hate interviewing with (for that matter Working with too) someone who wants to show how smart they are. If we bring someone in for a round of interviews it’s because we want to hire them so are looking to see if our prior judgement is correct. Don’t be mean to the candidate and don’t waste their time or yours.
This question came up in a weekly "random topic" talk that we had at an MIT lab I was visiting at the time, many years ago. One of the lab members - who was a very impressive coder and researcher - had been asked this question at a google interview. I remember being pretty surprised that he wasn't familiar with the fisher-yates shuffle (and that this would be considered a good question to ask at google). His first answer to the problem was actually one of the "obvious" (and incorrect) answers one might give. But then he also walked us through the process he went through with the interviewer on deriving a correct algorithm, along with a mathematical justification of its correctness. I think regardless of whether one is familiar with the typical algorithms, being able to explain and justify them does show skills. (And fwiw, he did end up getting an offer and working at google).
The questions I got were very specific to playing card patterns. The one I remember best was "How many times does it take to perfectly cut and shuffle a deck of cards before it is back in original order". Spoiler: A "perfect" shuffle is called a Faro shuffle and the holy grail of false shuffles to master as a magician. When a deck is cut evenly at 26 cards (doable with practice or a slightly bent or irregular marker card) and Faro shuffled correctly eight times, the deck will return to its original order.
If I really liked the company I might indulge your question, but it would annoy me unless you were a game development company and this was a real problem someone faced recently.
I general I don't like live coding questions because they don't reveal anywhere near the quality of work I produce if left alone to think for a bit. If the questions pertain to a real world problem I will noamally indulge them though. As an interviewer I don't make people do them. I often do live code -review- to see if people can understand code and spot security flaws or bugs as I find that a more useful skill than coding anyway, and code review -is- something actually often done together with peers in the real world.
I sometimes ask for people do take-home tests if they have no open source projects I can reference, because seeing how people code on their own is how I find out if they can do the job. If they use search engines to help, I don't care. That is how real life works.
That said, I only do this if I know the employer is willing to pay them for the time. Work simulation goes both ways.
If I am going to make it like real work, I need to pay for it like real work.
Stuff like whether the algorithm will always stop, or whether it runs O(N) vs O(N square). The main point to me was more to be able to have a conversation about the solution rather than it being absolutely right. I remember quite a few people using randomness, the most odd (and totally wrong) one using a random sort function over an array of (1..52).
Random sort meaning that sometimes a>b, other times a<b for the same values. Whatever algorithm a language's built in sort implements probably assumes that comparisons are consistent. I remember checking a few versions of perl and some created a core dump iirc.
Ah okay. Thought you meant using something like shuffle in Ruby.
I do wonder what the result of doing a randomized sort like that would be. Probably not really random. Feel like numbers near the median would be overrepresented in the middle of the array.
What is the catch here? In multi dimensional and infinite cases it can be a little tricky, but in this one is there more to it than "all permutations should have the same probability"?
I'm not an expert, but here are a few of the things that come to mind for me:
- One conception of random is subjective: the pattern must not be predictable by a particular person/entity. E.g., the Fibonacci sequence may seem random to a person with IQ 3, but not IQ 1000.
- I think related to that is the concept of cryptographically random: [0]
- Random numbers can have different statistical distributions. You referred to uniform randomness, but depending on the application, that's not necessarily what you want. E.g., [1] Especially for statistical / Monte Carlo modeling.
- Depending on just how random you need something to be and to whom, you may or may not need specialized computing hardware. [2]
- Sometimes people kinda want random, but they also want reproducibility if necessary. Think randomly generated unit test input, or randomly generated game levels. For those applications, it's helpful to know that most software uses pseudo- -random number generators (PRNG's). If you can remember the specific number used to seed the PRNG stream, you may be able to deterministically re-execute the code at will. Alternatively, if you want to (nearly) guarantee that subsequent runs of the program aren't the same, you'll want to somehow ensure that a different seed number is used for the different program runs.
So if anything about the job opening depends on this kind of stuff, IMHO it's a great interview question.
I have been routinely questioned about what happens from when you type www.somesite.com and when the webpage is displayed when interviewing over the years and realised that nowadays I could fill 2 whole hours talking about all the stuff that actually happens (and many times I would have to say “but about this specific thing I’m not very knowledgeable about)… whereas at the start of my career i would have probably spoken for like 15 seconds and felt smart about answering “such an easy question”.
Obligatory response, Dilbert’s “9… 9… 9…” number generator, “the problem with randomness, is that you can never be sure…” https://www.dilbert.com/strip/2001-10-25
"I could have told them I had a massively unfair advantage, but I did not bother."
I guarantee they knew you had an advantage without you saying something.
That's the whole point of interviews - to find the candidates with the advantages over the other. The question becomes whether a specific advantage is unfair, or if any advantage is unfair.
I answered one of those mind benders nearly immediately in an interview. I figured out the trick as they were telling it basically. They asked me if I had heard it before. I hadn't. A final interview with the CEO and he asked if I had heard it before and I said I hadn't. I later realized based on how they were asking if I had heard it before, they thought I was lying.
The question: You get on a ski lift going up. It's 1000m long and you move at 20m/s. Between when you get on at the bottom and you get off at the top, how many of the chairs going down do you pass?
I hate this question because it has an implicit bias that most likely the interviewer never saw. It's biased towards people who have ridden on a ski lift, which generally means someone wealthier.
If you're a poor kid who's never been skiing, you'll have a harder time conceptualizing the answer.
So... the answer is "impossible to know"? There's no data on how many seats there are, their distance, or whatever. There could theoretically be literally just the seat you're sitting on in the entire system. Then the answer is zero.
Let's neglect the horizontal distance the chair(s) travel at the bottom and at the top of the lift. Then the answer is "all of them," which holds true in your one-chair scenario.
The question reminds me of "how many groves are there on a vinyl record?"
Since I don't drink coffee, you are unlikely to ask me that question. But if you did, I might assume you are either joking or an idiot ;).
Clearly, it's a trick question (with unnecessary details to distract you from a possible solution) and the one asking probably thinks they are very clever. So now, whether you accept an equation or insist that it's impossible to solve when it's not really comes down to how you want to play that game.
It's n-1. I should have put the number of chairs in the question. I wasn't really trying to quiz everyone here, just identify which mind bender it was.
The "twist" on the answer is that you start below all the other chairs and finish above all the other chairs, so you must have passed them all along the way. I saw this immediately and answered "99" or whatever it was. In retrospect, I think they couldn't conceive of anyone figuring it out on the fly.
I suppose you assume the chairs are at even distances?
Imagine there's a circle with marks evenly spaced, eg roots of unity. When you rotate it halfway, the point that started at the bottom has passed (vertically) all the other points ahead of it, because at some stage each point has reached the top and started going down.
It could be sum of all the chairs -1, could be -2 if the chairs are two per row, could be that the hub where they turn around has a large radius and the spacing of the chairs is close enough of that you don't "pass" them, could be 0 if there aren't any other chairs.
I suspect the answer to this is "not enough information", which, I suppose, hints at an applicants requirements gathering thought process?
OT: I once wondered if normal human shuffling could actually achieve all possible permutations, where by "normal human shuffle" I mean take a deck of cards, split it into two roughly equal piles, and then merge the two piles by repeatedly taking the bottom card from one then the other, with some sloppiness in the "take the bottom card" part so that sometimes you might take more than one card but not too many.
The answer is yes. Here is a way to do it, although it is not very efficient.
Let P be a shuffle where the deck is divided exactly in half, and the merge perfectly alternates one card at a time between piles, starting with the half that was in the bottom before the cut. Let S(n) be a shuffle that is almost a P shuffle except that when the cards that would end up at locations n and n+1 in the P shuffled deck are at the bottom of their piles we drop them in the opposite order then go back to the normal drop order.
S(n) counts as a normal human shuffle. The result of an S(n) shuffle is the same as doing a P shuffle followed by swapping the cards at positions n and n+1 in the P shuffled deck.
If you take any deck and apply the same shuffle repeatedly you eventually get back to where you started. For example doing P 8 times brings you back to where you started. Let O(R) be how many shuffles it takes for shuffle R to come back to where it started, so O(P) = 8.
If you do O(S(n))-1 applications of S(n), then P, then one more S(n), that brings you back to where you started except that the cards at n and n+1 are swapped.
With this we have the capability to exchange adjacent cards in a deck. Any permutation can be reached by a sequence of adjacent exchanges, and thus normal human shuffling can reach every permutation.
As I said this method is not very efficient. The swap of n and n+1 by this method takes 120 shuffles if n is 22 or 28, 72 shuffles if n is 0 or 50, 56 shuffles for 1 or 49, 40 shuffles for 16, 17, 33, or 34, and 16 shuffles for any other n.
Putting the whole deck in a given order would then take tens of thousands of shuffles. Inefficient indeed!
That raises the question of how many normal human shuffles does it actually take to reach a given permutation? What permutation requires the most normal human shuffles?
I had the dunce's version of this. They asked me if I had seen the problem before. I (truthfully) answered yes, and they moved on to a different problem (which I aced).
I didn't tell them that I completely failed when given the original problem and didn't learn the right way since. And have bad memories of doing it and would probably panic if I tried again during that interview.
They were visibly impressed and told me I was moving on to the final interview stage right away. I declined, as I hate companies that select for algorithm puzzle skill instead of real world problem solving experience.