Two Interview Questions

February 18, 2014

It’s been a while since we had any interview questions. We have two today, since they are so simple:

1) Given a number n, find the smallest 3-digit number such that the product of its digits is equal to n. For example, given n = 100, the solution is 455.

2) Given two arrays, one with n items and one with n+2 items including the same items as the array with n items plus two additional items, find the two additional items. Assume none of the items are duplicates.

Your task is to write solutions to the two interview questions given 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 “Two Interview Questions”

  1. Jamie Hope said

    Alternatively for Task 1: If n is 0, then the answer must be 100; otherwise, no digit is zero and the digits are sorted with the smallest in the hundreds place and largest in the ones place. So, for each place we can start dividing from 9 down to 1 and keep the first that yields an integer quotient.

    For the general case where we want to find a number with num-digits digits:

    (define (task1c n num-digits)
      (if (= 0 n) (expt 10 (- num-digits 1))
          (let loop ((n n) (p 0) (d 9) (ds '()))
            (cond ((= p (- num-digits 1))
                   (and (< n 10) (undigits (cons n ds))))
                  ((integer? (/ n d))
                   (loop (/ n d) (+ p 1) 9 (cons d ds)))
                  (else (loop n p (- d 1) ds))))))
    

    That uses undigits from the standard prelude.

  2. Jamie Hope said

    Actually line 2 should look like “(if (= 0 n) (if (= 1 num-digits) 0 (expt 10 (- num-digits 1)))” but there ought to be other bounds checking there as well to make sure that n >= 0 and num-digits >= 1.

  3. Jussi Piitulainen said

    Objection to assuming in task 2 that the items are numbers, hashable, or comparable other than for equality. A mildly usable piece of information seems to be that there are two items to find. I don’t see what to do with the information that there are no duplicates – maybe the assurance that one cannot find the same item twice? (Probably it’s good to talk about sorting and hashing in an interview, but it should also be good to notice that these are not applicable to all kinds of items.)

    I’m actually a bit confused about the equality of procedures in Scheme. The following might be allowed to fail but it happened to work when I tested it. A realistic variant would be testing mutable pairs for identity.

    (define A (list cons car cdr))
    (define B (list cons append car cdr reverse))
    (define (find-two big small)
      (if (memv (car big) small)
          (find-two (cdr big) small)
          (values (car big) (find-one (cdr big) small))))
    (define (find-one big small)
      (if (memv (car big) small)
          (find-one (cdr big) small)
          (car big)))

    (call-with-values
        (lambda ()
          (find-two B A))
      (lambda (f g)
        (write (f (g '(r a t)) '(r a t)))
        (newline)))

  4. The solution of the second task in Python is trivial:

    >>> a = [2, 5, 7, 4, 1, 10, 15]
    >>> b = [2, 5, 7, 11, 4, 1, 3, 10, 15]
    >>> set(b) - set(a)
    {3, 11}
    
  5. Paul said

    Interview Task 1 in Python. setdefault(x) only has effect on the dict, if there is not a key x yet. Therefore, the a, b and c loop from low to high.

    from itertools import product
    
    class Interview1(object):
        def __init__(self):
            self.db = db = {}
            for a, b, c in product(range(1,10), range(10), range(10)):
                db.setdefault(a * b * c, 100 * a + 10 * b + c)
                
        def __call__(self, n):
            return self.db.get(n, False)
    
    interview1 = Interview1()
    
    print interview1(100) # --> 455
    
  6. Do not understand the problem, you have to avoid the false? To do a get() ?

  7. vibhu said

    #include
    #include
    void main()
    {
    int a,b,c=1,mul,flag=0;
    clrscr();
    printf(“enter the number”);
    scanf(“%d”,&a);

    for(int i=100;i<999;i++)
    {
    b=i;
    mul=1;
    while(b!=0)
    {
    c=b%10;
    b=b/10;
    mul=mul*c;
    }
    if(mul==a)
    {
    printf("%d",i);
    flag=1;
    break;
    }
    }

    if(flag==0)
    printf("the no not found");

    getch();
    }

  8. wiltonsilva said


    ;; 1) Given a number n, find the smallest 3-digit number such that
    ;; the product of its digits is equal to n. For example, given n = 100,
    ;; the solution is 455.

    (defn decompose [n]
    (let [u (mod n 10)
    d (/ (- (mod n 100) (mod n 10)) 10)
    c (/ (- (mod n 1000) (mod n 100)) 100)]
    (list c d u)))

    (defn prod [n]
    (loop [i 0]
    (if (= n (reduce * (decompose i))) i
    (recur (inc i)))))

    ;; 2) Given two arrays, one with n items and one with n+2 items including
    ;; the same items as the array with n items plus two additional items, find
    ;; the two additional items. Assume none of the items are duplicates.

    (defn diff-sets [s1 s2]
    (clojure.set/difference (set s2) (set s1)))

  9. idan said

    {code}
    Array_one=[1,2,3,4]
    Array_two=[5,4,3,2,1,8]
    Farray=[]
    for i in Array_two:
    if i not in Array_one:
    Farray.append(i)
    print (Farray)
    {code}

  10. Graham said

    Late to the party, but here’s a Haskell version. I went for simplicity over speed.

    import Data.Set (difference, fromList, toList)

    — problem 1
    search :: Int -> Maybe Int
    search n = head’ [k | k <- [100..999], n == (product . digits $ k)]
    where
    head’ ks = if null ks then Nothing else Just $ head ks
    digits 0 = [] — a lie, but OK here
    digits k = let (q, r) = k `divMod` 10 in r : digits q

    — problem 2
    find2Extra :: [a] -> [a] -> (a, a)
    find2Extra xs ys = (head d, head . tail $ d)
    where
    d = toList $ fromList ys `difference` fromList xs

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 634 other followers

%d bloggers like this: