dc360
BAN USER- 0of 0 votes
AnswersQuestion 1 / 1
- dc360 in United States
There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.
A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
At anypoint of time, the decreasing radius property of all the pegs must be maintained.
Constraints:
1<= N<=8
3<= K<=5
Input Format:
N K
2nd line contains N integers.
Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
3rd line denotes the final configuration in a format similar to the initial configuration.
Output Format:
The first line contains M - The minimal number of moves required to complete the transformation.
The following M lines describe a move, by a peg number to pick from and a peg number to place on.
If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one.
Sample Input #00:
2 3
1 1
2 2
Sample Output #00:
3
1 3
1 2
3 2
Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1
Sample Output #01:
5
3 1
4 3
4 1
2 1
3 1
NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout
If you are using "Java", the classname is "Solution"| Report Duplicate | Flag | PURGE
Facebook Algorithm
How is this approach any different than the number line method? Array a is the number line. With the data in the main method, the line is 5, 15, 28, 30. Then you draw a random number from 0 to 30 say 29 and search it in the number line and return left index of the range. (although there are issues in the binary search algo here. infinite loop for 28), but the idea is right.
- dc360 September 08, 2012The idea is good, but still generates duplicates. For the above example, this is the sorted-sums arrays.
[5, 6, 7, 7, 8, 9, 9, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 14, 14, 15, 15, 16, 17, 17, 18, 19]
We need to travel this array only up to elements 23/2 i.e. 11 and search for (23-a[i]). That avoids obvious duplicates like 5-18 and 18-5. But it produces some duplicates e.g.
2, 3, 10, 8 result of searching 5 for 18.
2, 8, 10, 3 result of searching for 10 for 13.
Another thing to note is that there are several duplicate sums, all of which need to be looked at. The sums created using different indexes are valid. It becomes a hybrid of binary and sequential search in both directions. That increases the complexity from log(n). I think its reasonable to expect duplicates in the sums array.
- dc360 September 07, 2012I sure hope that's what the interviewer meant because with the assumption your solution is pretty cool. So say one sum is 3+9=12, then you search in sum-sorted array for 23-12=11. Say you find 11 that came from 3+8. That's why you say its 2 * 3 + 9 + 8=23. But it does not use 4 elements from array as the question asked for. You might argue that it uses any 4th element with 0 coefficient.
The solution for 4 unique indices will be tedious. (23-sum) will have to be searched multiple times until indexes used to create 'sum' are not used to create (23-sum)
Did I get that right?
@eugene The problem statement clearly states "find all combination of four elements in the array". Interpreting "4 elements in an array" to mean "one element 3 times and one more element" would be unprecedented.
Do you think a logic that's faster than the logic that loops through "N choose 4" can exist for this problem?
Anyone with faster than O(n2) algorithm on this one? Check this one
7, 3, 4, 4, 3, 1, 8, 1, 1, 1, 3, 1 , 2, -1, -2, 3
N=21
I doubt if this can be done Order(N). Consider the 2nd 3. It is involved in 3 sequences that add up to 21. I think there is no option, but to calculate all n (n+1)/2 sums.
@eugene
Why do you say quadratic? To find the longest sequence in acyclic DAG first we need topological sort, which does a DFS proportional to V+E. Then the longest path logic goes over all vertices and relaxing all edges. I don't see where quadratic complexity comes into picture?
This was in a phone interview? I hope you weren't asked to implement it.
More specifically, IMHO, this is mincost maxflow problem. Create one source node with directed link of capacity 3 and cost 0 to every school. Create links of capacity 1 from every school to every other student with cost = distance between corresponding school and the student. Then create links of capacity 1 from every student to a sink node and cost 0. The use mincost maxflow algorithm to maximize flow and minimize the cost. When the algorithm is done, it gives 3 links going out from each school to 3 students such that the cost is minimum. The logic and implementations are very complex.
Nasser is right. Consider 2 parallel buckets. One comes up with top ten where last one is Y, 91 times and 11th is X 90 times. The other bucket comes up last as Z, 91 times, and 11th as X 90 times, and no Y at all. X actually appeared 180 times and Y only 91 times, but if you merge only top 10, the answer will not have X in it.
Could tracking more than top 10 in each bucket and merging more than 10 from each would guarantee the correct top 10? I don't know.
KMP maintains a table. I think Rabin-Karp or KMP both would be expected answers, but people on this forum think that "in-place" means no additional memory is allocated. I don't believe that's true. I think 'in-place' means that don't copy the string in other places such as arrays or suffix trees.
I don't know what you mean by Rabin-Karp is heavy. It only calculates the hash for the pattern, and then its rolling hash O(1) operation when inside the loop. On average should perform O(length of text)
Do you think Jdk's PriorityQueue is unsuitable for this operation? It does not provide "change" operation where priority of an existing object is changed, so it can move up or down. The only way to achieve that is to remove and add, but remove is O(n) implementation.
- dc360 August 29, 2012I think this algorithm will perform 2*n steps in the worst case. I think this is O(n).
1, 2, 4, 7, 11,
3, 5, 8, 12, 17,
6, 9, 13, 18, 22,
10, 14, 19, 23, 25,
15, 20, 24, 26, 27;
If you have above matrix, and pick the right bottom element to start, then the search will take n+n comparisons.
The logic does not look at all elements, so it has got to do better than n^2.
- Create S1=S and S2 empty. Sum1 is the sum of S and sum2 is the sum of S2 (0 to start)
- Keep iterating over S1
- Find an element in S1 which if moved to S2 would minimize (sum1-sum2). If you do find it, then move the element from S1 to S2 and update sum1 and sum2. If you can't find such an element, then break the loop.
I was able to get the following output
Input=[12, 4, 7, 1, 6, 3, 3]
S1=[4, 7, 1, 3, 3]
Input=[3, 3, 12, 4, 7, 1, 6]
[3, 3, 4, 7, 1]
Input=[3, 3, 2, 2, 2]
[2, 2, 2]
Input=[5, 3, 2, 13, 2]
[5, 3, 2, 2]
Input=[5, 5, 4, 3, 3]
[4, 3, 3]
Wikipedia says that the order if O(n+d), but I don't understand how that's possible. You are already in a loop that goes over the array and if you find an inversion, you go over again shifting. Martin here seems to be correct. O(N+kN). But what is Binary insertion sort?
- dc360 August 12, 2012
Is this really a dynamic programming problem? As per Wikipedia, the coin change problem specifies denominations of the coins and unlimited supply of those coins. Here the number of coins are fixed.
- dc360 September 09, 2012