EARLY BIRDS: 2013

Thursday, December 19, 2013

Sort a linked list in O(n log n) time using constant space complexity.

This one is easy. Merge sort can solve this problem.

See the following code for the merge sort from bottom to top

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *loop_list(ListNode *head, int len){
// There are len nodes from head(inclusive) to ret(exclusive)
while(head != NULL && len-- > 0) head = head -> next;
return head;
}

ListNode *merge(ListNode *head, int len){
// Merge len nodes beginning from head->next(inclusive), and return the last node.
if(head == NULL || head -> next == NULL) return NULL;

ListNode *a_beg = head -> next;
ListNode *a_end = loop_list(a_beg, len/2 - 1);
if(!a_end) return NULL;

ListNode *b_beg = a_end -> next;
a_end -> next = NULL;

ListNode *b_end = loop_list(b_beg, len/2 - 1);
ListNode *new_end = b_end == NULL ? NULL : b_end -> next;
if(b_end != NULL) b_end -> next = NULL;

ListNode *loop = head;
ListNode *a_loop = a_beg;
ListNode *b_loop = b_beg;
while(a_loop || b_loop){
ListNode *next;
if(!a_loop) {
next = b_loop;
}
else if(!b_loop){
next = a_loop;
}
else next = (a_loop -> val < b_loop -> val) ? a_loop : b_loop;
loop -> next = next;
loop = loop -> next;

if(next == a_loop){
a_loop = a_loop -> next;
}
else if(next == b_loop){
b_loop = b_loop -> next;
}
}
loop -> next = new_end;
return loop;
}

ListNode *sortList(ListNode *head) {
ListNode *fake_head = new ListNode(0);
fake_head -> next = head;
int num_merge = 0;
for(int len = 2; true; len *= 2){
num_merge = 0;
ListNode *loop = fake_head;
while(loop && loop->next){
loop = merge(loop, len);
num_merge ++;
}
if(num_merge <= 1) break;
}
head = fake_head -> next;
delete fake_head;
return head;
}
};

Leetcode: Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

The following is a O(n^2 lg n) algorithm because I use TreeMap instead of HashMap.

If I use HashMap, then the run time is O(n^2). But I did not find a way doing better than O(n^2).

Another question is that to use HashMap in java I need to define my own equals() and hashcode() functions, which is quite annoying. Especially hashcode() function, any one have a idea how to produce a good hashcode() function for this?

/**
* Definition for a point.
* class Point {
*     int x;
*     int y;
*     Point() { x = 0; y = 0; }
*     Point(int a, int b) { x = a; y = b; }
* }
*/
import java.util.*;

class Slope implements Comparable<Slope>{
int x;
int y;
Slope(int a, int b){
      if(b<0){
          a *= -1;
          b *= -1;
      }
      x = a; y = b;
}
public int compareTo(Slope other){
      return this.x * other.y - this.y * other.x;
}
}

public class Solution {
    int numPointsCentered(Point[] points, int id){
        Map<Slope, Integer> counts = new TreeMap<Slope, Integer>();
        int num_same_point = 0;
        int return_max = 1;
        for(int i = 0; i < points.length; i++){
            if (i==id) continue;
            if (points[i].x==points[id].x && points[i].y==points[id].y){
                num_same_point++;
                continue;
            }
            Slope slope = new Slope(points[i].x - points[id].x, points[i].y - points[id].y);
            if(counts.containsKey(slope)){
                counts.put(slope, counts.get(slope) + 1);
            }else{
                counts.put(slope, 2);
            }
            return_max = Math.max(return_max, counts.get(slope));
        }
        return return_max + num_same_point;
    }

    public int maxPoints(Point[] points) {
        int num_points = 0;
        for(int i = 0; i < points.length; i++){
            int new_center_points = numPointsCentered(points, i);
            num_points = Math.max(num_points, new_center_points);
        }
        return num_points;
    }
}

Friday, October 11, 2013

Interview : a strategy to stop flipping the poker and win

Question:

You are playing a card game with me. Suppose I shuffle a deck of 52 cards, then I show you the card one by one to you from top to bottom. You can stop me during this whole process, based on your memory of the previous cards you have seen. If you stop me, and there are still cards left in the deck, if the next unshown card is red, you get one dollar from me, otherwise if the next unshown card is black, you give me one dollar; if no cards left in the deck, you get one dollar if the last card is red, and you give one dollar if the last card is black.

