Infibeam Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
;;Given an unsorted array and a number a, find a pair of numbers(b,c) from the arraysch that a=b+c.
(defun find-pair (a lst)
(if (null lst)
(format t "Provide list")
(rec-pair a (car lst) (cdr lst) (cdr lst))))
(defun rec-pair (a b lst olst)
;(format t "~A ~A ~A ~A~%" a b lst olst)
(if (null olst)
(format t "done searching!")
(if (null lst)
(rec-pair a (car olst) (cdr olst) (cdr olst))
(if (= a (+ b (car lst)))
(progn
(format t "pair for ~A is (~A, ~A)~%" a b (car lst))
(rec-pair a (car olst) (cdr olst) (cdr olst)))
(rec-pair a b (cdr lst) olst)))))
;;Given an unsorted array and a number a, find a pair of numbers(b,c) from the arraysch that a=b+c.
(defun find-pair (a lst)
(if (null lst)
(format t "Provide list")
(rec-pair a (car lst) (cdr lst) (cdr lst))))
(defun rec-pair (a b lst olst)
;(format t "~A ~A ~A ~A~%" a b lst olst)
(if (null olst)
(format t "done searching!")
(if (null lst)
(rec-pair a (car olst) (cdr olst) (cdr olst))
(if (= a (+ b (car lst)))
(progn
(format t "pair for ~A is (~A, ~A)~%" a b (car lst))
(rec-pair a (car olst) (cdr olst) (cdr olst)))
(rec-pair a b (cdr lst) olst)))))
1) If you can use hash table, let's go
It is O(n)
- Alex Fetisov December 13, 2011Also you can sort the array and then it is a famous problem.