bramcohen: Challenge Problem

Bram Cohen (

bramcohen) wrote,
@ 2007-04-03 15:25:00

Challenge Problem
I'm rather fond of putting technical challenges in jobs postings. They're an effective filter and help to establish that yes, really, this is a programming gig.

But for some reason my last batch of challenges hasn't gotten any right answers. For example, the following:

What is the exponent of the largest power of two whose base seven representation doesn't contain three zeros in a row?

Am I crazy here? I think anyone who can't get the right answer to that problem with a few minutes of coding has no business being allowed to graduate from a CS program, and yet I still get wrong answers.

Please don't post spoilers. If you happen to get the right answer you can mail it to jobs at bittorrent dot com.

(Post a new comment)

	dojothemouse 2007-04-03 11:20 pm UTC (link)
	So, you're trying to figure out who can configure a batch mailer to send you enough guesses? (Reply to this) (Thread)

	bramcohen 2007-04-04 12:12 am UTC (link)
	No, anyone who sent a zillion guesses would get disqualified, although if someone sent a wrong answer then later said 'oops, here's the right answer' I'd probably let through. It isn't a trick question, nor a particularly hard one. (Reply to this) (Parent)(Thread)

(no subject) -

dojothemouse, 2007-04-04 12:34 am UTC

loic
2007-04-03 11:27 pm UTC (link)

Yeah, my naive, brute-force search took me just a couple of minutes to build, though I'm not convinced that I have a correct answer since no proofs were involved, and it's a really really dump search.

When I was looking around a new job became obsessed about the puzzles metaweb was publishing. I went and relearned eigenvectors to look for a new algorithm for maintaining directed acyclic graphs (note to self: finish that research) but eventually the job advertisement didn't actually inspire me to go and work for the company.

(Reply to this) (Thread)

bramcohen
2007-04-04 12:16 am UTC (link)

The question didn't ask for a good algorithm, just a right answer. That's another funny thing with interview questions, if I ask people to rewrite some awful code to run 'reasonably fast' they hardly ever stop at 'reasonably fast' and always go for 'super optimized'. Maybe they're afraid to cut it short for fear getting marked wrong by an overly zealous interviewer. I'd give them credit for understanding the basics of asymptotic analysis.

There's a bit of a joke with regards to the correct answer - it's in a field of mathematics where we basically can't prove anything, so what you do is test numbers up to a high enough value that you're convinced there couldn't possibly be any higher ones, and send in the highest you found. I'd also give props to someone for sending in their answer with that caveat.

(Reply to this) (Parent)(Thread)

(no subject) -

elitegrunt, 2007-04-04 01:37 am UTC

(no subject) -

bramcohen, 2007-04-04 06:33 pm UTC

(no subject) -

toddmarshall, 2007-04-12 05:15 pm UTC

(no subject) -

lupoleboucher, 2007-04-04 05:42 am UTC

(no subject) -

agthorr, 2007-04-05 05:09 pm UTC

Should probably specify that, then -

illiterat, 2007-04-05 08:07 pm UTC

	kemayo 2007-04-03 11:57 pm UTC (link)
	Do people misunderstand the question and go down the wrong path (resulting in an answer that is correct for their assumptions), or do they just plain get it wrong? (Reply to this) (Thread)

	matt_havener 2007-04-04 12:10 am UTC (link)
	I did this ... luckily the real solution was within +-1 of my incorrect answer (Reply to this) (Parent)

bramcohen
2007-04-04 12:21 am UTC (link)

Hard to say, I don't really bother evaluating wrong answers too often. There was one person who sent in code which ought to work with no answer, and upon inspection it turned out that he was using a recursion which blew through the call stack size limit. Of course that counted as wrong - if you either can't be bothered or don't know how to fix that problem, I don't want to hire you.

(Reply to this) (Parent)

	suppressingfire 2007-04-04 12:02 am UTC (link)
	Students hate algorithmics. At my school, one of the ways they try to keep the students interested is to add bonus questions in a section called "interview questions" onto homeworks. (Reply to this) (Thread)

	bramcohen 2007-04-04 12:19 am UTC (link)
	The question didn't ask for a good algorithm, it just asked for a right answer. If you achieved it with a suboptimal asymptotic, then well bully for you, if I'd wanted an optimal asymptotic I'd have asked for an optimal asymptotic. It's meant to be a test of basic competence, not a super technical challenge. (Reply to this) (Parent)(Thread)

(no subject) -

suppressingfire, 2007-04-04 12:25 am UTC

(no subject) -

