Three Interview Questions

May 13, 2014

One of the sites that I watch from time to time is Career Cup, which publishes coding questions that have been asked in actual job interviews. These questions came through this morning:

1) Consider a sorted singly-linked list having the following nodes: 10 -> 30 -> 50 -> 70 -> NULL. You are given a pointer to node 50 and a new node having the value 40. Can you insert node 40 correctly in the list maintaining the ascending order?

2) Given a linked list 5 -> 4 -> 3 -> 2 -> 1 produce a linked list 4 -> 2 -> 0 -> 2 -> 1 by subtracting the last node of the list from the first, the next-to-last node from the second, and so on, stopping at the midpoint of the list.

3) Write a program to output the number of consecutive trailing zeros in the factorial of a number. For example, if the number is 5, then 5! = 120, and there is one trailing zero.

Your task is to write programs to answer the three interview questions posed above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

11 Responses to “Three Interview Questions”

  1. Fragbay said

    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.

  2. Fragbay said

    I mean, a new 50 node.

  3. Jussi Piitulainen said

    Ceci n’est pas une Python.

    def insert(links, elem):
        '''Insert in ascending order.'''
        return ( (elem, ())
                 if links == ()
                 else (elem, links)
                 if elem < links[0]
                 else (links[0], insert(links[1], elem)) )
    
    print('Test result 1:', insert((10, (30, (50, (70, ())))), 40))
    
  4. Jussi Piitulainen said

    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, ())))))

    def reverse(links, aux = ()):
        return ( aux
                 if links == ()
                 else reverse(links[1], (links[0], aux)) )
    
    def tail(links, meter):
        '''Return the last half-meter of links.'''
        return ( links
                 if meter == () or meter[1] == ()
                 else tail(links[1], meter[1][1]) )
    
    def sub(longer, shorter):
        return ( longer
                 if shorter == ()
                 else (longer[0] - shorter[0], sub(longer[1], shorter[1])) )
    
    def subrevtail(links):
        return sub(links, reverse(tail(links, links)))
    
    print('Test result 2:', subrevtail((5, (4, (3, (2, (1, ())))))))
    
  5. Jussi Piitulainen said

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

  6. informatimago said
    ;; 1) Consider a sorted singly-linked list having the following
    ;; nodes: 10 -> 30 -> 50 -> 70 -> NULL. You are given a pointer to
    ;; node 50 and a new node having the value 40. Can you insert node
    ;; 40 correctly in the list maintaining the ascending order?
    
    
    (defun insert-at-node (node data)
      (setf (cdr node) (cons (car node) (cdr node))
            (car node) data)
      node)
    
    (let ((list (list 10 30 50 70)))
      (insert-at-node (nthcdr 2 list) 40)
      list)
    --> (10 30 40 50 70)
    

    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.

    ;; 2) Given a linked list 5 -> 4 -> 3 -> 2 -> 1 produce a linked
    ;; list 4 -> 2 -> 0 -> 2 -> 1 by subtracting the last node of the
    ;; list from the first, the next-to-last node from the second, and
    ;; so on, stopping at the midpoint of the list.
    
    (defun palinsub (list)
      (loop
        :for slow = list :then (cdr slow)
        :for fast = list :then (cddr fast)
        :while (cdr fast)
        :finally (return (append (mapcar (function -) list (reverse slow))
                                 (if fast
                                     (cdr slow)
                                     slow)))))
    
    (assert (equalp (palinsub '(5 4 3 2 1)) '(4 2 0 2 1)))
    (assert (equalp (palinsub '(5 4 3 2))   '(3 1 3 2)))
    (assert (equalp (palinsub '(3))         '(0)))
    (assert (equalp (palinsub '())          '()))
    
    ;; 3) Write a program to output the number of consecutive trailing
    ;; zeros in the factorial of a number. For example, if the number is
    ;; 5, then 5! = 120, and there is one trailing zero.
    
    (defun count-factors-in-n (n f)
      (if (zerop n)
          0
          (loop
            :with quo
            :with rem
            :do (multiple-value-setq (quo rem) (truncate n f))
                (setq n quo)
            :while (zerop rem)
            :sum 1)))
    
    (defun count-factors-in-factorial-n (n f)
      (loop
        :for i :from 1 :to n :sum (count-factors-in-n i f)))
    
    (progn
      (assert (= (count-factors-in-factorial-n  4 5) 0))
      (assert (= (count-factors-in-factorial-n  5 5) 1))
      (assert (= (count-factors-in-factorial-n  6 5) 1))
      (assert (= (count-factors-in-factorial-n 24 5) 4))
      (assert (= (count-factors-in-factorial-n 25 5) 6))
      (assert (= (count-factors-in-factorial-n 27 5) 6)))
    

    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.

  7. matthew said

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

    fcount 0 k = k
    fcount n k = fcount n' (k+n') where n' = n `div` 5
    
    main =
         print (fcount 487 0) >>
         print (fcount 100 0) >>
         print (fcount 1000 0) >>
         print (fcount 10000 0) >>
         print (fcount 100000 0)
    
    119
    24
    249
    2499
    24999
    
  8. matthew said

    And for the second problem, a little Haskell function:

    f s t [] = s
    f (a:s) (b:t) r = (a-b):f s t (drop 2 r)
    g s = f s (reverse s) s
    
    main = print(g[5,4,3,2,1])
    
  9. Vivek said

    @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…

  10. Lev Lozhkin said

    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:

    def trailing_zeroes(n):
        zs = 0
    
        while n >= 5:
            n //= 5
            zs += n
    
        return zs
    

    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.

  11. Kevin Hall said

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: