Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I cheated on my Microsoft interview (2019)

facet.net

Post reply on HN
Print view View original

61–70 of 503 posts

Re: I cheated on my Microsoft interview (2019)

#61

Post by paulsutter »

whiplash451 wrote: post #60
paulsutter wrote: post #57

Who wouldn’t just sort the array and check it? His solution is very brittle: it fails in so many ways if the data had unexpected properties. Real world requirements usually contain inaccurate assumptions. He spent days to find a terrible answer, when the obvious solution is much better

Maybe those who care about computational complexity for instance?

Even if you had terabytes of data sorting is still the easiest answer. Especially if you had terabytes of data in fact. Brittle solutions suck

Start with what works and then optimize

Sophomoric is exactly the word here, and it’s no surprise that the story is about Microsoft

Re: I cheated on my Microsoft interview (2019)

#62

Post by whiplash451 »

Znafon wrote: post #14

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…

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).

Re: I cheated on my Microsoft interview (2019)

#63

Post by redredrobot »

mrweasel wrote: post #50
napo wrote: post #13

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 i…

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 m…

You tell the interviewer you are familiar the question instead of pretending to come up with a solution on the spot. Is that not obvious to everyone?

Re: I cheated on my Microsoft interview (2019)

#64

Post by qcoh »

paulsutter wrote: post #57

Who wouldn’t just sort the array and check it? His solution is very brittle: it fails in so many ways if the data had unexpected properties. Real world requirements usually contain inaccurate assumptions. He spent days to find a terrible answer, when the obvious solution is much better

How is it brittle? It solves the problem at hand, which is unambiguous (I think).

Re: I cheated on my Microsoft interview (2019)

#65

Post by ciupicri »

williamkuszmaul wrote: post #35
Znafon wrote: post #14

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…

Using 64 bit integers, we can store the square of any 32 bit integer. Not that small...

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.

Re: I cheated on my Microsoft interview (2019)

#66

Post by ppsreejith »

jwilk wrote: post #27
Sesse__ wrote: post #17

Earlier quoted context omitted.

> 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).

You could delay division by 2 until the end. I.e ((2 * S mod N - n*(n+1) mod N) mod N) / 2

Where S is the sum of the array achieved through iterative addition with every addition mod N and N > 2n.

Re: I cheated on my Microsoft interview (2019)

#67

Post by anonymousDan »

AlchemistCamp wrote: post #52
napo wrote: post #13

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 i…

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 th…

Isn't this the famous Gauss proof/algorithm that he came up with when he was 5 or something?

Re: I cheated on my Microsoft interview (2019)

#68

Post by sverhagen »

lynguist wrote: post #46

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 a…

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...)

Re: I cheated on my Microsoft interview (2019)

#69

Post by jwilk »

rocqua wrote: post #30
vjerancrnjak wrote: post #19

Earlier quoted context omitted.

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.

What is the closed form solution of the xor-sum though?

s(n) =

• 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

Re: I cheated on my Microsoft interview (2019)

#70

Post by rurban »

nine_zeros wrote: post #7

This is not cheating. Tech companies are literally looking for candidates who have seen the problem before. If they were truly testing for engineering skills, the interview would mirror real day to day world more.

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.

Post reply on HN