That’s not cheating, that’s not a problem at all. Neither ethical nor otherwise.
You happened to know a working solution, this was by chance, but you also managed to sell it, explain it and it’s a solution you developped.
And the fact that the poster did well on the full-day follow up at Redmond and was invited to join either of the teams he interviewed with means that he was certainly qualified to pass the on-campus interview.
I wouldn't even call this cheating to be honest, people practice interview programming questions all the time, he just practiced the right one for the day.
He cheated more on writing a clickbait title than actually "cheating" on the interview. This is the same thing as when a kid in class thought studying was a way to cheat.
That's harsh because TFA does mention that they feel outright uncomfortable (even after 18 years!) how big a role luck played in them clearing that fizzbuzz interview question:
> I've struggled with this a lot over the years, but I finally decided to share my story. I don’t think I would have made it past the first round of interviews at Microsoft if I hadn’t gotten so lucky. So pretty much, my entire career is built on one amazing stroke of luck.
...which explains why they felt like they "cheated".
Out of pretty much all the people I know, I can't think of any successful career not pivoting on one such fateful moment of "luck". One lucky question/answer, one fortunate encounter, one near miss. Of course we'll never know how the road not taken looks like. Any moment could actually be a pivotal one but most are very unassuming and only the memorable ones stick with us, making them feel more important.
Also, as someone who's been tested with this kind of questions (in the math and physics fields at least), I realized many times you aren't evaluated for knowing the answer but for how you go about trying to find it even if you fail.
This particular question is close to my heart as I was tested with it as a pupil in school. The teacher wrote this on the blackboard and asked me to come over and solve it (not having any prior knowledge). After a bit of fidgeting with the chalk I stared writing on consecutive lines 1, 1+1, 1+1+1 and after a few lines it dawned on me it looks like the "lower" half of a square of side n as cut by its diagonal. So I proudly concluded that the sum is n^2/2. Which was of course wrong, I forgot to add an n/2 to that since the "diagonal" is shifted right a bit. Still got top mark and maybe it was one of those moments that set me on a path. This went on through high-school, university, post graduate studies, and early career. It was only when I was knee-deep in real work that people started to care less about how I think and more about just the end result.
Preparing for this kind of question isn't cheating as long as you understood the answer.
I remember this too, from our 4th-grade "G&T" math teacher telling us the story. Although I use the formula so rarely that I don't keep it memorized, whenever it does come up, I think back to that day in class and that moves the gears enough that I can derive it empirically pretty quickly from small-number examples and the knowledge that it involves two consecutive numbers.
> Out of pretty much all the people I know, I can't think of any successful career not pivoting on one such fateful moment of "luck". One lucky question/answer, one fortunate encounter, one near miss.
> Preparing for this kind of question isn't cheating as long as you understood the answer.
TFA notes that because of lack of interview prep material in 2004, even when the author knew the question before-hand, it took them days to arrive at an optimal answer. And then it dawned on them that everyone else at the job fair, who may be seeing a question for the first time, only had 15 mins in a pressure-cooker situation to solve it.
TFA also notes that the author intentionally misled the interviewer as if they were solving the puzzle then and there: I casually explained how I could simply use a mathematical formula to calculate the sum of 1 to n (like, who doesn’t know the sum(1 to n) formula?) and compare that to the sum of the integers in the array. I slowly wrote out the solution I had come up with over days of thinking about the problem, being sure to pause periodically as if I was figuring it out for the first time. I talked through my thinking and made sure I had all the proper error checking in place. I double and triple checked my syntax. My handwritten code was perfect.
I won't lie to someone's face but I've deliberately misled gatekeepers hundreds of times in order to grab the opportunity to deliver excellent work. People are judgy and scared, and we all know the exchange rate between false positives and false negatives is a farce, and when it comes to my ability, you're damn right I know better than they do. The idea that I have a moral obligation to gift them decisions about my future is laughable. I've never had any complaints and I've never lost a minute's sleep. If they don't like me after they've known me more than 45 minutes, they can put me in review and fire me. I won't cry about it.
I understand that I just don't consider it cheating despite their reaction during the interview. I'm not going by any formal definition of "cheating" here. But this person took the question as a practice question, not with the knowledge that it will be asked. They also did the work on proving and understanding it.
Let's put it another way. If you take an exam after practicing with any kind of practice questions (something that has been done since the dawn of time and the education system) and happen to run into the same questions in the real exam, was that cheating or better targeted learning? Or if you find out about a job from a friend who works there, is it cheating because you have a significant insider advantage over people who never knew about the job?
In my opinion true cheating would have been made up of a) someone feeding them the real questions and/or b) someone feeding them the answers. It involves an unwillingness to put in effort and a premeditation that I didn't see in the story. This person was indeed in a conflict of interest but I wouldn't call them "a cheater".
P.S. If I were in that interview I would have provided the full answer almost instantly, not needing any kind of hesitation to "simulate" the thinking process. I know the answer without any relation to the interview. So there could be 2 outcomes: a) I get unfairly excluded under the suspicion of cheating justifying the need to fake the thinking to avoid this or b) I would have passed to the next stage making that whole charade effectively inconsequential.
Gotcha. Btw, I'm personally in agreement with you, as that's how I think about it all, too. TFA wasn't, and I merely attempted to point out why.
GP's claim that TFA might be over-exaggerating it a bit for marketing purposes may also be correct, given that it was authored by an exec at a recruitment firm.
I believe that the attention he is seeking is simply marketing. Almost all of his content revolves around hiring and working in tech, which is the core focus of his business. The overall trend is, "I've seen the bad, and built something better, so check us out."
I don't have a problem with people marketing themselves on LinkedIn - it that not the entire purpose of the site?
lol thanks! I actually hate the attention, in part because of comments like this one. Though this one was comparatively mild.
I do it to generate sales leads for my startup. We're bootstrapped so being able to generate leads without any ad spend or outbound sales means we don't have to raise money to grow. I used to write blog posts but they take so much longer. Hence no new posts on the blog since 2019.
Now I focus on LinkedIn. A single viral post on LinkedIn can get 2M-5M views on average. It will generate $1M-$2M in potential business for us. This way I can spend 50% of my time writing code, 45% doing CEO stuff, and 5% doing marketing.
Its not cheating but it's absolutely unethical. OP is right that they should have disclosed that they had seen the problem before. It only is that the right thing to do but also good interviewers can tell when you genuinely thought about a problem vs just regurgitated the solution.
As unethical as the hundreds of interviewers who pretend to believe that the candidate in front of them, just somehow managed to find within minutes the solution to some programming puzzle, and not through hundreds of hours of mentoring and self-practice.
I would propose to change coding interviews to the following scheme:
Step 1:
Interviewer ask a coding question. If candidate is able
to answer correctly then move to Step 2
Step 2:
Candidate asks a coding question from Interviewer.
If Interviewer answers correctly go back to Step 1.
If Interviewer is not able to answer correctly
in 60 min, and Candidate is able to explain solution
and implementation, move to Step 3
Step 3:
Interview is over and Candidate automatically
qualifies for next hiring phase.
I agree that interviewers asking stupidly hard questions that they wouldn't be able to figure out in an interview is a problem, but I don't see how your solution would remotely work. How would you ensure the questions are equally difficult?
If the candidate can manage the question the Interviewer should be able also. After all he/she was already hired.
If a company decides to approach hiring with the naturally confrontational approach of, "let me find out in 60 minutes if you are smart enough to work here", I don't see why it should stop there.
After all recruiters always mention, it is good for you if you are also inquisitive, show interest in the company and ask questions :-))
Why can't a candidate also check if their future managers and the company are
worthwhile to work there? It is always mentioned that a candidate is a much interviewing the company as the company is interviewing them...
Now...how many interviewers are suddenly uncomfortable? ;-)
Is that not what is happening, when the candidate pretends he never seen the question during the interview but in reality he practiced it before on LeetCode :-)
Ohhh you mean the candidate should just be able to test the interviewer if they want, to see how technically capable the interviewer is?
That's an interesting idea. I'd support that as an interviewer - I think the question candidates ask would also give you some information about the candidate too.
Sadly I doubt that sort of thing would ever become normal. Plus interviews already take enough time. Not sure I'd really want them to take any longer.
Not only is it clickbait, the author is founder and CEO of a technical recruiting company. Clearly the article is written to generate leads for Facet. This is basically just astroturfing. The author should have opened with a conflict of interest statement at the very top.
Also, OP should have included (2019) in the title. It's kind of an old piece.
I remember this formula was part of a book called "Formelsammlung" (german for equation-collection) that we were allowed to take to math exams in university in cs. This is a simple know or don't than you have to deduct issue.
If this would have been true, he would have asked about Gauss (it's one of the most famous math tricks in highschool afterall). he didn't ask, op didn't know either. so I would have suspected cheating.
op's answer is constant n, but could have been improved to n/2 on average with a hash table. (but some constant overhead). so it really depends on the size of n.
I told that story to my friend's daughter a couple of years ago. Next time I visited she was excited to tell me how she used it to win a sheet of stickers by betting one of her classmates she could add up the numbers faster than they could with a calculator. It was clever of her to add the calculator handicap into the mix. Makes me wonder if there are math hustlers outside of casinos.
I think it's fair game. You called ahead of the job fair, which allowed you to prepare.
They were also lazy with their recruiting questions.
If they wanted to select on skills instead of knowledge of interview question gimmicks, they would have asked for a link to your profile showing off your work, and look at it after the fair.
Arrest this man! How dare you practice for an interview? /s
Granted some people practice 100+ questions, you practiced only 1, and it was the right one. Same same.
Lucky indeed, but I wouldn't attribute your success to luck. You were clearly a good enough engineer to receive 2 offers, and good enough to build a career there.
We all have multiple encounters with low-probability scenarios in life. If you have a 10% chance of succeeding at something, and you have 50 attempts, and you only need one success, then your actual chance of succeeding is 99.5% rather than 10% - almost inevitable.
I'm surprised that atm there is a consensus in the comments saying that it's not cheating. Companies ask interviewers to not reveal the questions they had to other candidates. It's likely that his friend was told not to say that. Overall he clearly had an unfair advantage, and even if legally it wouldn't be the definition of "cheating" it would go against the intent of the interview: which is to evaluate candidates in front of a new problem.
Kudos to the author for being honest about all this. I think it's a real issue and that we should find more solutions to prevent this than candidates signing an NDA.
Imho when doing such interview, questions should not rely on a "trick" and even if they do, candidates should be evaluated on everything else: how they explain the code, how they react to feedbacks, how easily they transcribe what they explain to code. It's not perfect but it helps.
A good example to make this question more fair, as an interviewer, would be to rapidly give the (n-1)*n/2 trick quickly if the candidate doesn't know it. And not care too much if they do know it.
Comapre it with people who applied too, but didn't have that "internal" knowledge
Is it fair from that "not well networked" person perspective?
It's not even like he found this question randomly on the internet, he got it from MSFT employee, lol.
I have really mixed feelings about this
Edit.
Don't get me wrong, apparently author was(and is) capable of doing his job, so it isn't a big problem, but what if author wasn't capable of doing the job and passed just due to the advantage?
I know person who told beginner programmer what X company asks on interviews and that guy actually managed to pass that interview due to the knowledge
but was fired like 3 months later due to lack of skills
> Is it fair from that "not well networked" person perspective?
Fairness becomes a bit of a contrived concept once you start to factor in higher order effects. Then it just turns into fair if it advantages me, and unfair if it doesn’t.
I helped a friend get a job once because I knew who was going to interview him, and I knew he had a blog where he published all his thought-leader technical opinions.
Is that fair or unfair? Probably neither. It’s more of a random coincidence that my friend benefitted from this. But is it fair that I have learned more about my local industry by going to industry events and listening to people present things, and talking to people, etc? That probably is fair, and that’s how I learned the tip I gave to my friend.
Fairness isn’t really relevant to the problem here. If you believe that there is a problem at all, then the problem is that the screening process can be influenced by random coincidence.
> but what if author wasn't capable of doing the job
Than Microsoft would've been scammed out of $350 worth of plane tickets, $150 worth of hotel commodations and $1000 worth of employee time. Hardly the end of the world for a multi billion dollar company
> and passed just due to the advantage?
Passed a six hour Microsoft on-site grilling due to knowing the question for a 15 minute off-site interview question?
While I can absolutely see why people would view this as cheating, I'm also not sure what he was suppose to do. It's a case of: "Hey, look, I really want this job so I took the time to prepare and studied the kind of question you might ask. I happen to know the answer to this question, could you ask a new one that I don't know the answer to?" If I where the interviewer, I'd just stop the interview at this point and move the candidate along to the next interview anyway. He's clearly smart enough and has already invested time.
Personally I don't put a ton of value in question like this, so I'm less inclined to view it as cheating, and more like proper preparation... and a bit of luck.
Close to 0% chance someone would find out, as that would involve the person revealing the question also facing consequences - unless the company has some elaborate scheme involving modified and unique questions tailored for each candidate, and keeping track what candidate got which question. But that obviously wouldn't work with a trivial question like the one OP got.
Either that, or some third party which could have intercepted the communication between OP and the friend revealing the question. But again, what are the chances...
And on a tangent - should candidates "grinding leetcode" reveal that they've encountered the question before? That's the whole point of leetcode.
I've seen candidates deny that they've seen the problem given, blitz through the basic version (intended as a quick warm-up), and then completely choke when a slight twist is added. Let's just say that really raises some questions...
It's not even a trick, though. The sum of zero and n is n. The sum of 1 and n-1 is also n. So is the sum of 2 and n-2, and so on. There are n+1 numbers when counting from zero to n, and they can be paired so that each pair adds up to n.
It's a pretty obvious thing that anyone who spent much time thinking about math as a kid or teenager would have encountered, and maybe that's who MS wanted to hire! Especially back then when more of their programming needs dealt with algorithms and mathematical thinking, as opposed to gluing libraries together, I think it makes some sense.
Just googled it, and it looks like he did is a little differently. He paired 1 with n and then 2 with n-1, etc... yielding n/2 pairs that add up to n+1. It still works out to (n+1) * n/2, though :)
Apparently biographers disagreed about his age at the time but they all had the same method and the same problem of summing numbers from 1 to 100.
I disagree. He heard about this question beforehand during a casual encounter with an employee. So what? The onus is on Microsoft to have a more robust process than using basic riddles like those.
Would he have chosen to volunteer the info, he would have actively decided to penalize himself against all the other candidates who had also heard about this question before. This would have been borderline stupidity.
What about a case where the interviewee is given an obscure problem to solve, yet already encountered and solved the problem in a different context?
It would be difficult to classify as cheating if they did not learn about about the question from an inside source. On the other hand, it also defeats the presumed purpose of the question (i.e. to test problem solving skills).
I was in that situation before, explained how I knew the solution, and did not get the job. While there were probably other reasons for their decision, they said they wanted to give the position to someone who was pursuing a career in software development, at the end of the day the candidate is going to be up against people who would offer up the solution with out further explanation. That is an awfully good way to stifle opportunities based upon the presumed (and possibly incorrect) intent of the question.
It's a quiz problem, and it's supposed to have "trick" solutions.
However, if he wants to play that game, he should provide proof of his solution, not fiddle with syntax or error checking. That's why discussion is more important, and how he can show that understands what he's doing and not just memorizing tricks. (... none of which matters for his future role anyway.)
The formula "falls out" naturally if you're used to working with summations:
I learned this formula before high school. It was considered trivial.
The demonstration was to write the sums 1+2+...N and N+(n-1)+...+1 and add them up position wise. The sum comes n*(n+1)/2 (divide by 2 for the two sums).
I came up with another solution (which is purposefully complicated):
It is known that the sum of n-th roots of unity is zero.
So if we choose the n-th roots of unity as ω and calculate Σ ω^ai, the result should be 0 + ω^(the duplicate number).
So I opened the python interpreter, and I used this very trivial method of calculation (instead of summing the sine and cosine functions independently), and using asin and acos functions, got the result. It turned out to be accurate for n=1e6 with an error of ~1e-5. So it should be usable for much bigger n too.
In my view the trick in this question is to think about adding up numbers not how you add them up.Since this was a programming question you don't need to know the formula you can add up the numbers in a loop. It wouldn't even be much slower since you need a loop of size N anyway for the purpose of adding up numbers in the input.
Xor solution and adding solutions are the same solution it's just a matter of what binary function you use for calculating sum. You can use any commutative, associative binary function which has inverse. You can use addition, xor or even multiplication.
I don’t disagree with anything you said. However, if the prevailing attitude was “fuck these companies that pay me these privileged tech salaries”, we’d all be treated much worse.
It's not "fuck them", it's just don't confuse a business relationship with a social relationship. Companies don't pay high salaries because they want to be nice, they do it because the market requires it. The second the market stops requiring it, they'll stop doing it. They'll treat employees only as well as the market and the law requires, employees should do the same or they'll be taken advantage of.
> Companies ask interview[ees] to not reveal the questions they had to other candidates.
I'm not condoning the author's actions, but I don't think any company has explicitly told me that. (I assume by "interviewers" you meant "interviewees.")
I would not have though to use this formula. The sum of the integers grows as the square of n so if n is anything but small you will overflow and get an erroneous answer.
This interview question has everything bad imo: no practical uses, test knowledge of math formulas (which every math/CS major would have but none of the self learning folks). It’s very easy to stress and fail when given such a test, and even already knowing I would have tried something else because of the overflow.
> I would not have though to use this formula. The sum of the integers grows as the square of n so if n is anything but small you will overflow and get an erroneous answer.
As long as you can get wraparound semantics, the overflow is actually unproblematic. (n(n+1)/2 + k) mod 2^32 - (n(n+1)/2 mod 2^32) = k mod 2^32 = k.
Even with wraparound semantics, you can't compute n(n+1)/2 naively, because (n(n+1) mod N) / 2 ≠ n(n+1)/2 mod N.
So actually not knowing the formula is kinda advantageous, because computing the sum as 1 + 2 + … + n (with every addition mod N) gives you the right answer (mod N).
Or you can assume N is less than 2^31, and clear out the top bit in the final answer (because that's the only place the wrong values can come from). Which is admittedly pretty hackish, but…
Edit: The simplest solution is probably just doing (n/2)*(n+1) (assuming n is even; move the division for n odd).
Yes, it's a question with a silly trick. Completely useless if one knows the answer, hard to spot if the person feigns struggle.
Although, n•(n+1)/2 formula is not necessary. One can start with an xor sum and find the duplicate by xor adding elements again. This is another silly trick.
Could also just use a hashtable, the keys are the array elements and the items are the occurrence of each element, then return the one with an occurrence of 2.
That’s a very elegant solution. Hard looking problems that had simple, trick solutions were called Jewish Problems at the entrance of some universities.
This would let the examiner fail a student for subjective reasons instead of academic success. The examiner would then be able to say « I failed them because of their skills, not because of their religions, look how easy the solution is ».
Perhaps this is what we are reproducing as an industry with all our convoluted interview processes, and it may be a decorum to choose the candidates we want instead of using objective criteria.
I’m referring to the easy looking, tricky to solve problems. I’ve heard them referred to by that term because they have been used at Moscow University to discriminate against Jewish students but I don’t know if they have other names.
It's interesting that doing competitive math makes it really easy to spot these kinds of problems and guess at their "true" difficulty. Honestly, I'm kind of surprised that "this problem is short" or "the solution is short" would ever fly as a measure of how easy a problem is, but I assume that a system that is intended to encode racism doesn't need a whole lot of logic behind it…
Of course, just the phrasing made me think the "trick solution" was eugenics, not a university admission trick. Unfortunately, historically "Jewish question" or "Jewish problem" has referred to these concerns [0]. Of course, following your first link it seems like the native phrase for it is in no way better, but that seems predictable as it's stemming from a racist premise in the first place.
I think you missed the point of the second sentence.
It's like saying the phrasing on the Chinese Exclusion Act is unfortunate. It's not the phrasing that's unfortunate, but the history of excluding Chinese. These questions were designed to allow screeners to discriminate, and were named after the group designed to be kept out.
edit: If you edit a comment in response to a response, it's polite to say [edited]. Otherwise, the conversation is a non-sequitur, which seems to be happening here a bit.
I didn't edit my comment, at least not from what I remember. May have been a typo fix in the first few seconds though, which I do a bit too often.
Not sure if my comment was clear, but I was referring to "hard problems with trick solutions were called Jewish Problems", which sounds like it's referring to the Final Solution.
Reminds me of a funny anecdote, I was staying with a friend of mine in Berlin and asked her what the second most common religion was in Germany. She casually said "used to be Jewish, but not sure now..." She was of course referring to the influx of refugees from Africa, but for a very brief moment it looked like her life flashed in front of her eyes.
Also it was 2004 and 64 bit machines weren't common. If I remember correctly you had only 2 GB available under Windows XP and if you wanted more, 3 GB to be more precise, you had to boot with a special parameter.
32-bit machines generally 64-bit arithmetic of some sort; for example "long long" in C is mandated by the standard to be of a width greater than or equal to 64 bits.
Yeah, 64 bit integers were available under gcc on Linux, but the memory issue remained. The array had to fit in 2 GB, unless of course the problem stated otherwise, for example the numbers were read from a file.
Let’s not overthink this. Microsoft is using this test as a low-pass filter to get rid of candidates who would:
- not find any answer in a few minutes
- find a wrong answer and argue about it in an obnoxious way
Any reasonable answer would probably do.
You would probably get more brownie points for asking what you need to optimize for (compute, storage) than providing what seems to be the best solution (using the sum trick).
Exactly. It’s basically fizzbuzz. The fact that he thought about this in advance and had an answer ready to explain is also a green flag for such an early filter.
True, but that doesn't matter at all given reasonable values of n. The number is in the range of n^2, but the algorithm is in the range O(1). Question is not that bad, my first thought was to use hash table to store what you see, then return when duplicate occurs. Don't like hash table fine, set an array of size n storing TRUE when you see the number. Notice it twice, then you've found the duplicate. No need for math, O(n) solution.
Honestly if you're stressing over a question like this, combined with thinking that integer overflow is even remotely something that you need to be concerned about in a question like this, you're definitely not passing any leetcode interview problems tossed around in today's interviewing culture.
Got a chuckle out of the author thinking this was some kind of cardinal sin.
The only person "at fault" here is his friend for telling him what interview question he received and I'd expect companies know this happens, which is one of the benefits of having further interview stages in the first place.
I would say the only person “at fault” is the interviewer for using such an awful question. This is precisely the kind of question that gives programming puzzle interviews a bad name. If you’ve heard it before, it’s trivial and proves nothing. If you haven’t, you have to have a clever a-ha moment in order to do anything but brute-force it. “Have you heard this one story about Karl Gauss as a child” is a really terrible hiring criterion.
So,based on reading the article; you'll see that to arrive at the solution the writer:
* Communicated with a colleague (communications/interpersonal networking)
* Thought hard about it (applying previous knowledge and experience)
* Looked up and found relevant information (knowing where to look)
* Combined the above to come to a solution. (and had the skill to put it together)
By coincidence the practice practice question was also the one that was asked at the interview. If the interviewers had asked a different question, similar steps would have needed to be applied[1].
The question itself was an obvious practice question. There are many decent answers to the problem. What they were looking for were the knowledge, skills and experience that needed to be applied in the process of solving the problem. The point was to see if the candidate had those abilities.
I'm fine with using a practice question for this. A real world problem often involves a lot of real world noise, which makes it impossible to efficiently resolve within the constraints of a 60 minute chat.
I am -however- fully open to an argument that perhaps some form of Goodhart's Law ("When a measure becomes a target, it ceases to be a good measure") may have struck again.
[1] Perhaps not the exact same set of skills, given the constraints of the interview setting. One COULD argue that the interviewers accidentally picked up on more than they were looking for.
Preparing is not cheating. You learned and used your knowledge in an appropriate setting. That is the skill set companies are looking for, also the colleague I would like to work with
That's neither cheating, nor pure luck, but good preparation. I've gone through lots of questions asked in interviews and if I got one of them for real I'd answer it immediately without an ethical soul searching
/*
Not sure if this is correct,
but there should be a solution along these lines
will explode if the array contains values outside of 1...n
also, invalidates the array
*/
int v = values[0];
for(;;){
if(v == values[v])return v;
int t = v;
v = values[v];
values[v] = t;
}
/*
I used to be able to do this without a compiler
*/
for(;;){
int i = values[0];
if(i == values[i])return i;
values[i] ^= values[0];
values[0] ^= values[i];
values[i] ^= values[0];
}
/*
full test code, does java really not have Arrays.shuffle?
*/
public static void main(String...args){
final int result;
Integer[] values = new Integer[12];
for(int i = 1; i < values.length; i++){
values[i] = i;
}
final int dupe = values[0] = 1 + new Random().nextInt(values.length - 1);
final var list = Arrays.asList(values);
Collections.shuffle(list);
System.err.println(list);
for(;;){
int i = values[0];
if(i == values[i]){
result = i;
break;
}
values[i] ^= values[0];
values[0] ^= values[i];
values[i] ^= values[0];
}
System.err.println(dupe + " " + result);
}
Holy crap, I wouldn't have thought twice about being lucky enough to roll out a solution I'd happened to have been thinking about for days. I am not seeing an ethics problem here, the guy was just very lucky to get a problem he was intimately familiar with.
Unless I'm misreading, the question as stated in the blog post never says there is only one duplicate (there might be many!), so in that sense I think his answer may be wrong. A more robust solution is just to have an array of n counters and just count how many times each item appears.
Why are all the other comments so negative and stuck up whether it constituted “cheating” or not? That wasn’t the point of this story.
It was a beautifully well written account on luck and how sometimes the things align. The interviewee at the time was receptive towards the kind of questions that are asked at Microsoft and got the right one. Good luck. And then he passed a 6 hr on-site interview as well! No luck at all!
Fully agree. Add to that that the question was super standard, it was quite likely that the candidate would have heard about it one way or another before the interview.
The author prepared with the info he had and was "lucky" that he got a question he knew and had situational awareness to sell it.
It's all positive traits in my book. The discussion about the ways to interview to smooth this out is great but I don't think he should self flagellate or consider that his entire career was predated on this.
If you have the right attitude, prepare and work for it, you find any number of paths to get to the next level.
It's unfortunate that interviews sometimes feel so badly fit to achieve the goal and we should actively challenge whatever practice we have an iterate to make things better for everyone.
It made me think of how courses take test questions straight from the class materials. And let's say I'm a big procrastinator, and I run out of time, studying the night before the test, and I decide only to go through the odd pages of my materials, and also let's imagine that the test writer, just by accident, took most (or at least, enough) questions from those odd pages, did I now cheat? (I think not...)
You cheated yourself out of knowledge acquisition by treating a course of education as only a means to get a certificate.
That's cheating.
You're supposed to study the whole course, the examination is a statistical test to see if it's likely that you studied, and can apply, the whole course. If you didn't study the course, you're misrepresenting yourself by during the exam.
That's cheating (in a different way to the first one).
Examinations are imperfect, they usually can't cover an entire course without being too onerous.
In this circumstance you cheated, but did not break the rules for taking the exam. You will be less competent on the course material than is intended for those who pass.
I highly doubt anyone will learn every bit of information in the book. I highly doubt anyone will remember every bit of information in the book. Which parts of it will be necessary are very dependent on one's future.
Making me thinking what if the author was not lucky enough to pass the initial interview. Well Microsoft just fail the author, and the on-site interview never happens?
I'm feeling that the initial interview might not be completely fair. But of course, many things in life are down to lucks. Good luck helps, I guess.
Recruitment agents are always pumping failed interviewees for the questions they were asked. They then make sure their next candidates are better prepared with this knowledge.
This guy really shouldn't feel so bad. It's Microsoft's fault for not rotating the questions better. That, or they did rotate the questions, and it really was absolute pot luck.
I've had similar experience - in an interview for my current job I got asked same question that I've already encountered in a previous job interview. It must be pretty popular in the area :)
It wasn't hard, and I solved it first time without help so it didn't feel like cheating, but I told the guy afterwards anyway. I did tech interviews from the other side before and from my experience having the perfect answer doesn't matter that much - what matters is showing how you solve problems and that you're familiar with common solutions and trade-offs.
When I interviewed at my current company, I was pretty stressed about the interview and watched some Numberphile videos the night before to take my mind off things.
Weirdly enough one of the problems discussed in the interview was about the Josephus problem which has a neat solution in binary [0]. I don’t recall if I ever asked the interviewer whether they also watched the video recently or how they came to think of it.
This is what happens when companies use riddles that have nothing to do with the job you’ll do and do not remotely relate to the skills that will be required on the ground.
The author spent days thinking about it, whereas sorting is the immediate obvious answer. Developer time is massively more valuable than computer time by a factor of 1000
And the clever approach only works on data that is perfect, and that’s extremely rare in the real world
502 comments
[ 3.2 ms ] story [ 259 ms ] threadAll good.
> I've struggled with this a lot over the years, but I finally decided to share my story. I don’t think I would have made it past the first round of interviews at Microsoft if I hadn’t gotten so lucky. So pretty much, my entire career is built on one amazing stroke of luck.
...which explains why they felt like they "cheated".
Also, as someone who's been tested with this kind of questions (in the math and physics fields at least), I realized many times you aren't evaluated for knowing the answer but for how you go about trying to find it even if you fail.
This particular question is close to my heart as I was tested with it as a pupil in school. The teacher wrote this on the blackboard and asked me to come over and solve it (not having any prior knowledge). After a bit of fidgeting with the chalk I stared writing on consecutive lines 1, 1+1, 1+1+1 and after a few lines it dawned on me it looks like the "lower" half of a square of side n as cut by its diagonal. So I proudly concluded that the sum is n^2/2. Which was of course wrong, I forgot to add an n/2 to that since the "diagonal" is shifted right a bit. Still got top mark and maybe it was one of those moments that set me on a path. This went on through high-school, university, post graduate studies, and early career. It was only when I was knee-deep in real work that people started to care less about how I think and more about just the end result.
Preparing for this kind of question isn't cheating as long as you understood the answer.
You are so correct (at proper timestamp): https://youtu.be/3LopI4YeC4I?t=211
> Preparing for this kind of question isn't cheating as long as you understood the answer.
TFA notes that because of lack of interview prep material in 2004, even when the author knew the question before-hand, it took them days to arrive at an optimal answer. And then it dawned on them that everyone else at the job fair, who may be seeing a question for the first time, only had 15 mins in a pressure-cooker situation to solve it.
TFA also notes that the author intentionally misled the interviewer as if they were solving the puzzle then and there: I casually explained how I could simply use a mathematical formula to calculate the sum of 1 to n (like, who doesn’t know the sum(1 to n) formula?) and compare that to the sum of the integers in the array. I slowly wrote out the solution I had come up with over days of thinking about the problem, being sure to pause periodically as if I was figuring it out for the first time. I talked through my thinking and made sure I had all the proper error checking in place. I double and triple checked my syntax. My handwritten code was perfect.
Let's put it another way. If you take an exam after practicing with any kind of practice questions (something that has been done since the dawn of time and the education system) and happen to run into the same questions in the real exam, was that cheating or better targeted learning? Or if you find out about a job from a friend who works there, is it cheating because you have a significant insider advantage over people who never knew about the job?
In my opinion true cheating would have been made up of a) someone feeding them the real questions and/or b) someone feeding them the answers. It involves an unwillingness to put in effort and a premeditation that I didn't see in the story. This person was indeed in a conflict of interest but I wouldn't call them "a cheater".
P.S. If I were in that interview I would have provided the full answer almost instantly, not needing any kind of hesitation to "simulate" the thinking process. I know the answer without any relation to the interview. So there could be 2 outcomes: a) I get unfairly excluded under the suspicion of cheating justifying the need to fake the thinking to avoid this or b) I would have passed to the next stage making that whole charade effectively inconsequential.
GP's claim that TFA might be over-exaggerating it a bit for marketing purposes may also be correct, given that it was authored by an exec at a recruitment firm.
I don't have a problem with people marketing themselves on LinkedIn - it that not the entire purpose of the site?
I do it to generate sales leads for my startup. We're bootstrapped so being able to generate leads without any ad spend or outbound sales means we don't have to raise money to grow. I used to write blog posts but they take so much longer. Hence no new posts on the blog since 2019.
Now I focus on LinkedIn. A single viral post on LinkedIn can get 2M-5M views on average. It will generate $1M-$2M in potential business for us. This way I can spend 50% of my time writing code, 45% doing CEO stuff, and 5% doing marketing.
I would propose to change coding interviews to the following scheme:
Step 1:
Interviewer ask a coding question. If candidate is able to answer correctly then move to Step 2
Step 2:
Candidate asks a coding question from Interviewer. If Interviewer answers correctly go back to Step 1. If Interviewer is not able to answer correctly in 60 min, and Candidate is able to explain solution and implementation, move to Step 3
Step 3:
Interview is over and Candidate automatically qualifies for next hiring phase.
If a company decides to approach hiring with the naturally confrontational approach of, "let me find out in 60 minutes if you are smart enough to work here", I don't see why it should stop there.
After all recruiters always mention, it is good for you if you are also inquisitive, show interest in the company and ask questions :-))
Why can't a candidate also check if their future managers and the company are worthwhile to work there? It is always mentioned that a candidate is a much interviewing the company as the company is interviewing them...
Now...how many interviewers are suddenly uncomfortable? ;-)
You mean ask them the same question that they asked? Of course they'll be able to answer it. What does that prove?
And I mean a different question.
That's an interesting idea. I'd support that as an interviewer - I think the question candidates ask would also give you some information about the candidate too.
Sadly I doubt that sort of thing would ever become normal. Plus interviews already take enough time. Not sure I'd really want them to take any longer.
Also, OP should have included (2019) in the title. It's kind of an old piece.
If they were truly testing for engineering skills, the interview would mirror real day to day world more.
op's answer is constant n, but could have been improved to n/2 on average with a hash table. (but some constant overhead). so it really depends on the size of n.
https://www.americanscientist.org/article/gausss-day-of-reck...
http://bit-player.org/wp-content/extras/gaussfiles/gauss-sni...
would have helped as well.
They were also lazy with their recruiting questions.
If they wanted to select on skills instead of knowledge of interview question gimmicks, they would have asked for a link to your profile showing off your work, and look at it after the fair.
This is utilizing your network and preparing for potential questions.
If Microsoft is risking to ask the exact same question to someone, it's their problem.
Granted some people practice 100+ questions, you practiced only 1, and it was the right one. Same same.
Lucky indeed, but I wouldn't attribute your success to luck. You were clearly a good enough engineer to receive 2 offers, and good enough to build a career there.
We all have multiple encounters with low-probability scenarios in life. If you have a 10% chance of succeeding at something, and you have 50 attempts, and you only need one success, then your actual chance of succeeding is 99.5% rather than 10% - almost inevitable.
Kudos to the author for being honest about all this. I think it's a real issue and that we should find more solutions to prevent this than candidates signing an NDA. Imho when doing such interview, questions should not rely on a "trick" and even if they do, candidates should be evaluated on everything else: how they explain the code, how they react to feedbacks, how easily they transcribe what they explain to code. It's not perfect but it helps.
Comapre it with people who applied too, but didn't have that "internal" knowledge
Is it fair from that "not well networked" person perspective?
It's not even like he found this question randomly on the internet, he got it from MSFT employee, lol.
I have really mixed feelings about this
Edit.
Don't get me wrong, apparently author was(and is) capable of doing his job, so it isn't a big problem, but what if author wasn't capable of doing the job and passed just due to the advantage?
I know person who told beginner programmer what X company asks on interviews and that guy actually managed to pass that interview due to the knowledge
but was fired like 3 months later due to lack of skills
Fairness becomes a bit of a contrived concept once you start to factor in higher order effects. Then it just turns into fair if it advantages me, and unfair if it doesn’t.
I helped a friend get a job once because I knew who was going to interview him, and I knew he had a blog where he published all his thought-leader technical opinions.
Is that fair or unfair? Probably neither. It’s more of a random coincidence that my friend benefitted from this. But is it fair that I have learned more about my local industry by going to industry events and listening to people present things, and talking to people, etc? That probably is fair, and that’s how I learned the tip I gave to my friend.
Fairness isn’t really relevant to the problem here. If you believe that there is a problem at all, then the problem is that the screening process can be influenced by random coincidence.
Than Microsoft would've been scammed out of $350 worth of plane tickets, $150 worth of hotel commodations and $1000 worth of employee time. Hardly the end of the world for a multi billion dollar company
> and passed just due to the advantage?
Passed a six hour Microsoft on-site grilling due to knowing the question for a 15 minute off-site interview question?
Personally I don't put a ton of value in question like this, so I'm less inclined to view it as cheating, and more like proper preparation... and a bit of luck.
Close to 0% chance someone would find out, as that would involve the person revealing the question also facing consequences - unless the company has some elaborate scheme involving modified and unique questions tailored for each candidate, and keeping track what candidate got which question. But that obviously wouldn't work with a trivial question like the one OP got.
Either that, or some third party which could have intercepted the communication between OP and the friend revealing the question. But again, what are the chances...
And on a tangent - should candidates "grinding leetcode" reveal that they've encountered the question before? That's the whole point of leetcode.
I've seen candidates deny that they've seen the problem given, blitz through the basic version (intended as a quick warm-up), and then completely choke when a slight twist is added. Let's just say that really raises some questions...
It's a pretty obvious thing that anyone who spent much time thinking about math as a kid or teenager would have encountered, and maybe that's who MS wanted to hire! Especially back then when more of their programming needs dealt with algorithms and mathematical thinking, as opposed to gluing libraries together, I think it makes some sense.
Just googled it, and it looks like he did is a little differently. He paired 1 with n and then 2 with n-1, etc... yielding n/2 pairs that add up to n+1. It still works out to (n+1) * n/2, though :)
Apparently biographers disagreed about his age at the time but they all had the same method and the same problem of summing numbers from 1 to 100.
Would he have chosen to volunteer the info, he would have actively decided to penalize himself against all the other candidates who had also heard about this question before. This would have been borderline stupidity.
It would be difficult to classify as cheating if they did not learn about about the question from an inside source. On the other hand, it also defeats the presumed purpose of the question (i.e. to test problem solving skills).
I was in that situation before, explained how I knew the solution, and did not get the job. While there were probably other reasons for their decision, they said they wanted to give the position to someone who was pursuing a career in software development, at the end of the day the candidate is going to be up against people who would offer up the solution with out further explanation. That is an awfully good way to stifle opportunities based upon the presumed (and possibly incorrect) intent of the question.
However, if he wants to play that game, he should provide proof of his solution, not fiddle with syntax or error checking. That's why discussion is more important, and how he can show that understands what he's doing and not just memorizing tricks. (... none of which matters for his future role anyway.)
The formula "falls out" naturally if you're used to working with summations:
Σi = Σ(n-i+1) = n² - Σi + n
2Σi = n² + n
... but the xor solution is more elegant.
The demonstration was to write the sums 1+2+...N and N+(n-1)+...+1 and add them up position wise. The sum comes n*(n+1)/2 (divide by 2 for the two sums).
So I opened the python interpreter, and I used this very trivial method of calculation (instead of summing the sine and cosine functions independently), and using asin and acos functions, got the result. It turned out to be accurate for n=1e6 with an error of ~1e-5. So it should be usable for much bigger n too.
Xor solution and adding solutions are the same solution it's just a matter of what binary function you use for calculating sum. You can use any commutative, associative binary function which has inverse. You can use addition, xor or even multiplication.
I'm not sure modulus-addition would be correct.
Don’t pretend they are an authority. They’re a bunch of idiots making it up as they go along like the rest of us.
I'm not condoning the author's actions, but I don't think any company has explicitly told me that. (I assume by "interviewers" you meant "interviewees.")
This interview question has everything bad imo: no practical uses, test knowledge of math formulas (which every math/CS major would have but none of the self learning folks). It’s very easy to stress and fail when given such a test, and even already knowing I would have tried something else because of the overflow.
As long as you can get wraparound semantics, the overflow is actually unproblematic. (n(n+1)/2 + k) mod 2^32 - (n(n+1)/2 mod 2^32) = k mod 2^32 = k.
So actually not knowing the formula is kinda advantageous, because computing the sum as 1 + 2 + … + n (with every addition mod N) gives you the right answer (mod N).
Where S is the sum of the array achieved through iterative addition with every addition mod N and N > 2n.
Edit: The simplest solution is probably just doing (n/2)*(n+1) (assuming n is even; move the division for n odd).
Although, n•(n+1)/2 formula is not necessary. One can start with an xor sum and find the duplicate by xor adding elements again. This is another silly trick.
This would let the examiner fail a student for subjective reasons instead of academic success. The examiner would then be able to say « I failed them because of their skills, not because of their religions, look how easy the solution is ».
Perhaps this is what we are reproducing as an industry with all our convoluted interview processes, and it may be a decorum to choose the candidates we want instead of using objective criteria.
There is some discussions and examples of such problems at https://arxiv.org/pdf/1110.1556.pdf and http://3038.org/press/shen.pdf.
[0] https://en.wikipedia.org/wiki/Jewish_question
It's like saying the phrasing on the Chinese Exclusion Act is unfortunate. It's not the phrasing that's unfortunate, but the history of excluding Chinese. These questions were designed to allow screeners to discriminate, and were named after the group designed to be kept out.
edit: If you edit a comment in response to a response, it's polite to say [edited]. Otherwise, the conversation is a non-sequitur, which seems to be happening here a bit.
Not sure if my comment was clear, but I was referring to "hard problems with trick solutions were called Jewish Problems", which sounds like it's referring to the Final Solution.
Reminds me of a funny anecdote, I was staying with a friend of mine in Berlin and asked her what the second most common religion was in Germany. She casually said "used to be Jewish, but not sure now..." She was of course referring to the influx of refugees from Africa, but for a very brief moment it looked like her life flashed in front of her eyes.
• n if n mod 4 = 0,
• 1 if n mod 4 = 1,
• n + 1 if n mod 4 = 2,
• 0 if n mod 4 = 3.
Or alternatively:
• s(4n) = 4n
• s(4n + 1) = 1
• s(4n + 2) = 4n + 3
• s(4n + 3) = 0
Proof by induction:
• s(4n + 1) = s(4n) ⊕ (4n + 1) = 4n ⊕ (4n + 1) = 1
• s(4n + 2) = s(4n + 1) ⊕ (4n + 2) = 1 ⊕ (4n + 2) = 4n + 3
• s(4n + 3) = s(4n + 2) ⊕ (4n + 3) = (4n + 3) ⊕ (4n + 3) = 0
• s(4n + 4) = s(4n + 3) ⊕ (4n + 4) = 0 ⊕ (4n + 4) = 4n + 4
I mean they might. Its a very famous formula, with a famous story attached, which is often covered in high school level math.
Regardless its a stupid question.
- not find any answer in a few minutes
- find a wrong answer and argue about it in an obnoxious way
Any reasonable answer would probably do.
You would probably get more brownie points for asking what you need to optimize for (compute, storage) than providing what seems to be the best solution (using the sum trick).
Honestly if you're stressing over a question like this, combined with thinking that integer overflow is even remotely something that you need to be concerned about in a question like this, you're definitely not passing any leetcode interview problems tossed around in today's interviewing culture.
The only person "at fault" here is his friend for telling him what interview question he received and I'd expect companies know this happens, which is one of the benefits of having further interview stages in the first place.
* Communicated with a colleague (communications/interpersonal networking) * Thought hard about it (applying previous knowledge and experience) * Looked up and found relevant information (knowing where to look) * Combined the above to come to a solution. (and had the skill to put it together)
By coincidence the practice practice question was also the one that was asked at the interview. If the interviewers had asked a different question, similar steps would have needed to be applied[1].
The question itself was an obvious practice question. There are many decent answers to the problem. What they were looking for were the knowledge, skills and experience that needed to be applied in the process of solving the problem. The point was to see if the candidate had those abilities.
I'm fine with using a practice question for this. A real world problem often involves a lot of real world noise, which makes it impossible to efficiently resolve within the constraints of a 60 minute chat.
I am -however- fully open to an argument that perhaps some form of Goodhart's Law ("When a measure becomes a target, it ceases to be a good measure") may have struck again.
[1] Perhaps not the exact same set of skills, given the constraints of the interview setting. One COULD argue that the interviewers accidentally picked up on more than they were looking for.
I wasn't joking though - I haven't been able to work for years and have no real hope of piecing myself back together.
(Mushrooms help, though they're seasonal - and there's no damned way the government's ever going to legalise them.)
I do believe it is only one.
It was a beautifully well written account on luck and how sometimes the things align. The interviewee at the time was receptive towards the kind of questions that are asked at Microsoft and got the right one. Good luck. And then he passed a 6 hr on-site interview as well! No luck at all!
The story resonated with me.
It's all positive traits in my book. The discussion about the ways to interview to smooth this out is great but I don't think he should self flagellate or consider that his entire career was predated on this.
If you have the right attitude, prepare and work for it, you find any number of paths to get to the next level.
It's unfortunate that interviews sometimes feel so badly fit to achieve the goal and we should actively challenge whatever practice we have an iterate to make things better for everyone.
That's cheating.
You're supposed to study the whole course, the examination is a statistical test to see if it's likely that you studied, and can apply, the whole course. If you didn't study the course, you're misrepresenting yourself by during the exam.
That's cheating (in a different way to the first one).
Examinations are imperfect, they usually can't cover an entire course without being too onerous.
In this circumstance you cheated, but did not break the rules for taking the exam. You will be less competent on the course material than is intended for those who pass.
I'm feeling that the initial interview might not be completely fair. But of course, many things in life are down to lucks. Good luck helps, I guess.
This guy really shouldn't feel so bad. It's Microsoft's fault for not rotating the questions better. That, or they did rotate the questions, and it really was absolute pot luck.
It wasn't hard, and I solved it first time without help so it didn't feel like cheating, but I told the guy afterwards anyway. I did tech interviews from the other side before and from my experience having the perfect answer doesn't matter that much - what matters is showing how you solve problems and that you're familiar with common solutions and trade-offs.
Weirdly enough one of the problems discussed in the interview was about the Josephus problem which has a neat solution in binary [0]. I don’t recall if I ever asked the interviewer whether they also watched the video recently or how they came to think of it.
[0]: https://youtu.be/uCsD3ZGzMgE
Real world requirements usually contain inaccurate assumptions. He spent days to find a terrible answer, when the obvious solution is much better
Start with what works and then optimize
Sophomoric is exactly the word here, and it’s no surprise that the story is about Microsoft
In the lack of additional constraint, sorting seems massively overkill.
Not sure why you are saying that sorting is simpler than the sum trick.
And the clever approach only works on data that is perfect, and that’s extremely rare in the real world
This is a hypersophomoric question