The sheet below is what I use to keep handy for quick revision of my algo-ds interview prep.
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example: Given the below binary tree,
1
/ \
2 3
Return 6.
1 (1003,2) = 1006
/ \
1053 = (50,1002) 1 2
/ \
50 2 (0,1000) = 1002
\
1000
Calculate leftsum & rightsum for all nodes. Return max of left_sum, right_sum + node.val from the function
def calc(node)
left_sum = calc(node.left)
right_sum = calc(node.right)
heap.push (left_sum + right_sum + node.val)
return max(left_sum,right_sum) + node.val
end
The value pushed into the heap - the max value will determine is the maximum path sum
def main()
calc(root)
heap.top
end
Total Accepted: 104626 Total Submissions: 287040 Difficulty: Medium Given a collection of distinct numbers, return all possible permutations.
For example, [1,2,3] have the following permutations: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
# @param {Integer[]} nums
# @return {Integer[][]}
def permute(nums)
get_permutations(nums)
end
def get_permutations(arr)
#puts arr.inspect
#return [arr] if arr.length == 1
output = []
arr.each_with_index do |val,i|
temp = arr.clone
temp.slice!(i)
get_permutations(temp).each do |out|
output << [val] + out
end
end
#puts output.inspect
output
end
Total Accepted: 100226 Total Submissions: 312193 Difficulty: Medium Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example, If nums = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
# @param {Integer[]} nums
# @return {Integer[][]}
def subsets(nums)
set = []
_subsets(nums,-1,set,[])
set
end
def _subsets(nums,i,set,subset)
set << subset
(i+1..nums.length-1).each do |j|
_subsets(nums,j,set,subset+[nums[j]])
end
end
##39. Combination Sum
Total Accepted: 96375 Total Submissions: 304890 Difficulty: Medium Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ [7], [2, 2, 3] ]
# @param {Integer[]} candidates
# @param {Integer} target
# @return {Integer[][]}
def combination_sum(candidates, target)
set = []
candidates.sort!.reverse!
_get_all_sets(candidates,target,[],set)
set
end
def _get_all_sets(c,t,sol,set)
if t == 0
set << sol
return
end
c.each_with_index do |val,i|
if val <= t
_get_all_sets(c[0..i],t-val,sol+[val],set)
end
end
end
Total Accepted: 78413 Total Submissions: 223903 Difficulty: Medium Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example, If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
# @param {Integer} n
# @param {Integer} k
# @return {Integer[][]}
def combine(n, k)
set = []
_subsets(n,k,0,set,[])
set
end
def _subsets(n,k,i,set,subset)
if subset.length == k
set << subset
return
end
(i+1..n).each do |j|
_subsets(n,k,j,set,subset+[j])
end
end
Total Accepted: 13878 Total Submissions: 41570 Difficulty: Medium Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
Show Hint Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Show Company Tags Show Tags Show Similar Problems
# @param {Integer} n
# @param {Integer[][]} edges
# @return {Boolean}
def valid_tree(n, edges)
visited_hash = {}
adj_list = {}
edges.each do |n1,n2|
adj_list[n1] ||= []
adj_list[n2] ||= []
adj_list[n1] << n2
adj_list[n2] << n1
end
queue = []
queue << adj_list.keys[0]
while node = queue.shift
visited_hash[node] = true
next_nodes = adj_list[node]
next if next_nodes.empty?
next_nodes.each do |n2|
#this represents a cycle
return false if visited_hash[n2]
#adj_list[n2].delete(n1)
queue.push(n2)
end
adj_list.delete(node)
end
# there are still nodes left that are not traversed. So its disconnected graph
return false if adj_list.keys.length > 1
true
end
Total Accepted: 91384 Total Submissions: 353375 Difficulty: Medium Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given s = "leetcode", dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
# @param {String} s
# @param {Set<String>} word_dict
# @return {Boolean}
class TrieNode
attr_accessor :next, :word
def initialize(word=nil)
@word = word
@next = {}
end
def inspect
self.next.each do |key,value|
puts self.word if !self.word.nil?
value.inspect
end
end
end
def word_break(s, word_dict)
root = build_trie(word_dict)
puts root.inspect
pos = 0
s = s.split(//)
char = s[pos]
node = root
while pos < s.length
if node.next[char].nil?
if root.next[char].nil?
return false
else
node = root
next
end
else
node = node.next[char]
end
pos += 1
char = s[pos]
end
return true
end
def build_trie(words)
root = TrieNode.new
words.each do |w|
node = root
w.each_char do |char|
#puts char
if node.next[char].nil?
node.next[char] = TrieNode.new
node = node.next[char]
end
end
node.word = w
end
root
end
Total Accepted: 70096 Total Submissions: 260086 Difficulty: Medium Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
Solution :- Let's look at an example:
[5, 8, 21, 15, 10, 6]
first, find 8;
then, find 10 from [21, 15, 10, 6] that is larger than 8 and is closest to the end;
swap, to [5, 10, 21, 15, 8, 6];
finally, the range [21, 15, 8, 6] needs to be in increasing order as [6, 8, 15, 21], we got [5, 10, 6, 8, 15, 21].