Two Interview Questions
February 18, 2014
The simplest solution for the first question uses three nested loops, computing the product and returning the first one that equals n; we use call-with-current-continuation to write imperative loops with an early return, and return #f if there is no solution:
(define (task1a n)
(call-with-current-continuation
(lambda (return)
(do ((i 1 (+ i 1))) ((= i 10) #f)
(do ((j 1 (+ j 1))) ((= j 10))
(do ((k 1 (+ k 1))) ((= k 10))
(if (= (* i j k) n)
(return (+ (* 100 i) (* 10 j) k)))))))))
> (task1a 100)
455
> (task1a 20)
145
> (task1a 476)
#f
That works fine if you only want to answer the question once. But if you will be asked the question repeatedly, it pays to compute and store all possible solutions; we work from largest to smallest so that smaller solutions will overwrite larger solutions:
(define task1b
(let ((xs (make-vector 1000 #f)))
(do ((i 9 (- i 1))) ((zero? i))
(do ((j 9 (- j 1))) ((zero? j))
(do ((k 9 (- k 1))) ((zero? k))
(vector-set! xs (* i j k) (+ (* 100 i) (* 10 j) k)))))
(lambda (n) (vector-ref xs n))))
> (task1b 100)
455
> (task1b 20)
145
> (task1b 476)
#f
The simplest solution for the second question sorts both arrays then scans them, returning the two mis-matches; we use lists instead of arrays, but the same principle applies:
(define (task2a lt? xs ys)
(let loop ((xs (sort lt? xs)) (ys (sort lt? ys)) (zs (list)))
(cond ((or (null? xs) (null? ys)) zs)
((lt? (car xs) (car ys)) (loop (cdr xs) ys (cons (car xs) zs)))
((lt? (car ys) (car xs)) (loop xs (cdr ys) (cons (car ys) zs)))
(else (loop (cdr xs) (cdr ys) zs)))))
> (task2a < '(4 7 9 6 1 3 8) '(3 4 1 8 2 9 5 7 6))
(5 2)
That takes time O(n log n). An O(n) solution inserts the items of the smaller array into a set, then looks up each element of the larger array and reports those not in the set; we assume a set implementation based on a hash table that admits constant-time access:
(define (task2b smaller larger)
(let loop ((smaller smaller) (s (make-hash)))
(if (pair? smaller)
(loop (cdr smaller) (s 'insert (car smaller) #t))
(let loop ((larger larger) (zs (list)))
(if (null? larger) zs
(if (null? (s 'lookup (car larger)))
(loop (cdr larger) (cons (car larger) zs))
(loop (cdr larger) zs)))))))
> (task2b '(4 7 9 6 1 3 8) '(3 4 1 8 2 9 5 7 6))
(5 2)
If you’re mathematically inclined, you will have noticed a third solution for the case where all the items are positive integers. Say that x and y are the two missing integers, with array A longer than array B. Then x + y = sum(A) − sum(B) and x · y = prod(A) / prod(B), and (x + y) ^ 2 = x ^ 2 + 2 x y + y ^ 2. Therefore, compute the difference of the sums of the two arrays, compute the quotient of the products of the two arrays, and solve for x and y:
(define (task2c smaller larger)
(let loop ((s 0) (p 1) (smaller smaller) (larger larger))
(if (pair? larger)
(if (pair? smaller)
(loop (+ s (car larger) (- (car smaller)))
(* p (car larger) (/ (car smaller)))
(cdr smaller) (cdr larger))
(loop (+ s (car larger)) (* p (car larger)) smaller (cdr larger)))
(let ((z (- (* s s) (* 2 p))))
(let loop ((x 1) (y (isqrt z)))
(let ((m (+ (* x x) (* y y))))
(cond ((< m z) (loop (+ x 1) y))
((< z m) (loop x (- y 1)))
(else (list x y)))))))))
> (task2c '(4 7 9 6 1 3 8) '(3 4 1 8 2 9 5 7 6))
(2 5)
The third algorithm is also O(n). Note that we built the difference of sums and quotient of products incrementally, to avoid large intermediate results, and solved for x and y iteratively, incrementing x from 1 and decrementing y from √z.
You can run the program at http://programmingpraxis.codepad.org/INTjkRBZ.
Programming Praxis 
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.
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:
>>> a = [2, 5, 7, 4, 1, 10, 15] >>> b = [2, 5, 7, 11, 4, 1, 3, 10, 15] >>> set(b) - set(a) {3, 11}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) # --> 455Do 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 xsReblogged this on Computer geek.