July 14, 2017 2:00 PM
Today’s exercise is an interview question from Microsoft:
You are given two bags, one containing bolts and the other containing nuts, and you need to find the biggest bolt.. You may compare bolts to nuts, to see which is larger, but you may not compare bolts to bolts or nuts to nuts. Write a program to find the biggest bolt.
Your task is to write a program to find the biggest bolt. 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.
The correct answer is obviously “There can be no such program”.
By John Cowan on July 14, 2017 at 3:35 PM
Of course, there can be such a program. But sometimes, there may be several biggest nuts:
(defun find-biggest-nut (nuts bolts) (loop :while (and (cdr nuts) bolts) :do (let ((bolt (pop bolts)) (bigger-nuts '()) (smaller-nuts '())) (dolist (nut nuts) (if (<= nut bolt) (push nut smaller-nuts) (push nut bigger-nuts))) (setf nuts (or bigger-nuts smaller-nuts))) :finally (return nuts))) (defun set-equalp (a b) (and (subsetp a b) (subsetp b a))) (assert (set-equalp (find-biggest-nut '(1 2 3 4 5) '(1 2 3 4)) '(5))) (assert (set-equalp (find-biggest-nut '(1 2 3 4 5 6) '(1 2 3 4)) '(5 6))) (assert (set-equalp (find-biggest-nut '(1 2 3 4 5 6) '(1 2 3 4 7)) '(5 6)))By Pascal Bourguignon on July 16, 2017 at 10:12 PM
Consider the case where the bag of nuts contains one nut, which is bigger than all of the bolts. Nothing in the task description rules this out. In this case it is impossible to discriminate between the bolts. John Cowan is right.
By Richard A. O'Keefe on July 20, 2017 at 7:54 PM