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
Here, the question is about solving a technical problem. You are not asked to write up a thesis on linguistics.
- Murali Mohan July 16, 2013You are going in the right direction. Apply dynamic programming and think a bit further.
- Murali Mohan July 16, 2013The number actually can be given using a recurrence relation:
T(n) = 2T(n-1) + 2* Summation [(T(j) * T(n-1-j] Where j runs from 1 to (n-1)/2
You are right, the values of T(n) can be computed bottom up using DP.
Question continued, trying out some formatting as a comment.
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
I think, here we will have to consider n, the upper limit as a constant and m as the input size. In such a case, we can have an auxiliary array of size n that maintains the count of numbers from 1 to n.
The problem can also be solved in O(n) time if the array is already sorted, but not sure if such an assumption can be made.
@vstudio
Nice one. Thumbs up!
If the question is interpreted as to print the elements in a level-by-level fashion, an alternative is to use a dynamic array of hashtables to solve the problem.
Suppose we have an array A of hashtables with size m. Then:
1. If a new pair (e1, e2) is seen in the input, check if e1 is present in the hashtable at location A]m-1].
2. If present, create a new hashtable at location A[m] and insert e2 into it.
3. Else, continue checking if e1 is present in the hashtables from A[m-2] up to A[0].
3a. If e1 is found in a hashtable at location j (where m-2 <= j <= 0), insert e2 into a hashtable at A[j+1]
3b. Otherwise insert e1 into hashtable at A[0] and e2 into hashtable at A[1].
After the input is processed, Iterate through each of the hashtables from A[0] to A[size-1] in that order and print the values.
Not all computer programs can be written down in the format specified by you.
- Murali Mohan July 14, 2013Not all computer programs can be written down in the format specified by you.
- Murali Mohan July 14, 2013@algos
Good one.
I think step 2 can be modified a bit to reduce the number of overall comparisons. .
Once the first matching bolt is placed in its correct position, take a 2nd nut at random and compare it with the first matching bolt. Based on the result, match the nut with bolts in either smaller group or bigger group.
Take a 3rd nut at random and based on the comparisons with the first and second matching bolts, compare it with bolts in the appropriate sub groups. Continue this until all nuts are matched.
This obviates the need to compare a matching bolt with all of the remaining nuts to divide them into sub groups. The nuts themselves don't seem to be required to divide into subgroups.
Summation of (3^(i/2) * 4^(i-1)/2) ,where i runs from 1 to k.
Here i/2 and (i-1)/2 are the integral values of quotients.
- Murali Mohan July 14, 2013Proof that the sum of the first n odd numbers = n^2 can get simpler by induction.
Base case: n = 1, sum = n^2 = 1^2 = 1.
Inductive hypothesis: n^2 holds for the sum of the first n odd numbers:
Inductive step: Sum of the first n+1 odd numbers
= n^2 + Value of (n+1)st odd number(= 2(n+1)-1 =2n+1)
= n^2 + 2n + 1
= (n+1)^2
Once you know that the sum of the first n odd numbers = n^2, the above question can be solved easily by plugging value into the formula. For a given odd number n, the value that needs to be plugged into the above formula is (n+1)/2, as for a given odd number n in the sequence, (n+1)/2 is it's ordinal value.
- Murali Mohan July 14, 2013printf("%d\n", 10);
for (int i = 9; i >=1; i--)
printf("0%d\n", i)
printf("welcome\n");
If the input is assumed to be given as 3 points A, B & C, the euclidean (or some other metric like manhattan) distances |AB|. |AC| & |BC| can be computed and then:
|AB| <> |AC| <> |BC| implies scalene
(|AB| == |AC|) || (|BC| == |AC|) || (|BC| ==|AB|) implies isosceles .
Good one. For a given odd n, (n+1)/2 denotes its ordinal in the sequence of odd numbers and the sum of the first (n+1)/2 odd natural numbers = ((n+1)/2)^2
- Murali Mohan July 13, 2013Algorithm please.
- Murali Mohan July 11, 2013Use binary search to locate a given number in that number sequence. From that location, proceed both to the right and to the left until you see different numbers and mark the boundaries.
If the binary search is unable to find the given number, return -1,-1
I guess it is about employing K-Nearest Neighbors(KNN) algorithm to solve the problem.
- Murali Mohan July 10, 2013@Amit
To find the closest numbers, you can use the hashtable method itself with a slight modification to querying the hashtable.
>> before inserting each element a[i] in hash check whether k-a[i] +/- j, with 0 <= j <= c, for some constant c, is already in hash..if yes return true
You may want to maintain variables that keep track of the minimum difference seen far and the corresponding pair of numbers that have the min. difference.
c will always be a constant here, for if we let grow c to the order of n, say n/2, then (k - a[i]) will be of order n, which implies that the array elements are so sparse that their number tends to be a constant. In other words, you will have an O(n) solution, albeit with an appreciable constant.
Good one, +1 from me. Yes, binary search with some minor modifications works. The modifications are:
1. Include the 'middle' element in the search range while recursing on the left half or the right half of the array. (In the original binary search, the middle element, however, is discarded when recursing on the subarrays)
2. If left with a subarray of length 1, return that number
3. if left with a subarray of length 2, with elements e1 & e2, and n as the given number,
a. if |e1-n| = |e2-n| return either of e1 or e2.
b. else return min{|e1-n|, |e2-n|}
Modifications #2 & #3 are base cases and the correctness of the algorithm rests on #1, which can be argued as:
if a[mid] < n, there is no point in searching the left half of the array as (n-a[mid-j]) >= (n-a[mid]), for all j, 1 <= j <= mid. However, among a[mid + k] where 0 <=k <= size-1, a[mid] itself might be the element having the least difference with n. Hence include the index 'mid' while recursing on the right subarray.
if a[mid] > n, there is no point in searching the right half of the array as (a[mid+j] - n) > (a[mid] - n), for all j, 1 <= j <= size-mid-1. However, among a[mid - k] where 0 <=k <= mid, a[mid] itself might be the element having the least difference with n. Hence include the index 'mid' while recursing on the left subarray.
@subajit
Varun is correct. Simply checking the next consecutive numbers wont work, because the elements of a triplet can be more than a unit distance apart from one another.
As a counter-example, consider the following sequence of numbers and their indices
numbers: 3 2 1 5 4 6
indices: 1 2 3 4 5 6
After sorting, the numbers and indices change to:
numbers: 1 2 3 4 5 6
indices: 3 2 1 5 4 6
The algorithm that checks 2 consecutive elements will not detect any of the triplets: {3,5,6} {3,4,6} {2,5,6} {2.4.6} {1,5,6} & {1,4,6} that are present in the original array.
- Murali Mohan July 09, 2013@Jeanclaude
Will the input array always have numbers between 1 and n?
How about maintaining whitelists of all known nouns and verbs in two separate hash tables? Each time a word is read from the given book, query the hash tables to see if the given word is a noun or a verb.
- Murali Mohan July 09, 2013@Nascent
Good one, though, code needs some more fixes:
for (i=25;i<=75;i++) // A can be started from 25, because B+C can together hold a maximum of 75
for (j=0;j<=50;j++) // j should start from 0, because B can be 0
for (k=0;k<=25;k++) // k should start from 0, because C can be 0.
@CodeCracker
Thanks for the suggestion :). I will try to change it.
Good one. The below condition, however, needs a small change
if (root == root1 && root == NULL) // instead of if (root == root1)
return true;
Start from an initial configuration like:
C=25, B=0, A=75
Keeping C fixed at 25, the configuration can be changed to the below in 51 steps
C=25, B=50, A=25
A change from configuration C=24, B=1, A=75 to C=24, B=50, A=26 is obtained in 50 steps. Continuing this way, a change from configuration C=0, B=25, A=75 to C=0, B=50, A=50 requires 26 steps.
Therefore the total number of configurations = 26 + 27 + ... + 51 = 1001.
public class CoinDistribution {
public static void main (String[] args) {
distribute();
}
public static void distribute() {
int c = 25, b = 0, a = 75, counter = 1, k = 0;
while(k <= 25) {
for (int j = k, d = 0; j <= 50; j++, d++) {
System.out.println(counter++ + ". C=" + (c-k) + ", B=" + j + ", A=" + (75-d));
}
k++;
}
}
}
Sorting is an obvious solution with O(nlgn) time complexity. This can be solved using connected components of a graph in O(n) time and space complexity as discussed at question?id=19778663
The graph in this case is 'linear', with each node having at most 2 edges, and hence can be built in O(n) time. Finding connected components, and storing the maximal connected component, in this graph using DFS has O(n) time complexity. Hence overall complexity is O(n).
Java implementation given below. Provide the input as:
16 1 21 7 4 6 15 3 2 8 14 9 17 35 19 45 18 73 22 44 43 71 20 33
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MaxConsecSubset {
int ccSize = 0, ccMin = 0, ccMax = 0;
int tmpSize = 0, tmpMin = 0, tmpMax = 0;
static HashMap<Integer, HashMap<Integer, Integer>> graph = new HashMap<Integer, HashMap<Integer, Integer>>();
public void DFS(int nodeId, int groupId) {
if (graph.get(nodeId).get(nodeId) == null) {
graph.get(nodeId).put(nodeId, groupId);
tmpSize++;
if (nodeId > tmpMax) {
tmpMax = nodeId;
}
if (nodeId < tmpMin) {
tmpMin = nodeId;
}
for (Map.Entry<Integer, Integer> entry: graph.get(nodeId).entrySet()) {
if (entry.getKey() != nodeId) {
DFS(entry.getKey(), groupId);
}
}
}
}
public void findEquivalenceClasses() {
for (Map.Entry<Integer, HashMap<Integer, Integer>> entry: graph.entrySet()) {
if (entry.getValue().get(entry.getKey()) == null) {
tmpSize = 0; tmpMax = -999999; tmpMin = 999999;
DFS(entry.getKey(), entry.getKey());
if (tmpSize > ccSize && (1 + tmpMax - tmpMin) == tmpSize) {
ccSize = tmpSize;
ccMin = tmpMin;
ccMax = tmpMax;
}
}
}
}
public 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);
int i;
while(scanner.hasNextInt()) {
i = scanner.nextInt();
if (!graph.containsKey(i)) {
HashMap<Integer, Integer> adjElements = new HashMap<Integer, Integer>();
adjElements.put(i, null);
graph.put(i, adjElements);
}
if (graph.containsKey(i + 1)) {
graph.get(i).put(i+1, null);
graph.get(i+1).put(i, null);
}
if (graph.containsKey(i - 1)) {
graph.get(i).put(i-1, null);
graph.get(i-1).put(i, null);
}
}
}
public static void main(String[] args) {
MaxConsecSubset maxCS = new MaxConsecSubset();
maxCS.readInput();
maxCS.findEquivalenceClasses();
System.out.println("The maximum consecutive subset is: [" + maxCS.ccMin + "," + maxCS.ccMax + "]" );
}
}
@Ayaskantam
What do you think is the complexity of List.contains() method?
@aka
Thanks! Discussions with you are only helping me to become a better learner.
@Another Aspirant
Yes, the lists need to be sorted even before they are compared.
IMO, EOF's solution is an optimized one. The logic to solve the problem is apparently correct, though the technical issues like overflowing can be handled by using modular arithmetic as suggested by him.
- Murali Mohan July 08, 2013@aka
We are following a DP-like approach where the solutions to subproblems are found before the solution to the given problem. The solutions to subproblems are added to the hashmap as they are computed. So, if the given number is divisible by 2 or 3 or 5, we need to check if the quotient (which is nothing but the product of the remaining factors) is also divisible by 2 or 3 or 5. Hence we are querying the hashmap to see if the quotient(solution to a subproblem) is present. If present, that means the given number is a product of 2(or 3 or 5) and the quotient(which is also a product of multiples of 2, 3 & 5). If the quotient is not present in the hashmap, it means the quotient was not product of multiples of only 2, 3 & 5 and so is not the current number.
As an example, consider the number 14 whose factors are 2 and 7. It is divisible by 2, but the other factor is 7. 7 is not divisible by 2, 3 or 5 and hence will not be present in the hashmap as a solution to a subproblem. Therefore 14 will not be in the sequence.
On the other hand, if you consider 18, it has factors 2 and 9. 9 will be present in the hashmap because it has factors 3 & 3, which again would be present in the hashmap as solutions to subproblems.
@PKU.SongChen
Good point. But the problem is, as the value of a number increases, the number of it's prime factors also increases and we may have to keep adding more and more prime numbers to the list of checks that does temp % p != 0(where p is a prime number). Moreover, finding out what all prime numbers are factors of a given number is leading us to the problem of factorization which falls in the complexity class NP.
In order to trade off O(n) space here, the other alternative is to check if the given number has only 2,3 & 5 as factors. This can be done by repeated division of the given number by 2, 3 & 5 until the quotient becomes 1.
Solution depends on the space and time complexity as asked by the interviewer.
1. A solution with O(n) space and time complexity is possible if the first list can be put into a hashmap and while traversing the second list, check if the friend is present in the hashmap and print it. If no common element is found print NONE in the end
2. If no extra space is to be used, sort both the lists- this results in time complexity of O(nlgn). Then check for common elements by comparing elements from both the lists and incrementing the pointers until either one of or both of the lists gets exhausted. If no common element is found print NONE in the end
Wonderful! While building the tree, if a node is inserted as a right child of a right child, the ancestor, parent and child form the required triplet.
- Murali Mohan July 07, 2013Seems the sequence mentioned in the question should start from 2 as 1 is not a multiple of 2 or 3 or 5.
An O(n) solution using DP can solve the problem by computing the values from 1st to the Nth number.
0. Maintain a counter, that is initialized to 1 and start from an initial value v, say 2.
1. Keep incrementing the value v and check if it is divisible by 2 or 3 or 5.
2. If divisible, check if the corresponding quotient of v/2 or v/3 or v/5 is present in the solutions to subproblems that are already computed. If yes increment the counter.
3. Return value v when the counter becomes N.
import java.util.HashMap;
import java.util.Scanner;
public class Multiplesof2and3and5 {
public static void main(String[] args) {
System.out.println("Please input N:");
Scanner in = new Scanner(System.in);
int N = in.nextInt();
findN(N);
}
private static void findN(int N) {
HashMap<Integer, Integer> DPMap = new HashMap<Integer, Integer>();
int temp = 2, i = 1;
DPMap.put(1, 1);
DPMap.put(2, 2);
while (i < N) {
temp++;
if ((temp % 2 == 0 && DPMap.containsKey(temp / 2))
|| (temp % 3 == 0 && DPMap.containsKey(temp / 3))
|| (temp % 5 == 0 && DPMap.containsKey(temp / 5))) {
i++;
DPMap.put(temp, temp);
}
}
System.out.println("The required number = " + temp);
}
}
Beautiful solution! The use of a predecessor array and the way the solution is coded up is quite instructive.
- Murali Mohan July 05, 2013Nice idea!
- Murali Mohan July 05, 2013@Anonymous
Ah!, My bad, I just read the second half of the question below. Thanks for the pointer.
>> It may be possible that T3 lost to T1 .. but that need not be taken into consideration while writing the order.
If we assume that only the neighboring elements should be in order, then the original quicksort algorithm itself, with modified comparison logic, will work.
The recursive implementation defined by eugene, with randomized selection of the pivot and no reduction in the size of the input set in each step, just provoked my curiosity about the correctness and termination of the algorithm.
Otherwise, it is an excellent idea to use the partition routine. Thumbs up! I see that insertion sort with modified comparison method is also good to solve this problem, though merge sort is unlikely to work.
@eugene, @vikas
Sorry, but none of the ideas of partitioning and topological sort can work here, thanks to an imprecise question. The reason being the given relation 'lost to' that is determined by calling the function: displayResult(Team T1, Team T2), is not a "total order".
Let '< 'denote the relation 'lost to' and consider the following outcome of the matches between 3 teams t1, t2 and t3 as returned by the function displayResult(TeamA, TeamB)
t1 < t2.(meaning t1 lost to t2)
t2 < t3 (meaning t2 lost to t3)
t3 < t1 (meaning t3 lost to t1) [Clearly, transitivity(t1<t2<t3) is broken here and hence the outcome is not a total order]
Now all of the following 6 permutations are wrong
t1 < t2 < t3 (violates t3 < t1)
t1 < t3 < t2 (violates both t3 < t1 & t2 < t3)
t3 < t1 < t2 (violates t2 < t3)
t3 < t2 < t1 (violates both t2 < t3 & t1 < t2)
t2 < t3 < t1 (violates t1 < t2)
t2 < t1 < t3 (violates both t1 < t2 & t3 < t1)
Hence no such ordering is possible. In other words, the goal is unreachable and hence no algorithm can exist. If only by a chance we get a linear ordering of the outcomes, we can linearly order the set in finite time. Otherwise, the program would run in an infinite loop and never halt.
Here, the question itself is not very clear. Had the ordering relation been defined as something like the 'number' of other teams the given team has won against, it was still possible to linearly order the team as the set of natural numbers, even if duplicates are present, with the relation "is greater than or equal to", form a total order.
@eugene
Even if we assume that we luckily got a linearly ordered set, I doubt, how your algorithm with the following logic would ever terminate
team t = pickRandomElementFrom(S)
When are you going to stop the process of randomly picking the element and partitioning it? With repeated random selections over the same set, whose size is unchanged, how would you ensure that each of the teams T1 to Tn gets picked as a pivot point so it is placed in its correct position?
Alternatively, if you get a random sequence of elements from a total order set as input, you can simply reduce your solution to sorting as sorting can perform linear ordering on that set.
There is another clean and neat DP solution based on DAG in the book cs.berkeley.edu/~vazirani/algorithms/all.pdf.
- Murali Mohan July 05, 2013Good one!
- Murali Mohan July 05, 2013Good one. At each node of the trie, maintain a linked list for the 3-digit numbers.
In order to address the query - 'Count the total number license numbers starting with ABC', you can as well maintain a counter that maintains the size of the linked list and update its value each time the linked list is updated. The query can then be addressed in constant time just by returning the value of that counter.
Nice approach, but could you please devise an algorithm? For ex: how would you compute the value of 'acegi'?
- Murali Mohan July 04, 2013The clock at the top can be sync'ed with the clock at the bottom, only if the time it takes to climb up the mountain is known.
Since there is no way to know the time it takes to climb up the hill, the clocks cannot be synchronized.
I think the number of comparisons in both the cases is the same. In order for an element to be placed at it's correct position in the larger array 3 comparisons are required in both the cases.
- Murali Mohan July 04, 2013@Epic_coder
I think the sorting step below can get a bit more expensive.
>> 2.Arranging/Sorting suffixes lexicographically using the suffix array << O(n)
Any comparison-based sorting of n elements has a lower bound of big-Omega(nlgn). n*lgn comparisons is again based on the premise that comparison between two elements takes constant time.
In the case of a suffix array, there are n elements, but the issue here is each element itself is an array. In order to compare 2 elements(here, 2 arrays), you need to check n numbers on avg to determine whether one element is larger or smaller to the other. In other words, the comparison between 2 array elements in a suffix array is not constant, it takes n comparisons on avg. Hence the total complexity would be (n^2 * lgn) in the sorting step.
DCL alone cannot solve the problem completely. In Java, you ought to combine the usage of 'volatile' keyword with Double Checked Locking, why because 'volatile' ensures memory visibility across all the threads when updates to a variable are made.
In the above post, 'instance' has to be declared volatile, so when another thread has set its value, the 'if (instance == null)' check in the code below works correctly in the current thread.
//if still null after lock has been acquired
if (instance == null) {
instance = new MySingleton ();
}
Not sure how to get the DCL anti-pattern work correctly in other languages.
- Murali Mohan July 03, 2013
Will this algo work for the input [-1 -2 -3 -4 -5] ?
- Murali Mohan July 16, 2013