Pigs get fat, Hogs get slaughtered!
I love this proverb, it tells me the most important business rule.
Saturday, November 19, 2011
Sunday, November 13, 2011
Saturday, November 12, 2011
How to post source code in blogspot
http://vivianningyang.blogspot.com/2009/05/how-to-post-source-code-in-blogspotcom.html
Correlation does not imply causation
http://en.wikipedia.org/wiki/Correlation_does_not_imply_causation
Wednesday, November 9, 2011
smart_ptr vs weak_ptr
http://stackoverflow.com/questions/4984381/in-c-shared-ptr-and-weak-ptr-differences
Thursday, November 3, 2011
Suffix tree
http://en.wikipedia.org/wiki/Suffix_tree
http://mila.cs.technion.ac.il/~yona/suffix_tree/
http://mila.cs.technion.ac.il/~yona/suffix_tree/
Wednesday, November 2, 2011
Rectangle overlap
From Crack a google interview lecture notes.
Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and
returns any pair of rectangles that overlaps, if there is such a pair. Axis‐aligned
means that all the rectangle sides are either parallel or perpendicular to the x‐ and
y‐axis. You can assume that each rectangle object has two variables in it: the x‐y
coordinates of the upper‐left corner and the bottom‐right corner.
Good Answer:
1. Create a sorted array of the x coordinates of the left and right edges of
the rectangles.
2. Then, use a "scanline" to move from left to right through the
rectangles.
3. Keep a binary search tree containing the y coordinates of the top and
bottom edges of the rectangles that overlap the scanline.
For each element of the array, check whether it is a left or right edge.
-If it is a right edge, remove the corresponding top and bottom edges from the BST.
-If it is a left edge, search the BST for rectangles that overlap the current rectangle;
if there is one, return the overlap.
Then, add the y coordinates of the top and bottom edges of the rectangle to the BST.
The search takes O(n log n) time, since it takes O(n log n) time to sort the rectangles
and each of the 2n iterations takes O(log n) time.
Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and
returns any pair of rectangles that overlaps, if there is such a pair. Axis‐aligned
means that all the rectangle sides are either parallel or perpendicular to the x‐ and
y‐axis. You can assume that each rectangle object has two variables in it: the x‐y
coordinates of the upper‐left corner and the bottom‐right corner.
Good Answer:
1. Create a sorted array of the x coordinates of the left and right edges of
the rectangles.
2. Then, use a "scanline" to move from left to right through the
rectangles.
3. Keep a binary search tree containing the y coordinates of the top and
bottom edges of the rectangles that overlap the scanline.
For each element of the array, check whether it is a left or right edge.
-If it is a right edge, remove the corresponding top and bottom edges from the BST.
-If it is a left edge, search the BST for rectangles that overlap the current rectangle;
if there is one, return the overlap.
Then, add the y coordinates of the top and bottom edges of the rectangle to the BST.
The search takes O(n log n) time, since it takes O(n log n) time to sort the rectangles
and each of the 2n iterations takes O(log n) time.
Linear programming: maximal sum of subsequence
maxim_subsequence( int num_arr[]; int size)
{
int sum=0;
int sum_max = 0;
for(int i=0; i
{
sum +=num_arr[i];
if(sum>sum_max)
sum_max = sum;
else if(sum<0) //sum will not contribute to new maximum subsequence.
sum=0;
}
return sum_max;
}
Array rearranging algorithm
/*Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an algorithm to change
this array to a1, b1, a2, b2, ..., an, bn.*/ a1, b1 ok
a1, a2, b1, b2-> a1, a2<->b1, b2-> a1, b1, a2, b2 ok
a1,a2,a3,a4,b1,b2,b3,b4 -> a1 a2 (b1 b2), (a3,a4), b3, b4-> it becomes 2 subproblems of the above
//size of arr_num must be even number
void rearrange(int arr_num[], int p, int q)
{
if ( p == q || g == p+1) return;
int r = (q+p)/2;
//Exchange: (p+r)/2........r<----> r+1......(r+q)/2
for(int i = (p+r)/2; i
{
int temp= arr_num[i];
arr_num[i]=arr_num[r+1+i];
arr_num[r-1+i] = temp;
};
rearrange(arr_num, p, r);
rearrange(arr_num, r+1, q);
return;
}
Tuesday, November 1, 2011
贪吃蛇走法
给一个吸地毯的irobot,和一个长方形的屋子,四面有墙,四个指令:
Bool moveForward()//向前走一格,走不了的话返回false
Void Rotate(int degree)//就是左拐右拐
Bool isClean()//当前单元格是否干净
Void clean()
把irobot 扔在屋子任意位置,写代码让irobot清理房间,每一格都要走过(单元格没有坐标)。
Stack and Queue
Can we implement a Queue using stack(s)?
Can we implement a minimum stack using stacks?
minimum stack has the following operation:
1. push, pop
2. get minimum.
Can we implement a minimum stack using stacks?
minimum stack has the following operation:
1. push, pop
2. get minimum.
What is a good OOD design answer?
1. Classes, subclasses.
2. relationship: is-a, has-a, 1->n, n->n
3. design pattern: singleton, observer, MVC.
4. flexible, extendable, reusable.
i.e. How to design a Parking lot?
2. relationship: is-a, has-a, 1->n, n->n
3. design pattern: singleton, observer, MVC.
4. flexible, extendable, reusable.
i.e. How to design a Parking lot?
Property of bitwise XOR
Can we prove?
number = number XOR number XOR number
This kind of property is useful some problems: odd man out.
number = number XOR number XOR number
This kind of property is useful some problems: odd man out.
Find Two Numbers in an Array that Sum to a Particular Value
//array of integer and a given value, a function to tell if the array contains 2 elements whose sum is equal to the value bool is_sum_num( int num_arr[], int size, int sum) quicksort(num_arr, size); //This part can be optimized in O(n). //Question for reader: how to do it? for ( int i = 0; i
How can we check whether a BT is a BST?
const int MIN_VALUE = -50000;
const int MAX_VALUE = 50000;
bool isValidBST( node *root) {
return isvalidHelper(root, MIN_VALUE, MAX_VALUE);
}
bool isvalidHelper(node *root, int min, int max) {
if(root == null) return true;
if ( root->value < min || !isvalidHelper(root->left, min, root->value)
return false;
if ( root->value > max || !isvalidHelper(root->right, root->value, max)
return false;
return true;
}
const int MAX_VALUE = 50000;
bool isValidBST( node *root) {
return isvalidHelper(root, MIN_VALUE, MAX_VALUE);
}
bool isvalidHelper(node *root, int min, int max) {
if(root == null) return true;
if ( root->value < min || !isvalidHelper(root->left, min, root->value)
return false;
if ( root->value > max || !isvalidHelper(root->right, root->value, max)
return false;
return true;
}
Subscribe to:
Posts (Atom)