## Three Interview Questions

### August 23, 2013

We have three simple interview questions today:

1) Verify that a binary tree is a binary search tree. In a binary search tree, all nodes to the left of the current node have values less than the value of the current node, all nodes to the right of the current node have values greater than the value of the current node, and those two rules hold for all nodes in the tree.

2) Remove duplicates from a list.

3) A girl counts on her fingers by counting 1 on her thumb, 2 on her index finger, 3 on her middle finge, 4 on her ring finger, and 5 on her pinkie. Then she continues the other way, counting 6 on her ring finger, 7 on her middle finger, 8 on her index finger, and 9 on her thumb. Then she continues the other other way, counting 10 on her index finger, 11 on her middle finger, 12 on her ring finger, and 13 on her pinkie. She continues in this way indefinitely. Write a program that, given n, determines which finger she will be on when her count reaches n.

Your task is to write programs that solve the three interview questions given above. 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.

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
```