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
@oOZz
Solution using hashtables is an obvious one. Did you think about data redundancy in such a design? Its huge! Also synchronization is a big issue if you duplicate/triplicate data at several places.
@oOZz
Your code is essentially reflecting the same idea. it's nothing new.
@Rohit
What are the semantics of the wildcard character in this context? Does it mean:
a. "match zero or more" of the character preceding the wildcard, or
b. "match zero or more" of any character in the place of wildcard?
Please clarify
Linked Lists should be fine.
A linked list of countries, where each node has two pointers
1. One that points to a linked list of states.
2. The other pointing to the next country node.
Each node in the state linked list will have 3 pointers
1. One pointing back to the it's country node.
2. Another pointing to a linked list of cities
3. The third pointing to the next state node.
Each city node will have 2 pointers
1. One that points back to it's state node
2. The other pointing to the next city node.
Queries 1 and 2 can be addressed in O(n) where n is the size of the country/state/city list
Query 3 can be addressed in O(1) time
@loveCoding
See cristian.botau comment. The idea of computing a % implies handling of overflows. Computing an exponential first and then taking modulus later will not give correct results for large x and y,
It works, but the generation of random numbers will not happen with equal probability.
The sum
[rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()]
actually creates numbers between 7 and 35 with unequal frequencies. There is only one way(7C0) to generate 7 & 35. There are 7(=7C1) ways[Any one of the seven invocations of rand5() returns 2 and the rest all return 1] to generate 8 and 34, 28 ways (7C1+ 7C2) to create 9 and 33 and so on. Therefore the frequency of generation of numbers between 0 and 6(you cannot return 7 when using %) will not be uniform.
There are solutions at: stackoverflow.com/questions/137783/expand-a-random-range-from-15-to-17 that work but needs to be modified to include the generation of number 0(The methods there are generating random numbers between 1 and 7 though)
Nice solution. The DP solution can provide you the longest palindrome present in the given string. However, I wonder, how you would trace the DP table to print ALL the palindromes available.
There are 2 cool solutions available for this problem at:
stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree
The solution using suffix arrays is complete and is very well explained.
Good one, though I see there is no need to use a heap at all.
1. Out of the n arrays, copy the first array to the end of the result array.
2. For the remaining n-1 arrays, merge each of them with the result array itself and keep storing the values in the result array.
For ex: if each of the n sorted arrays is m, then the result array is assumed to have a space of nm.
1. In the first step copy the contents of the first array into the end of the result array so the values are stored from nm-n+1 to nm (assume for simplicity, the index is based at 1)
2. Merge the second array with the result array starting at nm-n+1 and keep storing the values from nm-2n+1 to nm
3. Repeat the above steps until the final array when you start merging the result array from n + 1 and store the values from 1 to nm
The question clearly mentions not to use pow()
- Murali Mohan July 24, 2013Good one om, thumbs up!. Yeah, its a solution with O(n) time complexity. I too had thought on similar lines and wrote a small program to check the correctness of the idea and It works.
public static void maxBenefit(int[] values) throws Exception{
if (values.length < 1) throw new Exception("Invalid input");
int cMin = values[0], gMin = values[0], gMax = values[0], gdiff = 0;
for (int i=1; i < values.length; i++) {
if (values[i] < cMin) {
cMin = values[i];
} else if ((values[i] - cMin) > gdiff) {
gMin = cMin;
gMax = values[i];
gdiff = values[i] - cMin;
}
}
System.out.println("Max benefit of $" + gdiff + " happens by buying at $" + gMin + " and selling at $" + gMax);
}
However, there can be many pairs with optimal (maximum) difference, and the above algorithm returns the first or the last of such pairs based on whether we use '>' or '>=' respectively in the condition below.
} else if ((values[i] - cMin) > gdiff) {
@ Chih.Chiu.19
1. No. It's an O(N^2) algorithm. each element of the matrix is traversed at most thrice.
2. Diagonal traversal helps to encounter a vertex first rather than a side of a square/rectangle . Once you are at a vertex, you will know how to proceed from there.
Take as examples the following 3x3 matrices. The algorithm starting at top left (0,0) and traversing the diagonals will better be able to figure out the top left vertex of a square/rectangle and then proceed to figure out the rest of the geometric object.
0 0 0 0 1 1 0 0 0
0 1 1 0 1 1 1 1 0
0 1 1 0 0 0 1 1 0
For that matter, you can start at any of the four corners and then do a diagonal traversal to hit the vertex of the geometric object. From there you can proceed in horizontal and vertical directions to figure out the rest of it.
- Murali Mohan July 23, 2013Very nice point!
- Murali Mohan July 23, 2013@ Chih.Chiu.19
You seem to read and understand things in a hurry :-).
It has already been mentioned that his solution does not generate random numbers with equal probability.
>> If it is does not matter to generate numbers with equal probability, a simpler version could be:
Duplicate question. More clarity on the question and a few good solutions are available at: question?id=15555705
- Murali Mohan July 23, 2013Nice question. An algorithm to solve it goes like below.
0. Start at any corner, say top left.
1. Keep traversing along the diagonal from (0,j) to (j,0), where 0<=j<=N-1, until you hit a 1. If the upper left of the matrix is exhausted, keep traversing along the diagonal (i,N-1) to (N-1,i), where 1<=i<=N-1. Traversing the diagonal helps in hitting the vertex first, rather than a side of a square/rectangle.
2. if you hit a 1. start 2 pointers - one moving horizontally to the right and the other vertically down. Advance these pointers one step at a time as long as 1s are seen. and maintain in 'ones_count' variable, the count of 1s seen. If any one of them encounters a 0, go to step 1. If both of them hit 0s go to step 3
.
3. 'Transpose' the directions of pointers so the pointer that was moving horizontally to the right moves vertically down and vice-versa. Keep advancing the pointers one step at a time until 'ones_count' number of 1s are seen, which means we have found a square, or otherwise 0s are encountered in which case, go to step 1
Similar idea can be applied to find rectangles as well. Minor modifications may be needed to separately keep track of the number of 1s seen in horizontal and vertical directions. Also the condition to stop advancing the pointers would be different here.
It works. But, although not specified here, the question at other places wants the numbers from 1 to 7 to be generated with equal probability. Your algorithm generates numbers from 1 to 7, but with unequal probabilities as r and r%7 in () below depict.
1(1) 2(2) 3(3) 4(4) 5(5)
11(4) 12(5) 13(6) 14(0) 15(1)
21(0) 22(1) 23(2) 24(3) 25(4)
31(3) 32(4) 33(5) 34(6) 35(0)
41(6) 42(0) 43(1) 44(2) 45(3)
r%7 +1 count
1 4
2 4
3 3
4 4
5 4
6 3
7 3
If it is does not matter to generate numbers with equal probability, a simpler version could be:
do{
r = rand5() + rand5() -1;
} while(r>=8);
return r;
>> a. First for all the words calculate the key value and make an array of the key value. Here key value is calculated by multiplying the integer value of character by 10. Also if the character is uppercase then it is converted to lower case as ARe and are are same words.
Your method will not work if, along with "are", there are words like "ear" and "era" in the sentence, as they all compute to the same value. Even if you change the computation of key to something like multiplying each character by 10^x(or by using some radix(r), r^x) based on the position of the character in the word, the chances of collision are high.
For that matter, no matter what mapping function you use to map the strings to (a finite set of) numbers, there are going to collisions and to resolve them, you will have to go for a data-structure like a hashtable. A hashtable uses hash-functions(which do better distribution of numbers) and readily provides you a collision resolution mechanism.
Storing count at the leaves may not work. How do you track the count if the sentence contains words as "bet"and "better"?
- Murali Mohan July 22, 2013@Anonymous,
Without using extra space, or by using a constant amount of extra space, I can think of a naive algorithm, that given a word, compares it with all other words to find out the one with maximum occurrence count. Time complexity for this would be O(n^2).
Alternatively, in order to be more space-efficient, we can use a trie to save the words and maintain a count variable at each node. This saves space in the sense, all the words that have a common prefix will have the prefix characters specified only once in the trie.
While building the trie, keep track of the word that has maximum occurrence count in the list of words seen so far.
Use a hashtable with words as keys and occurrence word-count as values. Also make use of 2 running variables 1) max_repeated_word and 2)max_count.
0. Every time a word is read from the input, check if it is already present in the hash table. If not add to it with word-count =1.
1. If the word is already present, increment the word-count. Now check this word-count against max_count. If word-count > max_count, max_count := word-count and max_repeated_word := current word.
2. Repeat steps 1 and 2 until all the input is read.
3. print out max_repeated_word
Good argument. Thumbs up!
- Murali Mohan July 20, 2013Since the number of floors, N is infinite, we can't quantify the optimal number of throws in terms of N, but can only specify a strategy.
- Murali Mohan July 19, 2013The fastest way to reach infinity is to use Ackermann's function. It beats even factorial that beats exponential which beats a polynomial function.
If you have two eggs and infinite floors, while using the first egg, increase the gaps between two successive drops at the growth rate of Ackermann's function. While using the second egg, increase the steps linearly.
Good one, Thumbs up! Though knapsack problem is a maximization problem, and the question here is about minimization, the principle used to solve knapsack problem can nonetheless be applied by negating all the numbers to find out maximum value of the result. The result can again be negated to get minimum value.
Another DP approach that comes to my mind should also work.
Min_#_of_players_with_fan_count_sum(k) = Min( 1 + Min_#_of_players_with_fan_count_sum(k - fan_count_of_current_player),
Min_#_of_players_with_current_player_excluded_and_fan_count_sum(k))
Use 3 entities:
0. Candidate
1. Voter
2.Poll
Polling table will have VoterFK, CandidateFK & PollDate among other fields.
VoterFK, CandidateFK & PollDate must be a non-nullable fields
The composite key (VoterFK, PollDate) should be UNIQUE
Better yet, Candidate and Voter tables can be merged to form a Student table with a 'type' field that distinguishes a voter from a candidate contesting in an election. The 'type' field also provides the flexibility for a student to switch roles between a voter and a candidate at different points of time.
@Sibendu
Yeah, you are right! But I am doubtful if P3A himself had clarified this with the interviewer :-)
@Some guy
Nice solution! A few ideas that I would like to contribute..
Build a 2 suffix trees T1 and T2.
1. Build T1 for substring(n/3, 2n/3) and T2 for substring(2n/3, n).
2. Look for prefixes of substring(1,n/3) in both the T1 and T2.
3. The longest such prefix of substring(1,n/3) that is present both in T1 and T2 is a border with maximum length and having an occurrence count >=3
@Amit
Both 0,1 and 0,2 are valid answers. You can provide as an answer any one of many optimal solutions to a problem. Remember, for optimization problems, an optimal solution need not be unique, there can be multiple
@Sibendu Dey
When the question says "You have to select minimum number of players so that the total followers must be equal to a given number 'K'.", why do you want to make assumptions about the distinctness of the followers?
The example given is valid in the sense that you can combine player 0 and player 2 to get answer. You can as well combine player 0 and player 1 to get the answer. The combination need not be unique.
And when it comes to the specification asking for 'minimum' number of users, it is clearly an optimization problem and it is clear that you can use DP to solve the problem. Remember DP also gives "an" optimized solution to a problem and not "the" optimized solution as an optimization can have more than one solution.
The question clearly says NOT to use the pivot element.
- Murali Mohan July 19, 2013@ Chih.Chiu.19
You are not quite correct. You haven't completely understood my statements.
For the above configuration, work out what happens when the volume of water X = 5 & 6 and look at glass numbers 4, 5, 6 & 7, 8, 9, 10
At 5 liters you will see the following configuration, where the numbers in brackets denote the volume held.
At X= 5
4(1/2) 5(1) 6(1/2)
7(0) 8(0) 9(0) 10(0)
At X=6
4(3/4) 5(1) 6(3/4)
7(0) 8(1/4) 9(1/4) 10(0)
Do you now see that glass numbers 4 & 6 are not completely filled, yet glass numbers 8 & 9 get some volume inflow into them? That is what I mean when I say the all the glasses in the current row might not be completely filled, yet some glasses from lower row starts getting filled up.
@sjain
I haven't voted your comment down, though, after seeing your algorithm I too realized the problem(as probably the other lady/gentleman, who voted down your comment would too have) that the following condition alone is not sufficient.
if ( root.left > root.right ) {
return false;
}
You are checking for correctness only at parent-child level, whereas you would need to check for correctness at subtree level.
For ex: Suppose you are at a node in the right subtree of the whole tree and your above condition is satisfied. But, how will you ensure that your
root.left
is greater than all of the elements in the left sub-tree of the whole tree?
The recursive method which takes min and max permissible values as parameters and which checks at each sub-tree level that the node value is lying within those parameters works correctly. You may want to check solutions at: question?id=11146157
On the face of it, appears to be Dynamic Programming.
Min_#_of_players_with_fan_count_sum(k) = Min( 1 + Min_#_of_players_with_fan_count_sum(k - fan_count_of_current_player),
Min_#_of_players_with_current_player_excluded_and_fan_count_sum(k))
Time complexity- polynomial in n.
- Murali Mohan July 18, 2013Question was asked earlier also. Nice solutions provided at: question?id=21240663
- Murali Mohan July 18, 2013similar question at: question?id=11146157
- Murali Mohan July 18, 2013@vgeek
Good solution.
I think the trie approach as proposed by nitin is a clean solution.
1. Build a trie of height 3. While processing the input string, using a look-head of 2 positions, build a trie of prefixes of length 3.
2. Reverse the input string
3. Using the same look-ahead mechanism, check if any prefix is already present in the trie.
@__xy__
I am sorry. You are right! My solution does not work, deserves a down-vote.
@__xy__
It will work!
Read point #3a
>> ii. If the given element is not found in the left subarray apply this modified binary search AGAIN in the right subarray
@amit
You are right! My solution below does not work - I missed thinking about some fundamental use-cases before proposing a solution. Sorry about that!
It is possible! You need to apply binary search twice in that case. See my algorithm below.
- Murali Mohan July 18, 2013Use a modified binary search.
1. Check if the pivot element is equal to the given element. If yes, return the index.
2. If the pivot element != given element, compare the pivot element with it's adjacent elements that are to the left and to the right
Here 3 cases arise:
3a. The pivot element is the boundary element between the monotonically increasing and monotonically decreasing subarrays.
. i. Apply this modified binary search in the left subarray
ii. If the given element is not found in the left subarray apply this modified binary search AGAIN in the right subarray
3b. The pivot element lies completely in the monotonically increasing subarray.
i. if the given element < pivot element, look up in the left subarray
ii. if the given element > pivot element look up in the right subarray.
3c. The pivot element lies completely in the monotonically decreasing subarray.
i. if the given element < pivot element, look up in the right subarray
ii. if the given element > pivot element look up in the left subarray
if the given element is not found, return -1.
Even after applying binary search twice for case 3a, the complexity is still O(lgn), because it is at most once that the binary search is applied twice and each application of binary search has time complexity O(lgn)
- Murali Mohan July 18, 2013The path apparently need not be unique, is the question asking for a minimum step path? There are algorithms that do a knight's tour so that every square on the board is visited at least once. Any such algorithm can be employed to reach the destination.
en.wikipedia.org/wiki/Knight's_tour
As mentioned in the other posts, it can or cannot permit null values. It depends on how the implementer of a hashmap interprets null keys and decides whether to allow or disallow null as a key. In any case, there can be at most one 'null' as key.
- Murali Mohan July 18, 2013The question apparently is not very clear here. If it is a static data, you just take the last n element and compute the average.
If the data is coming in a stream, and you always want to know the avg of the last n elements, you need to use a queue as eugene mentioned.
Once you have computed the avg of the n numbers, when a new number comes in:
1. De-queue the first element and compute the new average as: ((n*avg - value of first element) + value of new element)/n
2. En-queue the new element.
@camelcase
While a solution for this problem is explored, there are several ways to look at this problem. My posting describes "the *rate* at which a particular glass(based on its position in the row) gets filled when a liter of water gets overflowed from all of the glasses above."
However, if only a few of the glasses in a row are overflowing at a given time, the above mentioned distribution pattern will not hold for a row beneath it.
Finally, the actual implementation of an algorithm to solve the problem has a different approach altogether than a mathematical way of looking at the problem.
About your argument, on what basis are you saying that denominator should be 2*level.Give reasons.
Use a trie. Read words from the string and add them to the trie if not present previously, else increment the count.
Traverse the trie and print out the words that have count > 1
A hashtable, with word as key and count as value should also work just fine.
In this problem the rates at which glasses get filled in are rational numbers, whose numerators form the binomial coefficients and denominators are powers of 2 - specifically 2 raised to the power of level at which glasses are present.
A litre of water (overflowed from previous level) gets distributed among the glasses at each level as follows:
level 0: 1
level 1: 1/2 1/2
level 2: 1/4 2/4 1/4
level 3: 1/8 3/8 3/8 1/8
level 4: 1/16 4/16 6/16 4/16 1/16
The above distribution pattern provides with a partial progress towards the actual algorithm that finds the amount of water in jth glass of ith row. The algorithm gets tricky because all the glasses at a level might not be completely filled yet, before water starts getting filled up in levels below (albeit, in an inverted triangle fashion).
----------------------------------------------------------------------------
The above observation apart, a DP-like algorithm below(that remembers quantities in glasses of the previous row) to find out the amount of water in jth jug of ith row can solve the problem.
0. For each glass, maintain 2 variables - the amount of water it holds and the amount of water it overflows.
1. For a glass at index i in the given row, look up two glasses in the previous row at index i-1 & i. (Boundary cases of indices need to be checked though)
2. The inflow into the current glass = half of outflow of glass in the previous row at i-1 + half of outflow of glass in the previous row at index i
3. Based on the inflow, volume held in the current glass = min(1, inflow) and the overflow at the current glass = inflow - volume held by the current glass
4. Repeat steps 1 to 3 until we reach the required glass.
An implementation in java goes like the below:
import java.util.Scanner;
import java.util.regex.Pattern;
class GlassStatus {
float heldVolume;
float overflownVolume;
}
public class GlassPyramid {
static int ipRowNum, ipGlassNum, ipVolume;
public static float computeWaterAt(float volume, int level, GlassStatus[] previousRows) {
if (volume <= 0)
return 0;
GlassStatus[] rows = new GlassStatus[level + 1];
float overflow1 = 0, overflow2 = 0, inflow = 0, tempVol = 0;
for (int i = 0, prev = i-1, next = i; i <= level; i++, prev++, next++) {
rows[i] = new GlassStatus();
if (prev < 0) {
overflow1 = 0;
} else {
overflow1 = previousRows[prev].overflownVolume/2;
}
if (next >= level) {
overflow2 = 0;
} else {
overflow2 = previousRows[next].overflownVolume/2;
}
if (level == 0) {
inflow = volume;
} else {
inflow = overflow1 + overflow2;
}
tempVol += rows[i].heldVolume = Math.min(1, inflow);
rows[i].overflownVolume = inflow - rows[i].heldVolume;
}
if (level == ipRowNum) {
return rows[ipGlassNum].heldVolume;
} else {
return computeWaterAt(volume - tempVol, level + 1, rows);
}
}
public static void readInput() {
Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(System.getProperty("line.separator"));
Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
scanner.useDelimiter(delimiters);
System.out.println("Input row#:");
ipRowNum = scanner.nextInt();
System.out.println("Input glass#:");
ipGlassNum = scanner.nextInt();
System.out.println("Input volume:");
ipVolume = scanner.nextInt();
}
public static void main(String[] args) {
readInput();
System.out.println("Volume in the glass=" + computeWaterAt(ipVolume, 0, new GlassStatus[] {}));
}
}
Nice Solution. +1.
- Murali Mohan July 17, 2013
Oh! If your data is correct, it is indeed a small one. In that case, any data structure would do!
- Murali Mohan July 25, 2013