Murali Mohan
BAN USER 0of 0 votes
AnswersHow do you swap bits at indexes i & j of a 32bit 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 N1. An array has indices ranging from 0 to N1. 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 SDE2 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 SDE2 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 SDE2 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 SDE2 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
@Nascent
Your question provoked me to think further. At first, I thought of using a stack to build a tree  when you see a beginning tag push it on to the stack and when you see the ending tag, pop it out of the stack. Before pushing on to the stack, if the stack has already any elements present in it, the top most element would be the parent element of the current element. This method should build the tree.
However, it seems there is no need to build a tree at all. As mentioned in other posts, a SAX parser should do the job just fine. I too realized it after giving it a little more thought. Some SAX parsers, like that of PHP, provide a mechanism to invoke callback functions on entering and exiting a node/tag. A callback function that checks whether the current tag matches the given tag and prints the value should work fine.
You have to start from the maximum number and keep concatenating down to the minimum number
 Murali Mohan July 02, 2013Section 11.4.3 of Brian Goetz's "Java Concurrency in Practice" has a mention about lock striping. It can be found at: freepdfdb.org/pdf/briangoetzjavaconcurrencyinpracticepdf
 Murali Mohan July 02, 2013OK. Since an XML document can be represented as a tree, we can do a levelbylevel traversal using 2 queues(or stacks).
One queue would hold the parent nodes and as a parent node is dequeued, the other queue is populated with it's children. Once the queue holding the parents is emptied, it will start holding the children of the nodes from the queue holding the children.
While adding to the queue(or removing from it) if a node matches the given tag, print its value.
Continue this till the bottom level of the XML tree is reached. Time complexity is O(n) since each node is visited only once. Space complexity is also O(n) because of the additional queues
@Nascent
Do we need to compute the two's compliment form and print it out as a string? Otherwise, since a computer anyway stores a number in two's compliment form, we can just print out the bits of the memory word.
Sharma ji, you should not use newInputArray[] as the question is asking for inplace modification.
 Murali Mohan July 02, 2013@Nascent
Are the entries specified using an XPath?
Since we can't hold even k elements in memory, another alternative is to use a minheap of size k/2. In the first pass, keep storing the top k/2 elements in the minheap and output them at the end of the iteration.
In the second pass, store the next top k/2 elements and output them.
Time complexity would be O(nlg(k/2)). If k is large, then it would make a difference to Subhajit's algorithm. Otherwise, time complexity would be nearly the same as his.
Nice.
 Murali Mohan July 02, 2013Use 4 pointers from the ends of the 3 sorted arrays as well as the larger array.
