balloonio

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.nxt = None

class NodeList:
    def __init__(self):
        self.size = 0

balloonio

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.key2node = {}
        self.nodelist = NodeList()
    
    def get(self, key):
        if key not in self.key2node:
            return -1
        node = self.key2node[key]

balloonio

class Node:
    def __init__(self, key, weight):
        self.key = key  # object key or id
        self.weight = weight
        self.prev = None
        self.nxt = None

class NodeList:
    def __init__(self):
        self.head = None

balloonio

class WeightRandom:
    def __init__(self):
        self.key2node = {}  # object key or id : the node contains the object info (weight, id)
        self.nodelist = NodeList()
        self.totalsum = 0

    # O(1)
    def setObjectWeight(self, obj_key, weight):
        # not in map and also try to zero weight, no op
        if weight == 0 and obj_key not in self.key2node:

balloonio

wr = WeightRandom()
wr.setObjectWeight(1, 1)
wr.setObjectWeight(2, 1)
wr.setObjectWeight(2, 0)
wr.setObjectWeight(3, 2)

for i in range(10):
    print(wr.getRandom())
    

balloonio

# 

balloonio

Palindrome

• dynamic programing with f[i][j] = whether s[i:j+1] aka s[i]..s[j] is palindrome or its length
• enumerate pivots, and expand from each pivot

Subsequence

• if using dynamic programing, in general f[i][j] = f[i+1][j-1] || f[i][j-1] || f[i+1]f[j] (meaning you can either take both end, left only, or right only

DP

balloonio

Installing Cassandra on Mac OS X

Install Homebrew

Homebrew is a great little package manager for OS X. If you haven't already, installing it is pretty easy:

ruby -e "$(curl -fsSL https://raw.github.com/Homebrew/homebrew/go/install)"