'How I Cheated On My Microsoft Job Interview' (facetdev.com) 263
Robert Sweeney spent 10 years working as a software engineer at Microsoft and Netflix, before becoming founder and CEO of the software development agency Facet. This week he blogged about how he cheated on his 2004 interview for a job at Microsoft.
It was his first job interview ever, when he was still a college senior majoring in computer science, and a Microsoft recruiter had invited him to an interview at an on-campus career fair: I immediately called my good friend Eli who had just started a new job at Microsoft. I asked him what the on campus interviews were like and how I should prepare for them. He explained that they would ask a random programming question that I would need to solve on a sheet of paper. If you did well, then they would fly you out for a full day of interviews at the Microsoft headquarters in Redmond, Washington. He had been asked to write a function that, when given an array of length n + 1 containing integers 1 through n, find the duplicate integer in an array. I wasn't sure how to prepare for answering a "random programming question", so I decided to just use the question Eli had been asked as practice and hope for the best...
Most of the interview is a blur, but I remember the interviewer being nice and I remember the programming question he asked me... I couldn't believe it. He asked me the exact same question as Eli. Should I tell him? I hesitated for a moment, pretending to be thinking about how to solve the problem. In reality I was having an intense internal debate on the ethics of interviewing. He didn't ask me if I had heard the question before, he just asked me to solve it. So I decided to just answer the question... 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... A few days later I received an invite to fly out to the Microsoft main offices. I interviewed with two teams over a period of 6+ hours. I didn't get asked any questions I had heard before this time, but I did my best... Sure enough, that next week I had a job offer from Microsoft from both teams... Within a couple of years of graduating from college, I had shipped software that was being used by nearly a billion people...
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. I also think my experience is a great example of one of the many reasons why the coding problems we use in developer interviews are so problematic: on the spot coding is just not a good way to judge technical ability.
Stack Overflow's CEO founder Joel Spolsky actually wrote some of Microsoft's internal programmer-testing guidelines when he worked there in the mid-1990s, and he later publicized them in a 2006 blog post which he says was later adopted by other tech companies, including Google.
He has since said that recruiting for IT is broken, adding "I think that I'm responsible."
Microsoft has since changed its interviewing practices.
It was his first job interview ever, when he was still a college senior majoring in computer science, and a Microsoft recruiter had invited him to an interview at an on-campus career fair: I immediately called my good friend Eli who had just started a new job at Microsoft. I asked him what the on campus interviews were like and how I should prepare for them. He explained that they would ask a random programming question that I would need to solve on a sheet of paper. If you did well, then they would fly you out for a full day of interviews at the Microsoft headquarters in Redmond, Washington. He had been asked to write a function that, when given an array of length n + 1 containing integers 1 through n, find the duplicate integer in an array. I wasn't sure how to prepare for answering a "random programming question", so I decided to just use the question Eli had been asked as practice and hope for the best...
Most of the interview is a blur, but I remember the interviewer being nice and I remember the programming question he asked me... I couldn't believe it. He asked me the exact same question as Eli. Should I tell him? I hesitated for a moment, pretending to be thinking about how to solve the problem. In reality I was having an intense internal debate on the ethics of interviewing. He didn't ask me if I had heard the question before, he just asked me to solve it. So I decided to just answer the question... 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... A few days later I received an invite to fly out to the Microsoft main offices. I interviewed with two teams over a period of 6+ hours. I didn't get asked any questions I had heard before this time, but I did my best... Sure enough, that next week I had a job offer from Microsoft from both teams... Within a couple of years of graduating from college, I had shipped software that was being used by nearly a billion people...
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. I also think my experience is a great example of one of the many reasons why the coding problems we use in developer interviews are so problematic: on the spot coding is just not a good way to judge technical ability.
Stack Overflow's CEO founder Joel Spolsky actually wrote some of Microsoft's internal programmer-testing guidelines when he worked there in the mid-1990s, and he later publicized them in a 2006 blog post which he says was later adopted by other tech companies, including Google.
He has since said that recruiting for IT is broken, adding "I think that I'm responsible."
Microsoft has since changed its interviewing practices.
GP didnt cheat (Score:3)
Re: (Score:2, Insightful)
Amateurs call it cheating.
Professionals call it networking.
Re:GP didnt cheat (Score:4, Insightful)
It doesn't sound like cheating to me either. Just proper preparation. There are sets of "interview problems" available in books and online, and if you practice them, at least one is likely to be close to a question you are actually asked.
But you can still get "honesty points" for admitting that you have seen the problem before. The interviewer may be impressed by your integrity.
A really slick interview hack is if you get a hard problem that you have no idea how to solve, you can say "Sorry, but I have seen this identical problem before. I don't want to take advantage of that, so can you give me another instead?" Then you get the points for "integrity" while also avoiding the hard problem.
The obvious approaches to finding a duplicate element in an array are:
1. Sort the array, and then scan for duplicates.
2. Scan the array once, and use a bit array offset to identify dupes.
For #1, time=O(n*log(n)), space=O(log(n))
For #2, time=O(n), space=O(n)
Is there another way?
Re:GP didnt cheat (Score:4, Interesting)
Re: (Score:2)
Does not cover edge cases as in there are multiple duplicated values, or the whole array only has the same value (yes, edge cases where not asked, but we call that "robust" or "robustness" in SE)
Re: GP didnt cheat (Score:3, Interesting)
sum - n(n+1)/2
Re: (Score:2)
sum - n(n+1)/2
I should have RTFA. I also should have read the summary more carefully. I was thinking it was an array of random integers, not a list of exactly 1 to n, with only one duplicate.
This guy's solution was very insightful. I don't think I would have thought of it.
Re: (Score:3)
Apparently, Microsoft hired a bunch of dweebs who could quickly think of this one weird trick for a situation that would never happen in the real world... But for decades these same people couldn't figure out how to do things like support multiple styles of line endings in a simple text edit control.
Re: (Score:2)
While that solution is elegant to write, it still isn't the fastest executing solution. Getting the the sum requires iterating through the entire array and reading each element, plus doing an ADD operation. A faster way for finding the duplicated element would be to do a binary search.
Since you know what value SHOULD be stored at any given point in the array with no duplicates up to that point (array[n] == n + 1), you can easily tell which side of your inspection point contains the duplicated element. By sp
Re: (Score:2)
That assumes the array is sorted. The problem doesn't state that.
Re: (Score:2)
You assume the array is sorted.
Which it is not.
The two duplicates are at random positions. And the numbers in the array are "arbitrarily distributed". There is no way not scanning the whole array.
Re: (Score:2)
I love problems that have elegant solutions! The knee-jerk answer is "loop through the array, looping each time through the remainder of the array, looking for the duplicate", but of course that's not only O(n^2), but is a lot of comparisons, so not only doesn't it scale well, but it's an expensive way to go about n^2 anyway.
It wasn't until I thought about it for a second that I realized that the entire content of the array (excluding the duplicate) was known, and that made me start thinking of how I could
Re: (Score:2)
It is O(n) ... why the funk would it be O(n^2)?
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
1. Sort the array, and then scan for duplicates.
The problem as stated does not require that the array be sorted, order of the data is neither implicit nor explicit in this problem. If the arrays are in memory or can be read sequentially from a data source, then the duplicate can be found by whatever method, saving a chunk of time by not sorting. Of course, sorting the array is one way to sample each element and do comparisons thereby finding the duplicate, but the statement "sort AND THEN scan" seems redundant, double the time and effort.
Re: (Score:2)
while ( A[A[N+1]] != 0 ) // valid data set is 1..N
{
t = A{N+1];
A[N+1} = A[t];
A[t] = 0;
}
Re: (Score:2)
For #1, time=O(n*log(n)), space=O(log(n))
Space is O(n).
Is there another way? ... you could use a hashtable e.g.
Yes, many
Re: (Score:2)
Is there another way?
$integers = array(1, 15, 9, 7, 1, 1000000); // they don't have to be sequential or sorted // have I seen this one before?
$tmp = array();
foreach ($integers as $integer) {
if (isset($tmp[$integer])) {
echo $integer;
break;
}
$tmp[$integer] = 'junk';
}
Reminds me of my lucky interview (Score:5, Funny)
Him getting the one exact question he had prepared for reminds me of a lucky thing that happened to me in an interview.
Interviewer: Which Linux distros are you most familiar with?
Me: I use Redhat / Centos for almost everything.
Interviewer (frowning): We use Debian. Do you have experience with Debian?
Me: Are you on the Debian security mailing list?
Interviewer: Yes ... ?
Me: Can you pull up the Debian announcement from this morning real quick?
Debian security alert email: Ray Morris discovered (a big security issue in Debian)
He had no more questions about my Debian experience after that. :)
Re: (Score:2)
But did you get the job? :P
Actually no, and I wonder why (Score:3)
Actually I was surprised I didn't get the job. I always kinda wondered why. The limited feedback I got in that time period was that I was applying for lower-level jobs than I should have. Hiring managers thought I'd either demand too high of a salary or less as soon as a better offer came along.
The phrase "imposter syndrome" came up here on Slashdot earlier today. I think I have a bit of that.
Typo: "or leave" (Score:2)
That should be "or leave as soon as a better offer came along".
That would be a reasonable concern. My salary has increased 6X over the last few years; I keep getting significantly better offers.
Re: (Score:2)
Dumb people just think they are freaking great.
Re:GP didnt cheat (w/o imagination or creativity) (Score:2)
This is just another "life hack". Carry on.
And that was moderated as "insightful"? Really, Slashdot.
My approach to the discussion was quite obvious. I looked for "imagination" or "creativity" and found no mention of either word anywhere in the discussion. Perhaps that was the only programming problem they used in those years? (I've read at least one book on the Microsoft interviews and they had other questions later on...)
Actually the discussion should have considered either term, but in the negative, as in Microsoft interviewers lack imagination or
Get Over It (Score:5, Insightful)
Honestly, this is a case where the Sweeney did the research on the Microsoft interview process and was properly prepared for it. If he worked there a few years, went on to NetFlix and is now CEO of his own company, then it could be argued that Microsoft got a good hire out of their process.
Nice O(n) algorithm to solve the problem - I'll have to remember it.
Re: (Score:2)
What worries me is that it took him a few days to come up with that.
Took me less than two minutes, and I stopped midway to explore a less optimal but perfectly functional way of doing it that actually allows capabilities the algorithm lacks.
I mean, shit, this isn't exactly hard. Didn't everybody learn the n(n+1)/2 algorithm when they were 13?
Re: (Score:3)
What he should also get over is any guilt that his career is built on a lucky moment. Most successful people with any level of self-awareness understand the lucky breaks which led to their success. Hard work only gets you so far. Most of these people made their own luck to some extent, but pure random chance nearly always plays a large part as well.
I had middling success in my career until I happened to join a rapidly growing company where I quickly climbed the ranks from senior developer to VP in just a fe
Ethics (Score:5, Insightful)
Re: (Score:2)
Impostor syndrome (Score:2)
I wouldn't worry about it (Score:2)
You got a job and it seems you were pretty good at it too. Don't do the "my entire career is built on one amazing stroke of luck" thing, it's wrong. You had a stroke of luck at the start, but seeing how you got an offer from both teams, and kept the job for a decade, you obviously were good enough.
Maybe you would have passed that first test too without the preparation, who can tell. But even if you hadn't, would that have meant that your future wasn't in software development?
Re:I wouldn't worry about it (Score:4, Informative)
I think he is pointing out, the weakness of recruiting. He got lucky to get a question he had time to think about and give an appropriate answer. Depending upon whether you have encountered a problem previously, most people cannot come up with a good solution at the snap of their fingers.
I also think that this is a serious problem, people want good answer immediately, like everyone has the same experiences as them and should be able to give them the same answer or process. I like to take my time and understand the problem I am trying to address and usually the first solution I come up with works, but it is not the best, but gets me along the lines towards that better answer.
If this were not true, why do this big companies keep shoveling S**T out the door so often? Management is part of the problem, but so is the whole hiring process. We don't really know how to ID good developers any more than we know to whether someone is going to be a good basketball player or football star.
Re: (Score:2)
In my experience most companies don't care about the best solution or the fastest solution, they just want something that works. So what they really care about is that you can solve problems quickly, even if the solution is not great.
In this case I expect many people would try to iterate over the array repeatedly. It's not the fastest but it works, and the performance problems belong to someone else who comes along later.
He didn’t cheat. He prepared himself. (Score:2, Insightful)
He did his research on the interview process by asking somebody who went through it. He then prepared for it as best he could. It’s no different than his learning that a potential employer asks “tell us about a time you...” questions about customer service methods, workplace interactions, etc, and then preparing answers to those questions instead.
If anything, what he did was highlight the lazy stupidity that is demonstrated in the hiring practices of many companies these days.
Surefire answer (Score:2)
Or is that answer a bit too "management" for a coding job.
Sad state of affairs at Microsoft (Score:2, Informative)
This is the question the author had to agonize over for days? Study up on the problem?
It's kinda sad that he couldn't think of 3 or 4 different solutions within minutes of hearing the question, all of which have different complexity (both big-O and terseness of the solution). I'd have asked questions like "Is the complexity an issue? Would you favor a solution that uses available libraries or do you prefer directly coded function? Is there any optimization you want (time/space tradeoffs). Would a clever use
Humble brag disguised as a mea culpa (Score:2)
Re: (Score:2)
Congrats dude, you cheated on an programming interview question that any competent programmer would know, even one fresh out of college.
There is a trick to this question, that is only applicable to this particular question. It's of no practical use whatsoever. Many competent programmers don't know that trick.
Finding duplicates in an array, on the other hand, is useful. I'd just create a counted set and pick the elements with count ⥠2.
Re: (Score:2)
First of all: he did not cheat.
I basically only get interview questions where I know the answer because:
a) I saw the problem somewhere and have a half memorized answer how to solve it
b) solved the problem myself long ago
c) it is a silly question, everyone should be able to answer. However I ask back after silly questions when the interview is over and I got several times: you were the only one answering correctly!
Secondly: /. are either wrong, or the explanation is wrong or the O cal
Half the answers here on
In case somebody wants a solution for the puzzle (Score:5, Informative)
The way the condition is given
"an array of length n + 1 containing integers 1 through n"
The array contains all integers in the interval [1,n] plus one duplicate, so you can write the sum over all its elements as the n-th partial sum plus the duplicate integer d:
sum(1+2+..+d+....+n) + d
(For illustration I chose d not to be 1,2, or n)
So all you have to do to find the duplicate integer, is to sum up over all integers in your n+1 long array and subtract the n-th partial sum from it. That yields d.
(I guess I could have been working at MS as it took me just a moment to come up with this answer, but yikes, than I would have had to work for MS. A company I disdained for almost as long as I have been working with computers).
Re: (Score:2)
Then again, I still manage to misspell "then" as "than".
Re: (Score:3)
Re: (Score:2)
Another similar solution is to use the fact that the sum of the first n integers is n(n+1)/2 . So you can take the whole sum and subtract off n(n+1)/2 from the total.
Here's a fun problem: Suppose that the you have n+1 integers and you don't have any guarantee that they are from 1 to n, just some set of n integers, and there's a single duplicate, can you still find a linear time algorithm to find the duplicate? (The answer is yes.)
A hash table is what first comes to mind.
Re: (Score:2)
A hash table is what first comes to mind.
Hash tables are not linear. The hashing is linear, but handling collisions is log(n), so you end up with O(n*log(n)).
A fast hash for integers is to make the table size BIG_PRIME and then the hash function is just (k % BIG_PRIME). But you still need to handle collisions.
Re: (Score:2)
A hash table is what first comes to mind.
Hash tables are not linear. The hashing is linear, but handling collisions is log(n)
This is wrong. A decent hash table implementation has average case O(1) for insert, delete and search. Individual operations may be slower, but the amortized time is still constant. To be precise, if the hash function approximates a uniformly distributed random variable (actually a pretty reasonable assumption; we have good hash functions), and the table is resized whenever the load factor exceeds a fixed c Also, for the stated problem you know the number of elements to be inserted, so it is possible to
Re: (Score:2)
A hash table is what first comes to mind.
You, I would hire. The summing approach is clever but it's also idiotic as it will only work for this one specific contrived problem. It can't be extended to more general cases, while a hash table approach can.
Re: (Score:2)
well yeah, expect that practically speaking it's an idiotic problem is the first place. the only reason for the problem, is to test whether the applicant knows or can figure out a trick as other posters have shown.
finding the index of the repeated entry, now that might be something of some practical utility in some cases, but just finding the value? completely useless apart from being a veiled IQ test (which may or may not be useful; i don't know or care).
Re: (Score:2)
ugh, "except" and "in". got started drinking a bit early today lol.
Re: (Score:2)
Yep, if you know the formula for the partial sum this is much more efficient.
Re: (Score:2)
If you're talking int32 and have a GB of memory to waste, you could simply walk over the array and use each value as an index in one or two bit sets and flip the bit at that position until you encounter an already flipped bit.
If you want to be fancy, you can do another walk prior to that to collect the min and max values in the array and use those to (down)size the bit set(s) to the range of values you're actually dealing with.
as a C function. (Score:2)
findRepeatedInteger(int arraySize, int* array) { // I know that "int" should be something like uint32_t but for clarity...
int i; // Get the sum of the numbers from 1 to arraySize;
int actualArraySum;
int arraySum = (arraySize * (arraySize + 1)) / 2;
for (i = actualArraySum = 0; arraySize > i; ++i) {
actualArraySum += array[i];
}
return actualArraySum - arraySum;
}
Argggh... Not quite right (Score:2)
This should be correct. I forgot that I should be looking for the sum of arraySize - 1 and not the full array.
findRepeatedInteger(int arraySize, int* array) { // I know that "int" should be something like uint32_t but for clarity...
int i; // Get the sum of the numbers from 1 to arraySize - 1;
int actualArraySum;
int arraySum = (arraySize * (arraySize - 1)) / 2;
for (i = actualArraySum = 0; arraySize > i; ++i) {
actualArray
Re: (Score:2)
Re: (Score:2)
If "int" is a signed 32 bit number, shouldn't the array size where problems start be 65,535?
I'm calculating this by knowing the square root of 2^32 is 2^16 and if I multiply 2^16 and (2^16 + 1) I'll end up with a negative 32bit value as the result will be greater than the maximum positive number is (2^31 - 1) or 2,147,483,647.
If I use unsigned 32 bit numbers, I can theoretically go as high as 91,681 but there is the problem that 91,681 x 91,682 is 8,405,497,442 and is greater than 2^32 (4,294,967,296). In
doesn't work? (Score:2)
array = 0,0,1
0 = 0 ^ (0 ^0)
1 = 0 ^ (1 ^0)
1 = 1 ^ (01 ^1)
But the duplicate is 0 not 1
array = 0,1,0
0 = 0 ^ (0 ^0)
0 = 0 ^ (1 ^1)
1 = 0 ^ (01 ^ 0)
Re: (Score:2)
typo:
array = 0,0,1
0 = 0 ^ (0 ^0)
1 = 0 ^ (1 ^0)
10 = 1 ^ (10 ^1)
But the duplicate is 0 not 2 or the item at index 2
try again:
array = 0,1,0
0 = 0 ^ (0 ^0)
0 = 0 ^ (1 ^1)
10 = 0 ^ (10 ^ 0)
Re: (Score:2)
While the answer is correct, the guy performing the interview, aka the interviewer, would most likely not grasp it and most likely would not have it on his list of "correct answers".
Yes, easy, and that's the problem (Score:2)
This isn't so much a program problem as a puzzle. If, under pressure, you happen to see the trick, great. If not, you're screwed.
Better would be a problem that requires more ordinary slogging, to model some data, use some data structures, etc.
Re: (Score:2)
Initialize all to false.
Tick off all the integers you find in the integer array, unless the value is already true.
If it is already true: You have the duplicate.
Re: (Score:2)
Okay now do that in a scalable way on an embeded 4K memory controller. Oh and use C without any hash libs since they would use too much memory.
Re: (Score:2)
That doesn't work? (Score:2)
your code does not seem to work
consider array = (0,0,1)
result = 0
i=0
result = result ^ ( i ^ 0) = 0 ^ 0 ^ 0 = 0
i=1
result = 0 ^ ( 1 ^ 0 ) = 1
i = 2
result = 01 ^ ( 10 ^ 01 ) = 10
so result is 2 but that's not the duplicate value (0) nor is it the index of the duplicate value (0 or 1)
Re: (Score:2)
Ah oops. this relys on the special feature that the integers start from 1 not zero.
so correcting my result
consider array = (1,2,1)
result = 0
i=0
result = result ^ ( i ^ 1) = 0 ^ 0 ^ 1 =1
i=1
result = 01 ^ ( 01 ^ 10 ) = 10
i = 2
result = 10 ^ ( 10 ^ 01 ) = 01
which works
Things that make you go . . . (Score:2)
Well, that line says it all (especially if he was from an Ivy League school.
I recall, that while an on-and-off contractor at M$, I once emailed them my cover letter stating I was undecided as to whether apply to Micro$oft or become a crack ho --- the only time I ever received a response from them, and was never able to score any interviews during my gigs there, but then I am not a grad of an Ivy League insti
Par for the course (Score:2)
CSC wanted to give me an aptitude test on my suitability to be a programmer. This was after 20+ years of writing software.
I deliberately failed it and told the guy running it.
I said, "This test is an insult to me and my profession."
I then pulled out two papers I'd presented on specific development techniques.
"This is what I can do."
Then I walked out.
A week later I got a letter telling me that I wasn't suitable to work as a programmer.
Numpties.
My future job interview at Microsoft (Score:2)
"Sir, I do not know off hand the best solution for that problem. But let me show you a great way of when given an array of length n + 1 containing integers 1 through n, finding the duplicate integer in an array."
It doesn't really matter if you got it right (Score:3)
From the interviewing side, it doesn't really matter if you got the answer right, or could even complete it. Especially as an entry-level hire. Sure, it's a plus, but it's not a giant one.
What I'm looking for when I ask these kinds of questions is how do you approach the problem, what is your thought process while solving it, how do you respond to any wrenches I throw into it, and do you understand a more elegant solution when I lead you to it or provide it. (It's also a spot-check on do you understand the basics of the language, but that's a secondary use of these questions)
The fact that you could or could not solve it isn't all that important - we can all find google and it's extremely unlikely that you will actually face these kinds of trick problems in the real world.
In the real world, you'd do something inefficient but simple-to-read and only switch to an elegant and fast solution if the profiler show it to be a bottleneck. Saving 100ms is huge, but if you only do it once in the lifetime of a long-running process, it isn't worth your time or the time of everyone after you who has to take 5 minutes to understand the elegant solution.
So the questions are about you and the way you think, not whether or not you get the right answer.
TL:DR - TFAuthor wasn't being asked what they thought they were, so they did not cheat.
Re: (Score:2)
Re: (Score:3)
From the interviewing side, it doesn't really matter if you got the answer right, or could even complete it. Especially as an entry-level hire. Sure, it's a plus, but it's not a giant one.
What I'm looking for when I ask these kinds of questions is how do you approach the problem, what is your thought process while solving it, how do you respond to any wrenches I throw into it, and do you understand a more elegant solution when I lead you to it or provide it. (It's also a spot-check on do you understand the basics of the language, but that's a secondary use of these questions)
The fact that you could or could not solve it isn't all that important - we can all find google and it's extremely unlikely that you will actually face these kinds of trick problems in the real world.
In the real world, you'd do something inefficient but simple-to-read and only switch to an elegant and fast solution if the profiler show it to be a bottleneck. Saving 100ms is huge, but if you only do it once in the lifetime of a long-running process, it isn't worth your time or the time of everyone after you who has to take 5 minutes to understand the elegant solution.
So the questions are about you and the way you think, not whether or not you get the right answer.
TL:DR - TFAuthor wasn't being asked what they thought they were, so they did not cheat.
It's the first few second that determines if you're going to give someone an offer.
The rest of the time is just spent reaffirming that belief.
Counter-Anecdote (Score:4, Interesting)
On the other hand, I was once asked a question in an interview (convert a C-string of digits to the equivalent integer), I gave the textbook answer from my college's computer architecture course, and the producer interviewing me refused to believe it worked. Even after I stepped him through a concrete example. I did not get that job.
Full story. [madmath.com]
Re: (Score:2)
I had an C++ phone interview a few weeks ago.
[A] I stopped the interview and told them: ok, let me talk first, perhaps after 5 minutes you think I'm not the right guy.
Background is, I did a lot of C++ from 1988 or so till 1999 (wrote my own subset of the STL etc.), and a few gigs later in embedded area up to about 2014. So, they wanted a coach for template meta programming in embedded devices.
One of the interviewers was a eastern european marketing droid, proclaiming loudly in the first place, she has no cl
Re: (Score:2)
So you quite correctly failed the interview. In an interview relevant for software development with peer review and ongoing company obligation for code maintenance, your code does not just have to convince the computer. And you insisting that this should be all that counts does not help.
Did you look at the link? dcollins' solution was utterly bog-standard -- and actually would have been my first approach as well (and I don't remember whether this algorithm was ever mentioned in any class I took; it's just the way I'd approach it -- in fact I wrote something similar a few months ago, though it was to convert from base 127, not base 10). The interviewer was an idiot, and an arrogant one. It's clear that he must not really have understood his own question, and probably didn't thoroughly un
Re: (Score:2)
I got a job at one place that I later found out they were trying to get an existing employee a promotion. To do that they had to sit the same job competition as I did which included writing a test. It was based on his daily work and wanted to know the commands for various things as it was for a systems administration position. I got one of the positions but he failed the test that was asking easy questions about his own job.
Easy (Score:5, Funny)
I would setup a new table in Oracle with a unique constraint on the column. Then I would use a SQL builder and insert items until I get an error. I would parse the XML error response, and infer from it whether it was the unique constraint that was violated.
Efficiency is my middle name!
Re: (Score:2)
I would expect from the parameters that you would be looking for duplicate records in a table if you were to approach the problem from a SQL perspective.
Surely, though, if the data is held in a SQL array (how it would get there I'm not sure), then a more traditional solution to the problem would be more efficient? I suppose it would depend on the size of the array, and CPU and Memory constraints of the database hardware, and rather the disk writes would be the bottleneck or the compute.
Re: (Score:2)
Interesting approach.
You would have got the job if you had printed out the stack trace of the error message and figured the result on your free time traveling home in the bus/train.
Try better next time! You know, don't work smarter, work harder and most importantly, work longer!!!
Re: (Score:2)
The user enters the numbers on their Microsoft Surface Pro tablet using Microsoft Cortana. From there a web service will send the data to the MS Azure Cloud Computing platform which will make use of the MS Windows OS backend. The numbers will be inserted into a Microsoft SQL Server database that has the constraint to prevent duplicate numbers from being added. When the duplicate number is found Microsoft Clippy will announce the number on the users MS Surface Pro tablet.
Just another example of F'd up Fizz Buzz (Score:2)
Re: (Score:2)
Not surprising (Score:2)
Big secret: my company uses the same set of problems when interviewing technical staff. It takes effort to make a good set, so we don't bother to change it. We want to see how candidates approach the tasks and present their solutions, so we give them several hours and access to internet and phone while they work on the set.
Probably the same thing happened, they were reusing good problems. I wouldn't worry. Life has a lot of lottery elements. Also there was much more to the selection process than this one pr
Nothing New (Score:2)
More than a half-century ago, I was a student at UCLA. Only three universities in the U.S. offered degrees in computer science, and UCLA was not one of them. Thus, I majored in mathematics with an emphasis on numerical analysis. I had just learned FORTRAN II but had not yet used it for pay.
I was looking for a summer job, and IBM (then the largest company in computers) was hiring students locally for summer jobs. I went to their offices and joined a number of other students seeking work there. The HR pe
This wasn't cheating. (Score:2)
This falls under the heading of "Did my homework."
If you happen to pick up valuable data during this process, kudos to you!
And he's right, he was merely asked to solve the problem, and did.
How is the Microsoft guy to know you weren't asked an IDENTICAL question at your last three job interviews?
I'd cheat too (Score:2)
Since most programming interviews are mostly pointless exercises in memory recall. I'd rather spend a few hours talking about design hypotheticals and the merits of different languages than force someone to sweat through a programming test. Tests are for colleges so a CS degree should tell you all you need to know about their abilities.
Re: (Score:2)
Re: (Score:3)
These kind of tests have nothing to do with the types of problems you regularly face with a given programming job. It's not like they asked you to write something actually related to what you do.
This particular question wasn't too bad but I've seen some that require memorizing specific algorithms and then writing out an implementation. It's absolutely crazy because most developers will look shit up anyway. Being good at memorizing does not mean you can actually write software.
As you mention this question wasn't bad, I actually think it's good.
Off the top of my head there's a couple decent answers, a pair of nested for loops or a single loop dumping it into a hash set. Again off the top of my head I don't know which would be more efficient but I suspect hashes become better as N gets big.
Weird little problems like this come up all the time when you're coding. And while you can probably get the right search terms to dig something out of stack overflow.... it's better if you can ju
Re: (Score:3)
That is the beauty of programming, getting to solve those "weird little problems".
For this example, there is a trick which makes it relatively easy, quick, and order-of-the-data independent. The problem states that there is an array of n values with integers 1 to n. In fact, it could be any set of n integers as long as they are sequential, thus for n=100, the values could be 1 - 100, 239 - 338, etc. Furthermore, they do not need to be ordered, just unique and all there. Then, there is an n+1 member that
Re: (Score:2)
Ahh, I didn't even notice the length of the array was 1 more than the number range, you basically have an unordered sequence with a single duplicate.
Instead of a hash just assign a second array of booleans with the same length, loop through and mark off each index... and when you see one already marked off you have your dupe.
O(N).
Re: (Score:2)
It's probably better to use a bitfield. A bitfield will require n/8 bytes of memory, but it has the advantage of not overflowing when N exceeds 65,000 or so. Same O(N) running time, but will probably be much slower in practice (addition is way faster than a memory access+branch). Still, it'll work for any value of N, assuming N is a standard 32 bit int and you have a modern machine with a reasonable amount of memory.
Re: (Score:2)
If you can modify the array, there are at least three approaches which run in linear time and use O(1) extra space.
One is the add and compare to triangle number approach. (NB overflow isn't a problem: it just means you're working modulo 2^32. If there are more than 2^32 elements in the array, use a 64-bit counter. If there are more than 2^64 elements in the array, you have other problems).
One is to adapt quickselect. Pivot on the midpoint of the range; check that the pivot isn't duplicated; and then recurse
Re: (Score:2)
For example, in this case I can think of two quick solutions to the problem presented in the summary. Create an extra
Re: (Score:3, Informative)
These kind of tests have nothing to do with the types of problems you regularly face with a given programming job.
I'll let you in on a secret: Interviewing isn't about "solving the problem". It is about "interviewing".
The interviewer doesn't much care if you get the right answer. They want to see how you think, and how you approach problem solving. You don't need a "real world" problem for that.
An astounding number of people that apply for programming jobs have no ability to write code. This includes people that have degrees in CS. These people can talk the talk, they know all the buzz words, they can analyze an
Re: (Score:2)
That's seems like the best solution to me, but you should be looping over n+1 since the array is one larger than n. Also you forgot to escape <, which is done by < but I get what you meant.
Re: (Score:2)
Re: (Score:2)
My first thought was actually some kind of bloom filter. It has the higher start-up cost of allocating memory which can be significant if the array is large. It has the possibility of finding the dupe very quickly after that if it's near the beginning of the scan, and worst-case it scans the entire array.
I'd code them up and time it, but it's not that interesting.
Re: Is that question a hoax? (Score:2)
Re: (Score:2)
Well, you forgot the other two solutions and the value for c is quite well determined, you can look it up here (I believe some people think it varies based on gravity and other unproven bollocks): https://en.wikipedia.org/wiki/... [wikipedia.org]
In my O calculus calculations I always use that c, always worked for me!!
Re: (Score:3)
Re: (Score:2)
This is brilliant. I would hire you.
Re: (Score:2)
OK that is really really cool.