Jane Street Capital: What is the smallest number divisible by 225 that consists of all 1’s and 0’s?
I believe it must end with a zero. And the next to last digit must be a zero. Keep on going. Via Chris Blattman, here are some more, along with a few snarky answers.
1100
probably not divisible by 225…
oh duh, forgot to check my work. but now i see the trick!
Nice, but why not 0.1?
0
It’s 225, but you have to write it in binary. The only number in base ten that could be considered fitting is zero.
Zero abuses the ordinary meaning of “divisible by.” Any number is divisble by 225 if we are willing to play semantic games. For example, 1 divided by 225 is 1/225, or .00444444….. Oh, you meant _evenly_ divisible? Well why didn’t you say so?
I tried adding, then generating a couple numbers (1, 10, 11, 100, 110, 111) before realizing they were getting factorial. Then I took the factorization of 225 (3*5*3*5) and said “we can make the 5′s into 10′s by multiplying by 2×2, giving us 900, then what do we multiply by to get a 111… number divisible by 9?” All numbers divisible by 9 have the sum of their digits divisible by 9, so it would have to have 9 ones, as close to the ones place as possible… 11,111,111,100. Would’ve been an agonizing interview and I might still be wrong!
Very nice. I gave up on that one.
A lot of the other ones were easy, and were just to see if you could use reasoning outside of text-book questions.
Although we covered Russian Roulette in 8th grade math, fortunately enough…
My logic exactly.
Tyler is correct about the last two digits.
225 is divisible by 9, so any number divisible by 225 must also be divisible by 9. Any number divisible by 9 must have digits which sum to 9 (or another number divisible by 9, and so on until you get to 9). The lowest number that meets these criteria is 11111111100 (nine ones followed by two zeros).
A bit of thought (and number theory) makes this relatively simple. 225 = 9 x 25. Any multiple of 25 must end in 00, 25, 50, or 75, but only the first is allowed here. Any multiple of 9 must have digits that sum to a multiple of 9, hence that sum must be one of 0, 9, 18, 27, … . An integer is a multiple of 225 if and only if it is a multiple of 9 and 25. Assuming they want a positive integer, the smallest is 11111111100.
0
10, actually, since the problem stipulates 1′s and 0′s.
Spoiler alert (I think):
.
.
.
.
.
.
11,111,111,100
I note that 225 = 25 x 9.
All products of 25 end in 25, 50, 75 or 00. Therefore the number must end in 00.
All products of 9 have digits that sum to 9. Therefore the number must have nine 1′s.
So the answer would be nine ones followed by two zeros.
Well, 225 is 9 x 25, and a multiple of 225 would be 225 x some integer n.
but if we break up the integer n into integers a and b s.t. n=ab, we can do something interesting like 9 x a x 25 x b
25 x b is obvious.
multiples of 9 have digits that add up to 9… so we can see where this is going. we don’t have to find a, nor do we need to.
Wouldn’t it just be 10? The question doesn’t require that the number be evenly divisible by 225.
Exactly. Nothing about positive integers or base-10 is stated. It does ask for ones and zeros so it’s not 1.
I agree the questioner should have said integer instead of numbers. 10 is good unles you think 01 is valid or decimal point does not count which would make the questions unanswerable.
My answer: 11111111100. (225*49382716)
Procedure I used: Multiply by 4 to reduce the number of non-binary digits, get 900. Remember that a number is divisible by 9 if the sum of its digits is 9. Note that I need two zeros on the end. Write nine ones followed by two zeros.
1,000,110
Solved it in 2 minutes in Excel. Must be a binary number, so just try them all:
A1 B1 C1
1 =dec2bin(A1) =mod(B1,255)
Copy down and on line 70 the first answer appears. Ok, so I’m sure this ruins the mathematical beauty of the question, but when the numerical solution is so easy, why fool around with the math?
-Mercy
Oops! It looks like I don’t get the job. I’m not sure why I read 255.
But my approach still works. Using the correct divisor of *225*, the number is indeed 11,111,111,100. And the DEC2BIN approach is a cute way of solving the problem.
Also, my approach still works even if you don’t have an arithmetic trick like the sum of the digits .
Quick! What about 522? 101,111,011,110
252? 111,101,111,100
If God wanted us to do math, he wouldn’t have invented computers.
-Mercy
that was a good trick to generate a list of 1&0 numbers. but if was the “lazy” solution, even if you took 5sec to do it in excel. i like seeing the logic of people here too
I read it as 255 originally too. Must be all that hexadecimal game-training as a kid…
11100001(binary) = 225 (decimal). 225/225 = 1.
The question did not specify base-10.
That was my thought. There was no base 10 stipulation made anywhere in the question.
Yeah, I know. When someone asks me what 1+1 is, I immediately think: “What kind of fool does he take me as? It must be 10.”
This is the answer I would have given. Work smarter, not harder.
I wonder what an interviewer would think of it?
Also, why not just 1 (base 225)? The numbers are the same size and you save yourself the effort of a binary conversion
“What a smartass.”
Maybe it’s a question to weed out those people who need base-10 specified for them.
225 decimal == 11100001 binary. All 1′s and 0′s and divisible by 225, it is all just a matter of what base you use.
So do you get extra points, or different tracks, for going with the easier (computer) or cleverer (binary) solutions? If you knew all three answers, which would you give?
The binary answer is clearly what they’re going for (ALL “brain teaser” questions given in interviews are ways of seeing if you can think outside the parameters of the question). But if you came up with the base-10 answer as well, that would be bonus points.
I thought maybe the binary shortcutters went to management and the “knows facts about divisibility” people went to workhorse math nerd jobs.
Knowing Jane Street, they would want to hear the decimal answer (seeing as it has one that is reasonably easy to get to). Now, if you told them the binary answer as well, I’m sure they wouldn’t count it against you.
11,111,111,100
How in base 10:
225=9*25
Digits of integers divisible by 9 must add up to 9
so the smallest integer thats 1′s and 0′s thats divisible by 9 is 111111111, now the smallest integer divisible by 25 that is 1′s and 0′s is 100. We multiply these two numbers together, tadah.
If you want to just go binary you can, but this is more fun.
Well, crap, someone on the thread beat me to it.
How about 111*111*100
That’s one of the easiest finance interview questions I’ve ever seen…
For the Goldman-Sachs question I would say:
If I had eight balls I wouldn’t be sitting here.
And I would be perfect for Goldman-Sachs.
The goldman sachs question was a bit of social engineering. Didn’t ask 9 balls, which is what the algorithm can do, but 8, in an effort to mislead.
Facebook question is standard computer science, generalized to 5-way trees
No, it takes three weighs for 8 balls instead of 2 weighs for 9 balls. 8 is 2 cubed, while 9 is 3 squared. So, for 8 balls, you divide the group into two groups of four each, weigh them, then divide the heavier group into two groups of two balls, weign them, then finish with weighing each ball of the heavier duo.
For 9 balls, you divide the balls into three groups of three balls each, weigh two of the groups, keeping the heavier group for the second weigh. If the two groups you weigh are equal, keep the unweighed group for the second weigh. You similarly weigh two balls from the chosen group. The heavier ball is the heavier ball, and if the scales are balanced, then the unweighed ball is the heavy one.
Wait, clever, with 8 balls you need two weighs.
You do the same thing with the nine-ball method. Weigh 3 balls vs. 3 balls, with 2 balls on the side. Then, you weigh the 2 balls against each other if the scales balance in the first weigh.
bingo.
that’s why it’s a trap
Facebook question is also social engineering/nerd snipe, at least as stated in the article.
Answer: One race, 25 horses on the track. The top 3 finishers are the fastest. There is no constraint given with respect to how many horses fit on a track.
Yes, the more interesting version of this question explicitly limits each race to five horses. In which case, seven races.
Break the 25 horses up into 5 nodes of 5 horses each and then determine the ranking of the horses within each node (5 races). Then race all of the top ranked horses against each other to determine the fastest horse (6 races).
You can exclude the bottom two horses from race 6 and all the horses in their nodes because they clearly aren’t in the top 3. Now, there are 5 possible horses to fill the second and third positions. Either the 2nd or 3rd horses from the winning node, the 1st or 2nd horses from the 2nd place node, or the 1st horse from the 3rd place node.
Race these 5 horses against each other, and you know the top three horses (7 races).
All the Sailer fans keep telling me that employers can’t ask these questions because they are racists. So what gives?
Plausible deniability is possible with these questions. The argument is about disparate impact by structured tests, and the employer can deny that is what is going on here.
You are referring to Griggs vs Duke Power http://supreme.justia.com/us/401/424. Griggs vs Duke Power applies to companies, but does not apply to SWPL ‘learning’ institutions such as Harvard etc. – prospective employees pay Harvard which then legally does the smartness tests that the employers are forbidden to do.
‘Markets in everything’
harvard can evaluate quants?
The article claims these questions are being asked directly by the companies not Harvard. Is the article wrong or does Griggs vs Duke Power not apply to all these companies for some other reason?
I am surprised so many people knew that multiples of 9 have digits that sum to 9 (or a multiple). Never heard that one before, seems a pretty useless fact?
You should have watched more Square One TV growing up.
http://www.youtube.com/watch?v=Q53GmMCqmAM
So I’m not the only one who had that song in his head through these comments.
“How would you market a telescope in 1750 when no one knows about orbits, moons, etc.?”
LOL, nobody knows about orbits and moons 75 years after Newton’s Principia?
“Suppose you had eight identical balls. One of them is slightly heavier and you are given a balance scale. What’s the fewest number of times you have to use the scale to find the heavier ball?”
The algorithm does work, and the answer is two times. Split into 3, 3, 2. Weigh 3 vs 3. If same, weigh 1 vs 1 and pick heavier. If different, throw away lighter 3, 2. Split heavier three into 1, 1, 1. Weigh any two. If same, unweighed is heavier. If different, heavier is heavier.
But I was wondering: How do you know that difference is statisticaly significant? There is measurement error, right? Is this to think out-of-the-box? If so, in the wrong way?
also, the google question there was pure combinatorics. I have heard better trick questions from tech companies. One game theoretic question was so good I started using it for finance (option theory) type positions (has a martingale solution as well).
IMHO, solving this in your head is the Wrong Answer. Here’s an off-the-cuff solution in Python:
#!/usr/bin/python
i = 0
while True:
i += 450 #only even multiples could possibly work
v = True
for j in str(i):
if j not in ["0","1"]:
v = False
break
if v:
break
print “i=”+str(i)
output:
i=11111111100
sigh, comments box ate the indenting which of course matters in Python…
Funny, I took the same solution approach but used java. Much prettier & surely faster to write in python.
“Zero. Zero divided by 225 is zero. Or, are you asking for the smallest nonzero natural number resulting in a quotient that is, itself, a nonzero natural number?”
Sorry about that, not meant to be a reply.
This one is really easy. 225=25*9.
Divisibility by 25 means ending with 00/25/50/75, so it obviously ends with 00.
Divisibility by 9 means repeated sum of digits modulo 9 is 9. So there must be nine 1s (or eighteen etc.).
The smallest number like that is 11_111_111_100 (9 ones, 2 zeroes).
That was one minute without a computer, did I get the job ;-p ? (was this for computer programmers or something?)
Answer consists of all 1’s and 0’s (a).
One has to multiply 225 by 4 to get the two last digits to 00 (b):
225 * 4 = 900
Hence, the answer is divisible by 900, and by 9.
Divisibility by 9 gives: every digit in the answer, added together, must be divisible by 9 (c).
(a), (b), (c) gives 11111111100, since it is also the lowest possible number.
Answer: 11111111100
My answer is 11111111100. The logic: to be divisible by 225 the number must be divisible by 25 and 9. Testing for divisibility by 9 is simple – the sum of the digits should be divisible by 9. Since the numbers are made of only 1′s and 0′s and divisibility by 25 will require ending in 0, the first number to try is 1111111110. Divisible by 9 but when divided by 25 leaves a fraction of 0.4. Add another 0 at the end and you now have a number divisible by both 25 and 9.
The easiest way to come up with the answer is to blog the question and let readers do the work.
This technique also has the advantage of working for every question listed.
The engineering answer is 1000
250 * 4 + uncertainty margin
Google: You are climbing a staircase. Each time you can either take one step or two. The staircase has n steps. In how many distinct ways can you climb the staircase?
Fibonacci.
I really like the 225 in binary form (my first gut reaction to save time) but these interviews are usually so moronic that the interviwers would probably call it a wrong answer. Not unlike so many professors who grade incorrectly because they cannot contemplate another to the ambiguous questions they pose. Or [some] stupid IQ tests (name the odd one out: cow, hen, pig, sheep).
I tried some of the answers posted here in R and they didn’t work or were bigger than my guess: 1,000,000,000
25 / 225 = 0.1111111…
but then
.025 / 225 = 0.000111111111…
so there is no limit: you can keep adding more zeros after the decimal point
Oops, misread the problem…
The racehorse question has no valid solution because it ignores performance variation. Apply the questioner’s reasoning to programming leads to “race conditions” and deadlocks. The sad state of software engineering makes a lot more sense now.
Comments on this entry are closed.