HauntedGhost
BAN USER- 0of 0 votes
AnswersGiven coordinates (X[i],Y[i]) of all the cities in the world(for simplicity lets consider we have 2D world map). You are given a user's location (x,y), find out the closest city to the user. Write code for it.
- HauntedGhost in United States
Update:
Time complexity of the solution should be better than O(n) as there will be multiple lookup queries with different input points.
You can preprocess the data in any way you like, but you need to minimize the query execution time complexity.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven an array of 0s and 1s, find out:
- HauntedGhost in United States
1. all the subsequences where number of 0s = number of 1s
2. max length subsequence where number of 0s = number of 1s
Update:
We need to find subarrays, not subsequences. Sorry for the confusion.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
int minDepth(node *root){
if(root == NULL) return 0;
return min( minDepth(root->left), minDepth(root->right) ) + 1;
}
I think we can do it in O(level of ith cup) also, idea is to calculate the water required to fill ALL the cups till nth level.
Water required to fill 1st level = C
Water required to fill 2nd level = 2C ( because 2 cups are there )
Water required to fill 3rd level = 3C ( 3 cups)
and so on
so water required to fill all the cups till nth level will be:
C + 2C + 3C + 4C + .... + nC = C * n * (n+1) / 2
Ok, now that we are given the cup number i, we can determine its level in O(level) let say L.
Now we need to check how much water is required to fill the cups completely till (L-1)th level.
water_required = C * L * (L-1) / 2;
if( water_required < M ) return 0; // i.e. upper cups are not filled (no overflow)
else {
int water_overflowed = M - water_required;
return (water_overflowed)/ no_of_cups_in_level_L;
}
We can not keep all the user online status in a hash map.. it will simply go out of memory for millions of users.
The idea is to implement a hashmap only, but distribute it across multiple servers just like Distributed Hash Tables (DHT). In DHT, we can setup multiple servers (nodes) and assign them the key space ( for eg. 1-100 user ids in node n1, 101-200 user ids in node n2 and so on) and then to set the online status of a user, you can simple send request any node, it will take care of routing the request to the actual node. Same with the getOnlineFriends status.
I think, this problem can be solved by KD Tree because all the rectangles are non-overlapping. We can split the set of rectangles in half by x and y axis alternatively and construct the tree.
The lookup algorithm would also be same as KDTree. This way you can construct the tree in O(nlogn) and lookup in O(logn).
<pre lang="" line="1" title="CodeMonkey26395" class="run-this">struct node{
int n;
node *left, *right;
};
node *root = NULL;
node *newnode(int n){
node *np = new node;
np->n = n;
np->left = np->right = NULL;
return np;
}
void insert(node *&root, node *np){
if(root == NULL) root = np;
else if(np->n < root->n) insert(root->left, np);
else insert(root->right, np);
}
int height(node *n){
if(n == NULL) return 0;
return max( height(n->left), height(n->right) ) + 1;
}
bool isBalanced(node *n){
if(n == NULL) return true;
if(abs(height(n->left) - height(n->right)) > 1) return false;
return isBalanced(n->left) && isBalanced(n->right);
}
void inorder(node *n){
if(n == NULL) return;
inorder(n->left);
cout<<n->n<<" ";
inorder(n->right);
}
int main(){
//int a[] = {5,2,4,7,8,2,4,67,9,2,3,56}, n = 12;
int a[] = {5, 3, 4, 2, 1, 8, 10, 6, 9}, n = 9;
cout<<"Input Numbers: \n";
for(int i=0; i<n; i++) insert(root, newnode(a[i]));
cout<<"Inorder: "<<endl;
inorder(root); cout<<endl;
cout<<"Height: "<<height(root)<<endl;
cout<<"Is Balanced: "<<isBalanced(root)<<endl;
return 0;
}
</pre><pre title="CodeMonkey26395" input="yes">{5, 3, 4, 2, 1, 8, 10, 6, 9} -> balanced tree
{5,2,4,7,8,2,4,67,9,2,3,56} -> unbalanced tree
</pre>
- HauntedGhost March 01, 2013