if all the numbers from 1 to 250, but one, were written in random order (no spaces) how would you find the missing number?
FOR EXAMPLE, 132456789101113 is 1-13 and not very random. most answers below have misunderstood me (well, less now that some have been deleted in shame... ;o)
you can get the digits, just by seeing what is missing. but then you seem to be left with a rather tricky partition problem. so i guess dynamic programming? is there a better way?
would it help to pick out unique combinations (if the pattern 249 occurs just once, it must be 249, unless it is the missing number)? how far would that get you?
i guess since you know the missing digits you should check for each permutation - you might get lucky and not find one.
is there some cute trick? something involving suffix trees?
[edit: anonymoushn has a good point - it's not guaranteed unique]
Add them all up, subtract that from the actual sum of 1-250 and voila. Optimization bonus: you don't need to do the second sum, there's a closed form (I don't remember what it is, but I do remember Gauss came up with it as a kid).
but you can get the formula by imagining the numbers as piles of pennies and then completing them to make a square and then splitting down the diagonal
*
**
***
*..
**.
***
\.. \
*\. + \
**\ \
where a \ is half a penny. so * = \\
so it's 1/2 * n * n (ie half the square) plus an extra 1/2 for each one on the diagonal.
# arr must contain all of the numbers from 1 to k except one
# returns the number which is missing
def missing_number(arr):
return ((len(arr)+2) * (len(arr)+1))/2 - sum(arr)
I can't really talk about the article, since it is down :(
Edit to reflect edit in the parent: The problem as posed is not soluble in general. For k=21,
Add all the numbers in the list up, and then subtract that value from the sum of 1 to 250. That value is the missing number, in O(n) time and O(1) space. This only works if all the numbers are only written once though.
Sum all the individual digits of 1-250 (e.g. 11 is 1+1 is 2). Sum all the individual digits in your string. Now you at least know the sum of the missing digits, and how many missing digits there are.
I would think you could start with assuming that all numbers are used, so you know how many of each digit you should see. Calculating how many of each digit you actually saw should give you a list of which digits were not seen. Then, you should have a much smaller search for the permutations of the missing digits. (This make sense?)
I'm ridiculously curious to know if there is a clever trick to this! :)
Once you know the actual sum, you can do it either:
sum all, subtract total - sum.
Or with data structures:
it would be a variant of the "given an array find all pairs of numbers that add up to a sum". The benefit of using the data structure approach would be that you can now find x missing numbers in the range 1 - 250.
note* the closed form might have a off by one error
Create an array of 250 booleans. Go through the list 3 times. First all the 1 digit numbers, then the 2 and 3 digit numbers. Set the array entry for the resulting numbers to true. The entry that is false is the missing number.
I'm sure there are faster ways but a quick and dirty approach would be to count how many of each digit are in the input string, then compare to the expected result, which is easy to figure out. This will tell you what digits are missing from the input. There will be at most 3 of them, then just search the input for the possible valid combinations of those digits, as soon as you find one that is missing, you're done.
So I see a number of replies that say 'add the list up' but there is no list. There are no spaces, you would have to add in the spaces yourself which is an extremely difficult problem.
Since there are no spaces in the list:
1) I would count the instances of didgits 0-9
2) compare those counts to the counts produced by the complete set of didgets
3) The ones that fell below in count are the didgits in the missing number
4) Count the instances of the permutations of your missing didgets
5) compare those counts to the counts from the full list
6) Done.
I just tried this -- you don't know _which_ combination is missing unfortunately in the case of a 2 or 3 digit number. With 3 you might be able to figure it out by using the limit of 250 (e.g. if 2 4 and 7 are missing there is only 1 to recombine them and have it be less than 250), but with two how do you differentiate between say 26 and 62 in a clever, non brute force way?
In case anyone wants a starting point:
import random
from collections import Counter
rand_list = range(0, 250)
random.shuffle(rand_list)
missing = rand_list.pop()
shuffled = ''.join([str(x) for x in rand_list])
full_list = ''.join([str(x) for x in xrange(0, 250)])
cntr = Counter()
for digit in full_list:
cntr[int(digit)] += 1
for digit in shuffled:
cntr[int(digit)] -= 1
digits = []
for k, v in cntr.items():
for _ in range(0, v):
digits.append(k)
My quick take on it is that you have to generate a list of all the 1-tuples, 2-tuples and 3-tuples in that very long string, along with the start and end indexes of each tuple.
Then you find a set of tuples which cover 1-250 (missing one number) and which don't overlap.
You can start by filtering out all the 3-tuples which are over 250.
I might use a hash table to put together a list of all duplicates. Any hash table entry with no duplicates has to be right. Use the indexes that have been removed from the "eligible" pool to remove tuples from the hash table. Iterate.
Of course it's entirely possible that iterating like that could still leave you without a solution. At which point a guess has to be made and to continue solving. If said guess is bad, backtrack and make a different guess.
Obviously it's harder to implement than to outline. And I've probably missed a bunch of optimization.
"Gee, that's an ugly way to store numbers. Where did this data set come from? What business process generated it, and under what constraints? Can I talk to the guys who own that process?"
I personally don't think this post is a serious compilation of question that get asked at Amazon considering the stature of the company nevertheless i think an interview at amazon will never be complete without rigorous test of candidates problem solving skills and/or the specific capabilities that he is applying for. Also the kind of questions that are mentioned in the article are the kind of questions HR's ask to confuse the candidate and the sole purpose of these questions is to check the candidates presence of mind and how he tackles those questions.IMHO Amazon is a great company to work at there is no doubt in that.
i am guessing this is a cultural thing, so i should apologise for being amused, or at least explain. to me a company like amazon is not a thing that deserves much respect in itself (although i can see how it is an accomplishment for jeff bezos and other people who have contributed). i don't think i am explaining very well, sorry. it might be something like "power distance" - http://en.wikipedia.org/wiki/Hofstede's_cultural_dimensions_...
anyway, to my culture, your reply seems inappropriately respectful (i am not saying it is since this is obviously a culturally-dependent judgement, just trying, clumsily, to explain...). hence the idea that they must have a hostage.
Hmm. I think data showing hiring vs time for companies would be more relevant than average tenure of an employee.
i.e. The faster a company grows, the less likely/harder it is to maintain culture and enforce hiring/recruiting standards - I can see how that may lead to shitty interview questions.
I worked for Amazon, and looked over the list of allowed/prohibited interview questions on the internal wiki. I did not see any of these question. Furthermore, they are against asking puzzle-type and behavioral questions.
Hmm, when I interviewed for an internship at Amazon, they asked me a behavioural question or two. Might have been that I had no previous experience and they needed to gauge how I worked with people somehow. Or that wiki isn't strictly followed by interviewers?
It's not a serious post... but I have interviewed with Amazon and their questions are a big part of why I don't work there. (The other reason is that when I asked people what they were working on, they all said they were rewriting all the Perl code in Java "because Amazon is a Java company" - apparently that was the biggest business need at the time)
Rather than go into great detail on why I don't like their questions, I'm going to pick out one that stands out as an example. It starts:
"Suppose I want to <description of some user story>, so I want you to design a system that <vague description of an implementation method>."
Okay, I'm thinking, done this before a lot of times, it's bland but not an unreasonable way to find out how somebody approaches problems. But they haven't finished talking, and they add one more sentence:
"Make sure you show me the objects and classes that your system will use."
This is the point when I try not to let my disappointment and irritation show. It's not just that they've completely prejudiced the question, by forcing it down one particular design path, it's that they've made it clear this is not a test of my ability to design systems, it's a test of my ability to mimic their design of the system. Worse yet, in one stroke this destroys any hope of finding out how the candidate thinks; instead, it just measures how well they can think along certain lines.
I don't have a problem with object-oriented designs - I'd probably have done things that way anyway. But I do have a problem with companies that hire based on conformity to groupthink. I don't want to work with a group of people who were selected based on their performance at this kind of question.
FYI Google's codebase is also heavily Java. I'm not sure if it's a good idea to judge companies/projects based on the language they use. [Edit: Okay, maybe I misunderstood that part]
Did the other interviewers also ask similar questions?
I didn't read a complaint against java per-se, but rather an observation that if your most pressing business concern is to rewrite (presumed) working code in one language into java purely for taste reasons, then maybe it wasn't a place he wanted to work.
asuffield didn't malign Java: he seemed to imply judgment about the fact that the company seemed to be converting working code from LANGUAGE1 to LANGUAGE2 for the purposes of being a LANGUAGE2 company.
In particular about this being the only major project they were working on. They didn't just rewrite, they stopped doing everything else in order to prioritise it. The mind boggles.
There's a lot more to software engineering at amazon than just rewriting perl code into java. There's also rewriting C++ code in java. And there's rewriting java code in java to accommodate for some service your code was dependent on being deprecated. Really, there's all kinds of fun.
"The other reason is that when I asked people what they were working on, they all said they were rewriting all the Perl code in Java "because Amazon is a Java company" - apparently that was the biggest business need at the time"
Having sat in on these kinds of discussions before at companies large and small, while it is certainly sometimes true that companies make a ridiculous platform decision like, "We're a java company", more often than not the decision is a lot more complicated. They might have felt that it was easier to hire people who knew Java, or they leveraged off the shelf software that was written in java, or they acquired a company with interesting tech based on java, or a million other reasons.
That doesn't mean they made the right decision, but I'm just making the point that what may trickle down as "we're a java company" didn't start out that way, and may not be based in that fundamental stupidity.
c'mon, if you are as smart as you believe yourself to be, do you actually believe that the reason they ported their Perl code to Java was because "Amazon is a Java company"?
I could see many reasons to port one of the worlds largest sites off of Perl and onto something like Java, one being the availability of developers that are proficient in Java vs Perl.
Also, if the company you work at uses OOP to design their systems it's perfectly normal to ask you to design something with regards to those restrictions.
If a company "uses $thing to design their systems" as a matter of dogma, I don't work there. And "Amazon is a Java company" was the actual reason given by the people I talked to. If they were lying or had no idea why they were doing the thing they'd been told to do, that's just a different reason why I won't work there.
I conducted interviews at Amazon. Sadly, most of the time that question was about measuring the ability of the candidate to do object-oriented design at all. Usually we didn't care what the final data model looked like, so long as it was logical (and much more often than not, it wasn't) - and we gave candidates every opportunity to explain and justify the classes they designed. But you are correct in that Amazon loves OO, and functional or other approaches wouldn't have been looked at favorably.
I just interviewed and got a job offer with Amazon as a college hire. The entire interview was literally a single long-ish (a few hours) coding project in the language of your choice. No HR nonsense, no questions about my weaknesses or challenges I have faced. It was quite refreshing from other interviews. I wrote code, wrote tests, wrote documentation, got a job, no bullshit.
I interviewed for Lab 126 (like everyone else on the internet). I was really excited about the prospect but the guy giving the interview had an attitude problem and was completely uninterested in the process.
He insisted on grilling me on a metaphor in my personal statement as if it were literally true. I honestly don't know if he was trying to piss me off, or was (slightly) autistic and didn't understand metaphors. Once I'd gotten him off that, I mentioned I had a friend who worked at Lab 126, which he was also completely uninterested in. When your interviewer isn't interested in the fact that someone you worked with for 5 years works down the hallway from him? You're not getting that job. It was pretty clear a decision had been made against me before the interview ever took place and Amazon was just wasting my time.
Interviews are a horrible test of how someone will perform on the job. Never in work life are you required to come up with a solution immediately. Those types of solutions are almost always wrong. It's only after deep thought and 100s of hours toiling on a problem from every angle that an elegant solution that simplifies presents itself. But sadly, the only way to know if someone is capable of that is to actually hire them for a trial week or 30 days and see how they do and immediately fire or sign for a longer term contract.
56 comments
[ 5.0 ms ] story [ 204 ms ] threadFOR EXAMPLE, 132456789101113 is 1-13 and not very random. most answers below have misunderstood me (well, less now that some have been deleted in shame... ;o)
you can get the digits, just by seeing what is missing. but then you seem to be left with a rather tricky partition problem. so i guess dynamic programming? is there a better way?
would it help to pick out unique combinations (if the pattern 249 occurs just once, it must be 249, unless it is the missing number)? how far would that get you?
i guess since you know the missing digits you should check for each permutation - you might get lucky and not find one.
is there some cute trick? something involving suffix trees?
[edit: anonymoushn has a good point - it's not guaranteed unique]
1727321173475
could be 1, 72, 73, 211, ... or 17, 27, 32, 117, ... or 172, ...
but you can get the formula by imagining the numbers as piles of pennies and then completing them to make a square and then splitting down the diagonal
where a \ is half a penny. so * = \\so it's 1/2 * n * n (ie half the square) plus an extra 1/2 for each one on the diagonal.
so it's n * n/2 + n/2 = (n+1) * n/2
Edit to reflect edit in the parent: The problem as posed is not soluble in general. For k=21,
You can discover the missing digits in linear time, but determining from there whether the input has a unique solution seems a bit annoying.If a valid permutation of the missing digits is missing, you win, but you can have a unique solution without that being the case:
1 2 3 4 5
12345
At this level it's no big deal. What happens when you get to double digits?
11 12 13
111213
Now what happens when they're not in a nice order?
5121892178
...11123...
Is that a 1, an 11, a 12, a 112, a 123?
I'm ridiculously curious to know if there is a clever trick to this! :)
Once you know the actual sum, you can do it either: sum all, subtract total - sum. Or with data structures: it would be a variant of the "given an array find all pairs of numbers that add up to a sum". The benefit of using the data structure approach would be that you can now find x missing numbers in the range 1 - 250.
note* the closed form might have a off by one error
Since there are no spaces in the list: 1) I would count the instances of didgits 0-9 2) compare those counts to the counts produced by the complete set of didgets 3) The ones that fell below in count are the didgits in the missing number 4) Count the instances of the permutations of your missing didgets 5) compare those counts to the counts from the full list 6) Done.
In case anyone wants a starting point:
Then you find a set of tuples which cover 1-250 (missing one number) and which don't overlap.
You can start by filtering out all the 3-tuples which are over 250.
I might use a hash table to put together a list of all duplicates. Any hash table entry with no duplicates has to be right. Use the indexes that have been removed from the "eligible" pool to remove tuples from the hash table. Iterate.
Of course it's entirely possible that iterating like that could still leave you without a solution. At which point a guess has to be made and to continue solving. If said guess is bad, backtrack and make a different guess.
Obviously it's harder to implement than to outline. And I've probably missed a bunch of optimization.
anyway, to my culture, your reply seems inappropriately respectful (i am not saying it is since this is obviously a culturally-dependent judgement, just trying, clumsily, to explain...). hence the idea that they must have a hostage.
Better to live in mud huts!
[0] http://www.businessinsider.com/companies-ranked-by-turnover-...
i.e. The faster a company grows, the less likely/harder it is to maintain culture and enforce hiring/recruiting standards - I can see how that may lead to shitty interview questions.
At that growth rate, you'd expect the tenure numbers to be dominated by hiring rather than turnover, a point the article misses completely.
(Per their annual reports, Amazon had 88,400 employees on 12/31/2012, 56,200 on 12/31/2011, and 33,700 on 12/31/2010)
It seems superficial and cynical, and doesn't seem to have anything useful to say. (Also, the post is tagged as 'Industry News'...??)
I worked for Amazon, and looked over the list of allowed/prohibited interview questions on the internal wiki. I did not see any of these question. Furthermore, they are against asking puzzle-type and behavioral questions.
Rather than go into great detail on why I don't like their questions, I'm going to pick out one that stands out as an example. It starts:
"Suppose I want to <description of some user story>, so I want you to design a system that <vague description of an implementation method>."
Okay, I'm thinking, done this before a lot of times, it's bland but not an unreasonable way to find out how somebody approaches problems. But they haven't finished talking, and they add one more sentence:
"Make sure you show me the objects and classes that your system will use."
This is the point when I try not to let my disappointment and irritation show. It's not just that they've completely prejudiced the question, by forcing it down one particular design path, it's that they've made it clear this is not a test of my ability to design systems, it's a test of my ability to mimic their design of the system. Worse yet, in one stroke this destroys any hope of finding out how the candidate thinks; instead, it just measures how well they can think along certain lines.
I don't have a problem with object-oriented designs - I'd probably have done things that way anyway. But I do have a problem with companies that hire based on conformity to groupthink. I don't want to work with a group of people who were selected based on their performance at this kind of question.
Did the other interviewers also ask similar questions?
"The other reason is that when I asked people what they were working on, they all said they were rewriting all the Perl code in Java "because Amazon is a Java company" - apparently that was the biggest business need at the time"
Having sat in on these kinds of discussions before at companies large and small, while it is certainly sometimes true that companies make a ridiculous platform decision like, "We're a java company", more often than not the decision is a lot more complicated. They might have felt that it was easier to hire people who knew Java, or they leveraged off the shelf software that was written in java, or they acquired a company with interesting tech based on java, or a million other reasons.
That doesn't mean they made the right decision, but I'm just making the point that what may trickle down as "we're a java company" didn't start out that way, and may not be based in that fundamental stupidity.
I could see many reasons to port one of the worlds largest sites off of Perl and onto something like Java, one being the availability of developers that are proficient in Java vs Perl.
Also, if the company you work at uses OOP to design their systems it's perfectly normal to ask you to design something with regards to those restrictions.
He insisted on grilling me on a metaphor in my personal statement as if it were literally true. I honestly don't know if he was trying to piss me off, or was (slightly) autistic and didn't understand metaphors. Once I'd gotten him off that, I mentioned I had a friend who worked at Lab 126, which he was also completely uninterested in. When your interviewer isn't interested in the fact that someone you worked with for 5 years works down the hallway from him? You're not getting that job. It was pretty clear a decision had been made against me before the interview ever took place and Amazon was just wasting my time.
Left a bad taste in my mouth.