Fmars Blog: August 2014

[Leetcode Solution] Jump Game II

Analysis

Let f[x] denote the minimum steps needed to jump to x.

f[y]=min(f[x]+1) if x + A[x]>=y

O(n) algorithm can be found.

if the f[y]=f[x]+1 (x<y and x+A[x]>=y), then any position k ( x<k<y ) won't give f[y] a smaller value

Note

Code

[Leetcode Solution] Permutations II

Analysis

Instead of treating duplicates as different elements, treat them as the same element with different number
Then each element is not at the state of used or not used. Instead, it is how many times can be still used.

Note

Code

[Leetcode Solution]Permutations

Analysis

Depth first search

Note

Code

Analysis

Using sort and compare to check if two string is anagram

Note

Code

Analysis

Using f[x]=f[x-1]*x could exceed the time limits because the range of x is the integer
Using f[x]=f[x/2]*f[x/2] would be fine.

Note

When x is negative, f(x)=1/f(-x). The only thing should be notice is that -INT_MIN==-INT_MIN. This case should be treated separately

Code

A trifle in C++ sort function.

If we want use sort function to sort a vector with self-defined data type, one method is passing a compare function as a parameter to sort.

The very clear details about how to define the comparison function can be found here.

But check the following code to figure out if there is any problem?

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
struct node{
    int a,b;
    node(int aa,int bb):a(aa),b(bb){}
};
bool cmp(node x,node y){
    return x.a<=y.a;
}
int main(){
    vector<node>v;
    v.push_back(node(1,2));
    v.push_back(node(1,2));
    v.push_back(node(1,2));
    v.push_back(node(1,2));
    v.push_back(node(1,2));
    v.push_back(node(1,3));
    v.push_back(node(1,4));
    v.push_back(node(1,2));
    v.push_back(node(1,2));
    v.push_back(node(1,3));
    v.push_back(node(1,4));
    v.push_back(node(1,2));
    v.push_back(node(1,2));
    v.push_back(node(1,3));
    v.push_back(node(1,4));
    v.push_back(node(1,3));
    v.push_back(node(1,4));
    v.push_back(node(1,3));
    v.push_back(node(1,4));
    v.push_back(node(1,5));
    v.push_back(node(2,3));
    v.push_back(node(2,3));
    v.push_back(node(3,4));
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<v.size();i++)
        cout<<v[i].a<<" "<<v[i].b<<endl;
    return 0;
}

It seems good right? However it will lead to segmentation fault.
It is because the comparison function requires the strict order of two items. Thus equal or less equal is not allowed to appear. The reason why is will crash can be talked later.

Comparison between Qsort and Priority_queue

For sort, cmp is a function pointer or comparison object.
However for priority_queue, the comparison is a class template.
Consider the following code.

Unsigned Int

Int and Unsigned Int

No matter what type of data it is, int or unsigned int, it is always stored as a 32 bits binary number in the computer. Thus a int could always convert with a unsisged int. The only problem is whether the convert result is as the same as we expected
This problem might be important because the size_t is the unsigned int type which is the return type of size() function. We use size() function very frequently and if we use it in a loop sentence, always a warning appear if you switch on the compiler option. Thus there is always a implicit conversion from int to unsigned int.
It could be right if all we talk about the non-negative. However if it is a negative number, problem could appear.

i=i+1;

Let's think about this program

#include<iostream>
#include<string>
using namespace std;
int main(){
    int i=-1;
    unsigned int u=100;
    if(i<u)
        cout<<"-1 < 100";
    else 
        cout<<"-1 > 100";
    return 0;
}

The output is "-1 > 100".
Is that weird? Yes it is. Because it is the implicit conversion from int to unsigned it. And -1 will be converted to a big num.

Actually since both int and unsigned int are the store as a binary number in computer, when conversion executed, it is not the actual conversion. It is just another output method. The bit info stored in memory doesn't change. What changed is how you read and parse this data, treat it as whether a int or a unsigned int. Have a look at following code

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    cout<<"2^32="<<(int)pow(2,32)<<endl;
    cout<<"Data type conversion"<<endl;
    cout<<"This is an illustation of how int convert with unsigned int"<<endl;
//unsigned int is directly represented by binary representation
//int is stored in two's complement. Thus if a int has n bits, then the bigget one is 2^(n-1)-1, however the smallest one is 2*(n-1) because the positve part uses one to represent the +0 thus the negative part donnot need to represent the -0.

    unsigned int u;
    int i;

    cout<<"11111...11111"<<endl;
    u=(unsigned int)pow(2,32)-1;
    i=u;
    cout<<"u="<<u<<endl<<"i="<<i<<endl;

    cout<<"10000...00000"<<endl;
    u=(unsigned int)pow(2,31);
    i=u;
    cout<<"u="<<u<<endl<<"i="<<i<<endl;

    cout<<"00000...00000"<<endl;
    u=(unsigned int)0;
    i=u;
    cout<<"u="<<u<<endl<<"i="<<i<<endl;
    return 0;
}

For more details about the two's complement can be found here at wiki
Now we can predict what if we convert a negative int to a unsigned int using the knowledge above

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    cout<<"2^32="<<(int)pow(2,32)<<endl;
    cout<<"Data type conversion"<<endl;
    cout<<"This is an illustation of how int convert with unsigned int"<<endl;
//unsigned int is directly represented by binary representation
//int is stored in two's complement. Thus if a int has n bits, then the bigget one is 2^(n-1)-1, however the smallest one is 2*(n-1) because the positve part uses one to represent the +0 thus the negative part donnot need to represent the -0.

    unsigned int u;
    int i;

    cout<<"11111...11111"<<endl;
    u=(unsigned int)pow(2,32)-1;
    i=u;
    cout<<"u="<<u<<endl<<"i="<<i<<endl;

    cout<<"10000...00000"<<endl;
    u=(unsigned int)pow(2,31);
    i=u;
    cout<<"u="<<u<<endl<<"i="<<i<<endl;

    cout<<"00000...00000"<<endl;
    u=(unsigned int)0;
    i=u;
    cout<<"u="<<u<<endl<<"i="<<i<<endl;
    return 0;
}

So far we're talking about the uselessness. Now the point I want say is, when ever use size() function or use a unsigned int, do remember to check if it has any operation with a int even worse it has a operation with a negative int.
Just think about this code. What will be outputed

vector<int> v;
for(int i=-10;i<v.size();i++)
    cout<<i;

Now we can step further talk about the overflow. Consider the following code

#include<iostream>
#include<climits>
using namespace std;
int main(){
    int i=INT_MAX;
    cout<<i<<endl<<i+1<<endl;
    i=INT_MIN;
    cout<<i<<endl<<i-1<<endl;
    unsigned int u=UINT_MAX;
    cout<<u<<endl<<u+1<<endl;
    return 0;
}

Yes,

INT_MAX + 1 = INT_MIN.
INT_MIN - 1 = INT_MAX.
UINT_MAX+ 1 = 0.

[Leetcode Solution] N-Queens II

Analysis

Note

Code

[Leetcode Solution]N-Queens

Analysis

The problem itself is simply just using a dfs could get the result

Note

The interesting thing happened from the valid check part. It is about the C++ data type conversion of unsigned int, details can be found here

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Maximum Subarray

Analysis

Dynamic Programming problem
Let f[i] denote the the maximum subarray value of the substring ending at i-th element,
f[i] = f[i-1]>0 ? f[i-1]+A[i] : A[i]
Like breadth first search state compress can be used because only the most previous one result is used

Note

Code

[Leetcode Solution]Spiral Matrix

Analysis

Just visited all the nodes in the matrix in a given order and print them
Use a variable dir to represent the current direction used to find the next node. If the next node is not valid, change direction and do it again.

Note

Code

[Leetcode Solution] Jump Game

Analysis

Simply maintain two variables p and q representing the current position and the farthest position where can be reached seperately.
Iterate the p if p<=q, and update q if the further place can be reached from the p

Note

Code

[Leetcode Solution] Merge Intervals

Analysis

Sort the intervals by the start value
Insert intervals while maintain by merge

Note

Never use equal or equal less in the comparison function for sort. Details look here