1. Use 3 way comparison to find out the maximum element of the 3 sorted arrays and place it at the end of the larger array. Decrement the pointer of the larger array and of the sorted array where the maximum was found.
2. Repeat step 1 until one of the array is exhausted.
3. Start doing 2way comparison and placing the maximum value in the larger array
4. Repeat step 3 until only one array remains
5. Copy the contents of the remaining sorted array into the larger array.
Maintain 2 pointers i and j.
0. Start at the beginning of the string.
1. Copy the character at j to the character at i and advance both i and j one step to the right.
2. If the character at index i is a '%', advance j by 3 characters to the right.
3. If the substring between i and j = '%3A', replace '%' with a '?' at the ith position and advance i by 1 position to the right. Otherwise do nothing.
4. Repeat steps 1 & 2 till j reaches the end of the string.
5. Terminate the string at position i.
@mani 4m sklm
Suffix arrays are usually used to solve problems that involve dealing with contiguous subarray/substrings etc.
DP on the other hand is particularly used to solve optimization(maximization or minimization) problems. Also, the given optimization problem has to have the following properties in order for DP to be applied.
1. Optimal substructure (Optimal solution to the problem is constructed from optimal solutions to subproblems)
2. Overlapping subproblems
I am unable to clearly see the above 2 properties in the given problem and so resorted to using a suffix array. You can give it a shot using DP, though, if you deem it fit to be applied.
There are 52 weeks in a year. So a given day has to appear at least 52 times, with 2 exceptions.
If Xday is the starting day in a nonleap year, then X day appears 53 times
if Xday is the starting day in a leap year, then X day and X+1 day both appear 53 times
@ashot madatyan
That's a valid concern. In approach #2, If we think further, we can get rid of the lg(N) additional space by using the following technique. In each round of tournament, if we are comparing elements at locations i and j (where i < j), if a[j] < a[i], then swap a[i] with a[j].
For ex: in the first round, the comparison would be between elements that are 1 location apart as follows:
(1,2)(3,4)(5,6)(7,8)..etc
If we suppose that a[1]<a[2] & a[5]<a[6], but a[3]>a[4] & a[7]>a[8] then swap a[3] with a[4] and also a[7] with a[8] so in the next round we compare:
(1,3)(5,7)... etc.. [Here the elements that need to be compared are 2 locations apart. Again if i<j and a[i]>a[j] swap a[i] with a[j]]
In the next round we will compare elements that are 4 locations apart as below:
(1,5)(9,13)... etc and this process goes on until only one element (i.e, the first element remains)
This ways, we will eliminate the need to have extra space and the minimum element at the end would always be the first element.
@Epic_coder.
Yeah, the problem could be solved by Suffix tree as well. I believe that using suffix array eases the implementation.
@vankasundeep.
The complexity I believe is O(n^2lgn) due to the sorting step.
Let h1 be the time required to climb up to the top of the mountain on the horseback and h2 be the time required to climb down to the bottom on the horseback.
Let p1 and p2 be times required for the person to climb up and climb down on foot.
The person has to make four different kinds of roundtrips and measure the round trip times.
1. Climb up and climb down on horseback. The round trip time would be: h1 + h2 = t1 (t1 is measured accurately using the clock at the bottom)
2. Climb up and climb down on foot. The round trip time would be: p1 + p2 = t2
3. Climb up on horseback and climb down on foot. The round trip time would be: h1 + p2 = t3
4. Climb up on foot and climb down on horseback. The round trip time would be: p1 + h2 = t4
Now we have four equations and four unknowns:
h1 + h2 = t1
p1 + p2 = t2
h1 + p2 = t3
p1 + h2 = t4
(t1 to t4 are measured values and hence are known). Solving the system of linear equations gives the values of h1, h2, p1 & p2.
Now start from the bottom of the hill, record the time, call it t, using the clock at the bottom and climb up either on horseback or on foot.
Once you reach the top, correct the clock's time at the top to be either t + h1(if you have climbed up the hill on horseback) or t + p1(if you have climbed up the hill on foot).
Use MSD radix sort to sort the numbers in descending order. Starting from the maximum value, keep concatenating the numbers.
 Murali Mohan June 30, 2013Does the word here mean that it is delimited by nonword character like space/tab/EOF/punctuation etc? What if the given word itself has spaces in between? Does building a trie help in this case? Could you please illuminate a bit more on the solution?
 Murali Mohan June 29, 2013@aka
Good one. one upvote from me. Did you test for all scenarios? I suspect there is a bug lurking though....I suppose that the following modification should be made
if(pivot < k)
q_s(a, pivot+1, right, kpivot);
else
...

