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
@anonymous
Here, I use the notion of a groupid, which is the id of a connected component. Initially the groupid is null. When a node is visited, groupid is set to a non-null value. This serves as a 'visited' flag in my algorithm. The groupid though is not much significance and is exclusively serving the purpose of a 'visited' flag.
Plz explain your algorithm
- Murali Mohan June 20, 2013@oOZz
Good one. Quicksort's partition subroutine is a wonderful subroutine. To me it appears to be one of the fundamental subroutines of computing that solves many types of problems in one shot. +1 for you for cleverly exploiting it's power. However, I would like to make slight modifications to your code as I see a small bug there.
The modifications are:
1. Getting rid of ktop variable. For the quick select algorithm, instead of passing k as input, you can directly pass n-k as input. (Instead of choosing the kth order static, we need to choose (n-k)th order static for this problem)
2. Adjust the value of k(added the statement k = k-p), when you recurse on the right part of the pivot.
static void quick_select(int[] array, int start, int end, int k) {
while (true) {
int p = rnd_partition(array, start, end);
if (k < p) {
end = p-1;
} else if (k > p) {
start = p+1;
k= k-p;
} else {
// at this point p == n-k is true
// so print array [k, n)
break;
}
}
}
A well-known Dynamic Programming problem. Follows the recursive structure:
min # of coins for the given value = min {1 + min # of coins for [the given value - Di]. where Di are values from the set of Denominations}
I have got a working solution for this: Give input as:
1 2 5 10 20 50 100 500 1000 887 (Here 1 to 1000 are the denominations and the last number is the value for which the change has to be made)
Other examples are:
2 5 3 (make a change for 3 using the denominations 2 and 5, outputs -1)
10 5 2 21 (make a change for 21 using the denominations 10 5 & 2, outputs 10 5 2 2 2)
20 5 10 6 (make a change for 6 using the denominations 20 5 & 10, outputs -1)
import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;
public class CoinChangingProblem {
static ArrayList<Integer> input = new ArrayList<Integer>();
static int ipmin = 999999;
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, max = 0;
while (scanner.hasNextInt()) {
intval = scanner.nextInt();
if (intval > max) {
max = intval;
}
if (intval < ipmin) {
ipmin = intval;
}
input.add(intval);
}
int[] coins = new int[max + 1];
for (int i = 0; i < coins.length; i++)
coins[i] = 99999999;
for (int i = 0; i < input.size() - 1; i++)
coins[input.get(i)] = 1;
for (int i = ipmin + 1; i < coins.length; i++) {
int min = coins[i];
for (int j = 0; j < input.size() - 1; j++) {
if ((i - input.get(j)) >= ipmin) {
if (min > (1 + coins[i - input.get(j)])) {
min = 1 + coins[i - input.get(j)];
}
}
}
coins[i] = min;
}
System.out.println("The denominations that make up the change are:");
show(coins, input.get(input.size() - 1));
}
public static void show(int[] coins, int val) {
if (val < ipmin)
return;
if (coins[val] == 1) {
System.out.println(val);
return;
}
int range, i;
for (i = 0; i < input.size() - 1; i++) {
range = val - input.get(i);
if (range >= ipmin && range < coins.length
&& coins[val] == 1 + coins[range]) {
System.out.println(input.get(i));
show(coins, val - input.get(i));
break;
}
}
if (i == input.size() - 1)
System.out.println(-1);
}
}
Good one. +1
- Murali Mohan June 19, 2013@Anonymous:
Regardless of the number of times DFS is called, the algorithm to find connected components runs in O(|V| + |E|). The reason for this is upon the first visit, DFS() marks a node as visited and explores its adjacency list. Once a node is marked as visited, its adjacency list is never explored again. Thus the adjacency list of each node in a graph is explored only once, hence the complexity O(|V| + |E|).
In this specific case, |E| < |V|, so the complexity is O(|V|) = O(n).
@jayram
Good test cases. Your suggestion to add a comment while voting down can be made a feature on careercup's website.
@oOZz
Randomized partition subroutine randomly chooses a pivot and partitions the set around that pivot so that all the elements less than the pivot are to the left of the pivot and all the elements greater than the pivot are to the right of the pivot. How would you tell the randomized partition subroutine to partition the set around the
(k-1)st element?
Since a hashset maintains uniqueness of elements, why not just add the elements from the array to a hashset, iterate over the hashset and print them? Time complexity: O(n).
- Murali Mohan June 19, 2013Use a min-heap of size k.
1. For the first k elements, add them to the heap as they seen.
2. For the rest of the elements if the given element is greater than the min-value of the heap, extract/remove the min element from the heap and add the new element.
3. In the end, all the elements present in the heap are the top k elements. Worst-case time complexity: O(nlgk)
Not any different from Praneeth's solution. This is not scalable.
- Murali Mohan June 17, 2013James, plz explain your algorithms in words instead of just giving your site URL.
- Murali Mohan June 17, 2013I think its correctness can be convinced in two ways: 1. Proof using pigeon-hole principle 2. Proof by induction.
If we let M denote the count of majority element and N the count of all the elements,
an assertion(A) can be made as - 'By the end of the algorithm, the value of counter is at least 2M-N and the current number holds the majority number'.
1.Since M>N/2, we can place the elements in such a way that the majority number, m alternates with other N-M numbers of the set. Again, since M>N/2, using pigeon-hole principle, M-(N-M) (= 2M-N) majority numbers have to be consecutive. This makes the counter to have a value of at least 2M-N and sets the current number to m. The rest of the traversal through the array decrements the counter by at most 1(when m is not the last element of the array) or retains the current value(when m is the last element of the array) and hence the current number is not set to any value other than m.
Induction: Induction is on the size of the set
Base case: A majority element exists in a 3 element set. Let the tuple
(v, n) denote the counter value and the current number respectively. Assertion holds in this case as can be seen by the following possible permutations.
m e m
(1,m) (1,e) (1,m)
e m m
(1,e) (1,m) (2,m)
m m e
(1,m) (2,m) (1,m)
m = majority element, e = any other element
Inductive Step: By inductive hypothesis, suppose the assertion A holds for N elements with M majority elements. There are 2 cases:
1. If we add another majority element to the set, assertion A continues to hold
2. If we add a non-majority element e then there are two cases:
a. After adding e, M>(N+1)/2 holds. Then A holds.
b. After adding e, M>(N+1)/2 does not hold. Then add another m so the invariant M>(N+1)/2 holds and consequently A holds.
I am hoping that I have not made fallacy in my argument. Nonetheless, corrections fixing my arguments are always welcome.
Yes, Hashtable is a better alternative to BST for this problem. I too realized this later. The algorithm can remain the same, but by replacing BST with a hash table.and a counter that maintains the number of users whose current time - last-logged-in time <= 10 mins it would be even better.
The counter is necessary to return the count of users in constant time. Otherwise iterating the hash table every time would require O(n) time. The counter needs to be updated every time we insert/delete elements to the hash table, though the updates to the counter are not needed while updating the hash table or adding to and removing entries from the min-heap.
Nice idea. If there are no duplicate lines in each file, I think you can even merge file1 and file2 into file3 and check if two lines are the same. About time complexity I think you will have to factor in the average length of a line of both the files as well. If it were m, time complexity would be O(mnlgmn)
- Murali Mohan June 17, 2013@rupesh, avenger,
Thanks for the correction. Sorry, I had misread the question.
@aka
I debugged your code a bit and found that the # of recursive calls are blowing up - more than what the straightforward recursive implementation of computing fibonacci numbers does.
I added the statement: printf("i=%d, j=%d\n", i, j); in your foo() function and started the execution with foo(5,5)
Following is the astounding recursion tree. Also please note that foo(5,5) is invoked repeatedly in the recursive calls which is not correct. I think you need to fundamentally redesign your program so it invokes only one recursive call. You may want to invoke recursion only for one case based on whether the next step is taking you closer or farther to your goal from the source. I assume it is better to start from the target and try to reach the source though. Anyways, good luck!
i=5, j=5
i=6, j=6
i=7, j=7
i=8, j=8
i=6, j=6
i=8, j=6
i=6, j=8
i=5, j=5
i=7, j=5
i=8, j=6
i=6, j=4
i=7, j=5
i=5, j=3
i=6, j=4
i=4, j=2
i=5, j=3
i=3, j=1
i=4, j=2
i=2, j=0
i=3, j=1
i=1, j=-1
i=3, j=-1
i=1, j=1
i=4, j=0
i=5, j=1
i=6, j=2
i=7, j=3
i=8, j=4
i=6, j=2
i=8, j=2
i=6, j=4
i=5, j=1
i=7, j=1
i=8, j=2
i=6, j=0
i=7, j=1
i=5, j=-1
i=7, j=-1
i=5, j=1
i=8, j=0
i=6, j=2
i=5, j=3
i=4, j=0
i=6, j=0
i=4, j=2
i=3, j=-1
i=5, j=-1
i=3, j=1
i=2, j=2
i=3, j=3
i=4, j=4
i=5, j=5
i=3, j=3
i=5, j=3
i=3, j=5
i=4, j=6
i=5, j=7
i=6, j=8
i=4, j=6
i=6, j=6
i=4, j=8
i=3, j=5
i=5, j=5
i=3, j=7
i=4, j=8
i=2, j=6
i=3, j=7
i=1, j=5
i=2, j=6
i=0, j=4
i=1, j=5
i=-1, j=3
i=1, j=3
i=2, j=4
i=3, j=5
i=1, j=3
i=3, j=3
i=1, j=5
i=0, j=2
i=1, j=3
i=-1, j=1
i=1, j=1
i=-1, j=3
i=2, j=2
i=0, j=4
i=-1, j=5
i=2, j=4
i=0, j=6
i=1, j=7
i=2, j=8
i=0, j=6
i=2, j=6
i=0, j=8
i=-1, j=5
i=1, j=5
i=-1, j=7
i=3, j=5
i=1, j=7
i=4, j=6
i=2, j=8
i=2, j=4
i=4, j=4
i=2, j=6
i=2, j=2
i=4, j=2
i=2, j=4
i=1, j=1
i=3, j=1
i=1, j=3
i=5, j=1
i=3, j=3
i=6, j=2
i=4, j=4
i=7, j=3
i=5, j=5
i=8, j=4
i=6, j=6
i=5, j=7
i=4, j=4
i=6, j=4
i=4, j=6
output 9
The question asks for pairs not triplets. The triplets question would be little harder. Can you come up with a solution for the triplets and share with us?
- Murali Mohan June 16, 2013@aka
I have found an online compiler here:
compileonline.com/compile_java_online.php
Seems there is a problem reading from standard input. You can just hardcode values at the following statements
int sourceI = 1; //scanner.nextInt();
int sourceJ = 1; //scanner.nextInt();
int targetI = 8;//scanner.nextInt();
int targetJ = 8;//scanner.nextInt();
@anonymous
Yes if a bishop's original coordinates are such AbsoluteValue(srcI-srcJ) is even, then it can move only along those squares whose AbsoluteValue(i-j) is even. If it's original coordinates are such AbsoluteValue(srcI-srcJ) is odd, then it can move only along those squares whose AbsoluteValue(i-j) is odd.
@aka
My program is outputting the following path.
1 1
2 2
1 3
2 4
1 5
2 6
1 7
It is basically following a zig-zag path from bottom left to top left.
@aka
Can you outline your algorithm? That should help us grasp your idea better. I could have tried to verify your program, unfortunately I don't have a C/C++ env. I guess I should install cygwin??
Good one. Will storing sum and sum of squares also work? Just wondering..
- Murali Mohan June 16, 2013Haha. Ain't the difference (2+3+4+5+1) - 0 = 15 greater than 13? Lol.
- Murali Mohan June 16, 20131. SELECT c.* FROM country c LEFT OUTER JOIN city i ON c.countryid = i.countryid WHERE i.countryid IS NULL
2.SELECT c.countryId, c.countryname FROM country c INNER JOIN city i ON c.countryid = i.countryid GROUP BY c.countryId, c.countryname HAVING COUNT(c.countryId) < 3
This is not a difficult problem. Two simple observations can lead us to an optimal solution
1. For a given location (i,j) of bishop, the next possible moves will have locations (i+k, j+k) ,where k=1 or -1
2. if (srcI, srcJ) is the source location and (tgtI, tgtJ) is target location then AbsoluteValue(srcI-srcJ) and AbsoluteValue(tgtI-tgtJ) must both be even or both be odd to be considered as valid moves.
3. This leads us to a simple recursive solution where we can trace the path from the source to the target by incrementing or decrementing x and y coordinates values(and at the same time checking that we lie within the boudaries).
Follows is a complete implementation: The source and target locations can be given as:
1 1
8 8
import java.util.Scanner;
public class BishopMoves {
public static void printMoves(int sourceI, int sourceJ, int targetI, int targetJ) {
int tmpI, tmpJ;
if (sourceI == targetI && sourceJ == targetJ) {
System.out.println(targetI + " " + targetJ);
return;
}
if (targetI > sourceI) {
tmpI = targetI - 1;
} else if (targetI < sourceI){
tmpI = targetI + 1;
} else {
if (targetI - 1 < 1) {
tmpI = targetI + 1;
} else {
tmpI = targetI - 1;
}
}
if (targetJ > sourceJ) {
tmpJ = targetJ - 1;
} else if (targetJ < sourceJ){
tmpJ = targetJ + 1;
} else {
if (targetJ - 1 < 1) {
tmpJ = targetJ + 1;
} else {
tmpJ = targetJ - 1;
}
}
printMoves(sourceI, sourceJ, tmpI, tmpJ);
System.out.println(targetI + " " + targetJ);
}
public static void main (String[] args) throws Exception {
Scanner scanner = new Scanner(System.in);
System.out.println("Input space delimited coordinates of the source location. Eg: 2 1");
int sourceI = scanner.nextInt();
int sourceJ = scanner.nextInt();
System.out.println("Input space delimited coordinates of the target location. Eg: 5 4");
int targetI = scanner.nextInt();
int targetJ = scanner.nextInt();
if (1 > sourceI || sourceI > 8) {
throw new Exception("Range of the coordinates is between 1 and 8");
}
if (1 > sourceJ || sourceJ > 8) {
throw new Exception("Range of the coordinates is between 1 and 8");
}
if (1 > targetI || targetI > 8) {
throw new Exception("Range of the coordinates is between 1 and 8");
}
if (1 > targetJ || targetJ > 8) {
throw new Exception("Range of the coordinates is between 1 and 8");
}
int sourceDiff = Math.abs(sourceI - sourceJ);
int targetDiff = Math.abs(targetI - targetJ);
if (Math.abs(sourceDiff - targetDiff)%2 != 0) {
throw new Exception("Invalid source and target location coordinates");
}
System.out.println("The path from source to target is:");
printMoves(sourceI, sourceJ, targetI, targetJ);
}
}
@emalaj23
The above is not the most inefficient code. An even more inefficient way of solving this problem is to have all the n! permutations of the array and check if the sum of the first and last elements sum up to the given number. I am sure there can be even more inefficient ways that beat my method.
@emalaj23
Good one, +1 to you. This is a better approach. Preprocessing the dictionary is a one-time activity. Finding the power set of a 7 letter tile and sorting them is constant time operation. (though the constant can be large).
Once the sorting is done, verification against the preprocessed dictionary is a blazingly fast operation.
@oOZz
Thought of giving a shape to my ideas using connected components of a graph. Finally, a flawless solution with O(n) time complexity that works putting an end to speculations.
Provide input as:
19 16 5 1 9 3 18 17 8 20 4 10 2 11 3 6 13 15 12 14
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) {
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:");
for (int j = maxCS.ccMin; j <= maxCS.ccMax; j++) {
System.out.print(j + " ");
}
System.out.println();
}
}
@Mrs Jumbo. If you compute hash code for a billion strings, the likelihood of collisions becomes very high. I therefore thought of using the line numbers to keep track of which all lines are hashing to the same bucket.
While processing the second file a line may hash to a bucket, but it need not be a string that exactly matches lines from the 1st file. Therefore, based on the line #s, we need to do exact string matching of those lines from the first file and if they match, increment the counter of the matching line.
Good one Anonymous. Are you James Chen yourself :-) ?
- Murali Mohan June 15, 2013Nice one praneeth. Your algorithm seems to fix the array by removing duplicates in-place. correct?
I guess you can have some savings with the below modification.
if Product % array[i] == 0
Product = Product/(array[i] * array[i])
skip
else
{
Nice explanation
- Murali Mohan June 15, 2013Yes, possible. Start two pointers i & j from the end of the string.
a. Keep copying the character from ith location to the jth location and decrement both i & j
b. When i encounters a space, decrement i, but not j
c Repeat steps a & b until i falls of the beginning of the string.
d. Keep setting 'space' character at jth location and decrement j unitl j falls of the beginning of the string
Build the adjacency list using a hash table.Keys would be the numbers and values would be (number, groupid) pairs.
Traverse the array. Add number k as a key to the hash table if not already present. If numbers k+1 and k-1 are present in the hash table, add k to their adjacency lists and vice-versa. (To add more to the implementation details, we need to add k to it's own adjacency list as well). We will then have constant time per insertion.
Initially the groupid is set to null for all of the elements.Iterate over the elements of the hash table and run DFS marking the groupid of the connected components if not already set. Alongside, maintain the size of the largest connected component and its groupid. In the end print all elements of the groupid with the largest size
Maintain a hash table with the following structure.
1. Use a Pair object with (line#, count) elements
2. Key of hash table would be the hashcode(something like MD5) of the string and value would be an arraylist of Pair objects.
[hashCodeOfString]-> ArrayList<Pair>()
For the first file, for each of the lines, compute the hashcode for key.. As it's value, store the corresponding line# and the initial count set to 1.
For the second file, for each of the lines, compute the hash code and if the hashcode matches, from the Pair object, match the current line with the corresponding lines from the 1st file. If the string comparison also matches increment the count field of the pair object.
Iterate over the hash table and print those lines with count > 1
@anonymous
I think we can try do better. The notion of 'consecutive numbers' divides the set into equivalence classes. We can construct an undirected graph with numbers as node values and edges between two nodes if they differ in value by 1. Run DFS to find connected components(which are equivalent classes) finding their size along. The connected component with maximum size is the maximum contiguous subset. Complexity would be O(|V| + |E|). In this case, since we have |E|<|V|, we can say that we have got a O(|V|) solution.
The disjoint-set data structure also enables to paritition the set into equivalent classes. I suppose we can use that as well to find a solution to this problem.
What is the expected time complexity? Sorting can get the job done easily in O(nlgn). Also, are there any pecularities about data that they all are +ve numbers and that they fall within a certain range, duplicates allowed etc etc?
- Murali Mohan June 14, 2013Good one oOZz. This is a better approach, though trades off time with space.
- Murali Mohan June 14, 2013An alternative is to use a BST along with an augmented field called counter at each node. Just keep adding to the BST from both the arrays. If the given element is not present, then add it to the BST with the counter initialized to 1. If the element is already present increment the counter.
To print UNION, print all the nodes of the BST.
To print Intersection, do an inorder traversal and print only those node whose counter > 1
For that matter oOzz's solution can be extended to have one hashtable with counter as value and doing the same thing as I said above. That reduces the number of hash tables from 2 to 1
@Anonymous
What result do you expect for this test case?
Sort the array and start pointers from both ends of the array checking if the given pair add up to the given value.
0. If the current pair sum equals the value of the given number print the pair.
1. If the current pair sum exceeds the given number decrement the right pointer by 1
2. else increment the left pointer by 1
I think you can use heap and BST separately for the two problems mentioned.
1. At any point of time, if you want to know only about the element that is repeated maximum number of times, you can use a max heap. For the max heap, the key will be the frequency/count of the elements in the array and an additional field, say, value would hold the element of the array.
2. At any point of time, if you want to know the element(s) that are repeated exactly n times, we can maintain a BST. Here again, the keys will be the frequency/count of the elements seen so far and an additional field called value would hold the element of the array.
@Loler. Thanks a lot for the suggestion, appreciate it.
- Murali Mohan June 13, 2013@Loler: Wonderful Loler, nice to know that great talent is around. Wanted to ask you for a favor - I have been working on question?id=12708671. Thought hard on the problem for days together and came up with a solution. Could you kindly verify if my idea works? [Kindly excuse my trumpeting there]. Apologies to all who find my post irrelevant to the current context - btw any other way of 1-1 communication possible here?
- Murali Mohan June 12, 2013Typical producer-consumer pattern. There are 2 ways to solve it. Either use a blocking queue or use a semaphore
- Murali Mohan June 12, 20134) is not a possibility. The min and max subarrays can either share only 0 as a common boundary or either of them can be present entirely in the other. See my proof by contradiction up in the post.
- Murali Mohan June 12, 2013Finally, a flawless algorithm based on Quicksort's partition subroutine.
1. Using modified partition routine, move all the -ve elements to the right side of the array and all +ve numbers to the left side of the array
2. Let the size of all the positive numbers be N.
3. Use Quicksort's modified partition subroutine to recursively check for the missing number either in the left half or the right half of the array. This results in an O(n) time complexity algorithm.
4. At each recursive step, for a subarray starting at index S, and ending at index E, the subarray is partitioned around the pivot (S + E)/2. We check if the pivot is correctly positioned at its location. Depending on the existence of the pivot at its correct location, we recurse either in the left half or the right half of the sub array to report the missing element.
5. If no element is missing, return 0.
Java code is below: Tested on the inputs in the following format.
2 3 -7 6 8 1 -10 15
2 3 7 6 8 -1 -10 15
-1 -2 -3 -4 4 3 2 5 7 6
-1 -2 4 3 2 -3 -4 1 7 5 8 -9 -10 -11
-1 -2 4 3 2 -3 -4 1 7 5 8 -9 -10 -11 10 12 6 9 11 13 15
import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MissingPositiveNumber {
ArrayList<Integer> numbers = new ArrayList<Integer>();
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();
numbers.add(i);
}
}
public int findMinMissing(int[] a, int start, int end, int missingMin) {
if (end - start <= 0) {
if (a[start] != start)
return start;
else
return missingMin;
}
int mid = (start + end) / 2;
int j = start, k = end;
while (true) {
while (j <= end && a[j] < mid)
j++;
while (k > start && a[k] > mid)
k--;
if (j >= k)
break;
else {
int temp = a[j];
a[j] = a[k];
a[k] = temp;
}
}
if (mid < a[mid])
return findMinMissing(a, start, mid - 1, mid);
else if (mid > a[mid])
return findMinMissing(a, mid, end, missingMin);
else
return findMinMissing(a, mid + 1, end, missingMin);
}
public int findMissingSmallestPosNumber() {
int[] vals = new int[numbers.size() + 1];
for (int i = 1; i <= numbers.size(); i++) {
vals[i] = numbers.get(i - 1);
}
int j = 1, k = numbers.size();
while (true) {
while (j <= numbers.size() && vals[j] > 0)
j++;
while (k >= 1 && vals[k] < 0)
k--;
if (j > k)
break;
else {
int temp = vals[j];
vals[j] = vals[k];
vals[k] = temp;
}
}
return findMinMissing(vals, 1, k, 0);
}
public static void main(String[] args) {
MissingPositiveNumber mpn = new MissingPositiveNumber();
mpn.readInput();
System.out.println("The least positive missing number ="
+ mpn.findMissingSmallestPosNumber());
}
}
@Loler: Do you work for Google? Wonderful!
- Murali Mohan June 12, 2013
I think the question could have been made clearer and the solution would depend on the requirements.
1. If the ancestor matrix is built sparsely, then determining whether a given node is an ancestor of another node would take O(n) time on avg.
2. If the matrix is built densely, then determining whether a given node is an ancestor of the other would take constant time.
Both sparse and dense matrices can be built recursively in a top-down fashion. To build a sparse matrix we will just mark the position of the parent node in the row of the child node.
To build a dense matrix we will have to copy the whole row of the parent node to the row of the child node and also mark the position of the parent node.
- Murali Mohan June 20, 2013