Is there a strategy for you to win with probability larger than 50%?

Sol:

There is not strategy for that. Think the game in a different way: when you stop me, suppose instead of deciding whether you win or lose based on the next unshown card, we decide whether you win or lose based on the last card in the deck: if the last card is red you get one dollar, otherwise if it is black I get one dollar. The two games are the same. But for the latter, whatever strategies you choose the probability for you to win is always 50%, and so does the former.

Interview : Expected time to see a bus

Suppose a bus is running on a loop route. It takes 10 mins for the bus to finish the route. If a guy arrives at a bus stop at uniformly random time. What is the expected bus waiting time?

Sol: image uniformly put a point at a line with length 10, so the expected waiting time is 5.

Now suppose there is a ice cream shop at the bus loop. Whenever the bus is close to the ice cream shop, the driver will flip a coin and decide whether to go eating an ice cream or not. It takes 10 mins for the driver to eat the ice cream. What is the expected bus waiting time if a guy arrives at a bus stop uniformly.

Sol: the key is to consider what uniform arriving time means. The bus is running either on a 10min-loop or a 20min-loop, each with probability 1/2. The bus keeps running, and the guy can arrive at any time between 0am - 24pm, uniformly. The time for the bus to be in a 20min-loop is two times larger than the time for a 10min-loop. So each day 2/3 of the time the bus is in a 20min-loop, and 1/3 of the time the bus is in a 10min-loop.

Thus, the probability for the guy to arrive when the bus is in a 20min-loop is 2/3. Expected waiting time is 10 for the 20min-loop and 5 for the 10min-loop. So the combined expected waiting time is

2/3 * 10 + 1/3 * 5

Thursday, October 10, 2013

understand pure virtual function, abstract class, and virtual function.

See the following program:

#include <iostream>
using namespace std;

class MathSymbol {
public:
virtual void doOperation() = 0; // pure virtual class, so MathSymbol is a abstract class
virtual void print(){
    cout<<"print MathSymbol"<<endl;
}
void move(){
    cout<<"move MathSymbol"<<endl;
}
};

class B : public MathSymbol {
public:
void doOperation(){
    cout<<"Operation in B"<<endl;
}
void print(){
    cout<<"print B"<<endl;
}
void move(){
    cout<<"move B"<<endl;
}
};

class C : public MathSymbol {
public:
void doOperation(){
    cout<<"Operation in C"<<endl;
}

void print(){
    cout<<"print C"<<endl;
}
void move(){
    cout<<"move C"<<endl;
}
};

int main(){
// MathSymbol a; // this is error. because MathSymbol is abstract.
MathSymbol *pa = NULL;

B b, *pb = &b;
C c, *pc = &c;

MathSymbol* array[] = {pb,pc};
int len = 2;

for(int i = 0; i < len; i++){
    array[i] -> doOperation();
}

for(int i = 0; i < len; i++){
    array[i] -> print();
}

for(int i = 0; i < len; i++){
    array[i] -> move();
}
return 0;
}

Its running result is:

Operation in B
Operation in C
print B
print C
move MathSymbol
move MathSymbol

One example explaining the virtual function

Virtual function will be realized after the it is called according to the object associated with it

Non virtual function will be realized by the compiler before the function is called.

See the program below:

#include <iostream>
using namespace std;

class A {
public:
void move(){
    cout<<"move A"<<endl;
}
virtual void print(){
    cout<<"I am A"<<endl;
};
};

class B : public A {
public:
void move(){
    cout<< "move B"<< endl;
}
void print(){
    cout<<"I am B"<<endl;
}
};

class C : public A {
public:
void move(){
    cout<<"move C"<<endl;
}
void print(){
    cout<<"I am C"<<endl;
}
};

int main(){
A a, *pa = &a;;
pa->print();

B b, *pb = &b;
C c, *pc = &c;

cout<<endl;
pb->move();
((A*)pb)->move();

cout<<endl;
pb->print();
((A*)pb)->print();

cout<<endl;
pc->print();
((A*)pc)->print();

cout<<endl;

A* array[] = {&a,&b,&c};
int len = 3;
for(int i = 0; i < len; i++){
    array[i]->print();
}
cout<<endl;
for(int i = 0; i < len; i++){
    array[i]->move();
}
return 0;

}