Murali Mohan
June 29, 2013 @aka
Suffix array is actually a 2D array. The suffix array for the given array {4,5,6,8,3,1,4,5,6,3,1} would be as below. Here, each element of the array itself is an array.
{4,5,6,8,3,1,4,5,6,3,1}
{5,6,8,3,1,4,5,6,3,1}
{6,8,3,1,4,5,6,3,1}
{8,3,1,4,5,6,3,1}
{3,1,4,5,6,3,1}
{1,4,5,6,3,1}
{4,5,6,3,1}
{5,6,3,1}
{6,3,1}
{3,1}
{1}
After sorting the suffix array, you'd get:
{8,3,1,4,5,6,3,1}
{6,8,3,1,4,5,6,3,1}
{6,3,1}
{5,6,8,3,1,4,5,6,3,1}
{5,6,3,1}
{4,5,6,8,3,1,4,5,6,3,1}
{4,5,6,3,1}
{3,1,4,5,6,3,1}
{3,1}
{1,4,5,6,3,1}
{1}
Checking for matching subarrays is easily done in a suffix array by comparing the prefixes. If you traverse the above sorted array and compare adjacent elements for similarity you'd see the prefix [4,5,6] is occurring maximum number(=2) of times and is also of maximum length. There are other subarrays as well, like [6], [5,6],[3,1] and [1] that are occurring 2 times, but they are shorter than the subarray [4,5,6], which is our required answer. HTH.
@Epic_coder
You are right, the statement that it reduces to finding the longest repeated substring is misleading. I am editing my post. Thanks for the correction.
However, the technique of building the suffix array still holds, because, it is going to make life easier in terms of matching subarrays. The other variables  frequency and length  as I mentioned helps in finding the solution.
Good one. +1 for you Subhajit. It is just that in order to find nth maximum number, you need to find M(n1)st order statistic in quickselect algorithm. Here M is the total number of elements in the array. That should address J's concern as well.
 Murali Mohan June 29, 2013Divide the big memory chunk into smaller chunks. Use lockstriping as is done by Doug Lea for ConcurrentHashMap to lock those smaller chunks in order to allocate/release memory for each thread.
 Murali Mohan June 29, 2013An O(n) solution is to use linear selection algorithm to find (k+1)st order statistic [ie (k+1)st min element]. All elements to the left of the index  k+1 in the partitioned array are the k minimum elements.
 Murali Mohan June 29, 2013there are 2 approaches, both involve n1 comparisons
1. Pick first element as the minimum. Compare the minimum with the rest of the n1 elements, each time updating it if the new element compared is less than the current minimum
2. Use a tournament type of approach, where adjacent elements are compared and min of the two is selected. Among the first set of minimum elements do the tournamenttype comparison again. Repeat the steps until the minimum is found.
KMP is an efficient string matching algorithm with time complexity O(n), where n is the length of the sentence.
Use a counter and each time KMP matches the word in the sentence, update the counter and return it in the end.
1. Build a suffix array and sort the array. Use 2 variables  one to maintain the length of the longest repeated sub array and the other to maintain the frequency.
2. Traverse the sorted array to find out the most occurring and longest repeated subarray and return it.
I think the following algo should work.
1. Compute the primes using sieve of Eratosthenes, upto m. Set m initially to a small number as 2 or 3.
2. If n < m then return the nth prime else set m = m^2 and repeat steps 1 & 2, each time reusing the previously computed sieve.
A bad app is the same as a bad question as this one. A good app is it's opposite.
 Murali Mohan June 27, 2013Use MSD radix sort and "concatenate" the numbers in descending order.
 Murali Mohan June 26, 2013Yet another approach is to form pairs of numbers from 4!(=24) permutations. Pairing should happen in such a way that at a given position, the maximum digit of one number should match with the minimum digit of the other number, the second maximum digit should match with the second minimum and so on.. For ex:
Pair up 1234 with 4321, 2134 with 3421 etc. The sum of each of these pairs is equal to 5555 and we have 12 pairs out of the total 24 permutations.
5555 * 12 = 66660
How about this approach?
With 4 placed in units place, there are 3! permutations of 123 in thousandths, hundredths and tenths place. That means 4 occurs in units place 3! times.
Similarly 3 2 and 1 each occur in units place 3! times. The sum of all numbers in units place is therefore 3!(4 + 3 + 2 + 1) = 6 * 10 = 60.
The same value happens to occur in tenths, hundredths and thousandths place as well, except that it gets multiplied by a power of 10 according to its position.
So, the total should be 60 + 600 + 6000 + 60000 = 66660.
Good one(+1 for you) and reason I see is that perfect square has odd number of factors. Since the doors were all initially closed, an even number of factors for a given door number closes it and the odd number of factors opens it.
 Murali Mohan June 26, 2013Use MSD radix sort and concatenate the numbers in descending order.
 Murali Mohan June 26, 2013@Sunny
