Smartynk's Website
Home Projects Hobbies Resources Contact Info Links

Useful 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

tree

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

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))
             (right-subtree (caddr G))
             (nodeval   (cadr 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))
                 (right-subtree (caddr G))
                 (nodeval (cadr 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))
    )
) 

    
    
^Return to top^
Contents (c) Copyright Stefan Martynkiw 2005-2011
Hosted on University of Alberta Webspace