bramcohen, 2007-04-04 12:31 am UTC

(no subject) -

therealdrhyde, 2007-04-04 10:59 am UTC

(no subject) -

elitegrunt, 2007-04-04 01:53 am UTC

(no subject) -

uke, 2007-04-04 04:06 am UTC

(no subject) -

suppressingfire, 2007-04-04 06:42 am UTC

(no subject) -

rizwank, 2007-04-04 09:07 am UTC

(no subject) -

bramcohen, 2007-04-04 06:40 pm UTC

(no subject) -

rizwank, 2007-04-06 10:20 am UTC

(no subject) -

bramcohen, 2007-04-06 08:36 pm UTC

All about COBOL -

misterajc, 2007-04-04 12:37 pm UTC

houdini_cs
2007-04-04 12:20 am UTC (link)

Is this a valid rephrasing of the problem?

Find the largest x = 2^n s.t. x in base 7 doesn't contain 3 zeros in a row. Give n

(Reply to this) (Thread)

	bramcohen 2007-04-04 12:22 am UTC (link)
	Correct. I was intentionally avoiding mathy notation to give people with hacker backgrounds a fair chance. (Reply to this) (Parent)(Thread)

(no subject) -

houdini_cs, 2007-04-04 12:41 am UTC

(no subject) -

rizwank, 2007-04-04 09:16 am UTC

	ryanlrussell 2007-04-04 12:23 am UTC (link)
	Right, that's my problem. I could probably code it up, but the original wording is horrendous. Is that indented to be part of the problem? (Reply to this) (Parent)

	anaraug 2007-04-04 12:30 am UTC (link)
	I thought up a way to do it in matlab in like... 5 seconds... but that's probably cheating. (Reply to this) (Thread)

	bramcohen 2007-04-04 12:35 am UTC (link)
	Did I say anything against using matlab? If I'd wanted particular techniques and languages, I'd have asked for particular techniques and languages. Mostly this test is about whether you can tell a computer to do arbitrary tasks without getting stuck on the minutiae of syntax. (Reply to this) (Parent)(Thread)

(no subject) -

anaraug, 2007-04-04 02:37 am UTC

(no subject) -

dojothemouse, 2007-04-04 12:38 am UTC

(no subject) -

grahams, 2007-04-04 03:40 am UTC

	markgritter 2007-04-04 12:39 am UTC (link)
	Hmm... the problem is that I spent more than a few minutes trying to figure out whether I believed that such a number existed or not, so I blew my budget without writing any code. :) (Reply to this) (Thread)

	bramcohen 2007-04-04 06:43 pm UTC (link)
	That's the joke. You won't get anywhere trying to prove it, and neither has any mathematician in history. It isn't hard to figure out at what point the 'probability' of there being an answer greater than what you've checked up to is insignificant though. (Reply to this) (Parent)

zaitcev
2007-04-04 01:18 am UTC (link)

Since I don't have a chance to get hired into Bram's shop anyway, I may as well admit that I'm failing this test (first among all commenters, as far as I can tell). I just cannot believe that if I found a number N which satisfied the criteria there would not exist a number M which also satisfies the criteria and yet larger than N. If the task were to find the smallest of such numbers, then it would be trivial. But finding the largest one makes absolutely no sense to me.

(Reply to this) (Thread)

Ditto.

phuff
2007-04-04 02:18 am UTC (link)

And then, add to the fact that this is Bram Cohen(!!!) doing the interviewing, and my immediate impulse is to give up. If this problem were given to me in a regular interview session, I'd ask the kinds of questions that have been asked here, and hopefully concessions would be made, like "reasonably sure" as you (Bram) put above. But, on the face of it, I'm not surprised that people choke when you give them this problem, even if they might otherwise be capable CS and math people.

(Reply to this) (Parent)(Thread)

(no subject) -

bramcohen, 2007-04-04 06:59 pm UTC

(no subject) -

phuff, 2007-04-04 10:37 pm UTC

(no subject) -

bramcohen, 2007-04-04 06:59 pm UTC

	misterajc 2007-04-04 01:40 am UTC (link)
	Anyone who claims to have the right answer to that after a few minutes programming has no business graduating with a math degree. I think your question may be selecting against some people you might be interested in hiring. (Reply to this) (Thread)

bramcohen
2007-04-04 08:53 pm UTC (link)

I would hope that anyone with a math degree would have some familiarity with the collatz conjecture and know that this sort of problem doesn't lend itself to formal analysis.

That said, apparently stating 'don't bother trying to prove your answer, just put together some code' might help when doing this sort of challenge posting, given the feedback of a few commenters here.