In the forloop vgeek is removing the elements until the sum % 3 = 0. I think that should work.
Can this algorithm be generalized for m generic divisors d1,d2...dm?
1. Augment the BST with size field.
2. First find the rank of the given key k, and let it be r.
3. Find the (r+1)st order statistic, which is the ceiling element of the key k.
(Finding rank and selecting the ith order static are standard procedures on a sizefield augmented BST)
@Sunny
Good one, +1 for you. Though I see you need to take care not to add the same string to both hashtable1 and hashtable2. For ex: a string of the form aaaaaaaaabaaaaaaaaa might have 'a' as the longest prefix as well as the longest suffix, but they cannot be permuted to form the longest contiguous sequence.
@yokuyuki
>> No, they're exactly the same. Rotating 1 to the right is the same as rotating n1 to the left.
But rotating 1 to the right is not the same as rotating 1 to the left.
Why not build a (balanced) BST such that its nodes are augmented by 2 fields? One field will maintain the count of the element from the first array and the other one will maintain the count of the element from the other array.
While building the tree, if a node is not present, insert it into the tree, otherwise update it's count fields depending on whether we are traversing the first array or the second one.
Once the tree is built, do an inorder traversal and check if the counts are equal. At any stage if the counts are unequal return false. Otherwise return true in the end. Time complexity to build the BST = O(nlgn). Inorder traversal requires O(n), hence overall complexity = O(nlgn)
Why use extra stack space and put all the chars of string2 on to it? Why traverse from the end of string1? Why this additional complexity? Is it in anyway more efficient than starting from the beginning of both the strings and comparing them character by character?
 Murali Mohan June 22, 2013@Sushant
On what criteria would you clear the hashset?
Actually, the solution to a problem depends on the context. If the problem is such that all we see are 32 bit numbers and we have 4GB of RAM, then one can use a bit vector to mark the presence of elements as they are seen. We can then check the bitvector to see whether or not an element exists.
Rotating to the right and rotating to the left are different. However, the code is easy.
public <T> void rotateRight(T[] t, int start, int end) {
if (start < end) {
T last = t[end];
for (int i = end; i > start; i) {
t[i] = t[i  1];
}
t[start] = last;
}
}
public <T> void rotateLeft(T[] t, int start, int end) {
if (start < end) {
T first = t[start];
for (int i = start; i < end; i++) {
t[i] = t[i + 1];
}
t[end] = first;
}
}

Murali Mohan
June 22, 2013 Compare the two strings character by character
 Murali Mohan June 22, 2013Keep adding the elements to a hashset and query it for the given element.
 Murali Mohan June 22, 2013Could you please elaborate what the questions were?
 Murali Mohan June 22, 2013I think the question should be asking to check if two (binary) trees are structurally similar, in which case you can use recursion to solve the problem.
 Murali Mohan June 22, 2013@Anonymous
