# Facts

How many binary tree and binary search tree can be made on n nodes with key values 1, 2, …, n?

• # of BST - (2n)C(n) /(n+1) -- catalan number
• # of BT - catalan number * n! = 2n ! / (n+1) !

In BT the layout matters, but the position doesn't. 1-2-3 is same as 2-1-3 if 2 and 1 as roots. In BST, they are different.

# Solutions

not so good solution in post: O(2^n) complexity because overlapping sub-trees in the same (start, end) range is not reused.

Two-dimension dp is used (similar to the matrix problem in CLRS). only that the result for each range is a vector

For BT, only one-dimension dp is necessary, i.e., # of nodes

# Problem

Given a list of sentences, find two sentences with the maximum common words. e.g.,
This is a good day
That was good day
You need to return the first and the second sentences because they share four common words.

# Problem

Given a server that has requests coming in. Design a data structure such that you can fetch the count of the number requests in the last second, minute and hour.

# Problem

Given a text file with 3 columns -- all integers:
id,parent,weight
each line is a node, 'parent' refers to 'id' of another node.
Print out, for each node, the total weight of a sub-tree below this node.

# K Most Frequent Words in a Stream C++ implementation

C++ implementation for this problem@geeksforgeeks

# Interview Question: iterator implementation

1. Design Pattern Gist
1. iterator object is dynamically created from container object :- begin(), end() return iterator obj
2. iterator object keeps the pos state (_cur ptr) :- manipulator for the pos is in iterator
2. Interface
1. functions: begin(), end(), cur(), next()
2. operators: n/a,n/a,*,++
3. concrete iterator object
1. current ptr
2. composition to the container object -: one(aggregate) to many(iterators) relations
4. concrete container object
1. iterator class == friend class
2. begin(), end() return iterator object (copy, not reference)

# Distributed Hash Table Techniques

DHT wiki

OS slides 10

CMU slides on distributed system
part 1
system requirement
part 2

1. replication + caching
2. partition:
1. horizontal partitioning + consistent Hashing consistent hashing wiki: implication on usage !implementation article shard_wiki
2. master/tablet

data consistency

Yahoo sherpa wiki

Generating IDs
instagram paper more summary
current understanding

1. timestamp at higher bits :- time sortable IDs
2. dedicated server: e.g., Apache zookeeper: similar idea as Flickr: single server for generating IDs. Flickr: a ticket server built on mysql's auto-increment and transaction.
3. sharding by Instagram:
1. timestamp(41 bits)+sharding_id(13 bits)+counter(10bits)
2. logical shards are for each schema
3. counter is per server incremental