iatbst
BAN USER1 Hash table:
2 balance BST(red-black tree)
hash versus bst
hash take constant time for lookup/insertion , whereas bst take O(lgn)
bst versus hash
tree support range search , whereas hash don't support any search involved order
and tree is space efficient than hash
My Solution: ( Fasade Design pattern )
idea: Going through different department to handle differenet new employee procedures is pretty inconvenient , so we need to create a interface class to handle all the procedures in one place , so this is a classic senario which Fasade Design pattern is applied .....
Class HR // class to handle procedure in HR department
{
Public:
HR();
~HR();
HR_Procedure();
}
Class Admin // class to handle procedure in Admin department
{
Public:
Admin();
~Admin();
Admin_Procedure();
}
Class Financial // class to handle procedure in Financial department
{
Public:
Financial();
~Financial();
Financial_Procedure();
}
Class Software // class to handle procedure in Software department
{
Public:
Software();
~Software();
Software_Procedure();
}
Class NewEmployee // Interface class to handle all the procedures in different classes
{
Public:
NewEmployee()
{
hr_p = new HR();
fin_p = new Financial();
admin_p = new Admin();
sf_p = new Software();
}
~NewEmployee()
{
Delete hr_p;
Delete fin_p;
Delete admin_p;
Delete sf_p;
}
ProcedureWrapper()
{
hr_p-> HR_Procedure();
fin_p-> Financial_Procedure();
admin_p-> Admin_Procedure();
sf_p-> Software_Procedure();
}
Private:
HR * hr_p;
Admin *admin_p;
Financial *fin_p;
Software *sf_p;
}
Void main()
{
NewEmployee *nep = new NewEmployee;
nep->ProcedureWrapper(); // handle all messy procedures in one place
Delete nep;
}
My solution :
Traversal until find the node, search down first , then return back to root, at every node on the way back, check if the other subtree have some nodes with right distance
// find node which have distance k to root
void FindDistanceK(NodePosition root, int k )
{
if (root == NULL || k < 0)
return ;
if(k == 0)
{
cout << root->Element << endl;
return;
}
FindDistanceK(root->Left, k-1);
FindDistanceK(root->Right, k-1);
}
/*work function: traversal first until find node, search down , then return back to root, at every node *on the back path, check if the other subtree have some nodes with right distance
*/
void DoFindK(NodePosition root, NodePosition node, int k, bool &find, int &updistance)
{
if(root == NULL)
return ;
// find node
if (root == node )
{
find = true;
FindDistanceK(root, k); // find any node below it
return;
}
// go left
DoFindK(root->Left, node, k, find, updistance);
if ( find)
{
updistance++;
if(updistance == k)
cout << root->Element << endl;
else
FindDistanceK(root->Right, k-updistance-1);
return;
}
// go right
DoFindK(root->Right, node, k, find, updistance);
if ( find)
{
updistance++;
if(updistance == k)
cout << root->Element << endl;
else
FindDistanceK(root->Left, k-updistance-1);
return;
}
}
// wrapper function
void FindK(NodePosition root, NodePosition node, int k)
{
bool find = false; // checker to indicate if node is found
int updistance = 0;
DoFindK(root, node, k, find, updistance);
}
a sligth change could fix it....
int min=Integer.MAX_VALUE;
void findMinDeapth(node root,int depth)
{
if(root==null)
return;
if (root.left == NULL && root.right == NULL )
{
if(depth<min)
min=depth;
return;
}
findMinDeapth(root.left,depth+1);
findMinDeapth(root.right,depth+1);
}
My solution : using a stack to reconstruct the tree( assumption: there is NO node which have only one child , in that case, tree's shape is not deterministic )
input is a integer array, positive number means “Node”, negative number means “Leaf”
1 if current cell is N, push tp stack
2 if current cell is L, make it to top’s left child (if no left child yet), otherwise make it as right child
3 if top have two children already, then pop, and make it as new top’s left or right child( left have priority than right, because go through left-right preorddr traversal ), then check the new top, if it have two children alreay, keep popping
// positive number means “Node”, negative number means “Leaf”
NodePosition BuildTree(int *input, int len)
{
stack<NodePosition> stk;
NodePosition temp, root;
for( int i = 0 ; i < len; i++)
{
// current node is “Node”
if (input[i] > 0 )
{
temp = (NodePosition)malloc(sizeof(TreeNode));
temp->Element = input[i];
temp->Left = temp->Right = NULL;
stk.push(temp);
if (i == 0)
root = temp;
}
else
// current node is “Leaf”
{
temp = (NodePosition)malloc(sizeof(TreeNode));
temp->Element = input[i];
temp->Left = temp->Right = NULL;
// save as top’s left child
if (stk.top()->Left == NULL)
stk.top()->Left = temp;
else if(stk.top()->Right == NULL )
// save as top’s right child and pop back
{
stk.top()->Right = temp;
// keep popping until top’s right is NULL
while(stk.top()->Left && stk.top()->Right)
{
temp = stk.top();
stk.pop();
if (stk.empty())
break;
if (stk.top()->Left == NULL)
stk.top()->Left = temp;
else
stk.top()->Right = temp;
}
}
}
}
return root;
}
I think this should work, any advice ? ( make a little change, return max length of '1', no start position )
int LeftOne( short num)
{
int count = 0;
while( num & (short)0x8000)
{
count++;
num <<= 1;
}
return count;
}
int RightOne(short num )
{
int count = 0;
while( num & (short) 1 )
{
count++;
num >>= 1;
}
return count;
}
int MaxContiguousOne( short *input, int len)
{
int max = 0;
int sum = 0;
for ( int i = 0; i < len; i++)
{
if ( input[i] == 0xEEEE )
{
sum += 16;
continue;
}
else
{
sum += LeftOne(input[i]);
if ( sum > max )
max = sum;
sum = RightOne(input[i]);
}
}
return max;
}
External sort + internal Sort
Step 1: partitioning
Divide the original file to k small file, k = original file size / available memory size .
Step 2: Internal sort
Input this small file to memory one by one, sort them and write back. In this case, maybe radix sort is better ( linear time, but linked list is used , overhead is large ), some other tradition sort method is OK.( maybe quicksort is best, it is called “QuickSort” for a reason☺ )
Step 3: Merge
You could chose M-way merge you want, 2 < M <= k ,
Pass = logM k
The key point in this case is to reduce I/O times as small as possible . In every single pass, all files are passed to memory and write back .
Total I/O = 2* Pass * (Blocks number of files )
Which means we need to reduce Pass number. There are 2 ways to achieve this:
1. enlarge M
Note: if M become so large, we’d better employ “Loser tree”, which reduce compare time to logM, otherwise we need to compare M-1 times to find a winner
2. reduce k
We could resort to “Replace-Selection Method” . The rule of thumb is that we could half k .( If we use “Replace-Selection Method”, every initial small file size will be different , to optimize I/O times, a Huffman tree style merge is recommended )
In my opinion, the edges BST have over Hash is its sorted attribute .
1, you could easily get Max, Min from BST,
2, Traversal data in order
3, lookup data in a certain range
etc.
Any way, if the operations you need have some thing to do with order , BST is better. Hash have NO order info saved , you could only lookup one by one ( of course for a single lookup , Hash could kick BST's ass with its super speed ) ....
I guess this code should work, return the first position of '1'....
int TransitionPoint( int *input )
{
int beg, end = 1;
while( input[end] == 0)
{
end <<= 2;
}
beg = end>>2;
return BinarySearch(input, beg, end );
}
int BinarySearch(int *input, int beg, int end )
{
int mid = (beg+end)>>2 ;
if (input[mid] == 0)
return BinarySearch(input, mid+1, end);
else
{
if(input[mid-1] == 0)
return mid;
else
return BinarySearch(input, beg, mid-1);
}
}
I guess this code should work, return the first position of '1'....
int TransitionPoint( int *input )
{
int beg, end = 1;
while( input[end] == 0)
{
end <<= 2;
}
beg = end>>2;
return BinarySearch(input, beg, end );
}
int BinarySearch(int *input, int beg, int end )
{
int mid = (beg+end)>>2 ;
if (input[mid] == 0)
return BinarySearch(input, mid+1, end);
else
{
if(input[mid-1] == 0)
return mid;
else
return BinarySearch(input, beg, mid-1);
}
}
I guess this code should work, return the first position of '1'....
int TransitionPoint( int *input )
{
int beg, end = 1;
while( input[end] == 0)
{
end <<= 2;
}
beg = end>>2;
return BinarySearch(input, beg, end );
}
int BinarySearch(int *input, int beg, int end )
{
int mid = (beg+end)>>2 ;
if (input[mid] == 0)
return BinarySearch(input, mid+1, end);
else
{
if(input[mid-1] == 0)
return mid;
else
return BinarySearch(input, beg, mid-1);
}
}
I guess this code should work, return the first position of '1'....
int TransitionPoint( int *input )
{
int beg, end = 1;
while( input[end] == 0)
{
end <<= 2;
}
beg = end>>2;
return BinarySearch(input, beg, end );
}
int BinarySearch(int *input, int beg, int end )
{
int mid = (beg+end)>>2 ;
if (input[mid] == 0)
return BinarySearch(input, mid+1, end);
else
{
if(input[mid-1] == 0)
return mid;
else
return BinarySearch(input, beg, mid-1);
}
}
Tested, this should work .
int FindRotationPoint(int *input, int beg, int end )
{
if ( beg == end )
return beg;
//edge case : no rotation
if ( input[beg] < input[end] )
return beg;
int middle = (beg+end)/2;
// lucky, find the one, no need further recursion
if ( middle > 0 && input[middle -1] >input[middle] )
return middle;
else if ( input[middle] >= input[beg] )
return FindRotationPoint(input, middle+1, end );
else
return FindRotationPoint(input, beg, middle-1);
}
Have tested, this should work.... suppose this is matrix m*n m<=n
void MatrixSpiral( int matrix[][], int m, int n )
{
int layer = ceil((double)m/2 );
for (i = 0; i < layer; i++ )
{
// edge case, last loop
if (m%2 == 1 && i = layer-1 )
{
//loop1 top, left -> right
for (j = 0 + i ; j <= n-1-i; j++ )
cout << matrix[i][j];
return;
}
//loop1 top, left -> right
for (j = 0 + i ; j < n-1-i; j++ )
cout << matrix[i][j];
// loop2 right, top->bottom
for( j = 0 +i; j < m-1-i; j++ )
cout << matrix[j][n-1-i]
// loop3 bottom, right->left
for(j = n-1-i; j >i; j-- )
cout << matrix[m-1-i][j];
// loop4 left, bottom->top
for(j = m-1-i;j>i;j--)
cout << matrix[j][i];
}
}
2-way merge backward...
Void MergeSort( int a[], int lena, int b[], int lenb )
{
int a_tail = lena – 1;
int b_tail = lenb – 1;
int ab_tail = lena + lenb – 1;
while( a_tail >= 0 && b_tail >= 0 )
{
if ( a[a_tail] >= b[b_tail] )
a[ab_tail--] = a[a_tail--];
else
a[ab_tail--] = b[b_tail--];
}
// if a[] finished first, copy b[] left to a[]
if (a_tail == -1)
while( b_tail >= 0 )
a[b_tail] = b[b_tail] ;
}
This is code for quickselect ( similar technique used by quicksort )
void swap( int *input, int a, int b)
{
int temp;
temp = input[a];
input[a] = input[b];
input[b] = temp;
}
int GetPivot(int *input, int beg, int end )
{
int pivot;
int middle = (beg + end)/2;
if ( input[beg] <= input[end] && input[beg] >= input[middle] )
pivot = beg;
else if (input[end] <= input[beg] && input[beg] >= input[middle])
pivot = end;
else
pivot = middle;
swap(input, pivot, end ); /* put pivot at end */
return input[end];
}
int QuickSelect ( int *input, int beg, int end, int k )
{
// 1 choose the pivot by median of 3
int pivot = GetPivot( input, beg, end );
swap(input, pivot, end ); /* put pivot at end */
// 2 move elements
int i = beg;
int j = end – 1;
while( 1 )
{
while( input[i] <= pivot )
i++; // move right until meet some one > pivot
while( input[j] >= pivot)
j--; // move left until meet some one < pivot
if ( i < j )
swap(input, i, j );
else
break;
}
swap(input, i, end ); // put pivot back
// 3 select recursively
if ( end – i > k - 1 )
return ( input, i + 1, end, k ); // the kth is in the second half
else if ( end – i == k – 1)
return input[i]; // the kth is the one
else
return (input, beg, i – 1, k -1 –(end – i ) ); // the kth is in the first half
}
My solution with a deque ....
deque<int> dq;
int cursor = -1; /* cursor is the index of current node in deque */
void GetVerticalSum( Node *root )
{
if ( root == NULL )
return ;
if ( cursor == -1 ) /* reach left , add elem in deque head */
{
dq.push_front ( root->data );
cursor = 0;
}
else if ( cursor == dq.size() ) /* reach right, add elem in deque tail */
dq.push_back( root->data );
else /* No need to add new elem in deque */
dq[ cursor ] += root->data ;
/* traversal */
if ( root->left )
{
cursor--;
GetVerticalSum( root->left );
cursor++;
}
if ( root->right )
{
cursor++;
GetVerticalSum( root->right );
cursor--;
}
}
My solution: ( level-travel with queue, a stack and a level count is used for spiral sequence ) this is a inplace algo, left pointer serve as previous and right pointer serve as next pointer
in doubly linked list ....
void TreeToDoubleLinkedList ( Node *root )
{
queue<Node *> que;
stack<Node *> stk;
Node *prev = NULL;
Node *current;
int level = 1;
que.push( root );
que.push( NULL ); /* NULL serve as level delimitor */
while ( !que.empty() )
{
current = que.pop();
if ( current == NULL ) /* this level finished */
{
while ( !stk.empty() )
que.push ( stk.pop() ) ;
que.push( NULL );
level++;
current = que.pop();
}
/* process current node */
if ( previous )
previous->right = current ;
current->left = previous;
previous = current ;
/* level 1,3,5,7.... */
if ( level%2 == 1 )
{
stk.push( current->right );
stk.push( current->left );
}
/* level 2,4,6..... */
else
{
stk.push( current->left );
stk.push( current->right );
}
}
current->right = NULL;
}
void AddSibling( Node *root )
{
Queue<int> que;
Node *temp;
Node *previous = root;
Node *levelFirst = root;
que.push( root ); /* Enqueue */
que.push( NULL ); /* NULL serve as level delimitor */
while ( !que.empty() )
{
temp = que.pop() ;
if ( temp == NULL )
{
levelFirst->sibling = previous ;
que.push( NULL );
temp = que.pop();
levelFirst = temp;
}
temp.sibling = previous ;
previous = temp;
if (temp->left )
que.push( temp->left );
if (temp->right )
que.push( temp->right );
}
}
/* BST version */
Node * LCA( Node *root, Node *a, Node *b )
{
if ( root->data > a && root->data > b )
return LCA ( root->left, a, b );
else if ( root->data < a && root->data < b )
return LCA ( root->right, a, b );
else
return root ;
}
/* Non-BST version */
Node *LCA( Node *root, Node *a, Node *b )
{
if ( cover(root->left, a) && cover(root->left, b) )
return LCA( root->left, a, b) ;
else if ( cover(root->right, a) && cover(root->right, b) )
return LCA(root->right, a, b);
else
return root;
}
bool cover( Node *root, Node *x )
{
if ( root == NULL )
return false;
if ( root == x )
return true;
return cover(root->left, x) || cover(root->right, x) ;
}
My solution : ( left subtree : go throught left-right traversal,
right subtree : go through right-left traversal .... )
bool IsSym ( Node root )
{
return CheckSym ( root.left, root.right ) ;
}
bool CheckSym ( Node left, Node right )
{
if ( left == NULL && right == NULL )
return true;
else if ( left == NULL || right == NULL )
return false;
bool ret1 = CheckSym ( left.left, right.right );
bool ret2 = CheckSym ( left.right, right.left );
return ret1 && ret2 ;
}
My solution : 2 pre-order traversals .
void AddSuccessor( Node root , Node node)
{
if ( node == NULL )
return ;
Node succ = node;
FindSuccessor( root, node.data, succ );
if ( succ == node ) /* No successor */
node.successor = NULL;
else
node.successor = succ ;
AddSuccessor( root, node.left );
AddSuccessor( root, node.right );
}
void FindSuccessor( Node root, int x, Node &succ)
{
if ( root == NULL )
return ;
if ( root.data > x && succ.data != x && root.data - x < succ.data - x )
succ = root ;
if ( root.data > x && succ.data == x )
succ = root ;
FindSuccessor( root.left, x, succ );
FindSuccessor( root.right, x, succ );
}
My solution is to use a level-order check . If in certain level, there are several nodes met the BST standard , return the one with biggest size, otherwise go to next level for further check . I use a queue to fulfill this algo, with NULL as level-delimitor .
Node LargestBst ( Tree root )
{
Queue q ;
Node bst ;
Bool start = false ;
int largeSize = 0;
q.Enqueue ( root );
q.Enqueue ( NULL ); /* NULL server as level-delimitor */
while ( ! q.Empty() ) /* Level-Order check */
{
Node temp ;
temp = q.Dequeue() ;
if ( temp == NULL ) /* One level finished , Check out if we have a winner and add NULL
for next level */
{
if ( start == true )
return bst ;
q.Enqueue ( NULL ) ;
temp = q.Dequeue() ;
}
if ( IsBst (temp) ) /* Check out if this node is a BST */
{
start = true ;
if ( Size (temp) > largeSize ) /* Size() is func to calculate BST size */
{
bst = temp ;
largeSize = Size(temp);
}
}
else /* Enqueue its two children for next level check */
{
q.Enqueue( temp->left );
q.Enqueue( temp->right );
}
}
}
My recursive solution is as follow :
Bool IsBst ( Tree root )
{
if ( root == NULL )
return true;
if ( ( root->left == NULL && root->right == NULL ) || /* case 1 */
( root->left == NULL && root->data < root->right->data ) || /* case 2 */
( root->right == NULL && root->data > root->left->data ) || /* case 3 */
( root->right != NULL && root->left != NULL && root->data > root->left->data && root->data < root->right->data) ) /* case 4 */
{
return IsBst( root->left ) && IsBst( root->right ) ; /* current node is OK, check children recursively */
}
else
return false ; /* current node is Bad, return false directly */
}
map is a data structure which store <key, value> pair . The standard opeartion for map is :
- iatbst February 25, 2012insert : insert a new pair in map , duplicated key could not be inserted again
lookup: look up specific pair by key fast
delete: delete pairs
Normally, there are 2 ways to implement map:
1 HashMap : use hash table to implement map, which make constant operation time;
2 TreeMap : use balance search tree to implement map, which make logarithmic operation time ( in C++ STL , red-black tree is employed to implement map and set )
So , in this case, i will say " map is a ADT( abstract data type) , wherease hashmap is a implementation of this ADT , besides hashmap, we could also resort to tree to implement map ...... "