evidanary

Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the following problem. Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range.  http://www.geeksforgeeks.org/bucket-sort-2/

In sharding you can have logical and physical shards: user_id % 8 = logical shard
logical shards -> physical shard map
{
 0: A, 1: A,
 2: A, 3: A,
 4: B, 5: B,
 6: B, 7: B
}

evidanary

Powerset of a set is all possible sets from that set: i.e. imaging you have a 1/0 for each element indicating on off. Then size is 2^N
def powerset(arr)
  partial = []
  pwr_helper(arr, partial, 0)
end
def pwr_helper(arr, partial, n)
  if(n >= arr.size)
    puts partial.inspect
    return
  end

evidanary

############################
Rubyisms
############################
To get nth bit of a number you can do a = 5; a[0] == 1; 5.downto(0).map { |n| a[n] }.join #"000101"

To average 2 positive integers: (x&y)+((x^y)>>1)
Sum 2 positive integers: (x+y) == (x&y)+(x|y) 

PriorityQueue API 'pqueue' : http://www.rubydoc.info/gems/pqueue/PQueue

evidanary

#######################
Time complexities
#######################
Priority Queue (Binary Heap) / Max Heaps or Min Heaps: 
top: O(1), pop: O(logn), add: O(logn), build: O(nlogn), Delete Random: logn if have pointer to element, N otherwise
API: remove, peek, pop, add, size

Priority Queue (Fibonacci Heap):
top: O(1), pop: O(logN), add: O(1), build: O(nlogn), ?Delete Random: logn if have pointer to element, N otherwise

evidanary

#######################
Sorting: http://bigocheatsheet.com/
#######################
Quicksort: 
Time Complexity: best O(nlogn), avg: O nlogn, worst :n^2 (to avoid worst use randomized pivot points)
Space Complexity: O(logn)
Randomly select pivot in a list, move all values lower than pivot to a left list, all values higher to right list.

Heapsort: 
Time Complexity: best O(nlogn), avg: O(nlogn), worst: O(nlogn)

evidanary

# power of a number
# Beware the power can be a float or negative
def pow(x,y)
  return 1 if y==0
  product = 1
  (1..y.abs).each do 
    product /= x.to_f if y<0
    product *= x if y>0
  end
  product

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

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

# 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

# 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