Nuts And Bolts

July 14, 2017

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.

Advertisements

Pages: 1 2

3 Responses to “Nuts And Bolts”

  1. John Cowan said

    The correct answer is obviously “There can be no such program”.

  2. 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)))
    
  3. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: