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

#######################
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

#######################
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

############################
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

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

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

{"record":[{"name":"Anime_Alexx","views7days":[{"date":"2025-05-14","count":211},{"date":"2025-05-15","count":110},{"date":"2025-05-16","count":123},{"date":"2025-05-17","count":70},{"date":"2025-05-18","count":85},{"date":"2025-05-19","count":102},{"date":"2025-05-20","count":256}],"addToCart7days":[{"date":"2025-05-14","count":45},{"date":"2025-05-15","count":24},{"date":"2025-05-16","count":27},{"date":"2025-05-17","count":17},{"date":"2025-05-18","count":22},{"date":"2025-05-19","count":25},{"date":"2025-05-20","count":51}],"orders7Days":[{"date":"2025-05-14","count":18},{"date":"2025-05-15","count":10},{"date":"2025-05-16","count":12},{"date":"2025-05-17","count":6},{"date":"2025-05-18","count":8},{"date":"2025-05-19","count":9},{"date":"2025-05-20","count":33}],"sales7Days":[{"date":"2025-05-14","count":1566},{"date":"2025-05-15","count":869},{"date":"2025-05-16","count":1044},{"date":"2025-05-17","count":521},{"date":"2025-05-18","count":696},{"date":"2025-05-19","count":782},{"date":"2025-05-20","coun