Code

[Leetcode Solution] Insert Interval

Analysis

Insert each interval in input into the result at the same time merge overlapped ones

Note

Code

[Leetcode Solution]Length of Last Word

Analysis

One pass algorithm
Use two counters denote the length of last word and current word separately. When '0' or '\0' occurs, let last equal to current

Note

Code

[Leetcode Solution] Spiral Matrix II

Analysis

Using the given strategy filing the blanks one by one
Each time fill one blank, then use a direction to find the next blank which needs to be filled. If it is a legal blank, then go ahead. Else change the direction and do the above again.

Note

The direction can be represented by a array.
Change direction can be represented by mod operation

Code

[Leetcode Solution] Permutation Sequence

Analysis

At first think about the search, it should be kind of slow. And actually it exceeds the time limits
The problem is only need to get the k-th element, so we can directly calculate what the k-th element is, rather then enumerate all the elements. The idea is like carry.
If we have n integers [1..n], and the number of permutation starting from each integer is (n-1)!, thus we can calculate the first number of required permutation according to k/(n-1).
Then we can update the k, and do this procedure recursively

Note

Dealing with something like carry, or divide the region, given the each region's size S, and the k-th number, ask which region this number located in. Make the k start from 0 and then use k/S to get it

Code

[Leetcode Solution] Unique Paths II

Analysis

f[i][j]= map[i][j]==0? f[i-1][j]+f[i][j-1] : 0

Note

Code

[Leetcode Solution] Unique Paths

Analysis

Dynamic Programming
let f[i][j] denote the number of unique paths to grid[i][j]
f[i][j]=f[i-1][j-1]

Note

Code

[Leetcode Solution] Minimum Path Sum

Analysis

Dynamic Programming
F[i][j]=min(F[i-1][j],F[i][j-1]) + grid[i][j]
Note the corner condition

Note

Code

[Leetcode Solution] Merge Two Sorted Lists

Analysis

Use two pointers point to the two input linked list
If both pointers are not null, compare the values and link the smaller one at the end of result list
If either one is null, link the other to the result list
If both are null, stop and return

Note

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Add Binary

Analysis

Each time add one digit from A and the corresponding digit from B. Save the carry and remainder. Store the remainder to result string

Note

Two input string might be in different size thus at the addition procedure, only add the digit that the string still has to the result
After all the addition, the carry might be 1. At this time add one more digit at the head of the result to handle it

Code

[Leetcode Solution] Plus One

Analysis

Start from the least significant digit to find the first p that Digits[p] != 9
Plus one to this digit and change the digits from the least significant one to 0 until this digit
If all the digits are 9, then assign the first as 1, change all others as 0, and add one digit 0 at the end

Note

Code

UPDATED AT 2ND PASS

[Leetcode Solution] Text Justification

Analysis

Note

Code

UPDATED AT 2ND PASS

[Leetcode Solution] Sqrt(x)

Analysis

Use binary search to find the square root

Note

Just like calculate the average of two integer, it should use mid = low + (high - low)/2
because of needing calculating mid * mid, mid should be defined as long long
Each calculation must consider the overflow

Code

UPDATED AT 2ND PASS

[Leetcode Solution] Climbing Stairs

Analysis

Dynamic programming
f[i] = f[i-1] + f[i-2]

Note

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Simplify path

Analysis

Use a stack to record the current path hierarchy, each element in the stack correspond to a folder in the path
Iterate the input path string and maintain the path stack. parse the sub string between two slashes

if sub string is /. or empty, do nothing
if sub string is /.. path stack.pop_back
if sub string is a folder name, path stack.push_back

Note

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Edit Distance

Analysis

A Dynamic Programming problem we solve by memorization
Let f[i][j] denote the minimum number of steps to convert word1[1..i] to word2[1..j], then we have

f[i][j] = min { f[i-1][j] +1, f[i][j-1]+1, f[i-1][j-1]+1, f[i-1][j-1] if word1[i]==word2[j]}

Note

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Set Matrix Zeroes

Analysis

Use the first row and first column to store if corresponding row or column contain '0'
Details need attention. First column and first row has one overlapping so use one more variable to store it
After using first row to store meta data, the first row itself could be changed. So first record the original state of the first row, then use it to store meta data

Note

Code

[Leetcode Solution] Search a 2D Matrix

Analysis

Use binary search two times. First search the right row and second search the right column

Search for the biggest element that smaller then target
Search the exact element equals to target

Note

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Sort Colors

Analysis

Note

Code

UPDATED AT LEETCODE 2ND PASS
NOTE:
when swap two elements in an array, if these two elements are the same one, error would happen.
Thus when implement swap function, checking whether two elements are the same is needed UPDATED AT LEETCODE 3ND PASS after been asked this question at FB interview

[Leetcode Solution] Minimum Window Substring

Analysis

O(n) complexity, the first touch is of course the two pointers.
Use two pointers to scan the string only one pass and dynamic update the status.

Say two pointers p and q. Let the substring between p and q is the required window. At the beginning p and q are equal to 0
If the formed window does not contain string T, then move pointer q forward until the window contains string T.
If the q reaches the end of string however still not contain T, then return false
If window already contains the T, move pointer p forward to minimum the size of window. Move pointer p until it is the minimum window that still contains T
Use a hash table to (C++ map) to count the number of each char appeared in T. If the char pointed by p has more number in map then that char appeared in T, then move forward p.

Note

The method count of set, map is only used to test if the element reside in the container rather then the number of reside. Thus the return value of count is always 0 or 1.
Always remember if you want to access a key in a set, if that key is not in the set or map, the access method will insert this key into the set. This might lead to vital fault. So before access a key in set, remember check if it is in the set using count. Otherwise error might occur just like access a null pointer

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Word Search

Analysis

Iterate each node in the matrix to do the DFS and find if the word exist

Note

Code

[Leetcode Solution] Search in Rotated Sorted Array II

Analysis

Almost the same as Search in Rotated Sorted Array
The only difference resulting from the duplicates is we cannot judge if a sequence is rotated by compare the first and last element of the sequence.
So the solution is when the first and last elements are the same, we just move backward of the first index, and do recursively.
So the complexity of the worst case is O(n) now

Note

Code

[Leetcode Solution] Search in Rotated Sorted Array

Analysis

Pretty interesting a problem
Binary search is still available however modification should be added when update the edge at the recursion timing.
There are several conditions needed to be handled separately (Let st,ed,mid denote the start, end and mid index)

If target = A[mid], find it
If A[st] <= A[ed], this is a ordered sequence

if target < A[mid], ed=mid-1;
if target > A[mid], st=mid+1;

If A[st] > A[ed] means this is a rotated sequence

If A[st] < A[mid], all of the first half sequence is the bigger part

If target < A[mid], there are two sub-sequence might contain the target because the first half is the bigger one

If target < A[st], st=mid+1
If target > A[st], ed=mid-1

If target > A[mid], st=mid+1;

If A[st] > A[mid] means that although the sequence is rotated into two part, but the mid element is belong to the original smaller part

If target < A[mid], ed=mid-1
If target > A[mid], there are two sub-sequence might contain the target because the first half is the bigger one

If target < A[ed], st=mid+1;
if target > A[ed], ed=mid-1

Note

Dealing with the binary search, decision whether to use < or <=, > or >= must be very very careful. Like in the termination condition while sentence and condition if sentence. The condition of two variables are equal mush be considered and decide whether to use =.

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Remove Duplicates from Sorted List II

Analysis

Add a auxiliary node at the very beginning of the list
Iterate all the nodes. At each node, detect if the adjacent following nodes is duplicated. If it is, delete all the duplicated ones. If not, move to next node and do the same

Note

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Remove Duplicates from Sorted List

Analysis

Iterate all the nodes. If the next node's value equals to its value, then delete next node

Note

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Maximal Rectangle

Analysis

Take advantage of this problem about how to solve the 1-dimensional problem
Now let's take a look at how to transform this problem to the 1-dimensional one, and then use O(n) algorithm to solve it (n is the number of nodes in the rectangle)

