Skip to content

Instantly share code, notes, and snippets.

View evidanary's full-sized avatar

evidanary evidanary

View GitHub Profile
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
}
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
############################
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
#######################
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
#######################
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)
# 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
# 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
# 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
# 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 = []
# 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