(Reply to this) (Parent)

robbat2
2007-04-04 02:09 am UTC (link)

The wording of your challenge leaves an additional problem. You want the largest power of two (and thus the largest exponent), so people could concievably be working it out still. If you'd asked for the smallest power of two that did contain 000 in base 7, it would have been dead simple.

For the scope of all exponents - E
you want the largest power of two - N
the base 7 representation of N - B
where B does not contain 3 zeros in a row

for exp = infinity downto 1 {
num = 2^exp;
str = dec2base(num,7);
ind = index(str,"000");
if(ind < 0) {
printf("exp=%d num=%d base7=%s\n",exp,num,str);
return e;
} }

This requires large amounts of processing to achieve an answer in a reasonable time, because there are no short-circuit tricks in converting successive powers of two into base7 that I'm aware of.

I have a large 4 digit exponent that solves the problem thus far (the exponent is prime as well, but there is no pattern to it). I'll email the exponent directly.

(Reply to this) (Thread)

me too

ianbicking
2007-04-04 03:00 am UTC (link)

The question as phrased just isn't a CS problem, it's a math problem. I can code up a search, but the only way I really know that I have the right answer is to assume that Bram was writing up a CS question (and not a math question) and thus it's feasible to do some kind of search, thus the highest number isn't too terribly high. So now that I've searched a couple-thousand non-matching numbers I guess the number I have is right (probably the same one you got).

But then it's one of those look-into-the-mind-of-the-questioner questions that we should all hate from school. (Did you ever do a true/false test, and then realize that 90% of the statements probably weren't intended to be false? I'd have to go back and decide how false a statement had to be before the teacher considered it "false")

(Reply to this) (Parent)(Thread)

Re: me too -

jered, 2007-04-04 09:04 am UTC

	muerte 2007-04-04 04:06 am UTC (link)
	Am I correct in assuming that there is no CORRECT answer? Theoretically you could count to infinity and that would take an infinite amount of time. That said you should post more of these puzzle they keep me entertained. (Reply to this) (Thread)

deviantq
2007-04-04 05:30 am UTC (link)

Clearly the only *CORRECT* way to code this is so that every iteration of the loop takes half the time as the previous one. Duuuuuh. :-P

Seriously, I saw this, saw "few minutes of coding," went "uhhh, you mean a few minutes of proving?" and then saw Bram's assertion that we don't know how to prove anything. If I hadn't seen that assertion, I would have given up, since I would have tried proving it for a while and then (presumably) gotten stuck. Coding was _not_ the first thing that came to mind.

(Reply to this) (Parent)

oh, wait - n is an *integer*

eldereft
2007-04-04 08:28 am UTC (link)

No special relationship among the 2ⁿ₇ springing readily to mind, I shall assert that the digits of said powers in the given basis form a random sequence (infinitely more irrationals, blah,blah,blah). Then, the only case in which this statement is provable other than statistically will be the case of three terminal zeros, which will be preserved by doubling. It remains only to find n & m such that (base ten):

2ⁿ = m*343

(Reply to this) (Thread)

	Re: oh, wait - n is an integer agthorr 2007-04-04 03:15 pm UTC (link)
	2ⁿ = m*343 There are no such integers, n and m. 2ⁿ will never be evenly divisible by 343. (Reply to this) (Parent)(Thread)

Re: oh, wait - n is an *integer* -

eldereft, 2007-04-04 06:22 pm UTC

Re: oh, wait - n is an *integer* -

agthorr, 2007-04-04 06:29 pm UTC

	cousin_it 2007-04-04 09:51 am UTC (link)
	"Anyone who can't get the right answer" should be "anyone who can't guess the right answer". I tried to think up a proof that the right answer even exists, and couldn't do this in a few minutes. I graduated with a math degree, work as a programmer. (Reply to this) (Thread)

	bramcohen 2007-04-04 08:47 pm UTC (link)
	You won't be able to prove the right answer. It's like the collatz conjecture - obviously true, but out of the scope of currently known mathematical tools. But checking up to a large enough number that the chances of there being a bigger one are miniscule is fairly easy. (Reply to this) (Parent)(Thread)

Possible framework for a proof -

benrogers, 2007-05-22 12:53 am UTC

11011110
2007-04-04 05:08 pm UTC (link)

They're an effective filter

It looks like in this case you're trying to filter the engineers from the mathematicians. That is, to play Devil's advocate a little, it seems you prefer to hire people who will just hack something out instead of thinking it through clearly first, because this is a problem where the first approach gets somewhere and the second approach doesn't. What I was hoping for as a result of the "few minutes of coding" was to generate enough data to see a pattern leading to a mathematical proof, but sadly, no.

