P
BAN USER- 0of 0 votes
AnswersConsider a cloak room. It has 3 compartments, small, medium, large
- P in India
1 medium = 2 small
1 large = 2 medium = 4 small
Design such a system, ensuring maximum capacity optimization of the compartments. Also, make the required number of moves (in-btw compartments) as minimum as possible.
Write class, functions. Wht functions will u expose. What token will you return back to the user.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Application / UI Design - 0of 0 votes
AnswersGiven pre order traversal of a tree. It has only 2 type of nodes, N & L (non-leaf, leaf).. Also, every node either has zero or two children.
- P in India
Produce the tree.
Eg: Pre-order NNLLL
Tree;
N
/ \
N L
/ \
L L| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersGenerate all the possible substrings using the characters of a given string. Write code. (The order of chars do not matter, i.e., ac <=> ca)
- P in India
i/p: abc
o/p: { a,b,c,ab,ac,bc,abc}
<Modified the language of the question, to avoid any confusions>| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a set of strings (large set), and an input string, you need to find all the anagrams of the input string efficiently. What data structure will u use. And using tht, how will u find the anagrams.
- P in India for Bing| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 1of 1 vote
AnswersGiven an array of 0's and 1's, and a number k, find the minimum window that contains k 0's. Write code.
- P in India for Bing
Extension, now the array contains integers from 0 .. 9 ... and another input array of size 10 is given, that contains the number of occurances of a digit. Find the min window that contains the given no of occurance for each digit.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersCOnsider the column names given in microsoft excel. A .. Z, AA ... Az, BA .... BZ, .......... ZZ, AAA, ..... and so on.
- P in India for Bing
Given a column name (string of charectors), find the corresponding number.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - -1of 1 vote
AnswersGiven an integer, and a number k, do a cyclic shift (left / right) by k bits of the number.
- P in India for Bing| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersDesign an online movie booking system
- P in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersGiven the number, find the immediate next (larger) palindrome
- P in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 2of 2 votes
AnswersDesign a data structure where the following 3 functions are optimised:
- P in India
1. Insert(n)
2. GetRandomElement()
3. Remove(n)
Write a class, and implement the functions. Give complexity of each of these ..| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Application / UI Design
in here,
(num << k) | (num >> (sizeof(int) - k));
when u do num << k, then aren't yo u already loosing the k bits ? since, it will pad them with 0's. So when it reaches (num >> (sizeof(int) - k), num is changed already, with k bits lost ! So,, wont be a cyclic shift.
Am I missing something ?
yes this is the logarithmic approach. The only difference is, in a binary approach, you discard half of the input size in every pass, whereas in this one, you are discarding only 1/4th of the input in one pass. so it will log base 4 (which is a constant times log base 2). and O(log (n*n)) is same as O(log(n)) ...
- P January 24, 2012Well, here is the algo i told.
1. Find the first window. Let start and end be the index of this window.
-- Width = end - start
Keep a min_width variable.
2. Now to find the next window, move the start pointer to second zero in the first window. now from start to end, we already have k-1 0's, we just need to find one more 0 after end. Find this zero, and set the end pointer to this index. this is the second window. set min_width as applicable (if this width is less than the prev width)
3) Keep on doing this, untill end reaches length - 1.
4) Return min_width
O(n) and in-place approach
I would answer smthing like this:
N lifts,
(Roughly)
M lifts that go to all floors.
N/2 - M/2 only for even floors
N/2 - M/2 only for odd floors
And say,
(both will go to ground floor and basement)
Now what N & M should be ? 75 floor building. If its a office building, perhaps, too much of movement.
On avg, smooth would be, one lift to cater to say 3-4 floors.
So, N = 75/3-4 = (rougly) 20
So, for M, required when one wants to go from odd to evn or vice versa. Around 2.
(if distance is large, I'd prefer going to nearest even / odd floor, and then take stairs for one floor. )
SO, estimate is 9 lifts for even floors, 9 lifts for odd floors, and 2 lifts tht go to all floors !!
I didn/t understand. could you pls take an example and give step by step explanation?
--> If you add 3 when a number is encountered and subtract 1 if not and only change a number if count hits 0 then you will get your answer.
What is this for> I dont think it'l help.
a) Find the number of nodes in each tree. treeA (n1), treeB (n2)
b) Find min(treeA), max(treeA), min(treeB), max(treeB) {O(n1 + n2) Worst case)}
c) The root of the merged tree, should be such that if n1 and n2 values were to be arranged in asc order, then root will be at index (n1+n2)/2 (To ensure it is balanced)
Using the info in step 1 and 2, we can find which tree this newRoot will lie in , and we can also find the node.
4) Delete this node from the tree. (O(log n)
5) Now traverse treeA in post order, delete the node from treeA, by setting the node's left and right pointers to null. Add it in the tree with the root as newRoot.
(Pls note that we are not creating any new node, but only changing pointers
6) do the same with treeB
Complexity: O((n1 + n2) log(n1 + n2))
worst case (O (n1 + n2)^2)
Constant space
void PrintKDiff(int [] A) {
int i = A.length - 2;
int j = A.length - 1;
//j always runs behind i
while ( i >= 0) {
if (i == j)
i--;
else if (A[j]-A[i] < k)
i--;
else if (A[j] - A[i] == k) {
print (A[i], A[j]);
i--;
j--;
}
else if (A[j]-A[i]> k)
j--;
else
//Should never reach here
}
Ex: k = 2
A[] = {2,3,5,10,12,13,15,16,17}
Yes, thiss seems correct. Thinking on the implementation part,
We will required to perform mod ops by nos 2,4,8,16, .. etc .. (powers of 2, sinc ewe always dived the sets into 2) .
If we can identify in the first go, which mod it will max require. We can do this in one shot. for N between 8 and 16, mod 8 will be required.
For a general N, we need to find the smallest n, such that, N <= 2^n
So, we can direct start placing them, in the array like,
0 mod n --
1 mod n ..
... till n-1 mod n ..
This is done in O(N) time and constant space.
Let me know if thr is somthing wrong here ..
Nice approach btw :)
The offset solution by lyra_vega, is a decent one.
Just thinking, can TRIE help here ? Given, that no of integers are huge, and span a large range. Whenever a number ends, we can append a diffrent kind of node, say, "EndNode", then also tells the number of occurance of that number, in addition to indicating the end of a no, on the path.
For this to be worth, the nos should be large enough. As in, if there are mostly 2-3 digits nos present, then this dosnt make much sense, since space will be taken up by pointers as well.
If however, the no of digits are large, then this makes a worthy soln.
How to improve if there are only two arrays and one is much smaller compared to the other?
-- Say sizes are , m (A[]) and n (B[]), m << n
Sort smaller array, A. For every element in B, search this in A. COmplexity O(nlogm+mlogm) = O((n+m)logm), if m<<n, then this is almost O(n). (Assuming, the arrays are not sorted.)
If they are already sorted as given,
O(nlogm) (We can use modified bin search, where the array to be searched in keeps decrasing by the x, where x is index of last found intersection), wiht a termination condition, whenever A[last_elem] < B[i]. Very close to O(n)
How to distribute this on a set of different machines?
--Map Reduce.
Divide the input data (total size, n) into k parts. -> k mappers -> Every mapper will find intersection of n/k sorted arrays.
Reducer will then combine the results from these k mappers and produce final output.
Basically you take advantage of parallelism. It is only recommended for large data sets, since it involves network latency. For small data sets, this might actually increase the total running time, because of several latencies involved
@eugene ..
If I cunderstood your approach correctly .. then u are dividing odd numbers into 2 groups, where avg of one grp lies in other grp (in case where avg(odd, odd) = odd)
... If you notice ... this approach fails after a certain no of off nos ..
group1 | group2
1 | 3
5 | 7
9 | 11
13 | 15
.. etc ..
group1 -> 1 modulo 4
group2-> 3 modulo 4
in grp1 avg(1,9) = 5, which is present in the same group, due to which this approach fails for total no of odd numbers > 4
let me knw if u were trying to propose something else ..
Okay, so after a lot of thinking, I guess I could finally crack it ..
The idea is ... if we have two BSTs, we can merge them in-place, by just changing the pointers.
A tree with a single node is a BST.
1) Travel to the left most leaf node, keeping a pointer to its parent. make this node as new root of the BST that we are going to build. and set parent->left = null;
We can take any leaf node. I'm not checking of diff cases, where say is tree is right skewed. If someone can take the initiative of adding that code .. I'l be grateful :-)
node* getNewRoot(node* root){
node* parent = root;
node* newRoot = root->left;
while(!((newRoot->left==null)&&(newRoot->right ==null))) {
parent = newRoot;
newRoot = newRoot->left;
}
parent->left = null;
return newRoot;
}
2) Traverse the remaining binary tree in port-order. and keep inserting nodes in the BST with newRoot as root. The key is, after you insert a node in the BST, set its left and right pointers to null, so that this node is 'removed' from the old tree.
void convertIntoBST (node* curr){
if(!curr)
return;
convertIntoBST(curr->left);
convertIntoBST(curr->right);
InsertintoBST(newRoot, curr);
curr->left=null;
curr->right=null;
}
void InsertIntoBST(node* root, node* curr){
while(!((root->left == null)&&(root->right == null))) //iterate until root is not leaf node
{
if(root->val > curr->val)
root = root->left;
else
root = root->right;
}
if(root->val > curr->val)
root->left = curr;
else
root->right = curr;
}
This converts the same binary tree into a BST, by changing the pointers. No new node is created.
How ever time complexity is larger than O(n). Can someone tell what ?
Yes, so now we know the N nos among which the median lies. But these N nos are not sorted.
We need to find N/2th (or N/2th and N/2 + 1 th) elment among these N nos.
If we apply order of statistics algo, we can find it in O(N).
Or we can choose to sort and get it in O(NlogN) which is much better than O(N^2) (N^2 is the total no of elements).
Good one .. :)
void Remove(string& s1, string& s2) {
char *p1 = *p2 = s1;
char *p3, *p2temp;
int len = strlen(s2);
while (p2 != '/0') {
p3 = s2;
p2temp = p2;
count = 0;
while (*p2temp++ = *p3++)
count++;
if (count == len)
p2=p2temp;
*p1=*p2;
p1++;
p2++;
}
//Discard rest of the string
*p1 = '/0';
++p1;
while(p1!='/0')
free(p1++);
}
Complexity: O(len(s1))
Can we do something like
(H=1, T=0)
Append one extra H (1) at the beginning of the string ..
then convert this into decimal ..
send this number ..
At B: Convert it into binary and discard the first 1, convert all 0 and 1 to T and H ..
Am I doing something wrong here ?
I would do something like this:
1) Store the data like,
starting time - duration of the meeting (can use a map)
So,
8 - 3
12 - 3
15 - 3
2) Sort the input based on starting time
8 - 3
12 - 3
15 - 3
If two entries are same, then keep only the entry with largest duration.
(Eg.
If data is:
8-3
12-1
12-2
12-3
15-3 ..
then keep
8-3
12-3
15-3 ..)
3) Check for 'edge' cases:
Biz hrs: 8 - 18
read first entry: (8-3)
Cant be scheduled in the morning:
read last entry (15-3)
18 .. Cant be scheduled in the evening. Continue.
4) Now make a fresh pass, starting from 0th element
for(i -> 0:N-1)
Calculate finish time of current entry: finish_time(i)
if (start_time(i+1) - finish_time(i) >= desired_duration
return yes
else
continue
After coming out from the loop
return no
Good point.
Lets see how can we use that.
First time, we know the first elements is A[0][0].
Then we need to companre A[0][1] and rest N-1 elements N-1 cols (A[1][0] ... A[N][0]) .. We just need to compare A[0][1] with A[0+1][0] (since in A[1][0] ... A[N][0], A[1][0] is the smallest) ..
The idea is, we just need to compare the values that have different column number, .. which should be done in constant time (since you can always find the smallest among N values in O(N)) ..
Will try to come up with pseudo code ..
Complexity (for original algo, which I guess I got wrong): M = N^2
O(M*N)
Is it not a merge sort, where we are given N sorted arrays and need to find the median of N arrays compbined?
Just run the merge sort algo, keeping a variable count, where count at any point gives the no of elements in the merged array.
PN: We are not storing the merged array, just keeping a count. Hence no extra space.
Stop when count = N^2 / 2. Return this value.
(only for odd numbers .. for even numbers, take both values n^2 / 2 and N^2 / 2 +1)
O(N^2 / 2) in constant space
Should be O(2^n) .. since overall there will be 2^n such substrings
- P January 31, 2012