For each column in the matrix, we can treat it as a max rectangle in histogram problem
Let say the second column in the matrix above, we can do such a transformation: each integer in the histogram is the number of consecutive '1' started from each element in this column, then it is

Then the whole 2D matrix can be transformed into several 1D problems. And this procedure can be done in O(n) taking advantage of that we can know the number of consecutive '1' in one place instantly if we know the number of consecutive '1' in the adjacent right place

After the transformation in O(n), we will execute the max rectangle in histogram algorithm several times which equals to the number of columns. Then return the max one.

Note

Code

[Leetcode Solution] Largest Rectangle in Histogram

Analysis

The O(n*n) algorithm is obvious

for each rectangle with the high of i-th element, using two indices move to left and right separately to find the region in which every integer is bigger then i-th element. Then the size of rectangle equals to height of i-th element times the distance between two indices
Based on this idea, O(n*n)is obvious. Iterate all the integer as the height integer, and find the formed rectangle size.

The O(n) algorithm is tricky however the behind idea is the same. The procedure that iterate all the integer and find out the rectangle formed by this integer is still needed. However for different integers, this find out procedure has a lot of common sub problems. So we can take advantage of this to do the O(n) algorithm.

Use a stack to store the integers
If the current integer is smaller then the element at the top of the stack, then push it into the stack
If the current integer is bigger then the element at the top of the stack, calculation needs to be done

The idea is the same
Because the current integer is bigger then the top of stack, thus the rectangle formed by the top of stack cannot contain the current integer but contains the integer before current integer.
Because the second to last integer in the stack is smaller then the integer at the top of stack, so the rectangle formed by the integer of top of stack cannot contain the second to last integer. However it contains the integer after the second to last integers.
At this time, the rectangle formed by the integer at the top of stack can be calculate

Push back a integer 0 at the end of the vector to enforce all the rectangle is calculated.

Note

Code

[Leetcode Solution] Partition List

Analysis

Note

Code

[Leetcode Solution] Scramble String

Analysis

With the same basic idea there are some slight different implementations in details.

Essence is recursion.Let f(s1,s2) denote if s2 is a scrambled string of s1. Then

f(s1,s2)==True iff there is a number i that

f(s1[1..i], s2[1..i])==True
or f(s1[1..i], s2[n-i..n])==True

There are some different implementation in major part like dynamic programming, momeriziation search and recursive search.
And there are some details slight differences.

When doing the search, in the recursion function signature, each time create the new sub-string and passing string itself, or using two indices to denote the start and end position and pass the original string reference. This strategy can reduce half of the running time
Before recursively check the sub-string, first pre valid if it is possible that two string are scrambled string by counting the number of each element appeared in both of the string.This can be done by two means

Sort and then compare
Hash and compare
First method reduce 20% time

Compared with memoriziation search, directly recursive search reduced the searching time which is beyond my expectation

Note

if using memorization, may not passing the hash table as parameter each time, instead, could use a static variable in function

Code

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Merge Sorted Array

Analysis

In-place algorithm
Each time compare one element in A and one in B. Put the bigger one into the target array
In order to avoiding disturb data in A as well as store result in A, combine in descending order and store from the tail of A

Note

Code

[Leetcode Solution] Decode Ways

Analysis

Problem itself is a typical dp problem however the test case could be pretty boring because some of them are weird because if the input string is a encoding message then how could it be a invalid string with 0 ways to decode
Let f[i] denote the ways can be decoded of the first i characters

F[i] = F[i-1] + F[i-2]

//if the number consisted by str[i] and str[i-1] is a valid number

F[i] = F[i-1]

//if the number consisted by str[i] and str[i-1] is not a valid number

Notice the substring "00" appears in the test case which is nonsense

Note

Code

[Leetcode Solution] Subsets II

Analysis

Two methods applied both of which are pretty straightforward

(1) Sort the original array and extract a new array without duplicates but count the number of each element. Then use DFS all possible subset and in each search step, iterate to insert the current element from 0 times to the number of that element times.
(2) Sort the original array and extract a new array without duplicates but count the number of each element. Generate the possible subsets iteratively. At each step, copy all of the previous generated results and insert the current element at the end of each results
Seems that iterative way should faster then recursive way however the running results are opposite.