(Reply to this) (Thread)

	bramcohen 2007-04-04 08:49 pm UTC (link)
	This is a test of ability to do some rudimentary coding and not a test of sophisticated mathematical knowledge, by design. (Reply to this) (Parent)(Thread)

(no subject) -

11011110, 2007-04-04 10:07 pm UTC

(no subject) -

bramcohen, 2007-04-05 12:06 am UTC

not really a psychological blockage -

brian_jaress, 2007-04-07 10:07 pm UTC

	Do you got more challenges? tuxeed 2007-04-05 06:20 pm UTC (link)
	Hello Could you give more challenges like this one? I've got a really boring job. It helps time-passing easily :) Thx a lot for your help. (Reply to this)

gareth_rees
2007-04-19 03:45 pm UTC (link)

A very nice problem, thank you.

However, I think you're being a tiny bit unfair in one or two of your comments here. Writing the program to compute the answer is easy, the work of a minute or two if you have arbitrary-precision arithmetic to hand (e.g., there's a one-line implementation using standard Unix command-line tools). What's not so easy is being confident that (a) there is an answer at all, and (b) that you've looked hard enough to have found it. Both those analyses are definitely part of what I think it means to produce a satisfactory answer to the problem.

Having said that, plenty of computer science graduates ought to be able to make a decent attempt at (a) and (b), since the necessary techniques are taught in discrete math courses.

(Reply to this) (Thread)

cartesiandaemon
2007-04-22 04:46 pm UTC (link)

I followed you here from your journal. I'd agree with what you said -- as a mathematician, my assumption was that the largest means the largest, not "the largest (with a very high degree of certainty)".

I infer knowing (or maybe deducing) the assumptions you made is part of what the question looks for, though maybe bramcohen should tell me if so. (I assume from there I could cobble together the algorithm trivially, though I admit I didn't try.)

(Reply to this) (Parent)

Challenge

terrycojones
2007-05-11 11:37 pm UTC (link)

Hi Bram Unless your point is to see how well people can write a loop, or how they think when they're coding, or whether they can multiply a string representing a base 7 natural number, or convert decimal to base 7, I think your comment: > I think anyone who can't get the right answer to that problem with a few minutes of coding has no business being allowed to graduate from a CS program, and yet I still get wrong answers. Is pretty much the opposite of what I'd be looking for. I'd rather someone who reasoned as follows: The obvious place for there to be 3 zeroes is at the end, i.e., a number that is a multiple of 7^3=343. But no power of 2 can ever be a multiple of 343 (clear from prime factorization). So can there be some fixed location within a base 7 representation that stays with 3 zeroes. No, because the less significant digits would increase in size to overwrite that region. So it looks like there might be a probabilistic approach in which one could argue that beyond exponent E the probability of not having 3 zeroes is at most P. But that's not _the_ answer. To get _the_ answer, it seems like one would have to come up with a smarter mathematical argument that there is some invariant which causes a set of 3 zeroes to recur. That approach might work. But to simply start writing code and stop your program at some point because you figure that's probably it.... well, that's like trying to decide if a Turing Machine doesn't halt by just running it for a while. So clearly we shouldn't be writing code. I.e., my peculiar craziness would tell me NOT to hire anyone who started writing code. Is that a spoiler? FWIW, I've been coding for 30 years, have a PhD in CS, and consider myself a pretty capable programmer. I've also done some math. I can't solve your problem by writing code for "a few minutes", so you may be setting the bar a little high :-) But maybe you're just looking for evidence that people can think for themselves, despite the presence of an intimidating interviewer insisting that they should be able to solve the problem with a few minutes' coding.

(Reply to this)

Probability?

seanferris
2007-06-27 10:33 am UTC (link)

Isn't this a problem of probability? An algorithm to calculate the exponential and convert it base 7 can be performed in matlab, c++ or scripted etc... And the problem is really how many iterations are required to know you've sampled a significant amount of high powers. Knowing very little about probability theory I search on good old google and found the following solution:

http://gareth-rees.livejournal.com/5982.html - very good explanations

So it took me about 5 minutes to get a reasonably good answer and then just plugged the algorithm into cygwin.

(Reply to this)

Username:		Create an Account Forgot your login or password? Login w/ OpenID
Password:
	Remember Me
	English • Español • Deutsch • Русский…

About

Help

Get Involved

Legal

Store

LJ Labs