The running result is listed as:

I am A

move B
move A

I am B
I am B

I am C
I am C

I am A
I am B
I am C

move A
move A
move A

Find the second largest element in an array with the minimum number of comparisons

I meet this question in an interview. It is actually a famous problem, whose solution is available here .

Here my thinking is provided.

1, The simplest case, suppose there are four elements, a,b,c,d, the minimum number of comparisons is 4:

a < b, c < d -> b < d -> max(b,c) is the second largest element.

That is, we compare (a,b), (c,d) to get the largest values b,d, then find the largest value d, the second largest value is in the set of all elements that have been compared with d, that is, b or c.

2, Suppose we have 2n elements: (a,b), (c,d), (e,f), ....... We have n pairs, so select the larger element in each pair to form an n-array: b,d,f....In total n comparison is needed.

Suppose our algorithm can find the largest two values from b,d,f,...., which is (b,d) with b < d, for example.

The second largest element can either be b or c, compare b vs c we get the second largest element.

Thus, if x(2n) is the number of comparisons needed for an 2n-array, we have x(2n) = n + x(n) + 1

Solve this recursive function with x(4) = 4, we get x(n) = n + log2(n) - 2.

Thursday, March 21, 2013

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Two dimentional dynamic programming
map[i][j] = true if s1[0,i-1] and s2[0,j-1] interleaves into s3[0,i+j-1].

public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// Start typing your Java solution below
// DO NOT write main() function
if(s3.length() != s1.length() + s2.length())
return false;

boolean[][] mat = new boolean[s1.length() +1][s2.length()+1];
for(int i = 0; i < mat.length; i++){
for(int j = 0; j < mat[i].length; j++)
mat[i][j] = false;
}
mat[0][0] = true;

for(int i = 1; i <= s1.length(); i++){
if(s1.charAt(i-1) == s3.charAt(i-1)){
mat[i][0] = true;
}
else break;
}

for(int i = 1; i <= s2.length(); i++){
if(s2.charAt(i-1) == s3.charAt(i-1)){
mat[0][i] = true;
}
else break;
}

for(int i = 1; i <= s1.length(); i++){
for(int j = 1; j <= s2.length(); j++){
char c1 = s1.charAt(i-1);
char c2 = s2.charAt(j-1);
char c3 = s3.charAt(i+j-1);
if(c1 == c3) mat[i][j] |= mat[i-1][j];
if(c2 == c3) mat[i][j] |= mat[i][j-1];
}
}
return mat[s1.length()][s2.length()];

}
}

Wednesday, March 20, 2013

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

using a stack, when the next height is larger, push its position into the stack, otherwise, pop a position and calculate the area of the maximum rectangle that can be formed using the height at the position.

remember: the bar right next to the top position at the stack after pop is always larger or equal to the bar at the poped position.

public class Solution {
public int largestRectangleArea(int[] height) {
// Start typing your Java solution below
// DO NOT write main() function
if(height==null || height.length == 0) return 0;
LinkedList<Integer> stack = new LinkedList<Integer>();

stack.add(0);
int i = 1;
int ret = height[0];
while( i < height.length + 1){
int nextv = i < height.length? height[i] : 0;
if(stack.isEmpty() || height[stack.getLast()] <= nextv)
{
stack.add(i++);
}
else{
int t = stack.removeLast();
ret = Math.max(ret, height[t] * (stack.isEmpty() ? i : i-1-stack.getLast()) );
}
}
return ret;

}
}

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

public class Solution {
public int trap(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if(A.length==0) return 0;
int i = 0; int j = A.length-1;
int lm = A[i]; int rm = A[j];

int sum = 0;

while(i<j){
if(lm <= rm){
if(A[++i] < lm) sum += lm - A[i];
else lm = A[i];
}
else{
if(A[--j] < rm) sum += rm - A[j];
else rm = A[j];
}
}
return sum;
}
}

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

make an inorder traversal, if the value is increasing, it is a BST.

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private TreeNode pre;
private boolean ret;
void inorder(TreeNode root){
if(ret == false) return;
if(root==null) return;

inorder(root.left);
if(pre == null){ pre = root;}
else{
if(pre.val >= root.val){
ret = false;
return;
}
pre = root;
}
if(ret) inorder(root.right);
}
public boolean isValidBST(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
pre = null;
ret = true;
inorder(root);
return ret;
}
}

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

