Just another interview problem ..
Given the following code:
def bst_distance(values, n, node1, node2)
# write you code here
endFix this problem:
Last active
March 8, 2017 11:44
-
-
Save tareksamni/9f0bebf5fc94b4547af317d6c6b646cc to your computer and use it in GitHub Desktop.
Just another interview question that I had to code in Ruby :)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 |
Author
tareksamni
commented
Mar 8, 2017
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment