Programming Praxis

8 Responses to “Three Interview Questions”

1. bhrgunatha said

   August 23, 2013 at 12:29 PM

   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

   August 23, 2013 at 12:32 PM

   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

   August 23, 2013 at 2:25 PM

   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

   August 24, 2013 at 5:30 AM

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

   August 25, 2013 at 9:34 AM

   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

   August 28, 2013 at 1:51 PM

   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

   August 28, 2013 at 1:52 PM

   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

   November 12, 2013 at 8:24 PM

   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