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
@nobrainer
You first need to define what 'balanced' BST means. Does it mean the left and subtrees are of equal height? or can be off by some constant number? or of equal size?
In order to iteratively traverse a recursively defined structure like a tree, we can make use of auxiliary stack(s) or queue(s) to get the desired output. But the problem definition needs to be precise first.
@Anonymous
The question is asking to focus you on a procedure for conversion and the conversion should not use a library function. However, in order to convert a number into a string of char literals, you ought to have an itoa() function, which you can always develop on your own.
Sorry, please read atoi() as itoa() in the above comment.
- Murali Mohan September 05, 2013Good solution based on higher level operations/abstractions like casting. +1. A little more formal treatment is below.
int i, j = 0;
i = (int) f;
f = f - i;
while(f > 0) {
f *= 10;
j = (j*10) + (int) f;
f = f - (int) f;
}
println atoi(i) + "." + atoi(j)
It might turn out to be a tough problem if casting is disallowed.
- Murali Mohan September 05, 2013Funny, but nice. +1
- Murali Mohan September 05, 2013@Abhi
>> If you are in the middle of the line this is probably going to be the worst solution.
What do you mean by or how can you define 'middle' for an infinite line in the first place?
A disk file typically has sequential access and hence poses challenges in terms of accessing a record randomly.
Therefore, make a copy of the file such that records of it form a doubly-linked list(which means records will have pointer to the previous one also). Use a double-ended queue(deque) of size ~2GB, so that as records are accessed from first to last or vice-versa, old records are de-queued from one end and new records are added at the other end.
Actually, the last condition
If visitedWebPages.size() >=m and visitedOnDates.size() < k
do nothing
is superfluous. It is not needed.
- Murali Mohan September 03, 2013@masterjao
Plz see my comment above. You are right, the base of the power does not actually matter here, nor does the initial value set to i.
For that matter, since it is an infinite line, i can be initialized to any value and the movement can be to the powers of any base. The bottom line is to have strategy to move back and forth incrementally.
There can be no optimal solution that can have time complexity defined in terms of a finite quantity 'n'
@Amit
What answer did you give? I suppose you can move forward and backward in steps of powers of 2.
0. Let i = 0
1. Move 2^i steps in one direction(either forward or backward)
2. i++
3. Reverse direction and move 2^i steps
4 Reverse direction and move 2^i + 2^(i-1) steps
5. Repeat steps 2 to 4 until the element is found
Sorry for a botched-up formatting.
- Murali Mohan September 03, 2013Use a combination of a hash-table and a hash-set .
Map userVisits = new HashMap<Integer, VisitDetails> // Here customerId would be the key of type Integer, VisitDetails object is the value defined as below.
class VisitDetails = {
Set visitedOnDates = new HashSet<Date>; // this holds dates visited on
Set visitedWebPages = new HashSet<Integer>; // this holds web page ids
}
Set reqdUsers = new HashSet<Integer> // this holds user id which satisfy the criteria mentioned in the question
When a user visits a webpage, the
userVisits
hashmap is consulted to get
VisitDetailsObject
object. Inside
VisitDetailsObject
the hashsets
visitedOnDates
and
visitedWebPages
are updated and then their sizes are checked.
If visitedWebPages.size() >=m and visitedOnDates.size() == k
, insert the user into
reqdUsers
[ which holds the users satisfying the criteria mentioned in the question]
If visitedWebPages.size() >=m and visitedOnDates.size() > k
remove the user from
reqdUsers
If visitedWebPages.size() >=m and visitedOnDates.size() < k
do nothing.
- Murali Mohan September 03, 2013Right! No guarantee that it is always possible. Consider the array [1,2]. This can't be divided into two sub-arrays of size 1 whose averages are equal.
As a preliminary response, the algorithm should first output whether or not such a partitioning is possible. If yes, then can print out the partitioned elements. And as far as the algorithm is considered, modifications to the DP solution of subset sum problem should work.
Killer thinking, +1. Fresh out of college? Just kidding... :-)
- Murali Mohan August 29, 2013@pretonesio.
>> If 5 bits for the second position are passed in, make a x,y grid on the opposite half of the board and use the 5 bits to locate the second position.
Could you please define/elaborate what you mean by 'opposite half of the board'?
If the first piece is located at position (0,0) and the second piece is located at (8,8), how will 5 bits suffice to identify the second piece relative to the first? Please clarify.
Good solution. You can use an extra O(n) space to get a solution with O(n) time complexity.
1. In a pre-processing step, go through the "source" array, compute the position of each of the 0 to n elements and store in the auxiliary 'position' array.
2. Start at the heads of both source and target array and compare the elements
3. If the elements are the same or the value of the target array ==0 proceed to the next elements. Otherwise go to step 4
4. Find position of 0 using the 'position' array and swap it with the current element 'e' in the source array and update the positions of 0 and 'e' in the position array. Now swap 0 with the target element(found again using the position array) and after the swap, update their positions in the position array. Advance the pointers of both source and target arrays.
5. Repeat steps 3 & 4 until all the elements are processed.
Good one, an alternative:
P(AUBUC) = P(A) + P(B) + P(C) - P(AnB) - P(BnC) - P(CnA) + P(AnBnC).
Since A, B, C are independent events, the above becomes
P(AUBUC) = P(A) + P(B) + P(C) - P(A)*P(B) - P(B)*P(C) - P(C)*P(A) + P(A)*P(B)*P(C), which is
1/3 + 1/4 + 1/2 - 1/12 - 1/8 - 1/6 + 1/24 = 3/4
"What should the question be?"
- Murali Mohan August 25, 2013@masterjaso
I don't think your algorithm will ensure the relative positions of both +ve and -ve numbers. Will you algorithm work for [-1 1 -2 2 -3 3]?
@Mukesh
You are right yet again. If the notion of the 'middle' node is modified to be the one which contains the middle character of all the concatenated stings, the above algorithm should work . In the first pass, count the total number of characters of all the strings put together. In the subsequent passes, the forward and backward pointers can keep a track of the length of the strings they processed so far to infer whether or not the "middle" node is reached.
@Mukesh
By reversing "ab"->"c"-> "cba" from the middle, I meant "ab"-> "cba"->"c". However, I realize that my procedure works only for a few particular cases and hence is not a generic solution. Further thoughts on it below.
The simplest solution, by using extra space, would be to concatenate all the individual strings of the DLL from left to right (or right to left) by writing their characters into a character array and then check if that character array is a palindrome.
Without using extra space, you need to traverse the DLL once to count the # of nodes to identify the middle node.(middle node position = total node count/2).
0. After that one can start from both ends of the DLL.
1. Compare the characters of the strings by traversing the string pointed by the first pointer in forward direction and the string by pointed by the second pointer in reverse direction.
2. If the first pointer exhausts the string, advance it to the "next" node.[Note: The second pointer can still be on its original node. It need not be moved simultaneously with the first one]
3. If the second pointer exhausts the string, advance it to the "previous" node.[First pointer can still be on its original node]
And a couple of base/boundary cases as below need to be handled.
4. After advancing, if the first pointer reaches the middle node, and if the second pointer had already reached the middle node, check that the rest of the string pointed to by second pointer is a palindrome or is empty.
5. A symmetric case of case 4.
Worked with the following cases and it seems my new solution works
a bcdc ba
abc c ba
a a
@Nomad
Nice approach, would you care to elaborate it a bit?
The answer is the expected value of a geometric distribution. See my comment below.
- Murali Mohan August 23, 2013If getting a number smaller than the number that is picked first is considered a success, and otherwise a failure, then these events become Bernoulli trials.
The question asks:
>> Find the expectation value of *number of times* you need to pick numbers...
The answer to the question: "How many trials before a success" is provided by geometric distribution, whose mean, E[X] = 1/p, where p is the probability of success.
Case 1: If you replace
Let m be the number picked, then probability of choosing a smaller number is m-1/n. The expected value is therefore 1/(m-1)/n = n/(m-1)
Case 2: if you don't replace
Let m be the number picked, then probability of choosing a smaller number is m-1/n-1. The expected value is therefore 1/(m-1)/(n-1) = (n-1)/(m-1)
@eugene.yarovoi
You are right. That occurred to me a bit late :-)
Read the question carefully
>> You are given a *sorted* skewed binary tree
Without using extra space, you can first run a recursive procedure, which at each step, determines the heights of the left-subtree and right-subtree, and then does 'rotations' with either of the left/right children as pivot according to their heights.
This method would be terribly slow because at each recursive invocation to find the height of the tree, the whole sub-tree would be traversed.
It can be sped up by storing a height variable at each node of the tree and computing it's value only once, but then it amounts to using extra space.
By using extra space, you can do an inorder traversal, and write the elements to the array.
After that, use binary search to find the middle element of the array and make it the root. Recursively invoke binary search on the left half and right half of the array to create left subtree and right subtree. This will give you a tree of min-height.
Thanks gokayhuz for informing about the errors. Appreciate it. Could you please give the rationale why i+j should be n+1?
- Murali Mohan August 22, 2013@Mukesh
You should not have skipped reading the first line.
>>0. Find the total node count and go to the middle of the DLL.
@Kevin.Pheasey
So, now you are with Amazon?
Okay, it must be the longest path between two nodes in a tree. Does the tree have only parent pointers or does it have pointers to children as well?
How is the tree object managed? Is there a pointer to the root or do you have pointers to children? How can it be passed to a method?
Please define what a diameter of a tree is!
- Murali Mohan August 19, 2013I don't have a proof of whether or not solving
M(n) = Min{ Min(i) + Min(j)}, where i+j = n & i>2 & j>2
can lead to
4 + ((N-5)/3)*2
But, using the recurrence relation above, a simple DP solution that correctly computes the value is possible.
- Murali Mohan August 18, 2013I think the moves can better be represented by a recurrence relation. There are several bases cases here. If M(n) is the number of moves required on a nxn chessboard, we have the following base cases.
For 3x3 board, M(3) = 4 moves
For 4x4 board, M(4) = 2 moves. LIkewise,
M(5) = 4
M(6) = 4
M(7) = 4
M(8) = 6
M(9) = 6
For n >= 10, We have
M(n) = Min{ Min(i) + Min(j)}, where i+j = n & i>2 & j>2
Is 2f(n)=O(2g(n))? effectively implies is 2f(n)=O(g(n))? Because, in Big-Oh notation, we drop the leading constants.
To answer "is 2f(n)=O(g(n))?", we have:
f(n)=O(g(n)), which means
f(n) <= Cg(n), for some C>0 & for all n >n0
Multiply by 2 on both the sides
2f(n) <= 2Cg(n). Now let D= 2C
2f(n) <=Dg(n), which implies
2f(n) = O(g(n))
Hence 4(Always) is the answer. Since 4(Always) is the answer, 1(Never) and 2(Sometimes) are NOT the answers. 3(Yes if f(n)≤g(n) for all sufficiently large n) is an implication of the assertion "f(n)=O(g(n))" provided in the question. Therefore, it is a part of the question and is not an answer.
6 moves
- Murali Mohan August 18, 2013Excellent! +1
- Murali Mohan August 18, 2013Another alternative is to use modified merge sort. The merge procedure needs to be modified so when a duplicate is returned, it is pushed towards the end of the array. This way the merge procedure produces an array which is sorted in the first part and has repetitions in the second part. The index delimiting the sorted part with the unsorted part would be returned by the merge procedure to it's caller.
Merge sort requires O(n) extra space, so this procedure can be used if space is not at a premium.
Use 3 pointers - first to point to the head node, second to move at a pace of one node at a time and third to move at a pace of 2 nodes at a time. Keep moving the second and third pointers so when the third pointer becomes equal to the first pointer, we have the middle node pointed by the second pointer.
- Murali Mohan August 17, 2013A few known ways:
1. Sort the array and count the duplicates by checking adjacent elements.
2. Use a hashtable with string as key and counter as value, Store the keys and update their corresponding counters as the array is traversed. In the end print out the count of the duplicates by traversing the hashtable
3. Use a modified trie to store the strings along with a counter field. While traversing the array, update the counters of the trie for each of the string. Traverse the trie and print out the count of the duplicates.
A few known ways:
1. Sort the array and remove duplicates by checking adjacent elements.
2. Use a hashset to store the elements and print them out.
3. Use a trie to store the strings and print them out by traversing the trie.
Exchange first and last elements, then exchange second and second-last elements and so on.
- Murali Mohan August 17, 2013Take 2 pointers- move the first one past 5 nodes from the head and then start the second one at the head. Keep advancing both the pointers one step at a time until the first pointer reaches the last node when which the second will be pointing to the 5th node from the last.
- Murali Mohan August 16, 2013@Eugene
Do you work for Microsoft/Amazon/Google? Could you please guide in preparing for their interviews?
@Amit
What if the x and y's strings are of unequal length? The question is asking to check if the combined strings of all the nodes is a palindrome, which does not necessarily mean that the first and last strings will be of equal length and so will be the strings of second and the second-last nodes
0. Sort the array. This will have complexity O(nlgn)
1. Then starting from the beginning of the array, count the total number of repetitions of all the elements. For ex: in the sorted array [1 1 1 2 2 3 3 3 3], the total number of repetitions would be 6 (2 1s, 1 2s, 3 3s). Set it to a variable called repetition_count, so repetition_count = 6.
3. Start two pointers, one at the end at n-1 and the other at the middle at n-repetition_count+1
4. Swap the values of the end and the middle pointer and decrement them both
5. if the end pointer has the same value as the one before one decrementing it, keep decrementing the end pointer until a new element is encountered
6. Repeat steps 4 & 5 until the end pointer gets to the index: n-repetition_count+1
Steps 3 to 6 in action below:
[1 1 1 2 2 3 3 3 3] swap and decrement both the pointers
^ ^
[1 1 3 2 2 3 3 3 1] decrement the end pointer
^ ^
[1 1 3 2 2 3 3 3 1] decrement the end pointer
^ ^
[1 1 3 2 2 3 3 3 1] decrement the end pointer
^ ^
[1 1 3 2 2 3 3 3 1] swap and decrement both the pointers
^ ^
[1 2 3 2 1 3 3 3 1] decrement the end pointer
^ ^
[1 2 3 2 1 3 3 3 1] stop
^ ^
@neezzz
- Murali Mohan September 08, 2013This doesn't look like an interview question, but looks more like an academic project being tried to getting done via careercup.