firstorder the value will increase, so we can find the first error

backorder the value will decrease, so we can find the second error.

change it

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode first;
TreeNode second;
private TreeNode pre;
void inorder(TreeNode root){
if(first != null) return;
if(root == null) return;
inorder(root.left);
if(pre == null) pre=root;
else{
if(pre.val > root.val) {
first = pre; return;
}
pre = root;
}
if(first == null)
inorder(root.right);
}
void backorder(TreeNode root){
if(second != null) return;
if(root == null) return;
backorder(root.right);
if(pre == null) pre = root;
else{
if(pre.val < root.val) {
second = pre;
return;
}
pre = root;
}
if(second == null)
backorder(root.left);
}

public void recoverTree(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
first = null;
second = null;

pre = null;
inorder(root);

pre = null;
backorder(root);

int temp = first.val;
first.val = second.val;
second.val = temp;
}
}

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Find the root, using recursive.

Note:
You may assume that duplicates do not exist in the tree.
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode buildTree(int[] a, int a1, int a2, int[] b, int b1, int b2){
if(a1 > a2 || b1 > b2) return null;
int rootval = b[b2];
int posA = a1;
while(posA <= a2){
if(a[posA] == rootval) break;
posA++;
}

TreeNode root = new TreeNode(rootval);
int posB = b1 + posA - 1 - a1;
TreeNode.left = buildTree(a,a1,posA-1,b, b1, posB);
TreeNode.right = buildTree(a,posA+1,a2,b, posB+1,b2-1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
// Start typing your Java solution below
// DO NOT write main() function
if(inorder.length == 0) return null;
//return null;
return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);

}
}

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

Recursively build the tree.

public class Solution {

TreeNode sortToBST(ListNode[] list, int start, int end){
if(start > end) return null;

int mid = (start + end) / 2;
TreeNode leftchild = sortToBST(list, start, mid-1);
TreeNode parent = new TreeNode(list[0].val);
parent.left = leftchild;
list[0] = list[0].next;
parent.right = sortToBST(list,mid+1, end);
return parent;
}

public TreeNode sortedListToBST(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode[] l = new ListNode[1];
l[0] = head;
int len = 0;
while(head!=null){
len ++; head = head.next;
}
return sortToBST(l,0,len-1);
}
}

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each paths sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

traverse the whole tree, then we get the answer.

import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> ret;
ArrayList<Integer> tran;
void buildPath(TreeNode root, int sum){
if(root.left == null && root.right == null){
if(sum == root.val){
ArrayList<Integer> n = new ArrayList<Integer>(tran);
n.add(root.val);
ret.add(n);
}
return;
}
tran.add(root.val);
if(root.left != null) buildPath(root.left,sum - root.val);
if(root.right != null) buildPath(root.right, sum - root.val);
tran.remove(tran.size()-1);
}

public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
// Start typing your Java solution below
// DO NOT write main() function
ret = new ArrayList<ArrayList<Integer>>();
tran = new ArrayList<Integer>();
if(root == null) return ret;
buildPath(root, sum);
return ret;
}
}

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6

recursive

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void flatten(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null) return;
flatten(root.left);
flatten(root.right);

TreeNode p = root.right;
root.right = root.left;
root.left = null;
TreeNode q = root;
while(q.right != null) q = q.right;
q.right = p;
}
}

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

let f_ij be the number of distinct subsequences of T[0,j] in S[0,i], then
f_i+1,j = S[i+1] == T[j] ? f_{i,j-1} + f_{i,j} : f_{i,j}

public class Solution {
public int numDistinct(String S, String T) {
// Start typing your Java solution below
// DO NOT write main() function
if(S.length() ==0 ) return 0;
assert T.length() >0;

int[] dp = new int[T.length()];
for(int i = 0; i < dp.length; i++) dp[i] = 0;

for(int i =0 ; i < S.length() ; i++){
for(int j = T.length()-1; j>=0; j--){
if(T.charAt(j) == S.charAt(i)){
dp[j] += j>0 ? dp[j-1] : 1;
}
}
}
return dp[T.length()-1];
}
}

Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).

For any value in loc i in array A, it takes only O(1) time to determine whether it is the median: only need to check whether there are exact amount of numbers in array B that are less than the value.

