February 18, 2014 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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.
By Jamie Hope on February 18, 2014 at 3:36 PM
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.
By Jamie Hope on February 18, 2014 at 3:42 PM
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)))
By Jussi Piitulainen on February 18, 2014 at 8:05 PM
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}By Ivan Ivanov on February 19, 2014 at 10:14 AM
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) # --> 455By Paul on February 20, 2014 at 12:53 PM
Do not understand the problem, you have to avoid the false? To do a get() ?
By Luis Uranga on February 22, 2014 at 9:52 PM
#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();
}
By vibhu on February 23, 2014 at 7:14 PM
;; 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)))
By wiltonsilva on February 24, 2014 at 6:52 PM
By coldgrnd on February 28, 2014 at 11:33 AM
{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}
By idan on March 2, 2014 at 8:46 PM
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 xsBy Graham on March 5, 2014 at 2:54 AM
Reblogged this on Computer geek.
By miguelpinia on June 17, 2016 at 3:43 AM