Interview – GURUnH

The most important job is recruiting.

Yes, it’s totally true. I have spent about a quarter of my time for finding the good guys and got both success and failure in seeing how good a candidate is. Then I have tried to create a question and used it for a year in all my interviews with candidates of developer position.

The interview question is:

Writing continuously the non-negative numbers by skipping the number which is built by only one digit (11, 22, 33… 111, 222, …), we have a sequence:

0123456789101213…19202123…

You can see the 10^th digit is 1. So let’s say 10^th 1. Compute:

10^th + 100^th + 1.000^th + …

My question is “What is your approach to solve this problem? Don’t need to give the final result”.

It’s so easy? Not sure – as it’s a kind of a problem that its hard increases fast by the data limitation. Could you find 100^th? 1000^th? 100.000.000.000^th? Yes, it’s much more different.

OK, let see some solutions that are described below:

Solution 1: Natural thinking

It seems we can build up and store this digit sequence in a string. And it’s so easy to get the digit by the index then. The code should be

StringBuilder sequence = new StringBuilder();
for (int number = 0; number < 1000; number++) {
    if (!BuiltByOneDigit(number)) {
        sequence = sequence.Append(number.ToString());
    }
}

int result = (int)sequence[1] + (int)sequence[10] + (int)sequence[100] + (int)sequence[1000];

StringBuilder sequence = new StringBuilder();

for (int number = 0; number < 1000; number++) {

if (!BuiltByOneDigit(number)) {

sequence = sequence.Append(number.ToString());

}

int result = (int)sequence[1] + (int)sequence[10] + (int)sequence[100] + (int)sequence[1000];

But how about the 100.000.000.000^th?

Solution 2: Optimisation

We can consider to stop the loop as soon as possible. For example, to generate a string with length 100.000.000.000, the maximum value of number in the loop should be less than 10.000.000.000 (why? could it be a smaller number?).

But it’s still too large. How many memory it takes to store 10.000.000.000 characters? 10.000.000.000 bytes > 9GB. But wait, why do we need to store whole the string? How many meaning digit? They are just 10^th, 100^th, 1.000^th.. digits. So just count to get the meaning digit and skip storing others. The code should look like

long length = 0;
long index = 1;
int result = 0;
for (int number = 0; number < 1000000000; number++) {
    if (!BuiltByOneDigit(number)) {
        string numberInString = number.ToString();
        if (length + numberInString.Length > index) {
            result += (int)numberInString[index - length];
            index *= 10;
        }
        length += numberInString.Length;
    }
}

// output: result

long length = 0;

long index = 1;

int result = 0;

for (int number = 0; number < 1000000000; number++) {

if (!BuiltByOneDigit(number)) {

string numberInString = number.ToString();

if (length + numberInString.Length > index) {

result += (int)numberInString[index - length];

index *= 10;

}

length += numberInString.Length;

}

// output: result

This way can reduce the memory use to constant and nearly 0. But 10.000.000.000 seems too big for reaching in loop.

Solution 3: Math approach

Let’s see another approach by math

How many digits do we have by writing a sequence from 0 to 9? 10
How many digits do we have by writing a sequence from 10 to 99? 162 = (99 – 10 + 1 – 9) * 2. Skipping 9 numbers: 11, 22, …
How many digits do we have by writing a sequence from 100 to 999? 2673 = (999 – 100 + 1 – 9) * 3. Skipping 9 numbers: 111, 222, …
…

OK, so what 4.321^th digit? 4321 – 10 – 162 – 2673 = 1476 > 0, this digit belongs to a number that falls in (1.000, 9.999) which has 4 digits. So its index from 1.000 = 1476 / 4 = 369. Then the finding digit should be 1 (in 1.369).

It’s not much easy but not difficult to implement in code and the process time is constant now.

It’s just a problem itself but how people approach or solve it can tell much about them.

After about one hundred interviews, I had a lot of data and categorise the candidates by the common feedback questions:

I cannot understand this question. I get no information because some of developers are super in building software by tools but have never faced this kind of problem. Just explain or give them another question.
I cannot solve this. Say goodbye to him, at least easy giving up is not my style or he should give me #1 feedback.
I think there is a rule here. 10^th is 1 so I guess 100^th, 1.000^th, 10.000^th.. are 1 as well. Life is not easy man. The interview question is for testing the logical not tricky thought.
What is its input? How to input data, from console? Why 10th is 1, it is 9?… I usually don’t waste my time for answering these questions. He just focuses on the minor things to forget real problem.
We can generate this string and get the digit by index after that. Yes, it’s the first solution, right? He looks like a normal developer. I usually go ahead with him by some questions depending on how he structure the program. “How many functions or methods you have?”, “How do we check a number that is built by 1 digit?” etc. And of course, some suggestion to optimise the solution, “What should you choose, optimise memory or speed?”, “How many meaning digits we have?” etc, and the story begins.
Ah yes, we should not maintain the whole string, we can remove the unnescessary parts. Sure, the second solution. He seems a good developer.
Yeah, we remove 9 numbers in 2-digit numbers that equals to 18 digits. We also remove 9 numbers in 3-digit numbers that equals to 27 digits. And the actual position of 1.0000 should be minused… He is a must-have guy at least in the talent aspect.

It just a common test for his IQ, but the specific code should shows his knowledge and skills in a specific language or platform. For example, good C# developer should use StringBuilder to build the sequence instead of using string. C++ developer should check the number that is built by 1 digit by operations instead of by converting it to string. Putting the condition like if (sequence.Length > 10.000.000.000) in the loop is not the good way in code in any language.

The guy who can show off the solution 3 in the first time – he is really intelligent or he has solved a thousand problems like that, maybe a code challenger, also a right man we would hire.

The guy who cannot pose the best solution at the first time but can come to the solution 3 after the advises has potential to become a great developer.

The guy who cannot come to the optimised solution after the advises just be a normal developer – not a smart guy. I have never hired him even though he has a lot of experience or certificated.

In my opinion, Java, .NET or what common technologies is so easy for a talent guy learns in a short time but technology-master cannot go far with a week algorithm coding background.

So far, I think it’s a good question to see the developer’s IQ that I used in a long time. Now I’m creating another :).

905 total views, no views today

GURUnH

Guru's notes

Tag: Interview

My interview question