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
The seven bags should have the gems distributed in the following way.
1, 2, 4, 8, 16, 32 & 37
The other part of the question where the teacher can put any number of gems in one purse and asking the student to distribute the rest is invalid. What if the teacher puts all of the 100 gems in one bag? In such a case the student will not be able to distribute the gems and will also not be able to give gems of the required number.
The question is asking not to use an additional array. However assuming we can use additional data structures other than array, this approach seems to be the most appropriate way to solve the problem.
- Murali Mohan August 13, 2013The question seems to be asking to serialize the tree into only one array. Your solution is creating 2 arrays - one for inorder and the other for pre/post order.
- Murali Mohan August 12, 2013The question seems to be asking to serialize the tree into only one array. Your solution is creating 2 arrays - one for inorder and the other for pre/post order.
- Murali Mohan August 12, 2013Good one, +1. Other than rope, other data structures I can think can be useful are: 1) stack for undo operations 2). NFA for 'find and replace' functionality etc
- Murali Mohan August 12, 2013Yeah, the nodes of a tree can be stored in the way a 'heap' is stored in an array. Starting from index 1, the left child can be started at index 2, and the right child at index 3. In general, for a parent at index i, the left child can be stored at index 2i and the right child at index 2i+1. If a node is not present a null(or some other special flag) can be stored at it's designated location. This should make it easy to reconstruct the heap back from the array.
- Murali Mohan August 11, 2013Good point schroeder. You are right, my algo will not be able to detect such squares.
- Murali Mohan August 08, 2013@tryingtosolvemystery
The sum from 1..n-1 is obtained from the cumulative array by using C1[n-1] - C1[0].
That is the main advantage of a cumulative array. You can obtain the summation between any two indices (i,j) in constant time once you have a cumulative array.
Use 2 cumulative arrays C1 and C2 for both the arrays. The locations C1[i] and C2[i] hold the sum of all values up to index i from both of the arrays respectively.
0. Start with a window of size n(starting at index i=0 and ending at index j=n-1)
1. Compare the values of that window size using arrays C1 and C2. Return (i,j) if they are equal
2. Reduce the window size by 1. Now i and j become 0 and n-2 respectively. Compare the values in the cumulative arrays for the ranges: (0,n-2) & (1,n-1)
3. Repeat steps 1 and 2 until the window size is reduced to 1 or a match in the cumulative arrays is found in which case the corresponding (i,j) would be returned.
Moore's voting algorithm, seems a pretty standard problem asked in the tech interviews.
- Murali Mohan August 07, 2013Use an auxiliary hashtable if space is not an issue to solve this problem. The keys of the hashtable would be the x-coordinates of the points and the values would be arraylists of integers holding the y-coordinates of the points.
Use a vertical sweep line and move it from the left of the plane to the right. When 2 or more points are encountered by the sweep line, calculate the difference between their y-coordinates and let it be d. Look up in the hashtable to see if the corresponding points at a horizontal distance 'd' exist previously. In other words, for 2 points on the sweep line with coordinates (x1,y1), (x1, y2), check in the hashtable if points exist with coordinates (x1-d, y1) & (x1-d, y2) exist (Here, d = |y1-y2|). If they exist, they form a square.
Finally add the newly encountered points to the hashtable and repeat the procedure until the vertical sweep line moves past the rightmost point(s).
Sort both the arrays and use a modified version of the 'merge' step that checks for the uniqueness of an element in both the arrays.
- Murali Mohan August 06, 2013Elegant solution, +1.
If space is an issue, another alternative is to sort both the arrays. A modified version of the 'merge' step of mergesort can be used to verify if a given element occurs exactly twice in either of the arrays or both of the arrays combined.
For part1 of the problem, use a min-heap of size k. After a number is read from the stream, if the size of the heap is less than k, insert it into the heap. Otherwise, if the given number is greater than the min-value of the heap, evict the min value and insert the given number into the heap. At the end, you will have top k elements left in the heap.
For part2, let L = m/k(m<k, per the question). Here again use a min-heap, but of size k/(L+1). In the first pass, find out the top k/(L+1) elements. In the second pass, find out the next top k/(L+1), by inserting into the heap only the elements which are less than the first top k/(L+1). Like this, make L+1 passes over the data, each time capturing a window of k/(L+1) ordered elements. In the end, we'll be left with top k elements.
It would be a two step process.
1. In step 1, start two pointers, one moving ahead one node at a time and the other two nodes at a time. This lets us find out the middle and the last element.
2. In step 2, using 3-pointer mechanism that points to previous, current and next nodes, delete the given node. Handle the special case of adjusting the pointers if the deleted node is the middle node.(The middle and last-element pointers obtained in step 1 are used here) Otherwise fix, the pointers or previous, current and next nodes regularly along with fixing the pointer to the middle node from the last node.
The question has some nuances to deal with. If the candies are all distinct as depicted with numbers in the example of the question, the below nested loop works. If the candies are all same inside a jar, the answer would be simply nC2.
Let the array a[] hold the number candies in jar j where 0<=j<n
sum = 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
sum += a[i] * a[j];
return sum;
@yashpal
Could you please elaborate the question a bit more?
Maintain a fixed size hashtable, say, of size 4. Input numbers would be keys and counts of their frequencies would be the values.
0. Maintain 2 pointers to mark the start and end of the contiguous subarray we are processing. Initially they will both point to the first location.
1. When a new number is encountered, if it is not already present in the hashtable AND the size of the hashtable <=3, add the key to the hashtable, with its count value = 1 and advance the end pointer.
2. if the size of hashtable becomes equal to 4, increment the start pointer, decrement the value of the corresponding key in the hashtable and if the count =0, remove that key from the hashtable.
Repeat steps 1 and 2 keeping track of the longest contiguous subarray which satisfies the property that the elements within it are at most 3 distinct numbers(in other words, at some time during the processing we will have longest contiguous subarray, with the size of our hash table being at most 3).
Time complexity: O(n)
Space complexity: O(1) with fixed size hash table.
Nice idea.+1
- Murali Mohan August 03, 2013Using a bit-vector is a good idea if the elements to be sorted are all unique or if they contain duplicates up to a certain constant number, say the numbers all can have up to a maximum of 4 duplicates. However, manipulating the bit-vector can get unwieldy if the input contains arbitrary number of duplicates.
In that case, a min-heap is a good alternative to sort huge data that don't fit into main memory at once. Two limits - an upper limit and a lower limit can define the range of elements to be stored in the heap. Make (the required number of) passes over the data, capture the defined range of elements and print them out at the end of the pass.
For ex:if we have space to hold 1000 elements but need to sort 2000 elements, a heap to hold 500 elements can be used, the rest of the space being used to load elements from hard-disk, and then in 4-5 passes, we can capture, and print the elements in the ranges: 1-500, 501-1000, 1001-1500 & 1501 to 2000.
Quite simple. The question is asking to convert a number in decimal(radix-10) system to another (radix-26) system. The regular radix conversion mechanism with a few tricks works:
1. Map as follows:
0 => A
1 => B
...
25 => Z
2. In the conversion process, reduce the value of the dividend by 1 at each step before doing the division.
For ex: If the input is given as 54, subtract 1 from it and do the conversion on 53 from radix-10 to radix-26. Detailed steps are below;
0. Input = 54 (reduce it by 1 before feeding to the next step)
1. Dividend = 53, divide it by 26 which gives remainder 1(=B) and quotient = 2
2. Dividend = 1 (quotient = 2 from previous step - 1) divide it by 26 which gives remainder 1(=B) and quotient = 0
3. Stop and produce the output BB.
@Miguel
Thanks for the test cases, I have blatantly missed the case of having 3 or more consecutive characters that are same. Either I need to refine my idea to handle such test cases or accept DP paradigm as the way to go! Thanks again!
>> assuming log k << m so it can be taken as m
FYI, In big-oh notation, conventionally you can ignore constants, but can't drop functions. Algorithms with complexity of O(log*(n)) are still mentioned as having asymptotic complexity in n, but never considered as constant-time algorithms just because log*(n) is very small.
@blackfever
>>total time complexity will be ->m is total no of element i.e m=k*n
What about the heap operation of insert that is of O(lgk) ? And you will have O(nk) inserts into the heap.
This ain't an optimization problem and hence no need of Dynamic Programming. A few loops with simple tricks can do the job.
An approach to solve this would be to:
0. Maintain a counter variable.
1. Check if the given string itself is an SString. If yes, increment the counter
2. Start at the rightmost character
3. Decrement the value of the current character
4. Check if the character >= 'a' and the character to the left is the same as the current character.
4a. If they are the same decrement the value of the current character
4b. If they are different, increment the value of the counter by 25^(Length_of_string - i)
5. Decrement i
6. Repeat steps 2 to 5 until i >=0
A less bloated implementation in java goes like below.
public class SString {
public static int scount(String s) {
boolean isSstring = true;
int count = 0, j, i;
i = j = s.length() - 1;
for (int l = 0; l < s.length() - 1; l++) {
if (s.charAt(l) == s.charAt(l+1)) {
isSstring = false;
break;
}
}
if (isSstring) {
count++;
}
while (i >= 0) {
char c = s.charAt(i);
double pow = Math.pow(25, j-i);
while(--c >= 'a') {
if (i == 0 || s.charAt(i -1) != c) {
count += pow;
count %= 1009;
}
}
i--;
}
return count;
}
public static void main(String[] args) {
System.out.println(scount("bcd"));
}
}
Duplicate question - previously posted at question?id=23869663
An approach to solve this would be to:
0. Maintain a counter variable.
1. Check if the given string itself is an SString. If yes, increment the counter
2. Start at the rightmost character
3. Decrement the value of the current character
4. Check if the character >= 'a' and the character to the left is the same as the current character.
4a. If they are the same decrement the value of the current character
4b. If they are different, increment the value of the counter by 25^(Length_of_string - i)
5. Decrement i
6. Repeat steps 2 to 5 until i >=0
An implementation in java goes like below...
public class SString {
public static int scount(String s) {
boolean isSstring = true;
int count = 0, j, i;
i = j = s.length() - 1;
for (int l = 0; l < s.length() - 1; l++) {
if (s.charAt(l) == s.charAt(l+1)) {
isSstring = false;
break;
}
}
if (isSstring) {
count++;
}
while (i >= 0) {
char c = s.charAt(i);
double pow = Math.pow(25, j-i);
while(--c >= 'a') {
if (i == 0 || s.charAt(i -1) != c) {
count += pow;
count %= 1009;
}
}
i--;
}
return count;
}
public static void main(String[] args) {
System.out.println(scount("bcd"));
}
}
@LinhHA05, @datta016
Nice idea.
x ^= ~(~0<<(32-startpos + 1)) | (~0>>>(endpos+1))
- Murali Mohan July 31, 2013How about this approach? A pathetically tedious one though.
Let L denote the level of a tree starting from 0. We can make use of 2 pointers to denote the start and end of the nodes in a level. These pointers need to be maintained at the current level as well as at the parent level. Assuming that we need to build a complete binary tree, we can process the nodes of DLL in numbers that are powers of 2.
At L = 0, we have 2^L = 2^0 = 1 node. The start and end pointers will point to this node.
At L = 1, we have 2^L = 2^1 = 2 nodes. L is odd, we push the elements of this level on to a stack. While pushing elements on to the stack, we reverse the previous/next pointers of the nodes. This again is a tedious process, where before pushing one element, we pop the previous element, change the pointers and then push 2 elements on to the stack. While popping the elements from a stack attach two elements at a time to nodes at parent level and keep advancing the start pointer of the parent level until it reaches the end pointer. At this level again, we have maintained pointers that denote the start and end of the nodes in this level.
At L = 2, we have 2^2 = 4 nodes. L is even here. No need to use a stack here and attach 2 nodes at a time to nodes at the parent level and keep advancing start pointer of the parent level until it reaches the end pointer
Repeat the above steps until the end level L=K is reached. At this level, if k is odd, then push 2^K elements on to the stack, NULLs being the "padding" nodes. Then attach the nodes to the nodes at the parent level.
Again, terribly tedious process, but just an attempt to solve the problem.
You are right in the sense that one needs to build an automaton for processing this. However, a regular language can be processed using an NFA and one needs to build an NFA to solve this problem. Turing machine can be used to process 'recursively enumerable' languages which are at the top of the hierarchy as defined by Noam Chomsky.
- Murali Mohan July 31, 2013@vgeek
I doubt the correctness of your algorithm. Could you please clarify if your procedure takes care of producing numbers that are multiples of a subset of powers of 2,3,5 & 7. For ex: will you algorithm be able to generate 2^2 * 3^2 * 5^2 * 7^2?
A pointer is a datatype, which stores the memory address of any datatype. The size of the pointer depends on the architecture of the system - a 32-bit system would have a pointer size of 32 bits to accommodate a memory address space of 4GB, a 64-bit architecture should use 64 bits for pointer data type. An array of pointers is an array of such address-holding datatypes.
Whereas a pointer to an array points to the (typically first) address of an array of locations which store a particular datatype, say ints, chars, etc, including pointers.
Miguel is right. The question is incomplete in the sense the total number of elements to be sorted are not mentioned. The choice of sorting algorithm depends on how many numbers are to be sorted and the specifics of the data, namely their distribution, frequency etc..
- Murali Mohan July 30, 2013Good one. The length of any word in English is bounded above by some constant number. So sorting a word need not be expressed with an asymptotic complexity in terms of n. But yes, if you have n words, your total sorting can become of complexity O(n). To store in a hashtable, you need O(n) extra space. However, inserts, retrievals from a hash table (with a good hash function is assumed to be) is of O(1) time complexity.
It is not clear as to how you arrived at O(n^2lgn) time complexity.
Right :) C's details?
- Murali Mohan July 29, 2013Simply rocks! :)
- Murali Mohan July 29, 2013@BVarghese
I am unable to ascertain the correctness of your procedure, but if you are interested, you can take a look at Section 33.1 of CLRS (tberg.dk/books/Introduction_to_algorithms_3rd_edition.pdf), which has a nice topic on line intersection of line segments. It's a bit elaborate, so difficult to discuss it here.
@ LinhHA05
Thanks a ton for an illuminating discussion.
Good explanation, thanks for it!. But, though the recurrence is right, sorry to say that you have got the analysis wrong buddy. For your recurrence, you can apply the master theorem as mentioned in page nos 58 and 59 of cs.berkeley.edu/~vazirani/algorithms/all.pdf. The solution for your recurrence is obtained by case 3 of the master theorem mentioned there and is O((mn)^b(3)), for the worst case and O((mn)^b(1)) for the best case, where b is a log function with base 4.
The best-case time complexity with this approach is therefore O(mn).
@LinhHA05
Though I haven't understood your solution thoroughly, I wanted to ask you, if your solution is similar to having a 'divide and conquer' approach, where the nxn(assume nxn instead of nxm) matrix is divided into four sub matrices and that in you search in a submatrix based on the min and min value of that sub-matrix?
Does your analysis fall on similar lines?
Could you please elaborate your idea of solving the problem using quaternary search tree in words? Quaternary search tree is new to me. Thanks!
- Murali Mohan July 26, 2013I suppose the following idea also should work.
0.Assuming 1-based index, for n elements, take mid = (n+1)/2.
1.Compute the sum from 1 to mid-1 and call it LSum
2.Compute the sum from mid +1 to n and call it RSum
3. If LSum = RSum return mid
4. if LSum < RSum
4a. whlle (LSum < RSum) {
if (mid ==n) return -1;
LSum += a[mid]
RSum -= a[mid+1]
mid = mid+1;
if (LSum == RSum)
return mid;
else if if (LSum > RSum)
return -1;
}
5. if LSum > RSum
4a. whlle (LSum > RSum) {
if (mid == 1) return -1;
LSum -= a[mid-1]
RSum += a[mid]
mid = mid-1;
if (LSum == RSum)
return mid;
else if (LSum < RSum)
return -1;
}
How about this approach?
Generate a random string of fixed length based on the character set that is URL-safe.
For ex: Suppose we want to generate a 6-char length string, generate 6 random characters from a URL-safe character set. Once you generate the random string, say h6Tu6M, use it to build a short-form URL like: shrt.ul/h6Tu6M.
Use a mapping table(say a hashtable) to map the short URL to the long URL.
Ex: h6Tu6M => domainwithlongname/with/lengthy/resource/path In this step we also need to ensure that the randomly generated string is not already in use. In case a duplicate is generated, try creating another random string.
The app which is hosted at: h t t p : shrt.ul/ can look up the short resource path h6Tu6M and redirect the user to the actual resource h t t p://w w w .domainwithlongname/with/lengthy/resource/path
Use a min-heap of size 5. Insert the last 5 elements of first array into it.
Use the last 5 elements again from each of the remaining arrays. Insert the element into the heap if it is greater than the min-element of the heap by evicting the min-element.
Perfect solution!
- Murali Mohan July 26, 2013To build a tree of n elements, time complexity can never be O(lgn). It is Big_Omega(n) because you have to deal with n elements.
- Murali Mohan July 25, 2013@cristian.botau
If the matrix happens to have all 1s, we start at the top-left corner and then the algorithm traverses along the 4 edges of the matrix, finds a square and quits. In this particular traversal, you will traverse 4n-4 elements and that is the maximum- sized square you can find in an NxN matrix. The question is asking us to find "a" square and we quit after seeing the first square.
Coming to the argument of each element being traversed at most thrice, the traversal mechanism I have mentioned will encounter a particular element at most thrice- first during the diagonal traversal and consecutively during either or both of horizontal traversal to the right and vertical traversal to the down.
Chih.Chiu.19 is confused and is talking about a completely different problem from "Cracking the coding Interview"book, where it is an "optimization" problem asking to find a square with 'maximum' size, whose solution provided in that book uses DP and is of the order O(N^3).
The problem here is asking just to find any square, whereas the problem mentioned by Chih.Chiu.19 is an optimization problem - its a big difference!
A related problem that is more difficult and requires true DP style approach can be found at: hackerrank.com/challenges/stockmax
- Murali Mohan July 25, 2013@oOZz
I agree that the solution does not require a true DP implementation where the solutions to subproblems are constructed using solutions to sub-subproblems and by using tables for memoization.. etc etc..
This looks more like a max subsequence sum problem, where the solution is obtained by storing values of subproblems in a single variable instead of tables.
Overlapping subproblems and optimal substructure may not be quite apparent in this problem, though, the principles of dynamic programming as to building solution in a bottom-up way and checking 'whether or not the current value contributes to the solution' are still valid here and that is what @om seems to mean by DP
Nonetheless, I see that our implementations conform to @om's idea with mine being a bit more elaborate and instructive and yours short and sweet.
0. Find the total node count and go to the middle of the DLL.
- Murali Mohan August 16, 20131. Reverse the DLL from its middle
2. Take two pointers - first at the first node and the second at the middle node.
3. Reverse the string of the node pointed by the second pointer and compare the strings. If they are equal or one is a substring of the other, go to next step, otherwise return false.
4. If both the strings are equal then advance both the first and second pointers else advance the pointer whose node's strings is smaller and check if either of the strings is equal or prefix of each other.
5. Repeat steps 3 and 4 until the second pointer gets past the end of the DLL and the first pointer gets to the middle node.
6 Return true.