new-questions.md

Summary of Questions

• Level 100: Write a program that returns a sum of two binary string. e.g. returns b 1011 given b 110, and b 101.
• Level 100: Write a program that returns a to the power of p efficiently. e.g. returns 81 given 3 to the power of 4.
• Level 100: Write a program that returns the the k-th smallest number given a list of integers. e.g. returns 7 given k = 4, and a list [3, 5, 1, 7, 9].
• Level 100: Write a program that given a string of parenthesis tells if it is balanced or not (return true or false) -- this program runs in O(1) space. e.g. balanced (true) for "((()))()", and unbalanced (false) for ")(" and "(()"
• Level 150: Write a program that given a string of parenthesis '()', angle-brackets '<>', square-brackets '[]', and brace brackets '{}', tells if everything is balanced -- this program runs in O(n) time. e.g. balanced (true) for "[{{()<>}}]<>", not balanced (false) for "[{{(<)>}}]<>"
• Level 200: Write a program that prints (on the screen) all balanced strings of parenthesis of a given size. e.g. print "()" given 1, "()()", and "(())" given 2, and "((()))", "(()())", "(())()", "()(())", "()()()" given 3
• Level 200: Write a program that returns top 1000 frequent search terms out of 256 x 1 GB log files using 8 x quad-core processor machines with 8 GB RAM --- deviated from a question of top 10 frequent words in a file.
• Level 200: Write a program that returns a predecessor of a node in a binary search tree --- from Cracking the coding interview.
• Level 200: Write a program that returns the lowest common ancestor of two nodes in a binary tree; not given a reference to parent nodes; trade space for time if possible --- deviated from Cracking the coding interview that dictates no additional data structures.
• Level 200: Write a program that returns all the paths of a sum in a binary tree --- from Cracking the coding interview.
• Level 200: Design a tic-tac-toe game and implement a function that tells if someone won the game --- from Cracking the coding interview --- estimation: 50 - 90 lines of code.
• Level 250: Write a program that resolves a depedency graph in scheduling a sequence of jobs or tasks based on their dependencies.

* Level 250: Write a program that tells if a directed graph has **a cycle or not** --- Amazon bar raiser asked me this question a year ago. * Level 250: Write a program that tells us if a path is matched by a wildcard pattern. e.g. returns true if a pattern is ***a*b?** and a path is **abababc** --- estimation: 10 - 15 lines of code. * Level 250: Write a program that determines the max amount of money while keeping the overal weight under or equal to 15kg? a classical 0/1 knapsack problem --- estimation: 12 - 18 lines of code.

Hints

• building algorithms around data structures such as dictionaries (hashtable, hashmap, treemap) and priority queues (binary heap, Fibonacci heap) leads to both clean structure and good performance --- algorithm design manual.

Detailed Description of Questions

Write a program that returns all the paths of a sum in a binary tree

# You are given a binary tree in which each node contains a value.
# Design an algorithm to print all paths which sum up to that value.
# Note that it can be any path in the tree - it does not have to start at the root.
#
# tree: -1
#         3
#       -1
#       2 3
def test_find_path_of_sum_in_linear_time
  tree = BNode.new(-1, nil, BNode.new(3, BNode.new(-1, BNode.new(2), BNode.new(3)), nil))
  assert_equal ["-1 -> 3", "3 -> -1", "2", "-1 -> 3"], BNode.find_path_of_sum(tree, 2)
end

Write a program that tells us if a path is matched by a wildcard pattern.

def test_wildcard_match?
  assert !Strings.wildcard_match?('?', '') # '?' should match a single character.
  assert Strings.wildcard_match?('?', 'q') # '?' matches a single character.
  assert Strings.wildcard_match?('*', '') # '*' matches zero or more character.
  assert Strings.wildcard_match?('*', 'c')
  assert Strings.wildcard_match?('*', 'ba')
  assert Strings.wildcard_match?('*x', 'cbax')
  assert Strings.wildcard_match?('x*', 'xcba')
  assert Strings.wildcard_match?('*x*y*', 'abxcdyef')
end