Skip to content

Instantly share code, notes, and snippets.

@tareksamni
Last active March 8, 2017 11:44
Show Gist options
  • Save tareksamni/9f0bebf5fc94b4547af317d6c6b646cc to your computer and use it in GitHub Desktop.
Save tareksamni/9f0bebf5fc94b4547af317d6c6b646cc to your computer and use it in GitHub Desktop.
Just another interview question that I had to code in Ruby :)

Just another interview problem ..

Given the following code:

def bst_distance(values, n, node1, node2)
  # write you code here
end

Fix this problem: problem

class Node
attr_accessor :value, :left, :right
def initialize(value, left, right)
@value = value
@left = left
@right = right
end
def self.from_array(arr)
return if arr.empty?
value = arr.shift
left_elems, right_elems = arr.partition { |elem| value > elem }
left = from_array(left_elems) unless left_elems.empty?
right = from_array(right_elems) unless right_elems.empty?
new(value, left, right)
end
# for debugging only
def to_s
"#{@value}{#{@left}|#{@right}}"
end
def self.path(root, val)
current_node = root
path = []
until current_node.nil?
path.push(current_node.value)
return path if val == current_node.value
current_node = val > current_node.value ? current_node.right : current_node.left
end
[]
end
end
# bst_distance(values, values_count, node1, node2)
def bst_distance(values, _, node1, node2)
tree = Node.from_array(values)
return -1 if tree.nil?
path1 = Node.path(tree, node1)
path2 = Node.path(tree, node2)
return -1 unless path1.size.positive? && path2.size.positive?
shared_path = path1 & path2
uniq_path1 = path1 - shared_path
uniq_path2 = path2 - shared_path
uniq_path1.size + uniq_path2.size
end
puts bst_distance([5, 6, 3, 1, 2, 4], 5, 2, 4) # should return 3
puts bst_distance([5, 1], 2, 5, 1) # should return 1
puts bst_distance([], 0, 5, 1) # should return -1
puts bst_distance([1, 5, 3], 3, 1, 1) # should return 0
puts bst_distance([1, 5, 3], 3, 2, 1) # should return -1
@tareksamni
Copy link
Author

screen shot 2017-03-07 at 22 16 36

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment