Smartynk's Website
Home Projects Hobbies Resources Contact Info Links

## Microsoft Interview 2014 -- Question 4

When I interviewed at Microsoft in Seattle for an SDE Internship, I was stuck on the last interview question. After taking CMPUT 325 (Functional Programming) at the University of Alberta, I realized that I could solve the problem with only a few lines of Common Lisp.

## Problem Description Given a tree, like the one on the right, find your Nth neighbour to the right. For example, if you want to find the 2nd neighbour to the right of -4, you'll get the 21 node.

There are some subtleties to the problem:

• The tree does not have to be full
• Your neighbour does not have to share the same parent

## The Interesting Solution

Here's the solution that I gave in the interview:

Assume that each node only has two children. Assign the "left path" (aka, the pointer to the left child) a "code" of zero. Assign the "right path" a code of one. Notice that any node n-levels deep in the tree can be accessed by an n-"bit" code.

This n-bit code can be given as a bitfield to a recursive function which follows the pointers down the the desired level.

• In the case that the tree is full, to find the nth right neighbour, one does a search through the tree, keeping track of the pointers followed, to find your starting node. Next, take that node and add (n)base-2 to it to arrive at an "instruction" that will guide you into the desired node.
• If the tree is not full, then there's an interesting issue. Adding (n)base-2 will work still, but the pointer-follower function will need to take in mind the following scenario:
• If the proposed pointer-follow is invalid, add 1 to the given bitfield and try again.
This solution is creative and kinda works, but definitely isn't what the interviewer was looking for.

## The Correct Solution (Procedural)

Magic things with BFS, and putzing with the queue.

## The LISP Solution

Description to follow

### LISP Source

```    ```

;;
;;      Stefan Martynkiw
;;      March 22, 2015
;;      The following code is under the Apache2 License
;;

; Find n-th neighbour to right in list

;Tree with duplicates
"
/-- 4----\
3               2
/    \           /    \
1       5      3        8
|      /  \      | \      /  \
6   7   3    0 1    10  11

"
;Our test tree is drawn above, represented below
(setq tree '(      (    ( (nil 6 nil ) 1 nil  )       3      ( (nil 7 nil ) 5 (nil 3 nil)  )      )
4
( ((nil 0 nil) 3 (nil 1 nil) )           2           ((nil 10 nil) 8 (nil 11 nil) ) )
)
)

;Test Tree without duplicates
"
/-- 1----\
2               3
/    \           /    \
4       5      6       ----- 7
|      /  \      | ----\        /  \
8   9   10   11 12    13  14

"
;Our test tree is drawn above, represented below
(setq tree2 '(      (    ( (nil 8 nil ) 4 nil  )       2      ( (nil 9 nil ) 5 (nil 10 nil)  )      )
1
( ((nil 11 nil) 6 (nil 12 nil) )           3           ((nil 13 nil) 7 (nil 14 nil) ) )
)
)

(defun solve-problem (G N J)
;Given Tree G, Node N, find the Jth neighbour to the right
(get-Jth-neighbour-to-N
(get-all-neighbours G (find-node G N 0) 0) ; Get's list of all things at N's level
N
J
)
)

;G is the given Tree
;R is the number of levels deep in recursion we need to be at (find it with find-node)
;F is the levels deep we're currently at

; Keep around as a variable the base tree so that when we're done recursing, that's all.
(defun get-all-neighbours (G R F)
;
; At each level, look at R, if R < F, recurse down,
; If R = F then return (append (each_node_at_this_level) )

(let  ( (left-subtree (car G))
(nextF (+ F 1))
)

(cond
( (eq R F)
(cond
((null nodeval) nil) ;Prune NILs from output list
(T
(append (list nodeval))
)
)
)
( (> F R)
;If we've recursed farther than we need to, then we're done
nil
)
(T
(append
(get-all-neighbours left-subtree R nextF)
(get-all-neighbours right-subtree R nextF)
)
)
)
)
)

;If you want K to be zero-indexed, call this function with accum=0
;If you want K to be 1-indexed, call this function with accum=1
(defun get-kth-item-from-list (L K accum)
(cond
((eq accum K) (car L))
(T
(get-kth-item-from-list (cdr L) K (+ 1 accum))
)
)
)

;Given a tree G, find node N, and return levels deep in variable R
;Pretty much DFS.
;Kinda buggy.
;If there are duplicate nodes, the strange behavior happens.
;The -1 trick is really gross. The recursive call used to evaluate to nil if there wasn't a match.
;However, there were bugs with that value propigating up depending on which half of the tree
;the actual value was found. Where the (max) call is, I thought about using a let and a cond to always
;just return a non-nil value, but because of the (+ 1 R) trick, the value of R would be unexpectedly
;incremented while evaluating the (cond).
;
;This solution is acceptible providing that there are no duplicate elements in the tree.
(defun find-node (G N R)
(cond
((null G) -1)
((atom G) -1)
(T
(let ( (left-subtree (car G))
)
(cond
((eq nodeval N) R) ;We've found our desired node. Return R.
(T
;If we're here, our current level didn't contain the desired node.
;As the function was written, it returned nil if the subtree search failed. It returns an
;appropriate R if the search was successful. The (max) below causes find-node
;to return an appropriate value
(max
(find-node left-subtree     N   (+ 1 R)   )
(find-node right-subtree    N  (+ 1 R)  )
)
)
)
)
)
)
)

(defun get-Jth-neighbour-to-N (L N J)
;List L, desired node N, J is zero-indexed index-N++ ,I is accumulator storing item
(cond
((eq (car L) N)
;We're at the desired start-point
(cond
((> J 0)
;Keep going
(get-Jth-neighbour-to-N (cdr L) (cadr L) (- J 1) )
)
(T
;Return where the item where we're at
(car L)
)
)
)
(T
(get-Jth-neighbour-to-N (cdr L) N J )
)
)
)

;Does list L contain Item I?
(defun contains (L I)
(cond
((null L) nil)
((eq I (car L)) T)
(T (contains (cdr L) I))
)
)

```
```