?

Log in

No account? Create an account

Tue, Apr. 3rd, 2007, 03:25 pm
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.

Tue, Apr. 3rd, 2007 11:20 pm (UTC)
dojothemouse

So, you're trying to figure out who can configure a batch mailer to send you enough guesses?

Wed, Apr. 4th, 2007 12:12 am (UTC)
bramcohen

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.

Tue, Apr. 3rd, 2007 11:27 pm (UTC)
loic

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.

Wed, Apr. 4th, 2007 12:16 am (UTC)
bramcohen

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.
(Deleted comment)

Tue, Apr. 3rd, 2007 11:57 pm (UTC)
kemayo

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?

Wed, Apr. 4th, 2007 12:10 am (UTC)
matt_havener

I did this ... luckily the real solution was within +-1 of my incorrect answer

Wed, Apr. 4th, 2007 12:02 am (UTC)
suppressingfire

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.

Wed, Apr. 4th, 2007 12:19 am (UTC)
bramcohen

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.

Wed, Apr. 4th, 2007 12:20 am (UTC)
houdini_cs

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

Wed, Apr. 4th, 2007 12:22 am (UTC)
bramcohen

Correct. I was intentionally avoiding mathy notation to give people with hacker backgrounds a fair chance.
(Deleted comment)

Wed, Apr. 4th, 2007 12:35 am (UTC)
bramcohen

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.

Wed, Apr. 4th, 2007 12:39 am (UTC)
markgritter

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


Wed, Apr. 4th, 2007 06:43 pm (UTC)
bramcohen

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.

Wed, Apr. 4th, 2007 01:18 am (UTC)
zaitcev

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.
(Deleted comment)

Wed, Apr. 4th, 2007 01:40 am (UTC)
misterajc

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.

Wed, Apr. 4th, 2007 08:53 pm (UTC)
bramcohen

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.

Wed, Apr. 4th, 2007 02:09 am (UTC)
robbat2

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.

Wed, Apr. 4th, 2007 03:00 am (UTC)
ianbicking: me too

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

Wed, Apr. 4th, 2007 04:06 am (UTC)
muerte

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.

Wed, Apr. 4th, 2007 05:30 am (UTC)
deviantq

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.

Wed, Apr. 4th, 2007 08:28 am (UTC)
eldereft: oh, wait - n is an *integer*

No special relationship among the 2n7 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):

2n = m*343
(Deleted comment)

Wed, Apr. 4th, 2007 09:51 am (UTC)
cousin_it

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

Wed, Apr. 4th, 2007 08:47 pm (UTC)
bramcohen

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.
(Deleted comment)

Wed, Apr. 4th, 2007 08:49 pm (UTC)
bramcohen

This is a test of ability to do some rudimentary coding and not a test of sophisticated mathematical knowledge, by design.

Thu, Apr. 5th, 2007 06:20 pm (UTC)
tuxeed: Do you got more challenges?

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.