Three Interview Questions

August 23, 2013

The first exercise is simple recursion through the tree:

(define (bst? lt? t)
  (or (nil? t)
      (and (or (nil? (lkid t))
               (and (lt? (valu (lkid t)) (valu t))
                    (bst? (lkid t))))
           (or (nil? (rkid t))
               (and (lt? (valu t) (valu (rkid t)))
                    (bst? (rkid t)))))))

The second exercise isn’t much harder. We use a hash table, insert new items only if they don’t already exist, and return the result when we are finished. We could equally use a set:

(define (dedup xs)
  (let ((h (make-hash)))
    (do ((xs xs (cdr xs)))
        ((null? xs) (enlist h))
      (when (null? (h 'lookup (car xs)))
        (h 'insert (car xs))))))

The third exercise takes a little bit of thought. After the first pass over the fingers, the pattern repeats with a cycle of eight:

(define (finger n)
  (case n
  ((1) 'thumb)
  ((2) 'index)
  ((3) 'middle)
  ((4) 'ring)
  ((5) 'pinkie)
  (else (case (modulo (- n 5) 8)
        ((3) 'thumb)
        ((2 4) 'index)
        ((1 5) 'middle)
        ((0 6) 'ring)
        ((7) 'pinkie)))))

We used hash tables from a previous exercise (I’ve been too busy — or lazy — to put them in the Standard Prelude). You can run the program and see examples at http://programmingpraxis.codepad.org/ebAifNzO.

About these ads

Pages: 1 2

8 Responses to “Three Interview Questions”

  1. bhrgunatha said

    finger seems a bit more complicated than it needs to be:

    (define (finger n)
    (case (modulo (- n 1) 8)
    ((0) ‘thumb)
    ((1 7) ‘index)
    ((2 6) ‘middle)
    ((3 5) ‘ring)
    ((4) ‘pinkie)))

  2. bhrgunatha said

    Ooops – formatting.
    Why not?

    (define (finger n)
      (case (modulo (- n 1) 8)
        ((0) 'thumb)
        ((1 7) 'index)
        ((2 6) 'middle)
        ((3 5) 'ring)
        ((4) 'pinkie)))
    
  3. ye said

    I concur with bhrgunatha. Indeed, it can be much simpler as he pointed out. The “minus one” can also be removed:

    (define (fingersimpler n)
    (case (modulo n 8)
    ((1) ‘thumb)
    ((2 0) ‘index)
    ((3 7) ‘middle)
    ((4 6) ‘ring)
    ((5) ‘pinkie)))

    Also, in the original solution above, the calculation appears to be off by one for numbers greater than 5. For example, (finger 6) would return “middle”

  4. Hanoch M. said

    About ‘remove duplicates from list’ (Python)
    def remove_duplicates (l1):
    return list (set (l1))

  5. Paul said

    In Python:

    def valid_bst(node, mini, maxi):
        """usage: valid_bst(root, -inf, inf)"""
        return node is None or (mini < node.key < maxi and
                     valid_bst(node.left, mini, node.key) and 
                         valid_bst(node.right, node.key, maxi))
        
    def remove_dup(alist):
        return list(set(alist))
    
    FINGERS = ["index", "thumb", "index", "middle", "ring", "pink", "ring",
               "middle"]
    def finger(n): 
        return FINGERS[n % 8]
    
  6. brooknovak said

    I do not think that the solution presented for the BST check is correct.
    From what I can make of the Scheme is that it only verifies that the immediate child nodes hold the BST property, but not ALL the descendants.
    I think this is a common oversight, which makes it such a good interview question! :)

    Let me present a solution that ensures for each node ALL right descendants are larger, and ALL left descendants are smaller or equal:

    public class BinaryNode where T : IComparable {
    public T Data { get; set; }
    public BinaryNode Left { get; set; }
    public BinaryNode Right { get; set; }

    public bool IsBST() {
    T max, min;
    return DoBSTCheck (out max, out min);
    }

    private bool DoBSTCheck(out T max, out T min) {
    max = Data;
    min = Data;

    if (Left != null) {
    T lmax, lmin;
    if (!Left.DoBSTCheck (out lmax, out lmin))
    return false;

    if (lmax.CompareTo(Data) > 0)
    return false;

    if (lmax.CompareTo(max) > 0)
    max = lmax;
    if (lmin.CompareTo(min) < 0)
    min = lmin;
    }

    if (Right != null) {
    T rmax, rmin;
    if (!Right.DoBSTCheck (out rmax, out rmin))
    return false;

    if (rmin.CompareTo(Data) 0)
    max = rmax;
    if (rmin.CompareTo(min) < 0)
    min = rmin;
    }

    return true;
    }
    }
    [/sourceccode]

    It is not terribly elegant (partly due to C#'s ugly generics code!), but the tracking of the min and max throughout the traversal does give an efficient solution!

  7. brooknovak said

    Opps – bad code formatting. Fixed formatting:

    public class BinaryNode<T> where T : IComparable  {
    	public T Data { get; set; }
    	public BinaryNode<T> Left { get; set; }
    	public BinaryNode<T> Right { get; set; }
    
    	public bool IsBST() {
    		T max, min;
    		return DoBSTCheck (out max, out min);
    	}
    
    	private bool DoBSTCheck(out T max, out T min) {
    		max = Data;
    		min = Data;
    
    		if (Left != null) {
    			T lmax, lmin;
    			if (!Left.DoBSTCheck (out lmax, out lmin))
    				return false;
    
    			if (lmax.CompareTo(Data) > 0)
    				return false;
    
    			if (lmax.CompareTo(max) > 0)
    				max = lmax;
    			if (lmin.CompareTo(min) < 0)
    				min = lmin;
    		}
    
    		if (Right != null) {
    			T rmax, rmin;
    			if (!Right.DoBSTCheck (out rmax, out rmin))
    				return false;
    
    			if (rmin.CompareTo(Data) <= 0)
    				return false;
    
    			if (rmax.CompareTo(max) > 0)
    				max = rmax;
    			if (rmin.CompareTo(min) < 0)
    				min = rmin;
    		}
    
    		return true;
    	}
    }
    
  8. agsalcedo said
    class Hand
    	def initialize
    		@current_finger = 1
    		@forward = true
    	end
    
    	def count_to n
    		counter = 1
    		until counter >= n
    			@current_finger += 1 if @forward and @current_finger < 5
    			@current_finger -= 1 if not @forward and @current_finger > 1
    			if @current_finger == 5 and @forward == true then @forward = false end
    			if @current_finger == 1 and not @forward then @forward = true end
    			counter += 1
    		end
    	end
    
    	def current_finger
    		case @current_finger
    			when 1 then return "thumb"
    			when 2 then return "index"
    			when 3 then return "middle"
    			when 4 then return "ring"
    			when 5 then return "pink"
    		end
    	end
    end
    
    hand = Hand.new
    hand.count_to 13
    puts hand.current_finger
    

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

Follow

Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: