[LeetCode] Unique Binary Search Trees II, DP Solution

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

Implementation

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

A String Problem Using Invert Index

Problem

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

Implementation

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

1d and 2d local minimum problem

O(lgn) 1d local minimum implementation

O(lgn) 2d local minimum implementation (downhill)

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

Server Metrics Design

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.

Implementation

 

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

tail -f implementation using circular buffer

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

DP Solution for Regular Expression Matching

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

Interview Question: topological sort in Tree

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.

Solution

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

K Most Frequent Words in a Stream C++ implementation

C++ implementation for this problem@geeksforgeeks

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

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)

 

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

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

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao