## 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 ton. For example, givenn= 100, the solution is 455.

2) Given two arrays, one with

nitems and one withn+2 items including the same items as the array withnitems 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.

Pages: 1 2

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:

That uses undigits from the standard prelude.

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.

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

The solution of the second task in Python is trivial:

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.

Do not understand the problem, you have to avoid the false? To do a get() ?

#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();

}

;; 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)))

{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}

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