asenthilkumargce
BAN USERAlgorithm fails for the below inputs
input : {2,4,7,7,7,7,7,7,7} , K = 3, Actual Ans: 21 , This algo ans : 42
input : {1,2,6,6,6,6,6,6,6,10} , K = 2, Actual Ans: 16 , This algo ans : 19
input : {1,2,3,3,4,4,6,6,6,11} , K = 2, Actual Ans: 17 , This algo ans : 19
input : {1,2,3,4,5,5,6} , K = 3, Actual Ans: 16 , This algo ans : 18
As you can see, it has a whole lot of failing cases.
"Code fails at {2,4,10} ans definitely 8; for K=1;"
Ans is 6 for K=1
The correct algorithm would be to check all possibilities of picking K pots in worst case and picking the one with minimum stones among them. Trying to do the problem with any other algorithm is going to fail as there can be an input formed which would make the algorithm fail.
To check all possibilities, it is actually tweaked program of getting all possible kth subset.
The code goes here. Feel free to challenge with any input.
public static int ThirstyCrowProblem(int[] input1,int input2,int input3) {
int n = input2;
int k = input3;
int tempk = 0;
if(input1 == null || k < 0 || k > input1.length || n <= 0 || input1.length != n) {
return -1;
}
if(k==0) {
return 0;
}
for(int i = 0; i < n; i++) {
if(input1[i] < 0) {
return -1;
} else if (input1[i] == 0) {
if(++tempk==k) {
return 0;
}
}
}
Arrays.sort(input1);
return minStones(input1,k-tempk,tempk);
}
public static int minStones(int[] input, int k, int start) {
List<Integer> minStones = new ArrayList<Integer>();
minStones.add(Integer.MAX_VALUE);
minStones(input,k,start,0,minStones);
return minStones.get(0);
}
public static void minStones(int[] input, int k,int start, int stones, List<Integer> minStns) {
if(k==0) {
if(stones < minStns.get(0)) {
minStns.set(0, stones);
}
return;
}
int[] clone = null;
for(int i = start; i <= input.length-1-(k-1);i++) {
if(input[i] == 0) {
continue;
}
clone = input.clone();
//change clone
int stns = 0;
int tempk = 0;
for(int j = clone.length-1; j >= i;j--) {
if(clone[j] == 0) {
continue;
}
if(clone[j] <= clone[i]) {
stns+=clone[j];
clone[j] = 0;
if(++tempk == k) {
break;
} else {
continue;
}
}
stns+=clone[i];
clone[j] -= clone[i];
}
minStones(clone,k-tempk,i,stones+stns,minStns);
}
}
Finding Sum and product of given numbers takes O(n) time complexity and yes I dont think it is possible with lesser time complexity
- asenthilkumargce May 22, 2013Input array: 20, 24, 28, 49, 5, 6, 7, 8, 9, 10, 11, 50, 51, 62, 4, 70
here your algorithm will remove index of numbers 5 and 4.
And the result is not sorted too.
Here the numbers to be removed are 20, 24, 28, 49 and 4
We can have each node for each server and can have a name field to denote server. The value of a node can be Number of connections currently being handled by the server. We can increase the node value of min-heap when the request is directed to any server and decrease when the request is served.
Here comes the problem.
1) How will you avoid race conditions
synchronising would be very bad idea, since it will badly affect the request serving
Dictionary Creation:
Data Structure: HashMap(AnagramHash key) contains HashMap(uniqueHash key)
hash1: anagramHash() - > Returns same hashcodes for all anagrams and not for non-anagram words
hash2: unique for each word
search:
Find hash 1 and hash 2 for any word and get the info
Time: O(1) i.e constant time
Anagram search:
find hash1 and return all objects in the inner hashmap
Time: O(1)
justify your answer
- asenthilkumargce November 02, 2012One has to check whether the code output and manual output matches all times with different input
- asenthilkumargce November 01, 2012Repeatable
- asenthilkumargce November 01, 2012
This algorithm fails for below case!
- asenthilkumargce May 06, 2015Input : {1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,8,11} , K=2, Actual Ans: 8, This Prog Ans: 19 !!!
Algorithm should look at all possibilities and then decide the minimum one