class Solution {
int[] A;
int[] B;

double median(int A[]){
if(A.length % 2 == 0)
return 0.5 * (A[A.length/2 -1] + A[A.length/2]);
else
return A[A.length/2];
}

double med(int small, int large){
if((A.length + B.length) % 2 == 0)
return 0.5*(double)(small + large);
else return Math.max(small,large);
}

double find(int A[], int B[], int left,int right){

if(left > right) return find(B,A,0,B.length-1);
int mid = left + (right-left+1)/2;
int r1 = mid + 1;
int r2 = (A.length + B.length)/2 - r1;

if(r2 > B.length) return find(A,B,mid+1,right);
else if (r2 < 0) return find(A,B,left,mid-1);
else if (r2 == 0){
if(A[mid] <= B[0]) {
int min = B[0];
if(mid+1<A.length) if(min > A[mid+1]) min = A[mid+1];
return med(A[mid],min);
}
else return find(A,B,left,mid-1);
}

if(B[r2-1] <= A[mid]){
if(r2 > B.length-1){
return med(A[mid],A[mid+1]);
}
else if(B[r2] >= A[mid]){
int min = 0;
if(mid+1>A.length-1){
min = B[r2];
}
else{
min = Math.min(A[mid+1],B[r2]);
}
return med(A[mid],min);

}
else {
return find(A,B,left,mid-1);
}
}
else{
return find(A,B,mid+1,right);
}

}

public double findMedianSortedArrays(int A[], int B[]) {
// Start typing your Java solution below
// DO NOT write main() function
this.A = A; this.B=B;
if(B.length == 0){
return median(A);
}
else if(A.length == 0) return median(B);

return find(A,B,0,A.length-1);
}
}

Populating Next Right Pointers in Each Node

Given a binary tree

struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

From top to down, build link to each level
remember: you have build right pointer of the previous level, so you can access all nodes in the previous level

/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {

public void connect(TreeLinkNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null) return;
TreeLinkNode l = null;
TreeLinkNode p = null;
TreeLinkNode head = new TreeLinkNode(0);

while(root != null){
l = root;
head.next = null;
p = head;
while(l!=null){
if(l.left!=null) {
p.next = l.left; p = p.next;
}
if(l.right!=null){
p.next = l.right; p = p.next;
}
l = l.next;
}
root = head.next;
}

}
}

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Using DP, calculate the minimal path sum from bottom to top.
Using an array to restore the partial result.

public class Solution {
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
// Start typing your Java solution below
// DO NOT write main() function
int height = triangle.size()-1;
int[] ret = new int[height + 1];
for(int i = 0; i<triangle.get(height).size(); i++){
ret[i] = triangle.get(height).get(i);
}
while(--height >=0){
for(int i = 0; i<triangle.get(height).size();i++){
int val = triangle.get(height).get(i);
val += Math.min(ret[i],ret[i+1]);
ret[i] = val;
}
}
return ret[0];
}
}

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

public class Solution {
public int maxProfit(int[] prices) {
// Start typing your Java solution below
// DO NOT write main() function
int ret = 0;
int preFit = 0;
for(int i=1; i<prices.length;i++){
int low = prices[i-1] - preFit;
if(low > prices[i]) low = prices[i];
preFit = prices[i] - low;
if(preFit > ret) ret = preFit;
}

return ret;
}
}

class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int ret = 0;
int preFit = 0;
for(int i = 1; i < prices.size();i++){
int low = prices[i-1] - preFit;
if(low > prices[i]) low = prices[i];
preFit = prices[i] - low;
if(ret < preFit) ret = preFit;
}
return ret;
}
};

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the
stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int ret = 0;
for(int i = 1; i < prices.size(); i++){
if(prices[i] > prices[i-1]) ret += prices[i] - prices[i-1];
}
return ret;
}
};

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

Let preOneSell be the maximum earning if we have only one transaction and we sell the stock at day i
Let preTwoSell be the maximum earning if we have two transactions and we sell the stock at day i

class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int preOneSell = 0;
int preTwoSell = 0;
int maxOneSell = 0;
int maxTwoSell = 0;

for(int i = 1; i < prices.size();i++){
int diff = prices[i] - prices[i-1];
preTwoSell = max( maxOneSell+diff, preTwoSell + diff);
preOneSell = max( preOneSell + diff, 0);

maxOneSell = max(maxOneSell, preOneSell);
maxTwoSell = max(maxTwoSell, preTwoSell);
}

