Hacker News Reader

Comment by orijing | Hacker News Reader

From the link:

What is the next line in the following sequence: 1 11 21 Answer: it's 1211 and the next is 111221

Why would 31 and 41 be illogical answers? I understand where 1211 comes from, but 31 and 41 are totally logical IMO. It's a linear function that goes up by 10.

View on HN

All problems of the form "Provide the next number of this sequence" are attempts to demonstrate that you think, or are capable of thinking, in a fashion similar to the way the decisionmaker thinks. 31 is a totally reasonable answer to that question, mathematically. So is pi. So is "zebra". (The question was "Provide the traditional lexicographic sorting in English of the elements zebra, one, twenty one, and eleven, except o comes before e.")

The reason that 31 is not a good answer in terms of securing a job is because your decisionmaker prides himself on being intelligent and he does not see arithmetic sequences as being sufficiently impressive. The reason pi is not a good answer is, despite there being uncountably many mathematical phenomena for which {1, 11, 21, pi} are correct answers, it is insufficiently elegant/tricky for what he has in mind.

I agree about 31 but not necessarily about zebra or pi. A reasonably meaningful metric is compressibility of the sequence, or how short code could produce it. Although that just opens a different can of worms, it could be argued that 31,41 is better solution than the one given in answer in OP which is better than pi or zebra.

That is begging the question -- it moves the "I am totally winging this because it makes me feel superior" from the "prefer 'elegant' answers" to "prefer 'elegant' languages for writing compressed descriptions of problems".

A rigorous program expressing the sequences to which "pi" and "zebra" are the next answers takes only 0 bits and 1 bits respectively to compress in Patio11, a pedantic language created purely for the purpose of this post. It is far more rigorous than either English or C-style pseudocode, has a well-defined grammar, and could have an interpreter written in any common programming language that would fit on the side of a business card.

I stick with the original contention: any problem of this nature is about either identifying birds of a feather or lording one's intellectual superiority over the candidate.

The problem arises when you are asked to provide further (possibly infinite nr) elements of the sequence: the first would still compress nicely as

"a(i)=i*10+1."

yours would be "a(3)=pi, a(4)=zebra, a(5)=cheetah, a(6)=akrcqfztaf a(7)=666" etc.

But I agree, if the question is just "what is the next element?" and so far only 3 are given, your answer is as good as anything else.

the decisionmaker is not bright but vain. Intelligent would be to test if applicants understand the concept of a function that creates a sequence.

A general "solution" to these kinds of sequences, if the sequences are mathematically related, is the method of common differences (e.g. http://www.purplemath.com/modules/nextnumb.htm). It would give 31 in this case, but it works for many other straightforward sequence-type problems. The basic idea is you calculate the difference between every two adjacent numbers to create a new sequence, then do the same for that; often the pattern becomes very clear then.

Ironically, the "problem" at hand appears to have come straight from that tutorial:

http://www.purplemath.com/modules/nextnumb7.htm

> Find the next number in the following sequence: 1, 11, 21, 1211, 111221,....

> This looks like a "math" sequence, but it isn't really. Instead, each term is a description of the preceding term. The first term is just one "1": 11. The second term is two "1's": 21. And so forth:

    one 1: 11
    two 1's: 21
    one 2 and one 1: 1211
    one 1, one 2, and two 1's: 111221
    three 1's, two 2's, and one 1: 312211

    So the next term is "312211".

This sequence, by the way, is called the look-and-say sequence. If you like it, you might be interested in this blog post on the length of the terms:

http://www.nathanieljohnston.com/2010/10/a-derivation-of-con...

Because the page gave it wrong. It should be 1 11 21 1211 111221 before you're asked to give more terms.

And seeing this question is a sign that the interviewer is trying to feel smarter than you.

It's a Look-and-say sequence. http://en.wikipedia.org/wiki/Look-and-say_sequence

An absurd question that reveals little about a person's programming ability. I would change the question entirely:

On a Cartesian grid is drawn a solid logo (e.g., show a picture of the Batman logo from the 1989 film), where each square represents a black or white pixel. How would you represent the image if you had to type the data points by hand for the computer to draw?

Both questions elude to run-length encoding.

To elude encoding, run length. To allude to run-length encoding, zip.

Probably for no reason other than it's too easy. Generally these questions seem to not be oriented around "seeing how you think" as much as they are about seeing if you come to the conclusion the interviewer wants you to come to.

—There is a standard library function for that…

—Nah, too easy. I'll implement my own.

I didn't say doing interviews this way was a good idea, did I?

Reply on news.ycombinator.com