Is this an optimization question where you need to minimize the number of phrases? Otherwise, there is always this trivial solution of splitting the ncharacter string into n phrases where each phrase pi = p0 + ith character
If we think in terms of the reverse of a word, the operation of adding the bytes and dividing them by 2 seems to get simplified. The notion of adding the bytes and shifting them to one position right in a regular word, transforms, in a reversed word, to ignoring the result of addition of LSBs in each byte of the input words.
Based on the above notion, the following principle worked.
1. Run an index, i from 1 to 32
2. Extract the ith bit from the words of A and B. (This can done by extracting their LSBs and then shifting them one position to the right.)
3. Add the ith bits of both A and B and store the values of result and carry.
4 if (i % 8 == 1) shift C one position to the left and add the carry
5 if (i % 8 != 1) compute the result of adding ith bits of A and B, shift C one position to the left and add the result.
6. In the end, reverse C and print the value.
Tested the following program with inputs:
0x7FFFFFFF (maximum integral value in Java)
0x7FFFFFFF (outputs 0x7FFFFFFF)
0x00000100
0x00000300 (outputs 0x00000200)
0x7aacacac
0x7ccecece (outputs 0x7bbdbdbd)
import java.util.Scanner;
import java.util.regex.Pattern;
public class BytewiseAddition {
static int fa, fb;
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("First number:");
if (scanner.hasNext()) {
String ip = scanner.next();
if (ip.toLowerCase().startsWith("0x")) {
ip = ip.substring(2);
}
fa = Integer.parseInt(ip, 16);
}
System.out.println("Second number:");
if (scanner.hasNext()) {
String ip = scanner.next();
if (ip.toLowerCase().startsWith("0x")) {
ip = ip.substring(2);
}
fb = Integer.parseInt(ip, 16);
}
}
public static int computeSum(int a, int b) {
int i = 1, c = 0, previousCarry = 0, nextCarry = 0, tmp = 0;
while (i <= 32) {
if (i % 8 == 1) {
c = (c << 1)  previousCarry;
previousCarry = 0;
}
tmp = (a & 1) + (b & 1) + previousCarry;
nextCarry = (tmp & 2) >>> 1;
tmp &= 1;
a = a >>> 1;
b = b >>> 1;
if (i % 8 != 1) {
c = (c << 1)  tmp;
}
i++;
previousCarry = nextCarry;
}
c = (c << 1)  previousCarry;
return revBitString(c);
}
public static int revBitString(int i) {
int mask = 1, rev = 0, maskComplement = 1, count = 0;
while (maskComplement != 0) {
maskComplement = maskComplement << 1;
count++;
}
maskComplement = 1 << count  1;
while (mask != 0) {
if ((mask & i) != 0) {
rev = rev  maskComplement;
}
maskComplement = maskComplement >>> 1;
mask = mask << 1;
}
return rev;
}
public static String zeroPrefixHexString(String s) {
return "0x0000000".substring(0, 10  s.length()) + s;
}
public static void main(String[] args) {
readInput();
System.out.println("C="
+ zeroPrefixHexString(Integer.toHexString(computeSum(fa, fb))));
}
}

Murali Mohan
June 21, 2013 Similar question has been solved using dynamic programming at: question?id=19378664
Follows the recursive structure:
currentSum = max{A[i], max{A[i2] + A[i], A[i2]}, max{A[i3] + A[i], A[i3]}, } // i runs from 2 to N.
Full working implementation in java is given below. Give the input numbers using space as delimiter.
Eg: 1  1 3 8 4
1 5 3 9 4
1 2 3 4 5
import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MaxSumSubset {
static ArrayList<Integer> input = new ArrayList<Integer>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator")
+ "\\s");
scanner.useDelimiter(pattern);
int intval, tempMax = 0;
while (scanner.hasNextInt()) {
intval = scanner.nextInt();
input.add(intval);
}
int[] vals = new int[input.size()];
if (vals.length > 1) {
vals[0] = input.get(0);
vals[1] = Math.max(input.get(0), input.get(1));
for (int i = 2; i < input.size(); i++) {
tempMax = Math.max(vals[i  2], vals[i  2] + input.get(i));
vals[i] = Math.max(tempMax, input.get(i));
if (i  3 >= 0) {
int tempMax2 = Math.max(vals[i  3],
vals[i  3] + input.get(i));
vals[i] = Math.max(tempMax2, vals[i]);
}
}
}
tempMax = 99999999;
for (int i = 0; i < vals.length; i++) {
if (vals[i] > tempMax) {
tempMax = vals[i];
}
}
System.out.println("Maximum sum=" + tempMax);
}
}

Murali Mohan
June 21, 2013 Open Chat in New Window
My 2 cents.
 Murali Mohan July 03, 2013On a 32bit machine, the OS can create virtual memory of up to 4GB. That would be the upper limit of address space of a process. On 64 bit machines, the virtual memory can be expanded to 2^64 and so is the address space of a process.