Note

Code

DFS

Iteration

UPDATED AT LEETCODE 2ND PASS

[Leetcode Solution] Reverse Linked List II

Analysis

Idea is quit straightforward. First find the m-th element. Then reverse the linked list started from m to n. Finally return the head of list
Note the if m could equal to 1 so we add auxiliary node ahead of the list. Then do the reverse without needing to consider if m==1. Finally delete the first auxiliary node and return the next node

Note

Code

[Leetcode Solution] Restore IP Addresses

Analysis

Because the length of input string is supposed to be short, a straightforward dfs could be used
Within the DFS, each time extract next sub string with length of 1 or 2 or 3. If the sub string is a valid number, then search next step.
A valid ip address number could be checked

its integer number is no more then 255
If its length is bigger then 1, then the first character cannot be '0'

Note

str.substr(i,j) cannot be used as a parameter in a function defined as void func(string& str)
The atoi function is used to c string rather then string. So it should be called like atoi(str.c_str())

Code

[Leetcode Solution] Binary Tree Inorder Traversal

Analysis

It's pretty simply by using recursive way to do in-order traversal of the binary tree
There are two ways to do it iteratively

First, using a stack dfs with a state variable for each node to indicate if the left child has been visited. If it is ,then visit this node and then visit the right child sub tree. Else if the left child sub tree has not been visited, set the state variable as visited, and then visit left child sub tree first
Second traversal iteratively with constant space by using Morris in-order traversal which is a pretty tricky solution. It maintains the traversal order by delicate modify the tree and recover the tree back after traverse. The details can be found here

Note

If using a stack to store the traversal sequence of DFS, attention should be paid if the back of stack if frequently modified. Because after pop_back or push_back, the stack.back() might not the ones you expected

Code

[Leetcode Solution] Unique Binary Search Trees II

GREAT PROBLEM

Analysis

Using the same idea with the previous problem "Unique Binary Search Tree" this problem could be solved
Let f[n] denote all of the root node of the unique binary search tree with n nodes, then f[n] is a combination of all of the root as the value of i-th element with all of the possible sub-tree

Note

Code

[Leetcode Solution] Unique Binary Search Trees

GOOD PROBLEM

Analysis

Good problem with tricky idea behind it. Once read this problem one year ago at data structure course but a specific size of n which I solved by handy building up all the unique trees. Today focus this problem I still didn't figure out the solution myself.
Build up the binary tree with the same array of numbers but in different order will resulting into different trees.
Given a sequence with n elements in ascending order to build the binary tree. If we choose i-th elements as the root of the tree, then the problem will be reduced into two sub-problems which aim build up a binary tree with a sequence in ascending order with length of i-1 and n-i separately. This is the key trick of this problem which implies us solving the problem by dynamic programming without doubt
Let f[n] denote the number of unique binary trees can be built with a sequence with length of n. Then

f[n] = f[i-1]*f[n-i] (0<=i<=n)

Note

Code

UPDATED AT 3rd PASS

[Leetcode Solution] Interleaving String

GOOD PROBLEM

Analysis

DP problem
Let bool f[i][j] denote if sub string of s1 with length i and sub string of s2 with length j and interleave the sub string of s3 with length i+j
Then f[i][j]==true iff

s1[i]==s3[i+j] && f[i-1][j] or
s2[j]==s3[i+j] && f[i][j]

Note

Code

[Leetcode Solution] Validate Binary Search Tree

Analysis

Idea is straightforward by using the property that inorder traversal of binary search tree is an ascending sequence

Note

Attention should be paid that when we use INT_MIN as the smallest element as s specific value, some element in the input might be INT_MIN

Code

[Leetcode Solution] Recover Binary Search Tree

GOOD PROBLEM

Analysis

A inorder traversal of binary search tree results into a ascending order sequence
Thus a solution using O(n)space is straightforward. By performing inorder traversal and getting the ascending order sequence, it would be quite easy to find out the swapped elements
A solution using constant space is quite tricky because whether using recursion, the normal inorder traversal needs at least O(logn) space to store the searching status
The trick is constant inorder traversal found here call Morris In-order Traversal using Threading
After having constant space traversal method, we check each element while traversal if it is in a correct ascending order
Another trick is how to deal with the situation that the swapped two elements are adjacent ones

Note

In-order traversal binary tree in constant space

Code

[Leetcode Solution] Same Tree

Analysis

Using recursion
If the value of the root node of two trees are same, and the two pair of subtrees are same, then the two tree are the same.

Note

Code

[Leetcode Solution] Symmetric Tree

Analysis

Using BFS search each layer of binary tree from the root to leaf
Validate if elements in each layer is symmetric
If all the layers are symmetric, then so is the tree

Note

Code

[Leetcode Solution] Binary Tree Level Order Traversal

Analysis

Using BFS search each layer of binary tree from the root to leaf
Print out nodes in each layer

Note

Code

[Leetcode Solution] Binary Tree Zigzag Level Order Traversal

Analysis

Using BFS search each layer of binary tree from the root to leaf
When push back nodes in each layer to the result vector, push back them alternatively in order and reversed order

Note

Code

[Leetcode Solution] Maximum Depth of Binary Tree

Analysis

Using BFS search each layer of binary tree from the root to leaf and the node with biggest layer number is the depth of tree
Directly recursive call the function on both sub tree and return the max result plus one. Found code here

Note

Code

[Leetcode Solution] Construct Binary Tree from Preorder and Inorder Traversal

Analysis

Almost the same as previous problem

Note

Code

[Leetcode Solution] Construct Binary Tree from Inorder and Postorder Traversal

Analysis

Inorder traversal is a traversal scheme that first visit the left child node and then visit the parent node and finally visit the right node
Postorder traversal is visit the parent node and last
Given inorder traversal sequence and postorder traversal sequence, we can first find out the root node which stored at the end of postorder traversal sequence
Then according to finding the position of root node in the inorder traversal sequence, we can separate the sequence into two parts which are nodes belonging to left sub tree and right sub tree separately.
Have the length of each sub tree, we could also extract their postorder traversal sequence at the postorder traversal sequence of root node
At this point, we can build the two sub tree recursively and then point the root node child pointers to them.
The recursion termination condition is when the traversal sequence is empty

Note

Code

[Leetcode Solution] Binary Tree Level Order Traversal II

Analysis

Perform BFS on the binary tree layer by layer stored by two vector alternatively
Print the nodes within one layer separatively

Note

Code

[Leetcode Solution] Convert Sorted Array to Binary Search Tree

Analysis

Using recursion build up the sub tree then build up the tree

Note

Code

[Leetcode Solution] Convert Sorted List to Binary Search Tree

Analysis

Idea by using recursion.
For converting a sorted list to binary search tree, firstly find the middle item in the list.
Then recursively convert the first half list and second half list to two binary search tree separately.
Finally create a new node with value of the middle item and each child pointer pointing to the two binary search tree built recursively before.

Note

Code

Panasonic Interview FullTime 08.20.2014

After last time internship interview, because cannot part time at next quarter, so they directly scheduled this full time interview today
The entire interview process was definitely beyond my expectation because of the communication is totally different with any other interview before. Maybe it is because my English skills did improve a lot. Or maybe both interviewers are foreigner speakers so they won't talk too quickly. But all way, it was a unprecedented pleasant interview experience.

The first interviewer was a Indian female software engineer about ten year older then I but looks pretty shy and really friendly. All about some typical technical questions.

What is virtual function, how it is implemented at run time
What's the use of virtual destructor function
What the difference between free and delete
What design patter are you familiar with? MVC and single instance. So talk about how single instance implemented
Do you have multi-thread programming experience? So how to you synchronize two thread? Bull shit a lot about the memory consistence course and protocol. Review the cs295 about memory consistence and cs250 advanced architecture
What the difference between thread and process.
Swap two string pointers
The performance of your database system
After the technical interview on the way to manager's office, we talked about the status of international student. Talked about the weather of California and her hometown

The second interviewer was the manager here a middle aged Indian man who was really really voluble. Roughly 70 percent of the interview was chat. Asked about some very typical manager's questions and one programming question. Rest of the time was talking about his story. I think he tried to help me know something. I think he did it.

Describe everything of yourself to show me why should I hire you

my answer was nothing fascinating or interesting just plainly talked about everyone can say

What's your goal in 3 or 5 years. Do something else or start up your own company. Stay here or go back China.

want to be best in a tiny field

Why did you come to America?

The latest technology
maybe can talk about the difference of salary and the conversation talked with James to show that it's not the reason of any individual but the whole industry chain

Talked about English. If I know English before America, why.

Learn latest skills read bloggers and read the original textbooks because the translation
talked about why speaking is important

Why do you choose UCI

Ranking and Locality

Why do you choose computer science this major
Talked about his story. He told me that anxious is fine, everyone would be anxious when he enters the interview. But don't be afraid. Try everything you could to grasp the chance. Just think about the worst case. He said 20 years ago when he came to America himself, the college student association forgot to pick him up from airport. So he seat at airport all the night and then toke a taxi to the school himself. At that time he just thought about the worst case was airplane crashed during the trip. However he was been there safely which is already enough.
Asked about the advantage of using recursion and pop with a very straightforward recursion programming problem and required me to write the code on white board and talked about it
Asked if I have any question. However I have no idea

ePacket Interview 08.19.2014

ePacket which I thought is a normal start up as usual, however it is not at least from my perspective. Actually it's more like a very potential technology company founded by top university students. Of course it is still a start up but a very unusual one.
The interviewer is a Stanford student in EE and obviously he found no interests on me.

On the one hand I downplayed this interview just treated it as a trial for my full time interview. In fact I'm not ready to start and this interview leaded from a mistake application which I original wanted to apply internship. I didn't know what this company do even before one hour ahead of the interview
On the other hand, maybe even if I'm fully prepared both in skills, projects and interview skills, he would still have no interest on me because he is scouting someone much more smart and at least at a top university like Stanford.

But no matter the result is, it doesn't matter, what matters is what I learned from it

As usual, start with a self description

better put algorithm and data structure ahead of the low level knowledge which actually I cannot say I know a lot. Don't say anything like what you are interested in or what you are good it if you cannot convince interviewer by evidence and facts.
Must review of last quarter's advanced architecture class. It deserves it.

What field you mainly focused on during your college

The algorithm and data structure is the only field I'm not afraid of being ask any question, so talk it as much as possible and dominant the conversation
This question needs still consideration
If you said you are interested in architecture or network, it's very likely that be asked about what have you done or researched on. So if just one project, I'd better don't say like that.

Talk about your projects experience. What they want to hear is what difficult problems you solved or what improvement you did rather then plainly describe what you did or what you implemented. This is very important. Don't make your description boring without any useful information

First at all, review what has been implemented and what has been solved in each project
Package each project, extract the featured and highlighted part. Think about how to show them
For the system kernel, the obvious key is to show how did I debug the program. If said that the original simulator is not powerful enough, it is very likely asked that did you improve that?
For the PIMDM show the architecture of the job, the complexity is the featured point of this project
About the database management system, try to think out what problems you have solved.

For example today I was asked that in the B+ tree layer if the data store both in memory and disk, the time latency is significant, how do you solve it.
Review about the bug that runs different result on mac and linux about the memcpy error leading from the address overlap
What they want to know is not plainly description. They want to know the stuff exactly like this.

Asked about my research experience

Shit answer

Asked about explaining the most proud project or maximum project is size and what is your role that what you did in the project

my answer is the database system. However I just cannot clearly specify what is my role because the fact is that we almost did the project together and separated the project evenly. This needs consideration.

At last asked if I have any question about the company

Tree

If the depth of the tree are involved, attention should be paid to distinguish the edge condition is

p==NULL
p->left==NULL && p->right==NULL
see also

My Blog List

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

A trifle in C++ sort function.

Comparison between Qsort and Priority_queue

Int and Unsigned Int

Analysis

Note

Code

Analysis

Note

The interesting thing happened from the valid check part. It is about the C++ data type conversion of unsigned int, details can be found here

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Never use equal or equal less in the comparison function for sort. Details look here

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note