Roxanne
BAN USER 0of 0 votes
AnswersGiven a amount and several denominations of coins, find all possible ways that amount can be formed? eg amount = 5, denominations = 1,2,3.
 Roxanne in United States
Ans 5 ways
1) 1,1,1,1,1
2) 1,1,1,2 (combinations aren't counted eg 1,2,1,1 etc)
3) 1,1,3
4) 1,2,2
5) 2,3 Report Duplicate  Flag  PURGE
Google Software Engineer / Developer Algorithm
@id
This got me thinking. This may not be very efficient solution because the recurrence relation 'you think' you have here is T(n) = 4T(N/4) + c (where N = n^2) ~ leading to log<base 4>(n^2) complexity. But it's NOT.
Unlike binary search, this does not result in a decision tree at all, since after dividing in four parts, you may not be able to pinpoint one of the parts to proceed and may end up searching each 1/4 from every decision.
Which means that worst timecomplexity, my friend, is 4(n^2/4) ~ n^2 (leaving this as an exercise). Let me know if you need anymore clarification.
@ZSGoldberg "Obviously this solution also fails if there are duplicates in the array, we would have to know that the set of indices and set of values are the same."
You are right about solution failing for duplicates in array.
But we do not necessary need to know that set of indices and set of values are same. So 1 xor 20 xor 1 will still give you 20, since xor is associative, no order needed be maintained like 1 xor 1 xor 2 xor 2 .... etc.
Hope that's clear?
This may not work in most cases, clearly. Consider this sorted array  3 5 6 9 9 9 9 9 9 9 9 9 9 9. Your solution will keep on decrementing from the end, whereas only removing 3 from the beginning of the array could have given you the `min` no. of removals (=1).
 Roxanne January 28, 2014I don't quite get this solution. Just from the looks of it, it's O(nlogn + n * n/2) ~ O(n^2).
Also, consider the sorted array like  3 3 3 3 3 3 3 3 3 4 5 9
acc to step 3a) scanning from 3, first number with value <=6 is 4 with index 9. Total array size 12. Adding their diff 12  9 = 3 to index i? what will you gain out of that?
I think this is a dynamic programming problem and is same as coin change problem. You have say 3 coins 1,2,3 and you've to reach sum 5. All possible ways? 11111, 1112, 122, 23
Above problem can be translated to current problem  you have 5 rocks (N=5) and you have 4 coins (N1) 1,2,3,4. Count number of ways to reach sum 5. 11111, 1112, ....
Solution for coin change problem  geeksforgeeks.org/dynamicprogrammingset7coinchange/
Erasmus is right.
For n=3, following above 'correct' formula  f(n)=2*f(n1)+f(n2), f(1)=3, f(2)=9
f(3) = 2 * 9 + 3
f(3) = 21
According to permutation logic
1 2 3  3 places, 3 characters  total 3^3 = 27 permutations.
unwanted permutations  1 2 3 having a b c > 1 location possible. a b c can be permuted amongst each other at positions [1 2 3] in (nPr ways)  3P3 ways = 3!
final ans = Total permutations  unwanted permutations
final ans = 27  6
final ans = 21
One very simple one comes my mind is a 2D matrix (let's say initialized with 0s).
We keep track of head, tail and length of snake.
if head is in Right direction and so is Tail  you increment [i, n+1] col to 1 and [i, n1] col to 0 > to signify that snake has travelled in right direction.
if head is in Down direction and so is Tail  make [n+1, j] to 1 and [n1, j] to 0
interesting things happen when Snake makes a turn. You can store the history of all turns made by snake. Let's say at any point in Matrix P(bendRow, bendCol) when snake was travelling lefttoright, it makes a down turn. You change direction of 'Head' to Down, but direction of 'Tail' remains the same i.e. Right. So now when snakes moves forward, you change [i, bendCol+1] as 1 and [bendRowsankeLength1, j]. When 'Tail' passes over P(bendRow, bendCol), you delete that point.
Sanke die events  If head hits any of the matrix boundaries or lands up on a cell with 1 (i.e. sanke body still exists there).
int findRepetition(int[] array){
int ans = 1, count = 0, prevMax=0; prevNumber = Integer.MAX;
for(int i= 0; i< array.length; i++){
if(prevNumber == array[i]){
count++;
}
else{
if(count >= prevMax){
ans = prevNumber;
prevMax = count;
}
prevNumber = array[i];
count = 1;
}
}
return ans;
}

Roxanne
December 30, 2013 Good one. A simple Hashmap with timestamp as key and an atomic counter as value. Assuming 1000 sec per sec  on an avg 1 req per ms. Standard timestamps can easily be generated upto ms  hence least collision. Even if there are more than one req per ms, mutex on counter of that timestamp as key for just 23 values will be very cheap computationwise.
 Roxanne December 11, 2013It is. If naive sorting is done (by converting 2D array to 1D array), complexity is MlogM (M = N^2). In Kway merge, complexity is MlogN (since heap only contains N elements at any time).
Side note: Kway merge sort is also used to sort extremely long arrays which cannot fit in memory  called as external merge sort.
Backtracking will work, only first we have to form the mapping as to who was defeat by how many people. eg d  { b, c } (d was defeated by b and c} etc... Person who didn;t win against anyone, forms array[0] (there may be more than one such persons). Start backtracking on this map.
 Roxanne November 14, 2013It can solved mathematically too.
Say you are given 1230 > number of characters for each place are 
1 2 3 0
_______
3 3 3 4
so total number of result strings you'll get are 3*3*3*6 = 162 (Permutations)
So just create 4 arrays in this case 
1 c,d,e, c,d,e, c, d, e ...(repeat c,d,e 162/3 = 54 times)
2 v,f,r, v,f,r, v,f,r, ....( repeat v,f,r 162/3 = 54 times)
3 b,g,t (162/3 = 54 times)
0 z,a,q,x,s,w (repeat 162/6 = 24 times)
combine all 4 in one by
for ( i=0;i<162;i++)
{ finalArray[i] = a1[i]+a2[i]+a3[i]+a0[i] }
Open Chat in New Window
Attaching another great resource, use of different data structures in linux kernel  cstheory.stackexchange.com/questions/19759/corealgorithmsdeployed/19773#19773
 Roxanne January 29, 2014