Naveen Reddy Mandadi
BAN USER- 3of 3 votes
AnswersThere are exactly N advertising boards on the highway. Now a company want to advertise on some of these advertising boards (each advertising board costs some money).
- Naveen Reddy Mandadi in United States
Company strategy is that, they want at least 'K' advertisement should be there among M consecutive advertising boards. But at the same time Company want to pay minimum for its advertisement.
Now, what is the total number of ways Company can advertise meeting its minimum cost strategy.
Also 1 <= K <= M <= 50 and M <= N <= 10^9
As for Example: N = 3, M = 2, K = 1 ==> there is only one way for minimum cost, ie. 0C0 , where '0' denotes No company advertisement, and 'C' denotes company advertisement board.
Similarly, for N = 4, M = 2, K = 1 ==> there are 3 possible ways, ie. C0C0, 0C0C, 0CC0.| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 0of 0 votes
AnswersManage n queues in a given memory.
- Naveen Reddy Mandadi in India
Support below operations on queues.
//initialize n queues in memory m of size s
//queues will be identified with numbers from 0 to n-1
void initialize(void* m,int s,int n);
//enqueue object o into queue identified by q
//as long as there is free memory this should be successful
void enqueue(int q,Object o);
//dequeue an object from queue identified by q
Object dequeue(int q);
Give the best solution such that there will be minimum relocation of queues| Report Duplicate | Flag | PURGE
Microsoft Applications Developer Algorithm - 0of 0 votes
AnswerDesign a system for the customer to review a product. It should be able to incorporate web-services. Describe the entire flow from the client to the database.
- Naveen Reddy Mandadi in India| Report Duplicate | Flag | PURGE
Amazon Applications Developer Computer Architecture & Low Level Data Structures Application / UI Design - 0of 0 votes
AnswersConvert binary search tree to doubly linked list
- Naveen Reddy Mandadi in India| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 0of 0 votes
AnswersGiven list of words in the order as in the dictionary, find the order of the alphabets.
- Naveen Reddy Mandadi in United States
Suppose you are given words in the same order as in the dictionary like a, ant, ball, cat, do, dog, fog, frock etc.
From these words you know that there are alphabets a, n, t, b, l, c, d, o, g, f, r, k.
You don't know the order of these alphabets before hand.
You will have to find the order of these alphabets based on the order of the given words.
From a and ant you cannot make out anything.
From ant and ball you can make out that a comes before b in the order.
From ball and cat you can make out that b comes before c in the order.
From cat and do you can make out that c comes before d in the order.
From do and dog you cannot make out anything.
From dog and fog you can make out that d comes before f in the order.
From fog and frock you can make out that o comes before r in the order.
From these clues you should make out the order of the alphabets.
Not necessarily you will be given all the dictionary words, but the words which are sufficient enough to make out the order of the alphabets.
You can always say you cannot make out the order if the words given are not sufficient.| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 0of 0 votes
AnswersRemove all two zeros in the given string.
- Naveen Reddy Mandadi in India
Example: a3409jd00dk000d
Output: a3409jddk000d
Note: If there are less/more than two zeros consecutive, it should not be replaced.| Report Duplicate | Flag | PURGE
Microsoft Applications Developer Algorithm - 0of 0 votes
AnswersMultiply two large integers represented in char array.
- Naveen Reddy Mandadi in India| Report Duplicate | Flag | PURGE
Microsoft Applications Developer Algorithm - 0of 0 votes
AnswersFind level wise linked lists in a BST.
- Naveen Reddy Mandadi in United States
Example: 1 has children 2 and 3
2 has children 4 and 5
3 has children 6 and 7
6 has children 8 and 9
then the algorithm should give the below
result[0] = 1
result[1] = 2->3
result[2] = 4 -> 5 -> 6 -> 7
result[3] = 8->9| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 0of 0 votes
AnswersFind common ancestor of two nodes which has least value.
- Naveen Reddy Mandadi in India| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 0of 0 votes
AnswersThere are n nodes with a value in each node.
- Naveen Reddy Mandadi in United States
Communication between two nodes can happen any time to pass the node value from one to the other, every communication takes 1 second.
Whenever communication happens from node a to node b, node b's value can be changed based on node a's value.
One node cannot participate in communication to two other nodes at any point of time.
At any point of time each node can hold only one value.
We need to end up with "sum of the values in all the nodes" as the value in all the nodes, how much time is required?| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 0of 0 votes
AnswersReverse double linked list
- Naveen Reddy Mandadi in India| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm - 0of 0 votes
AnswersMerge two sorted arrays
- Naveen Reddy Mandadi in India| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm
In case the data is complex we would need to escape braces "{", "}" and comma "," in the text and un-escape at the server.
- Naveen Reddy Mandadi January 26, 2014I would send to the server in the in-order format {{1, 2, {3, 4, null}}, 5, {7, {null, 8, 6}, 9}}, there will be 3 elements in the curly brace representing left, root and right, you can as well put them as left, root, right for easier construction of tree on the server. On the server we would construct a tree using the java class, so that it will be easier for other operations on the tree.
- Naveen Reddy Mandadi January 26, 2014Can you describe what would be that approach?
- Naveen Reddy Mandadi May 29, 2013So what is the answer, can you give a formula?
- Naveen Reddy Mandadi May 27, 2013What is start variable doing in your program by the way?
Your program tells that you are adding mCk n-m-k times, even then your program is not efficient, you could have multiplied mCk with (n-m-k) to get the answer instead of having loop.
Most importantly how do you prove this is right?
Your program runs into infinite loop for 5, 5, 1, even if you correct your infinite loop by changing end != n to end < n it would return 0, but the answer is 5.
What is start variable doing in your program by the way?
Your program tells that you are adding mCk n-m-k times, even then your program is not efficient, you could have multiplied mCk with (n-m-k) to get the answer instead of having loop.
Most importantly how do you prove this is right?
Your program runs into infinite loop for 5, 5, 1, even if you correct your infinite loop by changing end != n to end < n it would return 0, but the answer is 5.
What is sequence_length by the way? Is it N/M? How did you come to the conclusion of 2^sequence_length? Not every 2 combinations can be beside each other, consider for example xx00 and 00xx, if we take them both together we are left with 4 zeros in between without any x which is violating the requirement of minimum K. Similarly it is not necessary that you take the same combination beside each other, consider for example 0xx0 and x0x0, if we take them both together it is a valid solution, also you notice that 2nd position to 5th position there are 3 x.
- Naveen Reddy Mandadi May 27, 2013This is exponentially complex. Can you try calculating value for N = 10 ^ 9, M = 1 and K = 1.
- Naveen Reddy Mandadi May 26, 2013This is exponentially complex. Can you try calculating value for N = 10 ^ 9, M = 1 and K = 1.
- Naveen Reddy Mandadi May 26, 2013Can you test this program for N = 10^9, M = 2, K = 1
- Naveen Reddy Mandadi May 26, 2013To calculate each combination it is O(n) complexity, to validate each combination is again O(n) complexity and therefore complexity of your logic would be n*nCp which is a huge value for n = 10^9, m = 2 and k = 1.
- Naveen Reddy Mandadi May 26, 2013First i proposed brute force method of checking all the combinations (Time Complexity: 2^N) but he asked for a better solution, then i proposed the below solution.
Please note from here on wherever i mean N / M, i actually mean floor value of N / M.
To get the minimum number of boards required we can calculate in greedy method, where we will have to select K boards (all the remaining boards if there are no K boards) after every M - K boards, which gives us as below.
min_boards = (N / M) * K if N % M <= M - K
= (N / M) * K + (N % M - (M - K)) otherwise
There are 4 different cases possible as listed below.
Case 1: N % M = M - K
Here the only arrangement possible is ----XXX----XXX----XXX---- for 25, 7, 3
Since the first M elements should have K selections, you can only arrange K selections among those M elements, the same applies for all successive M elements.
If you have to get a different combination for the last group (15 - 21 elements in the above example) you will have to remove at least one of the selection from the K selections, in which case the last M elements (19 - 25 elements in the above example) will lose a selection in which case minimum K criteria is not satisfied.
The same is the case for all the previous groups as well, therefore no other combination is possible.
Case 2: N % M = 0
We have an algorithm explained further down to analyze this case. Here since we have N / M groups, this is equivalent to T(G, M, K) where G = N / M.
Case 3: N % M > M - K
For example we consider ----XXX----XXX----XXX----X for 26, 7, 3
Since the first M elements should have K selections, you can only arrange K selections among those M elements, the same applies for all successive M elements.
The last M elements have K selections (XX----X in above example), but the first M - N % M (2 in above example) selections actually belong to the N / M group (3rd in above example), but it is not affordable for us to lose these selections as it will not let us satisfy the criteria of minimum K selection for the last M elements.
Similarly the same applies to all the previous groups. Therefore M - N % M selections in every group do not change and therefore there is no point calculating combinations for the same.
We can actually remove these elements and then try for the combinations.
Removing M - N % M elements in every group will make you remain with N % M elements in every group. If you notice carefully now the number of groups has increased by 1. So the new number of groups would be N / M + 1. As we removed M - N % M selections in every group K will now be K - (M - N % M), which is also same as N % M - (M - K).
Therefore this boils down to T(N / M + 1, N % M, N % M - (M - K))
Case 4: N % M < M - K
Let's consider ----XXX----XXX----XXX-- for 23, 7, 3
Since the first M elements should have K selections, you can only arrange K selections among those M elements, the same applies for all successive M elements.
For the last M elements (17 to 23 --XXX-- in above example) we cannot afford to lose these K selections out of these M elements. Therefore the combinations in the last group (15 - 21 elements in the above example) cannot have selections in the first N % M elements.
The same applies to all the earlier groups.
Therefore we could as well get rid of so many elements in every group and also the last N % M elements as we don't get to any selection in these.
Therefore we will end up with M = M - N % M, number of goups G = N / M and K will remain the same.
Therefore this boils down to T(G, M - N % M, K).
Assuming S(N, M, K) is the total number of combinations for N, M, K, based on the above analysis for different N, M, K we get the below relation between S and T.
S(N, M, K) = 1 if N % M = M - K
= T(N / M, M, K) if N % M = 0
= T(N / M + 1, N % M, N % M - (M - K)) if N % M > M - K
= T(N / M, M - N % M, K) if N % M < M - K
Based on the above relation between S and T you will end up needing to calculate T(G, M, K) where G is number of groups, each group containing M elements and N = G * M. This can be calculated as below.
Since N % M = 0, N can be divided into groups of size M each.
Since each group has to have K selected we cannot move the selection to other groups.
Now we get the different combinations for each group separately, selecting K boards out of M. Suppose we generate all the combinations and store in array l[MCK] identifying each combination by its index in the array. We can go for list and use iterator to navigate if M is large as MCK does not fit in the array for M > 33. Time complexity involved here is M * MCK and space complexity is MCK as you can use BitSet for each combination.
But for the contiguous sake we can have only some combinations in group 1 against every combination in group 2, so we can calculate all combinations that can preceed each combination, say we get m[][] where m[i][j] is set if combination j can preceed combination i. We can go for maps if M is large as MCK does not fit in the array for M > 33. This can be achieved in M * MCK * MCK time complexity and MCK space complexity as BitSet can be used for second dimension array.
This applies not just for group 1 and group 2 but for any group x and group x + 1.
Let's say V(G, i) is the total number of combinations where group G can have combination i.
T(G, M, K) = sum of V(G, i) for i from 0 to MCK - 1.
V(G, i) = sum of V(G - 1, j) for all j for which m[i][j] is set.
= 1 if G = 1.
This can be calculated by having an array v[g][i] where g is group index and i is combination index.
Calculate the values from g = 0 for all combinations based on recursive relation.
To save space we could as well have two arrays c[i] and p[i] where c holds values for current group combinations and p holds values for previous group combinations. We can go for maps if M is large as MCK does not fit in the array for M > 33.
This can be achieved in (N / M) * MCK * MCK time complexity and MCK space complexity.
So the total time complexity all three put together is M * MCK + M * MCK * MCK + (N / M) * MCK * MCK and space complexity is MCK.
But i was asked for even more better solution.
Any suggestions are most welcome.
What do you mean until m<=k+i?
That means i>=m-k? Then why did you start i from 0?
I think you actually mean until m = k + i.
Even then it gives 26 for N=15, M=5, K=2 but the answer is 175.
That is just one of the combinations, not all. We need the total number of such combinations possible.
- Naveen Reddy Mandadi May 25, 2013C00C is not valid as there is no company advertisement in 2nd and 3rd boards.
Every 2 consecutive advertisement boards should have at least one company advertisement board, meaning 1st and 2nd, 2nd and 3rd, 3rd and 4th.
when there are n elements and 4 operations per element, there itself you have the complexity of 4*n, how did you get 4*n*n?
Moreover if you do the brute force way, comparing all the rectangles the complexity would be O(n), why would anyone go for anything more than that?
I assume range tree helps finding elements between a range in O(logn). If we use 2D range tree how is it helping over 1D range tree? Because once we find range of x we don't need range of y, if we also look for range of y we end up with points in the rectangle
Say the given number n has d digits.
If d is even:
1. Find the left and right halves of the number (say L and R).
2. If reverse(L) > R then L.append(reverse(L)) is the answer.
3. Else calculate H = L + 1
4. If H has more digits than L then H.append(reverse(H / 10)) else H.append(reverse(H)) will be the answer.
If d is odd:
1. Find the left and right halves of the number both including the middle digit (say L and R)
2. If reverse(L) > R then L.append(reverse(L / 10)) is the answer.
3. calculate H = L + 1
4. If H has more digits than L then (H / 10).append(reverse(H / 10)) else H.append(reverse(H / 10)) will be the answer.
Note: reverse should preserve the leading zeros and division is an integer division
Minutes Angle = (360 * m) / 60 = 6 * m where m is the minutes.
Hour Angle = ((360 * h) / 12) + (360 * m / 12 * 60) = 30 * h + m / 2
From the above two values get the difference by subtracting the bigger value from the smaller value.
If the difference is more than 180 then 360 - diff will be the acute angle else diff itself is the acute angle.
What if there are repetitions, 123456 don't have any repetitions but in english text alphabets would repeat.
- Naveen Reddy Mandadi October 21, 2012The position of odd numbers should be same with respect to odd numbers and position of even numbers should be same with respect to even numbers.
- Naveen Reddy Mandadi October 21, 2012I think we have to assume the number of odd numbers and the number of even numbers is the same.
- Naveen Reddy Mandadi October 21, 2012Treemap insert and search are not O(1), they are O(logn)
- Naveen Reddy Mandadi October 20, 2012Say the given number n has d digits.
If d is even:
1. Find the left and right halves of the number (say L and R).
2. If reverse(L) > R then L.append(reverse(L)) is the answer.
3. Else calculate H = L + 1
4. If H has more digits than L then H.append(reverse(H / 10)) else H.append(reverse(H)) will be the answer.
If d is odd:
1. Find the left and right halves of the number both including the middle digit (say L and R)
2. If reverse(L) > R then L.append(reverse(L / 10)) is the answer.
3. calculate H = L + 1
4. If H has more digits than L then (H / 10).append(reverse(H / 10)) else H.append(reverse(H / 10)) will be the answer.
Note: reverse should preserve the leading zeros and division is an integer division
I think he was not satisfied because every node can be reached many different ways. Suppose if you reached a node traversing n nodes then it can be reached 6^n ways. This is exponential and therefore BFS would be inefficient. I would say go to the first node by traversing as much left, below and behind then traverse all the nodes layer by layer, row by row, cell by cell.
- Naveen Reddy Mandadi October 20, 2012We can maintain one map for name, valueIndex and one for index, value and one integer variable for maxIndex. By valueIndex i mean it will hold both value and the index.
maxIndex will be -1 initially.
For insert we add an entry to name valueIndex map and an entry to index, value map using the maxIndex and incrementing the maxIndex after that.
search(name) is nothing but get from name value map.
nthentry is nothing but get from index value map using n as the key.
delete is getting the entry from name, valueIndex map, deleting the corresponding entry in index, value map and then deleting the name, valueIndex map entry.
Assuming delete(2) what is mentioned in the question is zero based and not 1 based.
You can always say you cannot make out the order if the words given are not sufficient.
- Naveen Reddy Mandadi September 04, 2012then i actually mean sub-array. Is there a way to change my question or may be drop this one and add a more appropriate one?
- Naveen Reddy Mandadi August 31, 2012I have missed out something.
Not necessarily you will be given all the dictionary words, but the words which are sufficient enough to make out the order of the alphabets.
You can always say you cannot make out the order if the words given are not sufficient.
Suppose you are given all the dictionary words in the same order like a, ant, ball, cat, do, dog, fog, frock etc.
From these words you know that there are alphabets a, n, t, b, l, c, d, o, g, f, r, k.
You don't know the order of these alphabets before hand.
You will have to find the order of these alphabets based on the order of the given words.
From a and ant you cannot make out anything.
From ant and ball you can make out that a comes before b in the order.
From ball and cat you can make out that b comes before c in the order.
From cat and do you can make out that c comes before d in the order.
From do and dog you cannot make out anything.
From dog and fog you can make out that d comes before f in the order.
From fog and frock you can make out that o comes before r in the order.
From these clues you should make out the order of the alphabets.
how is sub-sequence different from sub-array?
- Naveen Reddy Mandadi August 31, 2012Does this work if there are negative numbers in the array?
- Naveen Reddy Mandadi August 30, 2012Sorry, my mistake, it is not BST, it is just a binary tree, i have mentioned it wrong in the question.
- Naveen Reddy Mandadi August 27, 2012It is not a BST, i would have mentioned if it is.
- Naveen Reddy Mandadi August 27, 2012If all are negative obviously the max sum will be 0 with no elements.
- Naveen Reddy Mandadi August 27, 2012Yes, your 256 array will cover the digits as well, i was mistaken in this regard.
Related to the negative values consider the example given box and obxx.
Based on the first string you get counts as 1 for b, 1 for o and 1 for x.
When we are passing through the second string we could decrease the count we got in first string.
When we first take o in obxx we decrease the count of o to 0.
When we take b in obxx we decrease the count of b to 0.
When we take first x in obxx we decrease the count of x to 0.
When we take second x (last character) in obxx we decrease the count of x to -1.
We got negative value here that means there is one x more in second string than in the first string.
We can terminate here without checking further characters if at all they exist.
But the next should be pointing to the previous and the previous to the next, you will have to change all the previous and next.
- Naveen Reddy Mandadi August 27, 2012I have answered the same with the algorithm. Its better if you can post the algorithm.
- Naveen Reddy Mandadi August 25, 2012Yes, parallel is possible
- Naveen Reddy Mandadi August 25, 2012You can as well decrease the value in the first array while traversing the second string, whenever we get a negative value we know they are not permutations of each other. And in the end we have to verify if the array has all zeros. This way you will save half of the space. Moreover we do not know if only characters are allowed, and also characters could be case sensitive.
- Naveen Reddy Mandadi August 25, 2012My indentation did not appear in the question.
Every inner brace should increase one indentation to the following lines.
Every close brace should decrease one indentation to the same line and the following lines.
Small correction: This is a BST
- Naveen Reddy Mandadi August 25, 2012Have maxNum, maxNumCount, secondMaxNum, secondMaxNumCount and hash table{num=>count}.
Update the values as we scan each element in the array.
Finally you will remain with secondMaxNum.
Complexity is just O(n).
Sorting complexity is nlogn.
Convert the given number to string, say s.
Have an array a of size 10, each value holds the count of number of digits in the number before decimal which are same as the index of the array. That is a[0] will have number of 0s, a[1] will have number of 1s etc.
Also have another variable m which holds the minimum non zero value before decimal.
Loop through the string and update m and a accordingly until you get the decimal or end of string.
Now print m followed by indexes of a, each index repeated the number of times the value it holds.
Similarly do it for digits after decimal, in this case m is not required.
Complexity of this algorithm is O(n) as we are reading each digit only once.
K maximum sums in a one-dimensional array
01: for k←1 to K do begin
02: min[k]←∞; M[k]←−∞;
03: end;
04: sum[0]←0; min[1]←0; M[1]←0;
05: for i←1 to n do begin
06: sum[i]←sum[i-1]+a[i];
07: for k←1 to K do cand[k]←sum[i]-min[k];
08: M←K largest elements of merge(M,cand);
09: insert sum[i] into min;
10: end
In the worst case for every number you take you have 2 paths to go, one is directly to the next number using the for loop and the other is recursive call to the next number.
Therefore the complexity of the program is (2^n)
How do you know there is a back-edge?
- Naveen Reddy Mandadi August 20, 2012Question mentions "each subset has one and only one matching number from any other subset", but in the example subsets 1 and 11 don't have any matching number.
- Naveen Reddy Mandadi August 12, 2012I think this is wrong.
For nmb = 6, for i = 0, j = 2 and i = 3 and j = 0 teams 3 and 4 play, repeating matches.
It works.
Hash all the possible sums and look for the numbers in c in the hash. Complexity is O(a.length*b.length)
Questions isn't clear, NEWS are not going to change position, they just make the robot turn to face that direction or are they? If so how many directions ever are beside each other, only the last one makes sense. ex: NEWS, robot turns to face north, then east, then west and then south, finally robot faces south there is no effect of NEW.
- Naveen Reddy Mandadi January 26, 2014