Murali Mohan
BAN USER- 0of 0 votes
AnswersHow do you swap bits at indexes i & j of a 32-bit memory word?
- Murali Mohan in India| Report Duplicate | Flag | PURGE
Marketshare Inc. Java Developer Algorithm - 1of 1 vote
AnswersYou are give a circular pizza with 3n pieces of pizza , each piece of pizza has different volume, The task is to eat n pieces of pizza such that the total consumed volume of pizza is the maximum, condition when the user chooses a piece of pizza he has to discard its immediate 2 neighboring pieces, the pizza is circular and every time we eat and discard there are new neighbors being formed per piece.
- Murali Mohan in United States
For ex:
pizza one : 2 1 1 2 9 1 10 1 9
pizza two: 1 9 2 2 9 1 1 10 1
pizza three: 1 9 2 2 9 1 1 10 10
Suppose the pizza was divided into 2n pieces, would your approach to find the maximum volume change from that of 3n pieces?| Report Duplicate | Flag | PURGE
Marketshare Inc. Java Developer Algorithm - 10of 10 votes
AnswersA tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1. The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes that node with id k is the root. For ex:
3 3 3 -1 2 0 1 2 3 4
In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4.
- Murali Mohan in India for Bangalore
Given such an array, find the height of the tree.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersIn an N*M grid, in how many ways can you reach from top left (0,0) position to an arbitrary location (i,j) provided you can only move to the right or to the bottom in one step?
- Murali Mohan in India for Bangalore
How do you compute the number of ways from (0,0) to (i,j) if there are arbitrary number of blocks on the way?| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - 3of 3 votes
AnswersDevelop an algorithm and write code to break a sentence without spaces into a sentence of valid words separated by spaces.
- Murali Mohan in India for Bangalore
For ex: thissentenceisseparated needs to be broken into: this sentence is separated
Assume that you have a dictionary to check for valid words. Your algorithm should return false if the sentence cannot be separated into valid words.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven n, how many structurally different binary trees can be formed?
- Murali Mohan in India for Bangalore
For ex: n = 1 => one tree
n = 2 => two trees
O O
/ \
O O
n = 3 => five trees
O O O O O
/ \ \ / / \
O O O O O O
/ \ / \
O O O O| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - 0of 0 votes
AnswersSuppose you have an array of +ve numbers, -ve numbers and zeroes. Devise an algorithm to find the maximum contiguous subsequence product.
- Murali Mohan in India
For 7 -3 -1 2 -40 0 3 6, the max subsequence product = -1 * 2 * -40 = 80
For -3 7 2 0 -5 7 -2 -2 2, the maximum subsequence product = -5 * 7 * -2 = 70| Report Duplicate | Flag | PURGE
InMobi Algorithm
- 0 Answers Interview with Sr. Dev Mgr at Amazon
All,
- Murali Mohan July 17, 2013
I have an interview scheduled with Sr. Dev Mgr at Amazon in a week from now. That is the last round and I am totally clueless as so what will be asked there. Can anyone plz plz plz guide me?
Thanks a million!| Flag | PURGE
Let the digits be stored in an array of size n.
for (j = n-1; j >=1; j--) {
for (i = j-1; i>=0; i--) {
if (A[j] >A[i]) {
swap(A[i], A[j]);
return;
}
}
print "Rearrangement of digits not possible, the given number has the highest value"
}
One thing to note is rearrangement as asked in the question is not always possible. For ex: in the digits are in non-increasing order as in 3321, no arrangement that can lead to next higher value is possible.
Otherwise, starting from the right-most end, we can keep comparing it with elements to it's left and swap them if the right side element is greater than the left side element. Repeat the process by starting again at the second right-most element and so on, until a swap could be performed or print out that such an arrangement is not possible
[Adding a missing step]
If the array element is not present, add it to the hashtable.
Use a hashtable that stores value of the array as 'key' and index as 'value'. Iterate through the array, each time checking if the array element is present in the hashtable. If yes, it implies that there is a cycle in the array and the length of the cycle = current_array_index - 'value' in the hashtable.
- Murali Mohan January 14, 2014Simply count the number of 1-bits in the word. Let their number be n. The highest integer would be the one with n 1s in the more significant positions and the lowest integer would have n 1s in the less significant positions.
bit_count = 0;
while (n) {
bit_count++
n = n & (n-1)
}
largest_int = 0;
bit_count1 = bit_count;
while(bit_count1--) {
largest_int = largest_int>>>1 | 2^word_size
}
smallest_int = 0
while(bit_count--) {
smallest_int = smallest_int <<1 | 1
}
The total number of steps in your procedure is 9 as opposed to 4 that you are thinking.
Each of the step listed by you indeed involves two steps:
>>. 1.First fill 3L and pour it into 5L and now 5L container has 3L and 2L empty
Filling the 3L can is one step and pouring it into 5L is another step
>> 2.another 3L into 5L, so 1L will be left in 3L container
Refilling 3L is one step and filling up 5L from 3L so 1L remains in the 3L is yet another step
>> clear the 5L and fill it with 1L that was left in 3L
Two steps again
4. fill 3L into the 5L , hence 4L.
How can you directly fill 3L into 5L can? You first have to fill the 3L can and only then will you be able to measure 3L. This step actually involves 3 steps:
I. First, you transfer the 1L from 3L can to 5L can
2. Fill up the 3L can
3. Transfer from 3L can to 5L can, which will then make up 4L
You can figure out the next higher value in the order traversal itself? Why do a separate binary search? InOrder traversal takes O(n) time and on the system stack takes something between O(lgn) for and O(n) space for balanced and skewed BSTs respectively.
- Murali Mohan January 11, 2014Use a running_counter and another variable to store the max_depth. On seeing a left parenthesis, increment the running_counter by one and on seeing a right parenthesis, decrement the running_counter.
Each time the running_counter is incremented, check it against max_depth and update it if needed. In the end, max_depth will hold the maximum depth of the parentheses.
Using a simple example of elements [1,2,3], build a tree of prefixes of the array as below:
123
/
-12 -- 3
\
1 --23
\
2 -- 3
Traverse the tree in a DFS fashion starting from the root, each time adding up the node values and checking against the target value.
The above tree can be created using prefix arrays of the suffix array of the given array.
Use a min heap of size 100. Insert the first 100 elements of the list into the heap. From the 101st element, check if the current element in the list is greater than the min element in the heap. If yes, delete the min element and insert the current element into the min heap. Repeat this until the list is exhausted and in the end, the top 100 elements will be present in the heap.
- Murali Mohan January 11, 2014The sequences
0 3 6.5
3 3 3.5
&
0 1 3.5 (5L waste)
1 3 0.5
actually consists of 3 steps each. Wastage is more(5L) than in my case(1.5L)
Let the water be distributed in the 3 jars(separated by commas) as below.
Initially:
0L,0L,9.5L, Distribute them into 5L and 3L jars as below:
5L,3L,1.5L Now throw away the 1.5 (wastage = 1.5L) so the distribution becomes
5,3,0. From here...
5,0,3
2,3,3
2,0,6
0,2,6
5,2,1
4,3,1 (Four is captured inside the 5L can in a total of 8 steps.)
Case 2 could rather be split into case 2 and case 3 for a clearer exposition.
Case 2: If an internal node is chosen as a root, the original root will have one child. The nternal node chosen to be the root will have one more child than before. Leaf nodes will have zero children
Case 3: If a leaf node is chosen as a root, the original root will have one child. The chosen leaf node will have one child and all other leaf nodes have 0 children. All internal nodes will have the same number of children as before.
Case 1: If the original root itself is choosen as the root and picked up, then the tree remains binary
Case 2: Otherwise, the original root will have one child. Internal nodes with k children become nodes with k+1 children, where 1<=k<=2. Leaf nodes will have zero or one(in case a leaf is picked as the root) children.
This can be done in two phases.
1. In phase 1, find out the location of the grey cell by scanning the 2D array and let it's location be (i,j).
2. In phase 2, find out the paths from (0,0) to (i,j) and then from (i,j) to (N-1,N-1) using DP. The black cells can be treated as 'blocked' sites/paths and we have known DP solutions to traverse from a cell (i1, j1) to (i2,j2) with some paths blocked in between them.
It is quite counter-intuitive and surprising to see how achieving the objective of getting minimum color value(=0) at every step, achieves the overall objective of emitting minimum smoke.
- Murali Mohan January 09, 2014First sort the array of colors so colors 0..99 are seen in that order.
Then there are two approaches to reach the solution.
1. While mixing, alternate between emitting minimum smoke and getting 0 as the resultant color of the mix.
2. A more elegant approach (thanks to a hint given by my friend) is to follow a greedy approach to get 0(by mixing 1 with 99 and then 2 with 98 and so on...) as the resultant color at each mixing step. This results in the jars array finally having 50 zeroes along with the color 50 in it. The 50 zero colors when mixed among themselves, vanish into a single zero color with 0 smoke. The lone zero color can then be mixed with color 50 so color 50 remains in the end.
Instead of mixing the 'other jars' in any order, you can try to give it a some order so the objective of emitting minimum smoke is met.
- Murali Mohan January 09, 2014Yet another gem from Amazon. I have a solution for this, which I will post shortly.
- Murali Mohan January 09, 2014Classic, +1.
- Murali Mohan January 08, 2014Build a complete graph of all the symbols of the periodic table. Let the graph have n nodes in total. Do DFS for all of the n nodes in the graph and at each step check for the validity of the word traversed so far by looking up in the given dictionary.
- Murali Mohan January 08, 2014One thing to note is that it may not always be possible to sort the numbers as asked in the question.
Suppose you have the strings:
abc
cba
bbb
Where will you place the string 'bbb' w.r.t the other strings?
Supposing that the input strings can be arranged as required in the question, first sort the array 'strings[]' using the natural order of the strings. Then we can maintain an auxiliary array that holds the locations of strings starting with a particular character. For ex: Lets have the array index_manager[] such that:
index_manager['A'] = 0
index_manager['B'] = 12
index_manager['C'] = -1
...
index_manager['Z'] = 2014
The following algorithm should work:
Starting with the first string in the sorted array, do the following
0. Let the current string be 'current_string' and print it.
1. Let the first character of current_string be 'F' and increment index_manager['F'].
If first_char_of(string[index_manager['F']]) != first_char_of(current_string) then index_manager['F'] = -1
2. Look at the last character of that string. Let it be some character 'L'. Look up the character in the index_manager[] array.
3. if (index_manager['L'] == -1) print 'Sorting not possible' otherwise go to step 4
4. Set current_string = string[index_manager['L']] and go to step 4.
We may need to take care of some other boundary conditions, but the schema in general should work.
@dhamu.31954
The question says that the input is already given as an adjacency list. In your method, you need an additional hashtable( extra O(e) space ) to find out unique nodes. DFS needs adjacency list, but not your extra hashtable.
@Vin
DFS is a graph algorithm and graphs don't have root nodes. A tree is a graph without cycles and with a distinguished 'root' node.
The solution is a good one. But calling it 'more efficient' is not appropriate. In order to count the number of nodes, you need to determine their uniqueness. You can do it either by sorting ( O(elg(e)) time complexity: e= #of edges) or using a hashtable( O(e) space complexity and O(e) time complexity), which are no way better than using DFS which is of O(1) space complexity and O(e) time complexity(in this case, for a graph where |V| ~ |E|)
- Murali Mohan November 28, 2013Since the tree is already given in a graph representation, apply either BFS or DFS. Return true if you encounter a node with 'isVisited' flag is true.
- Murali Mohan November 27, 2013Good one. Another alternative with similar effect is to create a 'reflected' BST where min node will occur at the place of max node etc. Then do an inorder traversal, keeping the running cumulative sum and updating the node values and then 'reflect' the BST back.
Doing a reverse inorder is more efficient both in terms of time and space though.
You got it almost right, the problem needs no programming. A simple counting can do.
3^5 - 3*3! = 225 is the answer.
3^5 for all the possible combinations of a,b & c in a 5-letter string.
3 is for the possible number of consecutive locations for 3 elements. (1,2,3) (2,3,4) and (3,4,5) are the 3 possibilities for consecutive locations of 3 elements in 5 places.
3! is the for the permutation of (a,b,c) in the 3 consecutive locations identified above.
The first time you see h() is returning some value, note it's value, comment out the calling of h() and then use that hardcoded value in g(). This will let you work past the calling of h().
Separately, you can write a test case to debug h() alone to find out the cause of the crash.
loop {
rem = value % 10
value /= 10
mystr[i++] = rem - '0' //sizeof(mystr) == sizeof(int) + 1 and mystr[i] = '\0' for 0 < i < sizeof(mystr)
} until value > 0
rev(mystr) // reverse by swapping ith and (n-1-i)th for 0 < i < sizeof(mystr)/2
nastra is right. Plain encoding would not work. use two arrays A1 & A2 of size 26(to be precise, the size of the alphabet). The indices would represent the characters of the alphabet and the values would represent their occurrence count.
The arrays should be initialized to 0 and when a character is encountered, the counter for that character should be incremented.
Sort the arrays now and check that counts of both the arrays match. If they match, then the strings are isomorphic, otherwise, they are not.
Uruk is right, space complexity is actually O(n)
- Murali Mohan November 11, 2013Two auxiliary cumulative arrays, say cumArrLeft[] & cumArrRight[] can be used to store the *indices* of maxHeight seen so far from the left and from the right respectively
Supposing we have the routine: computeWaterQuantity(startPos, endPos)
0. Start from the middle(say, mid) of the array.
1. leftMax = cumArrLeft[fmid]
2. rightMax = cumArrRight[mid + 1]
3.totalWaterQty = computeWaterQuantity(leftMax, rightMax)
4. if leftMax == 0 go to Step 8
5. newLeftMax = cumArrLeft[leftMax -1]
6. totalWaterQty += computeWaterQuantity(newLeftMax, leftMax); leftMax = newLeftMax;
7. goto step 4
8 if righttMax == (size_of_the_array - 1) go to Step 12
9. newRightMax = cumArrRight[rightMax +1]
10. totalWaterQty += computeWaterQuantity(rightMax, newRightMax); rightMax = newRightMax;
11. goto step 8
12 Stop
Since the arrays are sorted, a modified *merge* subroutine (of mergesort) can get the job done in O(n) time and O(1) space.
The arrays' *walk* of merge subroutine can keep track of the previously computed sum and current sum to disregard duplicates and stop when the Nth sum is reached.
The arrays' walk can be done as follows: Given indices i and j, we have previoussum = a[i] + a[j] and currentsum= Min((a[i] + a[j+1]) , (a[i+1] + a[j])). Update the pointers i & j accordingly for the next step in the arrays' walk.
Why not use a bit-vector?
- Murali Mohan October 28, 2013The question doesn't seem to be asking anything more than to print cartesian product of the elements.
- Murali Mohan October 17, 2013In your _move_ trick, the shift(which is nothing but repeated swaps) is implicit. You have certainly got tricked yourself into thinking that it is O(n) and you almost got me tricked into thinking that you are correct, and therefore a -1 from me.
The mere fact that array is mapped to contiguous memory locations in hardware implies that you cannot 'splice' it. Shifting, which is accomplished either by repeated swaps or repeated copying of elements to adjacent locations, is the way to go. Just because python/perl provides you splicing operation as an easy abstraction does not mean that the complexity of a single splice operation is O(1). Did you really check the internals of your interpreter?
@Eugene
Yeah, your approach is correct and elegant. The solution does not need the verbosity I gave. I could have refined my elimination step to disregard one person at a time as a Mayor instead of bothering about two. That also reduces the number of questions to be asked. The final validation step is necessary as I too see it. Great answer!
>> Either way, one person is always eliminated.
if both know each other or they don't know each other, then both of them need to be eliminated.
See my argument above that precisely captures all the cases.
>> After asking n - 1 such questions, only one person will remain.
You actually need to ask 2n-2 questions. Also, there is no guarantee than only one person will remain. It can also be the case that no person remains in the end if there is no mayor. Again, see my argument above for precise details.
A linear time solution is possible.
Maintain two sets: SetA containing all the people initially & SetB initially empty. Assuming that mayor exists in SetA, the idea is to pick people from SetA and move them one by one into SetB if he/she is not a mayor.
SetA = {1, 2, ..., n}
SetB = {} // initially empty.
Let the variable m hold the (possible) mayor. Initially m = null. Let |SetA| denote the cardinality of SetA
0. If |SetA| < 2 then "no mayor exists" else pick two elements (p, q) from SetA
1. if knows(p,q) == true then SetB = SetB U {p}, SetA = SetA - {p}, m = null else m = p
2. if knows(q,p) == true then SetB = SetB U {q}, SetA = SetA - {q}, m = null else m = q
3. if (m == null) go to step 0
4. if SetA == { } go to step 6
5. Pick a person r from SetA. set p = r, q = m and go to step 1
6 For all k in SetB, assert "knows(k,m) = true" // This step is important to handle the edge cases.
SELECT e.name FROM Employee e
INNER JOIN
(
SELECT depId, count(*) FROM Employee GROUP BY depId ORDER BY 2 DESC LIMIT 1
) t ON t.depId = e.depId
Without using extra space, you can just sort all three arrays. Use 'merge' like step to compare elements and find out duplicates in arrays 1 and 2 and place them in array 4. Use 'merge' like step again to scan arrays 3 and 4 to find out the unique elements
- Murali Mohan September 19, 2013A small edit:
>> on the path starting from min
should be
on the path starting from the right child of min.
mingjun is correct. No guarantee that all of the given elements in the set will fall on the path between min and max. The set g can have arbitrary elements.
However, if you store the elements of the group g in a hashset(an extra O(G(n)) space), then on the path starting from min, RECURSIVELY check both the children to see if either or both of them belong to the group g. In other words, do an Inclusive-OR of the recursive calls to return the result.
@anotherguy
You have got a nice use-case, the one with all -ve numbers. In this case, you would not want to check all non-positive numbers individually. Instead, It again boils down to whether you have an even number of -ve numbers or an odd number of them.
If the count parity is even, you will get maximum subarray positive product by multiplying all of the -ve numbers.
If the count parity is odd, you will get maximum subarray positive product by either multiplying from 0 to n-2 or from 1 to n-1
Both of the above cases are anyway handled by my algorithm in step 2 (and beyond) as show below
>>2. Between begin and end, take the count, c of the number of -ve numbers and note the 'first'and 'last' positions of -ve numbers
However, to address your issue, I need to slightly modify my procedure of demarcating the 'end' of the array in the step 1. The below statement can be changed from:
>> 1. From 'begin' traverse the array until you find a 0 and demarcate it as 'end'.
to:
>> 1. From 'begin' traverse the array until you find a 0 or reach the end of the array and demarcate it as 'end'.
However, the un-handled test case suggested by @Anonymous is more fundamental and is the one which indeed requires checking all -ve numbers individually. For ex: if we you have the array [0,-1,0,-2,0,-3,0], you will have to check each -ve number individually and pick the min of them to give you the maximum subarray (-ve) product.
@Anonymous
Excellent test case, thanks! For your type of input, say [0,-1,0]. my algorithm may not crash, but it would wrongly return 0. Instead, it should return -1 and yes, step 2 certainly needs modification.
When there are odd number of -ve numbers between begin and end, with an additional check to see if there is only one element between begin and end, we can return the lone -ve number's value itself as the max product of the subarray.
@Nitin R. Gupta
Seems you have barely understood the algorithm. See @anotherguy's comments for an explanation.
Decent explanations at: en.wikipedia.org/wiki/Fisher–Yates_shuffle
- Murali Mohan September 08, 2013One can use standard Fisher-Yates-Knuth shuffle algorithm
- Murali Mohan September 08, 2013>> The nearest leaf node can be above the given node as well
I only thought a parent and ancestors could be above a given node, I appreciate your thinking of leaves being above.
This question is not making much sense.
A. If all the elements are positive, the whole array would be the largest contiguous subarray whose product is maximum
B. If the elements are non-negative, we will have to find the maximum of product of subarrays delimited by 0s
C. If the elements can contain -ve numbers, +ve numbers along with zeroes, the maximum product of a subarray is obtained as follows;
0. Set begin = 0
1. From 'begin' traverse the array until you find a 0 and demarcate it as 'end'.
2. Between begin and end, take the count, c of the number of -ve numbers and note the 'first'and 'last' positions of -ve numbers.
2a. If the c is even, multiply all the numbers between begin and (end-1) and take the product
2b. If the c is odd, take 2 products - one of the contiguous subarray between the 'begin' and the (last-1) and the other of the contiguous subarray between (first+1) and (end-1) and take the maximum of the two.
3. If the current running product is greater than the maximum global contiguous subarray product, update the global contiguous subarray product
4. if end<size_of_the_array, move 'begin' to the next non-zero element to it's right and goto step 1. else stop
The question should be asking for 'a' nearest leaf node, because there can be many leaf nodes 'nearest' to the given node. For ex: full binary trees, say of sizes, 1, 3, 7, 15 etc have all the leaf nodes at the same height from the root and all are the nearest.
As far as the solution is concerned, doing a level order traversal from the given node and printing out the first leaf encountered should solve the problem.
Suppose you are given a mxn rectangle, where m>=n
- Murali Mohan January 17, 2014Then the total number of squares = m*n + (m-1)*(n-1) + (m-2)*(n-2).+..+(m-n-1)*(n-n-1)
In closed form, it becomes,
sum of the terms: (m-j)*(n-j) where j = 0..n-1