drekhi
BAN USERIf the number of elements is constant then the max height of the tree is c = floor(lg n). Basically, what this question is asking is that you perform Insert / Extract-Max operation and prove that it's constant time. Since the max-height is c, which is a constant, you can easily prove an upper bound on the number of operations.
- drekhi May 18, 2010See above ^ for explanation. Here is the code to do this:
TreeNode * ConvertToBST(TreeNode *root)
{
TreeNode *newRoot = root;
while(newRoot->left != NULL)
newRoot = newRoot->left;
InsertUnderNewRoot(root, newRoot);
return newRoot;
}
void InsertUnderNewRoot(TreeNode *root, TreeNode *newRoot)
{
if(root == newRoot)
return;
if(root->right != NULL)
{
InsertUnderNewRoot(root->right, newRoot);
root->right = NULL;
}
if(root->left != NULL)
{
InsertUnderNewRoot(root->left, newRoot);
root->left = NULL;
}
TreeNode *parent = newRoot, *curr = newRoot;
while(curr != NULL)
{
parent = curr;
if(root->key <= curr->key)
curr = curr->left;
else
curr = curr->right;
}
if(root->key <= parent->key)
parent->left = root;
else
parent->right = root;
}
Consider the left most leaf node as the new root node. Now do reverse inorder traversal and one-by-one add each node encountered under the new root node. Insert it like you were inserting in a BST.
Whatever solution you take make sure that for any node in the final tree, *all* the nodes in it's right subtree are greater and not just the right child. Some of the solutions mentioned above miss this. Same thing for vice-versa.
Well it's a "very large" file. The idea is that there isn't as much memory. So holding the complete data structure in memory is not possible.
Just like in External merge sort, you sort chunks of file and write all the sorted chunks to a temporary file. Now in the memory, create k chunks(k = number of chunks in file), although the chunk size in memory is not as big as it is in the file. This is fine since we'd load the remaining data in the memory chunk from the file chunk as we reach the end of memory chunk. Create a min-heap using the top elements (min elements) of each memory chunk. Now just keep Extracting the min element and filling in the heap. Since you are getting all the elements in sorted order, it's easy to keep track of 3 most used keys so far.
function findKclosest(point x, point A[], int n)
{
MAX-HEAP m = new MAX-HEAP(A[1...k])
MAX = m.GetMax();
for(c = k+1 to n)
{
if(Distance(A[c] < MAX)
{
m.RemoveMax();
m.Insert(new Node(A[c], distance(A[c], x));
MAX = m.GetMax();
}
}
m.Print();
}
even though it's O(nlog k) in theory, it performs better in practice (depending upon the distribution of points) because I compare against a MAX variable instead of getting the MAX from heap every time.
- drekhi May 14, 2010There are other ways to do this - i.e., have the time complexity of O(n) and Space complexity of O(n) (remember there is a function stack). How is this the most efficient solution ?
I could just iterate through the linked list, and at the same time create a reverse linked list (without touching the original). Then just iterate both of them and compare elements.
start with top right element
loop:
compare this element(e) with m
i) if they are equal then return its position
ii) e<m then move it to down (if outof bound of matrix then break return false)
ii) e>m then move it to left (if outof bound of matrix then break return false)
repeat the "loop" till u find element or returned false
This will work for M*N matrix(not only for N*N)
Order would be O(M+N), for above case it will be O(2N)
If the graph is not dense (i.e., E is small as compared to V) then you can have a linked list of all the vertices that are connected to any given vertex. If it's dense then you can use a matrix representation where M[i, j] = 1 means there is an edge from Vi to Vj. Following is a compact representation for "undirected" graph:
unsigned char * CreateUndirectedGraph(unsigned int vertices)
{
unsigned char *mem = NULL;
if(vertices > 0)
{
vertices = (vertices*(vertices + 1))/2;
unsigned int count = 0;
count = vertices >> 3;
if(vertices & 0x00000007)
{
count++;
}
mem = new unsigned char[count];
for(int i=0;i<count;i++)
*(mem + i) = 0;
}
return mem;
}
void SetEdge(unsigned int v1, unsigned int v2, bool value, unsigned char *mem)
{
if(mem != NULL)
{
if(v1 < v2)
{
unsigned int t = v1;
v1=v2;
v2=t;
}
unsigned int pos = (v1*(v1+1))/2 + v2;
unsigned int bytenum = pos >> 3;
unsigned char mask = ((unsigned char)1 << ((pos & 0x00000007) - 1));
if(value)
{
mem[bytenum] |= mask;
}
else
{
mem[bytenum] &= ~mask;
}
}
}
Things to consider:
- Copying 32 bits at a time instead of 8-bits. Data bus should be able to handle this much data.
- Memory address misalignment. It speeds things up to copy from addresses that are 32-bit aligned.
- Processor instruction set. For example, some Motorola processors can copy and post increment the pointer with a single instruction.
The recursive / tree solutions listed above require exponential time O(2^(M+N)). However, this problem can be solved in O(MN) time. Start with the cell (M,N) and then calculate the number of paths possible from adjacent cells,i.e., top, left. Go all the way to top left cell convering all the cells one diagonal at a time, running the same logic.
- drekhi May 08, 2010There is a O(N) solution to this problem. Just maintain an array of size 100, A[100]. Now as you progress through the N numbers, if the current number x is smaller than 100 then try to find its complement (100-x)in A (see if A[100-x] == true). If it's there then you have the solution. If not then set A[x] = true
- drekhi May 08, 2010
do a DFS. Store Start/End time stamp for each vertex. After the DFS is done compare timestamps for each pair or vertices to determine if there is a path between them in either direction.
- drekhi May 18, 2010