return max(maxOneSell,maxTwoSell);
}
};

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

1
/ \
2 3
Return 6.

Solution:
recursive function, returns the maximum single sided sum, and updates the maximum double sided sum while doing the recursion.

public class Solution {
int findMaxSingleSide(TreeNode root, int[] max){
if(root == null) {
return 0;
}
int left = findMaxSingleSide(root.left,max);
int right = findMaxSingleSide(root.right,max);
int longer = Math.max(left,right);
int result = Math.max(root.val, root.val+longer);

int newMax = root.val;
newMax = Math.max(newMax, newMax + left);
newMax = Math.max(newMax, newMax + right);
max[0] = Math.max(max[0], newMax);

return result;
}
public int maxPathSum(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null) return 0;
int[] ret = new int[1];
ret[0] = root.val;

findMaxSingleSide(root, ret);
return ret[0];
}
}

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

public class Solution {

boolean isAlpha(Character a){
return ('A' <= a && a <= 'Z') ||
('0' <= a && a <= '9');
}
public boolean isPalindrome(String s) {
// Start typing your Java solution below
// DO NOT write main() function
s = s.toUpperCase();
int i = 0;
int j = s.length()-1;

while(i<j){
if(!isAlpha(s.charAt(i))){ i++; continue;}
if(!isAlpha(s.charAt(j))){ j--; continue;}
if(s.charAt(i) == s.charAt(j)){
i++; j--;
}
else return false;
}
return true;
}
}

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

Solution:

Using BFS

public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {
// Start typing your Java solution below
// DO NOT write main() function
LinkedList<String> que = new LinkedList<String>();
Set<String> used = new HashSet<String>();

int ret = 1;
que.add(start);
used.add(start);

int lev1 = 1; int lev2 = 0;

while(!que.isEmpty()){
String t = que.removeFirst();
lev1 --;
// add new values
for(int i = 0; i < t.length(); i++){
String f = t.substring(0,i);
String e = t.substring(i+1);
for(int c = (int)'a'; c <= (int)'z'; c++){
String news = f + (char)c + e;
if(!news.equals(t) && dict.contains(news) && !used.contains(news)){
if(news.equals( end)) return ret+1;
que.add(news);
used.add(news);
lev2 ++;
}
}
}

if(lev1 == 0){
lev1 = lev2;
lev2 = 0;
ret ++;
}

}
return 0;

}
}

Tuesday, March 19, 2013

Merge k sorted linked list

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

One solution is to us a priority queue, or external heap to find the maximal value, coding in java is as follows:

public class Solution {

public ListNode mergeKLists(ArrayList<ListNode> lists) {

// Start typing your Java solution below

// DO NOT write main() function

if(lists.isEmpty()) return null;

Comparator<ListNode> comp = new Comparator<ListNode>(){

public int compare(ListNode a, ListNode b){

return a.val - b.val;

}

};

PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(),comp);

for(int i = 0 ; i < lists.size(); i++){

if(lists.get(i)!=null) queue.add(lists.get(i));

}

ListNode root = null;

ListNode p = null;

ListNode node;

while(queue.size()>0){

node = queue.poll();

if(node.next!=null) queue.add(node.next);

node.next = null;

if(root == null){

root = node;

p = node;

}

else{

p.next = node;

p = p.next;

}

return root;

}

Another solution is directly using the vector storing linked lists as a heap. This is code implemented in C++ using make_heap function

ListNode *mergeKLists(vector<ListNode *> &lists) {
vector<ListNode*>::iterator it = lists.begin();
while(it != lists.end()) {
if(*it == NULL) lists.erase(it);
else ++it;
}
if(lists.size() < 1) return NULL;

ListNode *head = NULL, *cur = NULL;
make_heap(lists.begin(), lists.end(), comp());

while(lists.size() > 0) {
if(head == NULL) head = cur = lists[0];
else cur = cur->next = lists[0];

pop_heap(lists.begin(), lists.end(), comp());
int last = lists.size() - 1;
if(lists[last]->next != NULL) {
lists[last] = lists[last]->next;
push_heap(lists.begin(), lists.end(), comp());
}
else lists.pop_back();
}

return head;
}

class comp {
public:
bool operator() (const ListNode* l, const ListNode* r) const {
return (l->val > r->val);
}
};

int sqrt(int n)

Solution: using newton method:

Solving f(x) = 0, using iterative method: x_1 = x_0 - f(x_0) / f'(x_0).

So the iterative for sqrt(n) is

y = x/2 + N/(2x)

Implementation:

x = 2^ceil(numbits(N)/2)
loop:
y = floor((x + floor(N/x))/2)
if y >= x
return x
x = y

Monday, March 18, 2013

Surrounded Regions

Given a 2D board containing X and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Solution:
Beginning from 'O' in the edge, find all 'O' linked with it. Set all these 'O' to be 't', these 'O's are not surrounded by 'X'

Then set all other 'O' to be 'X' and set 't' back to 'O'.

Complexity is O(mn)

import java.util.*;

class Pair{
int x;
int y;
Pair(int x, int y){this.x = x; this.y = y;}
}

public class Solution {

public void solve(char[][] board) {
// Start typing your Java solution below
// DO NOT write main() function
if(board == null) return;

int n = board.length;
if(n == 0) return;
int m = board[0].length;
if(m==0) return;

LinkedList<Pair> buf = new LinkedList<Pair>();
for(int i = 0; i < n; i++){
if(board[i][0] == 'O') {
board[i][0] = 't';
buf.add(new Pair(i,0));
}
if(board[i][m-1] == 'O'){
board[i][m-1] = 't';
buf.add(new Pair(i, m -1));
}

}
for(int i = 0; i < m ; i++){
if(board[0][i] == 'O'){
   board[0][i] = 't';
buf.add(new Pair(0,i));
   }

   if(board[n-1][i] == 'O'){
   board[n-1][i] = 't';
   buf.add(new Pair(n-1,i));
   }
}

while(!buf.isEmpty()){
Pair node = buf.removeFirst();
int x = node.x;
int y = node.y;
if(x-1 >= 0 && board[x-1][y] == 'O'){
board[x-1][y] = 't';
buf.add(new Pair(x-1,y));
}
if(x+1 < n && board[x+1][y] == 'O'){
board[x+1][y] = 't';
buf.add(new Pair(x+1,y));
}

if(y-1 >= 0 && board[x][y-1] == 'O'){
board[x][y-1] = 't';
buf.add(new Pair(x,y-1));
}

if(y+1 < m && board[x][y+1] == 'O'){
board[x][y+1] = 't';
buf.add(new Pair(x,y+1));
}
}

for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == 'O') board[i][j] = 'X';
else if(board[i][j] == 't') board[i][j] = 'O';
}
}

}
}

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Solution:
Using recursive function, sum(node, val) is the sum of all node to leaf given that the each node to leaf value should be attached val in front.

return sum(root, 0)

public class Solution {
int ret ;

void sum(TreeNode root, int val){
if(root.left == null && root.right == null) {
ret += val* 10 + root.val;
return;
}
val = val * 10 + root.val;
if(root.left != null) sum(root.left,val);
if(root.right != null) sum(root.right,val);
}

public int sumNumbers(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null) return 0;
ret = 0;
sum(root,0);
return ret;
}
}

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

import java.util.*;

public class Solution {
public int longestConsecutive(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
Set<Integer> buf = new HashSet<Integer>();

for(int i : num){
buf.add(i);
}

int start = 0;
int end = 0;
int ret = 0;

while(!buf.isEmpty()){
int v = buf.iterator().next();
start = v;
end = v;
buf.remove(v);
while(buf.contains(end+1)){
buf.remove(end+1);
end ++;
}
while(buf.contains(start-1)){
buf.remove(start-1);
start --;
}
ret = Math.max(ret, end - start +1);
}

return ret;
}
}

Friday, March 15, 2013

Leetcode - Palindrome Partition II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution:
Using F_k denote the minimal partitioning of substring of s from char k to end of s
Then F_k = min_{k<=m < end} {if palindrome(k,m,s), F_{m+1} +1; else +\infty;}
where palindrome(k,m,s) = true if from char k to char m in string s is a sub palindrome.
calculate palindrome(k,m,s) can also be done in O(n^2), by dynamic programming.
The entire complexity is O(n^2)

