## Three Interview Questions

### May 13, 2014

The first question (insert new node 40 in sorted linked list, given node 50) is a trick question. No, it is not possible to insert the node. You need a pointer to node 30 to perform the insertion, but there is no way to get a pointer to node 30 given only a pointer to node 50. This is a simple question to ensure the candidate understands linked lists.

The second question (subtract a linked list end to end) is tedious, but not hard. We use the tortoise-and-hare algorithm to find the middle:

`(define (subtract-first-half xs)`

(let loop ((front xs) (back (reverse xs)) (hare xs) (out (list)))

(if (or (null? hare) (null? (cdr hare)))

(append (reverse out) front)

(loop (cdr front) (cdr back) (cddr front)

(cons (- (car front) (car back)) out)))))

`> (subtract-first-half '(5 4 3 2 1))`

(4 2 0 2 1)

> (subtract-first-half '(4 3 2 1))

(3 1 2 1)

Another good question; the tortoise-and-hare algorithm should be familiar to all competent programmers.

The third question (number of trailing zeros in a factorial) is easy if you know the math and impossible if you don’t. We write numbers base 10, so there are as many trailing zeros as there are factors of 10 in the factorial of *n*, and since 10 = 2 * 5 and there are more factors of 2 than of 5 in any factorial, the number of trailing zeros will be the number of factors of 5. To find that, for each power of 5 up *n* add the number of times it divides *n*. For instance, if *n* = 487, there are ⌊487/5⌋ = 97 factors of 5, ⌊487/25⌋ = 19 factors of 5^{2}, and ⌊487/125⌋ = 3 factors of 5^{3}.

`(define (trailing-zeros n)`

(let loop ((k 5) (z 0))

(if (< n k) z

(loop (* k 5) (+ z (quotient n k))))))

`> (trailing-zeros 487)`

119

I don’t like this interview question. If you know the math, or if you have studied a book of programming interview questions, it’s easy; you can write the program as fast as you can type. If you don’t know the math, you will flail about looking for a solution, getting more and more nervous as time passes. In either case, the interviewer will learn nothing about your programming skills.

You can run the program at http://programmingpraxis.codepad.org/G17lhMD3.

The first can be a double trick question… it depends on if the nodes are modifiable. If so, you change the value in 50 to 40, and insert a new 40 node.

I mean, a new 50 node.

Ceci n’est pas une Python.

Traditional Lisp exercises. Much fun.

The above and the below produce the expected results in this form:

Test result 1: (10, (30, (40, (50, (70, ())))))

Test result 2: (4, (2, (0, (2, (1, ())))))

Oops. Yes, I did miss an initial condition in the first question.

This is correct, as long as the list is is originally in the ascending

order, and the node given to insert-at-node is effectively the node

containing the smallest item greater than the new data.

For any n>=2, in the decomposition in prime factors of n!, the

exponent of 2 is greater than the exponent of 5,

since (log n 2)/(log n 5) = (log 5 2) ~= 2.321928 > 1

Since only the multiples of an exponent of 10 will add a 0 to the

factorial, and there are more multiples of 2 than multiples of 5, we

can just sum the exponents of 5 factor by factor.

For the last problem, we can just repeatedly divide by 5 and add:

And for the second problem, a little Haskell function:

@informatimago –

Your factorial algorithm was interesting – building on top of it- if we just divide n by 5 – that seems to work although I did not test for very large numbers…

factorial(4) – will have 0 zeros (4/5)

factorial(10) – will have 2 zeros (10/5)

factorial(24) – will have 4 zeros (24/5)

factorial(25) – will have 5 zeros (25/5) and so on…

For number 3, counting factors in each iteration of a factorial is asymptotically less efficient than counting representation of progressively larger powers of the factor in n. Implemented in Python the faster solution looks as follows:

Even at small n, the difference in growth is significant:

(n was randomly chosen across range [1,10240], 1000 samples for each n were taken and averaged.)

n: Faster (s) Slower (s)

538: 3.74e-07 8.91e-05

1418: 4.32e-07 2.34e-04

3915: 4.85e-07 6.43e-04

4071: 4.86e-07 6.72e-04

6333: 4.85e-07 1.04e-03

6364: 4.85e-07 1.05e-03

8262: 5.03e-07 1.36e-03

8970: 5.00e-07 1.48e-03

9401: 4.99e-07 1.55e-03

9497: 5.01e-07 1.57e-03

After n=10240, the slower algorithm becomes unwieldy, while the faster method still runs in under 4e-04 seconds with n above 480 digits.

Vivek is correct. For the second problem, all we have to do is divide by 5. The reasoning is that the prime factors of 10 are 2 and 5. For n!, every 5th value of n will give us a factor of 5. Every second value of n will give us a factor of 2, so we’ll have plenty of factors of 2 (i.e. in the prime factorization of n!, we’ll always have at least as many factors of 2 as we do factors of 5). So every 5th value of n!, we’ll add another 0 to the end of the number.