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
Total non-sense.
- Murali Mohan February 12, 2014Simply.pass a flag to the recursive function mentioning whether or not it is the rightmost node. By definition, root is also the rightmost(as well as the leftmost node) and hence, technically it should not get printed. If the interviewer wants so, we can make an exception to this, by exploiting the fact that root node can always be known..
f (node, isRightMost) {
for (i = 1 to node.Children.size() - 1) {
f(node.Children[i], false)
}
f(node.Children.lastChild, isRightMost)
if (!isRightMost) {
print node.value
}
}
Invoke using: f(root, true)
- Murali Mohan February 11, 2014Yes, in-order and pre-order or in-order and post-order. You need two representations to uniquely reconstruct the tree.
- Murali Mohan February 11, 2014Initially choose some number k of the form 7x10^x for some x, where k > the given number N.
Suppose k = 7000,
1. Place a 7 one position at a time and see if N divides k. For ex: 7007, 7070,7700.
2. Then place 2 7's at positions and see like in 7077, 7707, 7770 etc. and test if N divides k.
In essence, the problem is asking to generate the possible combinations of 7's and 0's and then check for divisibility. The problem is combinatorial in nature and my solution has exponential time complexity in the number of digits of N.
If the bridges are modeled as edges of a graph, the question seem to be essentially asking for a graph planarity testing algorithm.
- Murali Mohan February 07, 2014Appears to be related to searching a maze. In such a case, a graph becomes a natural choice to model the situation. Coffee rooms are special in the sense, we can start DFS from such nodes.
Walls can be modeled as nodes that block the path from a cubicle to a coffee room. The DFS has to be modified to bypass the blocked nodes(i,e walls) and starting from coffee rooms, search to find a cubicle node that is empty..
A trie stores only one 'instance' of a common prefix of several strings. Thus it saves memory that is consumed by 'common' prefixes of strings.
- Murali Mohan February 06, 2014Use 'merge' subroutine of mergesort.
- Murali Mohan February 06, 2014Build a complete graph of the letters from chars[] array. Use DFS to navigate the complete graph, each time checking for the existence of the word based on the sequence of letters seen so far.
- Murali Mohan February 06, 2014To find patterns using regular expressions, one needs to be build an NFA and it's equivalent DFA.
- Murali Mohan February 06, 2014Time complexity of my solution is O(n^2) and space complexity is O(1)
- Murali Mohan February 05, 2014A simpler solution would be to have an auxiliary array Test[1..9] whose elements are all initialized to 1 before the scanning of a row or a column or a 3x3 block.
When traversing each of the 9 rows/columns/3x3 blocks, clear the value of Test[k] against the number k encountered in the sudoku solution and at the end of the iteration check that whole Test[] array is cleared.
That was a breeze man... how could you miss it?
- Murali Mohan February 05, 2014This question is poorly defined with several vague terms and without stating the objective clearly. I am assuming that selecting the *most efficient* elevator means the user should be able to reach his destination in the least amount of time and the lift movement should also be minimum.
Though the problem has been posed as an optimization problem, there are some serious caveats for it to be one. The problem in reality is inherently probabilistic in nature for the state of the system is ever changing and unpredictable.
An attempt can however be made to find out an optimal choice at a given snapshot of the system when a user wants to navigate. This includes several assumptions like the wait time at each lift is constant and is uniform across all the lifts and independent across the lifts.
If we assume there are k lifts and floor numbers start from 0 and go up to 'max_floor' we can have 3 arrays to manage the state of the system.
updown[1..k]: holding 0/1 to denote whether the lifts are moving up(=0) or down(=1)
currfloor[1..k] current floor the lift is on
nextfloor[1..k] floor the lift is headed to. If nextfloor[] were a two dimensional array with all future stops registered, the problem would get tougher..
If the user currently on 'presentFloor', and wishes to go to 'destFloor', based on the user's choice to go up or down, we select a subset of the lifts from updown[] array.
For the selected subset of lifts, compute the values vi = mi/ni, where mi = f(presentFloor, destFloor, nextFloor[i], i) and ni=g(presentFloor, currentFloor[i], i)
f(presentFloor, destFloor, nextFloor, i) {
nextFloor = abs(nextFloor - updown[i] * max_floor)
destFloor= abs(destFloor- updown[i] * max_floor)
presentFloor= abs(presentFloor- updown[i] * max_floor)
if (nextFloor-presentFloor) /(destFloor- presentFloor) > 1)
return 1
else
return (destFloor- presentFloor) /(nextFloor-presentFloor)
}
g(presentFloor, currentFloor) {
return presentFloor - currentFloor
}
Rationale behind computing vi's: vi's is the ratio of max_possible_travel_time_to_dest_floor to min_waiting_time_for_a_lift_to_arrive, max_possible_travel_time_to_dest_floor here is roughly obtained my minimizing the stop time en route the destFloor. However, if nextfloor[] were a 2D array with all future stops registered, the value of max_possible_travel_time_to_dest_floor has to be obtained by minimizing the stop time en route the destFloor, which is nothing but c*no_of_stops_between_current_floor_and_next_floor_or_dest_floor, for some constant c.
So, To choose a particular lift sort vi's and pick the one with max vi
The above greedy heuristic should work and it's correctness can be established by exchange argument, though I don't own the rigor at the moment to prove it.
It's an excellent idea to partition the set based on the above mentioned properties.
- Murali Mohan February 05, 2014Known question. Burn the first rope from both the ends and the second rope from only one end. When the first rope completely burns away, 30 minutes would have elapsed and the second rope can now burn for 30 more minutes.
Now start burning the second rope from the second end and start boiling the egg. Stop boiling the egg when the second rope completely burns as it would now measure 15 mins.
Time complexity of my solution is O(k) and it's space complexity is O(k) too (for using system stack in recursion), where k = log_base_10(N).
- Murali Mohan February 02, 2014The corrected equations are:
1. For d1 < 4 f(d1,d2,...,dk) = d1 * 9^(k-1) + f(d2,d3,..,dk)
2. For d1 >= 4 f(d1,d2,...,dk) = ceil(abs((4-d1)/5)) * (d1-1) * 9^(k-1) + f(d2,d3,..,dk)
The above 2 equations combined:
f(d1,d2,...,dk) = ceil(abs((4-d1)/5)) * (d1 - floor(d1/4) - floor(d1/8)) * 9^(k-1) + f(d2,d3,..,dk)
The special case when d1 = 4 needs to be handled differently is a brilliant catch @Super Mario. Cheers! Admit that I have missed it and needs to be handled differently. It should also rather have been 9^(k-1) than (k-1)^9 - sorry for the lack of attention on my part while typing the answer. Thanks for the corrections!
- Murali Mohan February 01, 2014@Alin
So with a RAM of more than 16GB on PCs and Smart Phones these days, do you still want to sort 4GB data using *external* merge sort?
Why use *External* merge sort if the elements are all in an array? Use Quicksort.
- Murali Mohan January 31, 2014Base64 encoding. Advantages - easy to use. Disadvantages: Verbose text.
- Murali Mohan January 31, 2014Probability that they do not collide: 1/4
If all go in the same direction.. they will collide if they all move with unequal speeds.
This can be solved by a recursive approach that works by removing Most Significant Digits(MSD) one at a time in each recursive step and counting the number of numbers that don't include 4.
Suppose the given integer N has k digits - d1,d2,...,dk. There are 2 cases: d1 < 4 and d1>=4 and the recursion yields itself as:
1. For d1 < 4
f(d1,d2,...,dk) = d1 * (k-1)^9 + f(d2,d3,..,dk)
2. For d1 >= 4
f(d1,d2,...,dk) = (d1-1) * (k-1)^9 + f(d2,d3,..,dk)
Both can as well be combined to:
f(d1,d2,...,dk) = [(d1 - floor((d1)/4) - floor((d1)/8)) * (k-1)^9] + f(d2,d3,..,dk)
The base cases are:
f(d) = d, for d<4. [It could have been d+1, had the question not been asking for numbers *lesser* than the given number]
f(d) = d - 1, for d>=4 [It could have been d, had the question not been asking for numbers *lesser* than the given number]
Recursion works, but applied in a different way. The recursive approach deals with removing Most Significant Digits(MSD) one at a time in each recursive step and counting the number of numbers that don't include 4.
Suppose the given integer N has k digits - d1,d2,...,dk. There are 2 cases: d1 < 4 and d1>=4 and the recursion yields itself as:
1. For d1 < 4
f(d1,d2,...,dk) = d1 * (k-1)^9 + f(d2,d3,..,dk)
2. For d1 >= 4
f(d1,d2,...,dk) = (d1-1) * (k-1)^9 + f(d2,d3,..,dk)
Both can as well be combined to:
f(d1,d2,...,dk) = [(d1 - floor((d1)/4) - floor((d1)/8)) * (k-1)^9] + f(d2,d3,..,dk)
The base cases are:
f(d) = d, for d<4. [It could have been d+1, had the question not been asking for numbers *lesser* than the given number]
f(d) = d - 1, for d>=4 [It could have been d, had the question not been asking for numbers *lesser* than the given number]
The question is incomplete. The answers would differ for a simple interest vs compound interest.
- Murali Mohan January 30, 2014Take two consecutive rows, concatenate the strings as a cartesian product of the rows and merge them into a single row. Repeat the steps until only one row is left. The procedure can follow either a top-down approach or a bottom-up approach, with the initial rows being the first two or the last two respectively.
- Murali Mohan January 30, 2014K-way merge. Keep merging one pair of chunks at a time. After the first pass, k/2 chunks will be left. After the second pass, k/4 chunks will be left and so on. At each pass, need to take care of merging the last remaining chunk as a special case in case k/i is odd, where i = 1..k
- Murali Mohan January 30, 2014I can think of two approaches:
1. Sort all the 5 arrays and 'walk' through them using 5 pointers to 5 arrays to find out the intersection of elements.
2. Use 2 hashsets. Put all the elements of the first array in the first hashset. From the 2nd array onwards, check if the given array element is present in the first hashset, if yes, put it in the second hash set. At the end of the iteration, clear the first hashset and use it for the next iteration.
We need logical right shift here, so >>> is correct. Otherwise, the arithmetic right shift >> would always yield -1.
- Murali Mohan January 29, 2014If the input array contains more than a string starting with 'a', how can you sort with the constraint that we can use only one swap for strings starting with 'a'? Am not I not understanding it clearly? Please explain.
- Murali Mohan January 27, 2014n & ~n
- Murali Mohan January 26, 2014Along with (endSum == beginningSum) , you will have to ensure that (startIndex == endIndex - 1)
- Murali Mohan January 23, 2014Simply use a cumulative array. Keep summing up the elements until the end. If the value at the end is n, the breaking point is the location where the sum is n/2.
- Murali Mohan January 23, 2014I mean, we need to verify:
counter_of_chunk1 >=0
counter_of_chunk1 + counter_of_chunk2 >=0
...
counter_of_chunk1 + counter_of_chunk2 + .. + counter_of_chunkn >=0
@eugene.yarovoi
If we suppose the file is divided into serial chunks with IDs assigned to them from 1 to n. How about computing the counter for each of the chunk in parallel and store them separately. In the end, we can check that the cumulative sum of the counters from chunk 1 to chunk n never becomes negative. Would this work?
@Suzker
Good test case, actually the algo needs modification. the cumulative sums need to be checked as soon as a right parenthesis is encountered and not at the end of the reading the chunk. Chunks are useful only in retrieving parts of a large file.
@SatyajeetTripathy is going in the right direction. Why not take 2 counters, say, left_paren_count and right_parent_count? Ensure that the cumulative sum of these variables for all but the last chunk is such that: sum(left_paren_count) >= sum(right_paren_count). By the last chunk the cumulative sums should be such:
sum(left_paren_count) = sum(right_paren_count)
24. Factorize multiples of 5
5 = 5x1
10 = 5x2
15 = 5x3
20 = 5x2x2
...
25 = 5x5 (one extra 5)
..
50 = 5x5x2 (one extra 5)
...
75 = 5x5x3 (one extra 5)
..
100 = 5x5x4 (one extra 5)
All of the 20 multiples of 5 up to 100 have one 5 each. The multiples 25,50,75 & 100 have one extra 5 each. Hence the total number of 5s = 24. Each of these twenty four 5s when multiplied by 2(which are at least 50 in number) yields a zero and hence the total number of 0s = 24.
Assuming the intervals begin and end at integral values, sort the intervals using their begin values.
Using an auxiliary array aux[n], where n is the maximum end value of all the intervals
counter = 0;
for (i = 1..n) {
if an interval opens at i, counter++;
if an interval closes at i, counter--;
aux[i] = counter
}
Go over aux[] array to find out the maximum value. Do a reverse lookup to find the list of intervals that contain the maximum value of aux[] array.
- Murali Mohan January 22, 2014Have a recursive method called getNoOfLeaves(). The base case of recursion returns 1 for leaf nodes. During the bubbling up(unwinding) of the recursive calls, sum up the number of leaves from both it's children and check if it equals to the given k. If yes, add the node to a list.
- Murali Mohan January 22, 2014Finding out the number of 1s in a given number n:
count = 0;
while(n) {
count++
n = n & (n-1)
}
Next integer having the same number of 1s in a given n:
Starting from the rightmost 1, traverse the bits to it's left to find the rightmost 0. Swap the 0 bit with the 1 bit to it's right.
i = 0
while (!(n & ( 1 << i ))) { i++}
while (n | ( 1 << i )) { i++}
n = n | (1 << i)
n = n & ~(1 << (i-1))
DFS is a natural selection for searching a maze.
- Murali Mohan January 21, 2014To test whether or not two vertices are connected, both BFS and DFS suffice.
- Murali Mohan January 21, 2014Square up each of the elements of the array and put them in a hash table. This requires O(n) extra space. Then for all of the n^2 combinations of elements, check if their sum of their squares exists in the hash table with O(n^2) time complexity.
A complete graph of the elements with nodes holding the squares of elements may also get the job done. Running DFS from each node and traversing a depth of up to 3 levels, can help check for the existence of Pythagorean squares.
@Joker.eph.
Thanks for the correction.
This is like asking to print all the 'valid' permutations of the word, the validity of whom is checked against a given dictionary.
- Murali Mohan January 17, 2014Maintain an 'order' table as below.
order[0] = ""
order[1] = thousand
order[2] = million
order[3] = billion
order[4] = trillion
...
Have another table called text[] such as:
text[0] = "zero"
text[1] = "one"
..
text[999] = "nine hundred and ninety nine"
1. Count the number of digits to figure out the what 'order' the number belongs to - say, millions or thousands or units. This is obtained by order[(digit_count(n) -1)/3]
2. Chomp 3 digits at a time and print out: text[chomped_digits] + order[(digit_count(n) -1)/3] If chomping the number from MSDs is difficult, reverse the number, extract the last 3 LSDs using a % operator and then again reverse the extracted 3(or less) digits.
3. Go back to step 1 until the number is exhausted.
For ex:
1.123,456:
One hundred and twenty three *thousand*(order), four hundred and fifty six
2. 9,999,999
Nine *million*, nine hundred and ninety nine *thousand*, nine hundred and ninety nine.
Easy one.
Sort the input array on the lines of 'Dutch National Flag' sorting scheme so all 0s come to the left and 1s come to the right. Take 2 pointers/indexes - P1 pointing to the start of the subarray with 0s and P2 pointing to the start of the subarray with 1s.
For ex:
In iteration k, exchange f(k) 1s from the P2's beginning with 0s from P1 and move ahead the pointers P1 and P2 accordingly. Stop when no such exchange is possible.
- Murali Mohan February 12, 2014