public class Solution {
public int minCut(String s) {
// Start typing your Java solution below
// DO NOT write main() function
int n = s.length();
int[] d = new int[n + 1];
d[n] = 0;
d[n-1] = 1;
boolean[][] map = new boolean[n][n];
for(int i = 0; i < n; i++) {
map[i][i] = true;
}
for(int l = 2; l <= n; l++){
for(int j = 0; j + l -1 <= n-1; j++ ){
if(j+1 <= j+l-2)
map[j][j+l-1] = s.charAt(j) == s.charAt(j+l-1) && map[j+1][j+l-2];
else map[j][j+l-1] = s.charAt(j) == s.charAt(j+l-1);
}
}
for(int j = n-2; j >= 0; j--){
int sum = n + 100;
for(int m = n-1; m >= j; m--){
if(map[j][m] ){
sum = Math.min(sum, 1 + d[m+1]);
}
}
d[j] = sum;
}
return d[0]-1;
}
}

Thursday, March 14, 2013

Facebook interview question - placing objects

Move Objects

There are N objects kept in a row. The ith object is at position x_i. You want to partition them into K groups. You want to move all objects belonging to the same group to the same position. Objects in two different groups may be placed at the same position. What is the minimum total amount by which you need to move the objects to accomplish this?

Input: The first line contains the number of test cases T. T test cases follow. The first line contains N and K. The next line contains N space seperated integers, denoting the original positions x_i of the objects.

Output: Output T lines, containing the total minimum amount by which the objects should be moved.

Constraints: 1 <= T <= 1000

1 <= K <= N <= 200

0 <= x_i <= 1000

Sample Input:

3 3

1 1 3

3 2

1 2 4

4 2

1 2 5 7

Sample Output:

0 1 3

Explanation:

For the first case, there is no need to move any object. For the second case, group objects 1 and 2 together by moving the first object to position 2. For the third case, group objects 1 and 2 together by moving the first object to position 2 and group objects 3 and 4 together by moving object 3 to position 7. Thus the answer is 1 + 2 = 3.

Solution:

Let i = 1,2,...end denote the loc id, pos_i denote the position of loc i, wei_i denote the number of objects in loc i in the beginning.

f_1(i,j) is the min cost of grouping objects from loc i to loc j together.

f_k(i) is the min cost of grouping objects from loc i to the end into k groups

Then f_k(i) = min_{i<=m < end}{f_1(i,m) + f_{k-1}(m+1)}

class Solution{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = Integer.parseInt(sc.nextLine());

for(int i = 0; i < T; i++){
String line = sc.nextLine();
Scanner lc = new Scanner(line);
int N = lc.nextInt(); int K = lc.nextInt();

line = sc.nextLine();
lc = new Scanner(line);
int[] buf = new int[N];
int k = 0;
while(lc.hasNextInt()){
buf[k++] = lc.nextInt();
}
System.out.println(minNum(N,K,buf));
}
}

public static int numMove(int i, int j, int[] pos, int[] wei){
if(i == j) return 0;
int ret = -1;
for(int k = i; k <=j; k++){
int sum = 0;
for(int t = i; t <=j; t++){
sum += wei[t] * Math.abs(pos[t] - pos[k]);
}
if(ret < 0) ret = sum;
else ret = Math.min(sum, ret);
}

return ret;
}

public static int minNum(int N, int K, int[] buf){
if(N <= K) return 0;
Set<Integer> temp = new TreeSet<Integer>();
for(int i = 0; i < buf.length; i++) temp.add(buf[i]);

int end = temp.size();

if(end <= K) return 0;

int[] pos = new int[end];
int k = 0;
for(int i : temp){pos[k++] = i;}

int[] wei = new int[end];
for(int i = 0; i < wei.length; i++){
int sum = 0;
for(int j = 0; j < buf.length; j++){
if(buf[j] == pos[i]) sum ++;
}
wei[i] = sum;
}

int[][] map1 = new int[end][end];
int[] update = new int[end];

for(int i = 0; i < end; i++){
for(int j = i; j < end; j++){
map1[i][j] = numMove(i,j,pos,wei);
}
}

for(int i = 0; i < update.length; i++){
update[i] = map1[i][end-1];
}

for(k = 2; k <= K; k++){
for(int i = 0; i < update.length; i++){
if(i + k >= end) {
update[i] = 0; continue;
}
int min = -1;
for(int m = i; m <= end -2; m++){
int newvalue = map1[i][m] + update[m+1];
if(min < 0) min = newvalue;
else min = Math.min(min,newvalue);
}
update[i] = min;
}
}
return update[0];

}

}