evidanary

# check if there is two integers which sum up to the targeted sum
def two_sum(arr, target)
  arr.sort!
  size = arr.size
  i, j = 0, size-1
  count = 0
  while(i<j) do
    sum = arr[i] + arr[j]
    if sum == target
    	count += 1

evidanary

# check if there is three integers which sum up to the targeted sum
# fix k from 0...size-2 and then run sum of 2 numbers equal to target (see above)
def target_sum(arr, target)
  arr.sort!
  size = arr.size
  i, j = 0, size-1
  count = 0
  (0...size-2).each do |k|
    i=k+1
    j=size-1  

evidanary

# Check if a binary tree is valid
class Solution
    def initialize()
        @prev = nil
    end
    def is_valid_bst(root)
        return true if root.nil?
        left = is_valid_bst(root.left) 
	    return false if (@prev && (@prev >= root.val ))
	    

evidanary

# Unique Permutation of all elements in an array
# Do something like if(i > 0 && nums[i] == nums[i - 1] && use[i - 1]) continue;
# See solution #https://discuss.leetcode.com/topic/31445/really-easy-java-solution-much-easier-than-the-solutions-with-very-high-vote
# Space: O(N), Time: N^N
def unique_permute(str)
    chars = str.chars
    chars = chars.sort
    res = []
    used = (0...arr.size).map { |i| false}
    perm_helper(chars, [], used, res)

evidanary

#Combinations
# Time complexity: N^K where k = target
# Space complexity: K * N^2
def nchoosek(numbers, target, partial=[])

  if partial.size == target
    puts "#{partial}"
    return
  end
  (0...numbers.length).each do |i|

evidanary

# Topological sort
Do a DFS and push items in a queue as you traverse the leaf nodes adding deepest element first
Queue will hold sorted output (for dependency management)
graph = {0 => [1], 1 => [2,3], 2 => [3], 3 => []}
def topo_sort(graph)
	seen = Set.new
	queue = []
	graph.each do |node, v|
	  dfs_helper(graph, node, seen, visited)
	end

evidanary

# Insertion Sort
def insertion_sort(arr)
	return arr if arr.nil? || arr.empty? || arr.size == 1
	(1...arr.size).each do |idx|
		j = idx
		while(j>0 && arr[j] < arr[j-1]) do
			temp = arr[j]
			arr[j] = arr[j-1]
			arr[j-1] = temp
			j -= 1

evidanary

# Merge sort implementation with extra space
def merge_sort(array)
  return array if array.size <= 1
  left = array[0...array.size / 2]
  right = array[array.size / 2...array.size]

  merge(merge_sort(left), merge_sort(right))
end
def merge(left, right)
  result = []

evidanary

# Implement a Trie using hash (You need to first figure out what operations the trie has to support)
# add, contains, word_count, remove, etc.
class Trie
  attr_accessor :root
  
  def initialize()
  	@root = {}
  end
  
  # returns false if already present

evidanary

# Square root of a number
# Use newton rhapson's method
def sqrt(x)
  r = x
  r = (r + x/r) / 2 while r*r > x
  r
end