Similar String

Problem

Similar string is defined as matching by insert/delete/replace one char of any one of string.

Implementation

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

[Leetcode] zigzag conversion

 

Digiprove sealCopyright secured by Digiprove © 2014 Del Bao

[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