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
this is Hoffman encoding in disguise
- Murali Mohan February 27, 2016O(1) space complexity and O(logn) time complexity
- Murali Mohan December 27, 20151. For both n1 and n2, count the number of nodes on their paths till the root. Let them be c1 and c2.
2. Suppose c1 > c2.
3. Traverse the parent/ancestor nodes of n1 for (c1-c2) steps till we reach some ancestor a1.
4. Compare a1 and n2. If (a1 == n2) return n2; else go to step 5
5.Traverse the parents/ancestors of a1 and n2 till either you find same ancestors or reach the roots (and beyond)
What a retard... assignment statement cannot be present in the ternary operator.
- Murali Mohan July 26, 2015Actually CalledFunc() should be present in a try-catch-finally block. If you are using your own lock objects, they must be explicitly released in the finally block.
- Murali Mohan July 26, 2015Actually CalledFunc() should be present in a try-catch-finally block. If you are using your own lock objects, they must be explicitly released in the finally block.
- Murali Mohan July 26, 2015Simply extend LinkedHashMap class and in the constructor set the parameter 'accessorder' = true.Override the method removeEldestEntry() and you are done.
LinkedHashMap manages the data using a hashtable and doubly-linked list. Whenever a hashtable key is accessed or inserted or modified, value is moved to the tail of the linkedlist. In that way, the least recently used element is always present at the head of the linkedlist.
This can be done using recursion.
int maxLength = 0;
findMaxLength(node, parentNodeVal, lengthSoFar) {
if (node.Val == parentNodeVal + 1) {
if (lengthSoFar + 1 > maxLength) {
maxLength = lengthSoFar + 1;
}
lengthSoFar++
} else {
lengthSoFar = 1;
}
for (Node child: node.Children) {
findMaxLength(child, this.val, lengthSoFar);
}
}
1.You light first candle on day one. heights -> {1,2,2}
2.You light second and third and extinguish first one . heights ->{1, 1,1}
3.You light all the candles. heights -{0,0,0}
>> How can you light candles 2 and 3 when they are already lit? Question is very ambiguous.
@Anonymous
>> autoboli, to encode / decode each card, both sides would use an array filled with a pre-determined card order:
Where is the pre-determined card order? The deck is being shuffled...
Why is this solution correct?
What does the statement: bits += log((double)x) mean?
Can someone please explain?
@Zzenith.. I thought the same.
- Murali Mohan February 23, 2015Sort the initial list of Range classes that do not overlap.
Given the newRange class that may or may not overlap...
Do a binary search on the sorted list of Range classes to figure out the overlapping range.
The meat of the solution lies in the criteria to search in the left/right subarrays using both the Range.begin and Range.end keys.
The question is a bit vague. Are you asking for the evaluation of the expression in a string?
One approach would be to get character array of the string and then use stack data structure to evaluate the expression.
To evaluate the expression, you also need precedence and associativity rules of the operators.
I know of a recursive procedure. The whole string is to be processed one character at a time, by checking if the string processed so far is valid and the remaining unprocessed string recursively passed to the method. Dynamic programming using tables should yield better results.
- Murali Mohan September 25, 2014I know of a recursive procedure. The whole string is to be processed one character at a time, by checking if the string processed so far is valid and the remaining unprocessed string recursively passed to the method. Dynamic programming using tables should yield better results.
- Murali Mohan September 25, 2014int n = 0
while (number > 0) {
number >> 1;
n++
}
Brilliant!
- Murali Mohan August 18, 2014Excellent! +1(10 times)
- Murali Mohan July 31, 2014From the meaning of a 'tree' being sorted, I could only that much!
- Murali Mohan July 31, 2014Use recursion.
Base case: Leaf is always sorted.
Recursive case: return true if: left subtree is sorted and right subtree is sorted and that root_of_left_subtree < root < root_of_rightsubtree.
Just realized that simple count won't suffice, need to figure out monotonically increasing subsequences from left to right as well as from right to left of the given element.
- Murali Mohan July 28, 2014Good question, though the problem statement is a bit vague. I assume that the problem is asking to find out all the elements to the left and right of the current element in the array that are greater than current element.
One approach is to use two cumulative arrays - one that stores the count of elements greater than the current element to it's right and the other to store the count of elements greater than the current element to it's left.
The cumulative arrays are computed by building BSTs so during the insertion of an element, we figure out the number of elements that are greater. We need to build two BSTs - one while traversing the array forward and the other while traversing the array backward.
Either sort and find out the duplicates or use a hashtable to count the duplicates.
- Murali Mohan July 28, 2014I may not understood your solution completely, but I don't think we need all the trouble.
Since both the arrays are sorted, we start two pointers at the middle elements of the arrays. Compare the elements.If they are equal they are the medians. If one is less than the other, move the pointer of the lesser value to the right. A constant number of such technical manipulations of the pointers and comparisons of the elements, you should be able to realize the median. Let me know if you have a counter-example.
@ysoseriou
You are right up to the point:
>> Read 1 Gb of data from disk, sort them and put them back onto the disk as group0. Similarly prepare group1, group2,.....group199.
Further to this, you can do an external merge sort to sort all of the 199 groups. Once you get the whole data sorted, you can use a min-heap of size k to maintain the top k most frequent strings as you read the data in a stream.
I don't think the solution is complete here in any sense.
- Murali Mohan July 24, 2014This is the solution!
- Murali Mohan July 24, 2014wikipedia->AKS_primality_test
- Murali Mohan July 24, 2014AKS algorithm for primality testing
- Murali Mohan July 24, 2014Reverse the whole sentence first. Then leave the first word and reverse the second word. If the question is really asking to have this pattern of reversed word and a non-reversed word, continue this processing of reversing alternate words till the end.
- Murali Mohan June 30, 2014Not sure what it means by doing it better than in O(N^2). The number of array elements is O(N^2) and it takes at least O(N^2) steps to initialize the matrix. Also, is a node predecessor of itself?
Suppose the matrix was initialized with 0s. The next steps are to put 1s in it satisfying the above criterion.
Use recursion to solve this problem. During the unwinding of recursion -
1) If you are at the leaf node, do nothing.
2) else
2a. Copy 1s from the rows of left and right children
2b. Set M[currentNode][leftChild] = 1 and, M[currentNode][rightChild] = 1
If we look at the averages in another way, the problem is asking whether it is possible to divide the set into two subsets such that the sum of elements of one subset is a multiple of sum of elements of another subset. Apparently, this is a variant of partition problem and I think some existing DP algorithms should work, though I haven't worked out the details.
- Murali Mohan June 26, 2014If we look at the averages in another way, the problem is asking whether it is possible to divide the set into two subsets such that the sum of elements of one subset is a multiple of sum of elements of another subset. Apparently, this is a variant of partition problem and I think some existing DP algorithms should work, though I haven't worked out the details.
- Murali Mohan June 26, 2014And yes, MD5 is a hash function that returns a fixed-size hash value. The size is the same from an empty string to an infinitely-long string.
- Murali Mohan June 11, 2014MD5 is simply a cryptographic hash function. Hashing is a one-way transformation of data from one form to another. Don't dream of reconstructing the original data from hashed data.
BTW, are you trying for an algorithm to break encryption?
In the forward pass count the number of 'ic's in the string. Let the count be n. In the backward pass, start at 2*n places beyond the end of the string and keep copying the characters until (ic) is encountered. (ofcourse a look-ahead of 1 character is needed in the scan to capture 'ic'). Once ic is encountered, replace it with MSFT and continue till the beginning of the array.
- Murali Mohan June 10, 2014Using library function is not appropriate.
Use 2 pointers - Initially both point to the beginning of the array. The first pointer keeps track of a space and the second pointer is advanced to find a non-space character.
Upon finding the non-space character, it is copied to the location of the first pointer and then both the first and second pointers are advanced. The second pointer has to deal with a boundary condition that it has to treat the first space character after the word boundary as part of the word.
Does anyone have any involved ideas using Branch and Bound or so?
- Murali Mohan June 08, 2014I wonder if DP can get the job done. I tried a recursive brute-force with memoization of subproblems. The numbers of subproblems are varying at each level...not sure how that can be captured using DP. The total number of subproblems that need be searched for an input of size 3n using brute-force is n!*3^n .However using memoization, that number can be reduced as the following examples illustrate.
Input(Size 36):
0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0
Output:
Time taken in secs=284
Maxsize = 72
No. of subproblems of size(3): 936
No. of subproblems of size(6): 18018
No. of subproblems of size(9): 97240
No. of subproblems of size(12): 226746
No. of subproblems of size(15): 279072
No. of subproblems of size(18): 201894
No. of subproblems of size(21): 91080
No. of subproblems of size(24): 26325
No. of subproblems of size(27): 4872
No. of subproblems of size(30): 558
No. of subproblems of size(33): 36
No. of subproblems of size(36): 1
Input(Size 39):
0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0 0 9 8
Output:
Time taken in secs=1149
Maxsize = 81
No. of subproblems of size(3): 1183
No. of subproblems of size(6): 28392
No. of subproblems of size(9): 189618
No. of subproblems of size(12): 545870
No. of subproblems of size(15): 831402
No. of subproblems of size(18): 749892
No. of subproblems of size(21): 427570
No. of subproblems of size(24): 159705
No. of subproblems of size(27): 39585
No. of subproblems of size(30): 6448
No. of subproblems of size(33): 663
No. of subproblems of size(36): 39
No. of subproblems of size(39): 1
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.regex.Pattern;
/**
* @author Murali Mohan
*
*/
class PizzaPiece {
int size, index, leftNeighbor, rightNeighbor;
boolean isTaken = false;
PizzaPiece(int size, int index) {
this.size = size;
this.index = index;
}
}
public class PizzaPiecesDP {
static List<PizzaPiece> pieces = new ArrayList<PizzaPiece>();
static List<PizzaPiece> selectedPieces = new ArrayList<PizzaPiece>();
static Map<String, Integer>[] pieceSubsets;
public static String getKey(int chosenPizzaIndex, List<PizzaPiece> pizzaPieces) {
Collections.sort(pizzaPieces, new Comparator<PizzaPiece>() {
public int compare(PizzaPiece piece1, PizzaPiece piece2) {
return piece1.index - piece2.index;
}
});
StringBuffer key = new StringBuffer();
for (int i = 0; i < pizzaPieces.size(); i++) {
if (!pizzaPieces.get(i).isTaken) {
key.append(":" + pizzaPieces.get(i).index);
}
}
return key.toString();
}
public static int computeMaxSubset(List<PizzaPiece> pizzaPieces, int startIndex, int remSize) {
//System.out.println("Begin: startIndex=" + startIndex + " remSize=" + remSize);
int max = 0, maxIndex = -1;
String key = "";
Integer remOptSize;
if (remSize == 3) {
key = getKey(startIndex, pizzaPieces);
remOptSize = pieceSubsets[0].get(key);
if (remOptSize == null) {
if (!pizzaPieces.get(startIndex).isTaken && !pizzaPieces.get(pizzaPieces.get(startIndex).leftNeighbor).isTaken && !pizzaPieces.get(pizzaPieces.get(startIndex).rightNeighbor).isTaken) {
max = Math.max(pizzaPieces.get(startIndex).size, Math.max(pizzaPieces.get(pizzaPieces.get(startIndex).leftNeighbor).size, pizzaPieces.get(pizzaPieces.get(startIndex).rightNeighbor).size));
pieceSubsets[0].put(key, max);
} else {
System.out.println("WARN: Something's wrong!");
}
} else {
max = remOptSize;
}
} else {
int i = startIndex;
for (int j = 0; j < remSize; j++) {
key = getKey(i, pizzaPieces);
remOptSize = pieceSubsets[((remSize - 3) / 3)].get(key);
if (remOptSize != null) {
max = remOptSize;
} else {
int previous = pizzaPieces.get(i).leftNeighbor;
int next = pizzaPieces.get(i).rightNeighbor;
pizzaPieces.get(previous).isTaken = true;
pizzaPieces.get(i).isTaken = true;
pizzaPieces.get(next).isTaken = true;
PizzaPiece secondLeft = pizzaPieces.get(pizzaPieces.get(previous).leftNeighbor);
PizzaPiece secondRight = pizzaPieces.get(pizzaPieces.get(next).rightNeighbor);
secondLeft.rightNeighbor = secondRight.index;
secondRight.leftNeighbor = secondLeft.index;
remOptSize = computeMaxSubset(pizzaPieces, secondRight.index, remSize - 3);
if (max < remOptSize + pizzaPieces.get(i).size) {
max = remOptSize + pizzaPieces.get(i).size;
maxIndex = i;
}
pizzaPieces.get(previous).isTaken = false;
pizzaPieces.get(i).isTaken = false;
pizzaPieces.get(next).isTaken = false;
secondLeft.rightNeighbor = previous;
secondRight.leftNeighbor = next;
}
i = pizzaPieces.get(i).rightNeighbor;
}
pieceSubsets[((remSize - 3) / 3)].put(key, max);
}
//System.out.println("End: startIndex=" + startIndex + " remSize=" + remSize + " max=" + max + " maxIndex = " + maxIndex + " size = " + ((maxIndex == -1) ? 3 : pizzaPieces.get(maxIndex).size) + " key = " + key + " keysize = " + key.split(":").length);
return max;
}
public static void main(String[] args) {
System.out.println("Input 3n pizza sizes separated by space. Enter twice to start execution");
Scanner scanner = new Scanner(System.in);
Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
scanner.useDelimiter(delimiters);
int piecesNumber = 0;
while (scanner.hasNextInt()) {
PizzaPiece piece = new PizzaPiece(scanner.nextInt(), piecesNumber++);
piece.rightNeighbor = 0;
if (piecesNumber > 1) {
piece.leftNeighbor = (piecesNumber - 2);
pieces.get(piecesNumber - 2).rightNeighbor = piecesNumber - 1;
}
pieces.add(piece);
} ;
pieces.get(0).leftNeighbor = pieces.size() - 1;
if (piecesNumber % 3 != 0) {
throw new RuntimeException("# of pizza pieces is not a multiple of 3");
}
pieceSubsets = new HashMap[piecesNumber / 3];
for (int i = 0; i < piecesNumber / 3; i++) {
pieceSubsets[i] = new HashMap<String, Integer>();
}
long startTime = System.currentTimeMillis();
int maxSize = computeMaxSubset(pieces, 0, pieces.size());
long elapsedTime = (System.currentTimeMillis() - startTime)/1000;
System.out.println("Time taken in secs=" + elapsedTime);
System.out.println("Maxsize = " + maxSize);
for (int i = 0; i < pieceSubsets.length; i++) {
System.out.println("No. of subproblems of size(" + ((i+1) * 3 ) + "): " + pieceSubsets[i].size() /*+ ", "+ pieceSubsets[i].toString() */);
}
}
}
@Sunny.
Good one.Killer solution is not working lol. DP is the way to go. Thanks for the counter example.
Here is my killer solution that uses a greedy strategy. Several iterations are used, where a greedy strategy is applied in each iteration to find local maximum and then a global maximum is computed among the local iterations.
package com.marketshare.interviews;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.regex.Pattern;
/**
* @author Murali Mohan
*
*/
class PizzaPiece {
int size, index;
PizzaPiece(int size, int index) {
this.size = size;
this.index = index;
}
}
public class PizzaPieces {
public static void main(String[] args) {
List<PizzaPiece> pieces = new ArrayList<PizzaPiece>();
List<PizzaPiece> selectedPieces = new ArrayList<PizzaPiece>();
int localMax = 0, globalMax = 0;
System.out.println("Input 3n pizza sizes separated by space. Enter twice to start execution");
Scanner scanner = new Scanner(System.in);
Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
scanner.useDelimiter(delimiters);
int piecesNumber = 0;
while (scanner.hasNextInt()) {
PizzaPiece piece = new PizzaPiece(scanner.nextInt(), piecesNumber++);
pieces.add(piece);
} ;
if (piecesNumber % 3 != 0) {
throw new RuntimeException("# of pizza pieces is not a multiple of 3");
}
// Sort the arrayList
Collections.sort(pieces, new Comparator<PizzaPiece>() {
public int compare(PizzaPiece piece1, PizzaPiece piece2) {
return piece2.size - piece1.size;
}
});
for (int i = 0; i < piecesNumber / 3; i++) {
PizzaPiece firstPiece = pieces.get(i);
List<PizzaPiece> chosenPieces = new ArrayList<PizzaPiece>();
chosenPieces.add(firstPiece);
localMax = firstPiece.size;
int chosenPiecesount = 1;
for (int j = i + 1; j < piecesNumber; j++) {
PizzaPiece currPiece = pieces.get(j);
boolean canBeAdded = true;
// This for-loop should be a binary search tree to make the
// search and hence the solution more efficient
for (int k = 0; k < chosenPieces.size(); k++) {
PizzaPiece chosenPiece = chosenPieces.get(k);
if (((currPiece.index + 1) % piecesNumber == chosenPiece.index)
|| ((currPiece.index - 1 + piecesNumber) % piecesNumber == chosenPiece.index)) {
canBeAdded = false;
break;
}
}
if (canBeAdded) {
chosenPieces.add(currPiece);
localMax += currPiece.size;
chosenPiecesount++;
if (chosenPiecesount == piecesNumber/3) {
break;
}
}
}
if (localMax > globalMax) {
globalMax = localMax;
selectedPieces.clear();
selectedPieces.addAll(chosenPieces);
}
}
System.out.println("The maximum size that can be chosen is: " + globalMax);
System.out.println("Pieces' (size, position) are:");
for (PizzaPiece piece: selectedPieces) {
System.out.print("(" + piece.size + "," + (piece.index + 1) + ") ");
}
}
}
Well, DP is not needed. A killer solution with greedy-like strategy would work. I am posting my solution as a separate another comment.
- Murali Mohan June 03, 2014I think you are trying to flip the bits at positions i & j. The question is asking to swap the bit value at location i with bit value at location j.
- Murali Mohan June 03, 2014@Eugene.Yarovoi
Please ask me where you are not clear. I am also taking a stab at it using DP.
@Sunny, your understanding is correct and the example you gave is absolutely fine.
- Murali Mohan June 02, 2014Three numbers sum to zero in 2 cases:
1) Two -ve numbers and a +ve number sum to 0
2) Two +ve numbers and a -ve number sum to 0.
So, sort the array in ascending order, that gives subarrays of +ve and -ve numbers in sorted orders.
1. Then run a double for-loop, from the start, on the negative sub-array, and for this -ve tuple, look for the corresponding positive number(that sums up to 0) in the positive sub-array from the end.
2. Also run a double for-loop, from the end, on the positive sub-array, and for this +ve tuple,
look for the corresponding negative number(that sums up to 0) in the negative sub-array from the start.
Worst-case time complexity: O(n^2), Space complexity O(1)
Complex problem, backtracking is the algorithm technique that needs to be used though. Modifications to the solution of the standard problem should work.
- Murali Mohan April 16, 2014(0,0,0,0,0),(1,1,1,1,1,1,1)
The format is botched-up. If the array were separated into tuples, P1 and P2 would be initially pointing to the beginning of each tuple respectively.
Alas, what a fate Careercup is suffering from!
- Murali Mohan January 30, 2018Here we have advertisement of astrologers who can solve more than interview/technical problems... solving life's problems. LoL! Long live Careercup. Long live Astrologers!. Haha