mbriskar
BAN USERWe do not need to sort the whole array.
What about firstly distributing the array into groups of 1-intervals. For example 1-2,2-3... based on the integer part of the number (in java Map<Integer, List<Float>>).
Then sort these List<Float>s and for every single number, count it as : list.length + binarySearch on the group on the left and group on the right.
Complexity will be O(n) for dividing into the groups + O(k*logk) for sorting the groups + O(n*2*log k) for checking the neighbors.
K-th largest element can be found in O(n) regardless of the fact that this is max-heap. You can use selection algorithm (quickselect).
But I cannot think of a method to do it in log(n) and was not lucky to find anything else except some proof that this cannot be done faster..
The result in the question is built differently but following the same logic.
Firsty you take 1st last digit for first number, then 2 last digits for the second, then 2 last digits for the first number, then .... You can take 2 at once, because it doesn't matter about the variation in the same level of the number.
So it was like 1 2 7 8 9 -> 9 _ -> 9 78 -> 129 78
No recursion, extra O(n) space
public static void main(String[] args) {
compute("a?b?c?");
}
public static void compute(String s)
{
List<Integer> questionPosition = new ArrayList<>();
for(int i=0;i<s.length();i++) {
char character = s.charAt(i);
if(character == '?') {
questionPosition.add(i);
}
}
//for faster modification than String
char[] inputArray = s.toCharArray();
//to know when to end
int numberOf1s =0;
//which questionmark to process next
int currentQuestion=0;
while(numberOf1s < questionPosition.size()) {
if(currentQuestion<questionPosition.size()) {
char q = inputArray[questionPosition.get(currentQuestion)];
if(q == '?') {
inputArray[questionPosition.get(currentQuestion)] = '0';
currentQuestion++;
} else if(q=='0'){
inputArray[questionPosition.get(currentQuestion)] = '1';
numberOf1s++;
currentQuestion++;
} else if(q=='1') {
inputArray[questionPosition.get(currentQuestion)] = '?';
numberOf1s--;
currentQuestion--;
}
} else {
printArray(inputArray);
currentQuestion--;
}
}
// last 1's were not printed
printArray(inputArray);
}
private static void printArray(char[] inputArray)
{
for(int i=0;i<inputArray.length;i++) {
System.out.print(inputArray[i]);
}
System.out.println();
}
The only problem that I see here is that you have to recompute the String every single time and you don't save any results between. This may be a problem, because you are doing it (2^n) times where n is the number of '?'.
I think this can be improved a little bit and done in a simpler way by storing last permutation of the string and remembering which '?' we are dealing with now. You only need O(n) memory to memoize the '?' positions in the array to speed it up, but you may save time (not complexity, it's 2^n still). I will write my own answer with my solution, maybe somebody will be interested.
O(n) time complexity, O(n) space complexity
public static void main(String[] args) {
int[] a = new int[] {1,3,2,0,5};
int[] b = new int[] {2,1,3,0,5};
arrangeArrays(a, b);
}
public static void arrangeArrays(int[] a, int[] b) {
Map<Integer,Integer> aPositions = new HashMap<>();
for(int i=0;i<=a.length-1;i++) {
if(a[i] != b[i] || a[i]==0) {
aPositions.put(a[i],i);
}
}
arrange(a, b, aPositions);
for(int i =0; i<a.length;i++) {
System.out.println("a: " + a[i] + ", b: " + b[i]);
}
}
public static void arrange(int[] a, int[] b, Map<Integer,Integer> aPositions) {
while(aPositions.size() !=1) {
final Integer zeroIndex = aPositions.get(0);
final int bZero = b[zeroIndex];
if(bZero == 0) {
final Iterator<Integer> iterator = aPositions.keySet().iterator();
Integer next = iterator.next();
if(next == 0) {
next = iterator.next();
}
final Integer nextIndex = aPositions.get(next);
swap(a,zeroIndex,nextIndex);
aPositions.put(0,nextIndex);
aPositions.put(next,zeroIndex);
} else {
final Integer zeroSwap = aPositions.get(bZero);
swap(a,zeroIndex,zeroSwap);
aPositions.put(0,zeroSwap);
aPositions.remove(bZero);
}
}
}
public static void swap(int[] a, int i, int j) {
int swapInt = a[i];
a[i] = a[j];
a[j] = swapInt;
}
The solutions using Bernoulli trial are not correct, because they count multiple occurrence of i multiple times. They are quite close though.
Let me introduce dynamic programming that may be helpful with this problem. Hopefully there are no bugs, but if they are, feel free to raise your hands.
Let P(M,N) be a function that counts probability that within N fields, there will be at least one with exactly i matches from the N numbers hashed inside.
P(M,n < i) =0
P(0,i) =0
P(M,N) = sum (for x <- 0..N:
if( x==i) :"probability that exactly x integers matches into Nth slot"
else: "probability that exactly x integers matches into Nth slot" * P(M-1,N-x)
)
The probability in quotes is (1/M)^x * ( (M-1)/M ^ (N-x) ) * (n choose x)
- mbriskar June 06, 2015Longest common subsequence:
S(i,j) = longest common subsequence of strings 0..i, 0..j
S(0,j) =0, S(i,0) =0
S(i,j) : if(i==j) S(i-1,j-1)
else max(S(i-1,j),S(i,j-1))
Longest common consecutive subsequence:
STRING: It is best done by creating common suffix tree for both Strings and then finding the deepest node in the tree that has a path to both ends.
INT: I think you can do the same for Strings. Otherwise, the complexity will be O(n^2) using dynamic programming by counting every possible pair (I am not aware of any other algorithm)
This is good idea and works very good. However the only problem I see here is the heap created will not have minimal length (you call it only on the left child and the right child will be alone). This is not a complete binary tree, left branch is almost always longer
- mbriskar June 01, 2015buried has a good DP solution, however I think there is no need to calculate every single subarray possible. My idea is:
M(i,j), where i is the number of spare painters, j is the number of spare boards (0..j) and then
M(1,j) = board_length_sum(0-> j)
M(i,1) = first_board_length
M(i,j) = min(for k from 0->j : M(i-1,k) + board_length_sum(k -> j) )
The idea: I always go from end of the boards array and try to assign painter to some subarray with indices from k to j, where k is always between 0 and the current end of boards array. To check all such possibilities (k from 0 to j) it takes O(n). Then call the same function on subarray without considering the painter already assigned and boards that he painted.
After all, the final complexity is O(K * N^2) (you need to take care not to calculate bord_length_sum() again but to calculate it from the already calculated subarray)
If we can preprocess check, why not to preprocess whole result and have it in O(1) :-)... On the other hand, idea to find the edge palindrome is good idea, because you don't need to count with all possibilities, just cut off the first palindrome on the right, because this cut will surely need to be done and it doesn't matter when.
- mbriskar May 31, 2015AFAIK normal n+1 is O(1) amortized, just everytime adding +1 bit, save extra space for needing to count with carry.
So now assume every 1 bit has saved extra time for being carried. Now 111 +1 -> use 3rd extra time to 110 -> use 2nd extra to -> 100 use first extra -> 1000 and now save extra time for the new 1. Now from 1000 -> 1001 and save extra time for the last 1..
It is actually not so simple to prove that it will be on diameter but I think it is true.
a) you start already on diameter. Then the node most far away from you must be on diameter, otherwise diameter is wrong (further node from "diameter" and the latest further node found is longer than the diameter).
b) you are not already on diameter. There must be a path to diameter though (it is connected). So the minimum path you can get from diameter is diam/2. In case you can find something else that is not part of diameter (otherwise by a) you would end in diameter) is larger or equal, than diameter can be improved at least by +1 length.
Both cases lead to a conclusion, that you will find a node on a diameter.
I have seen correct solution to this somewhere here. It may be done in O(n) by having a queue. I will start with window from the left, adding each element to the TAIL of the queue with doing it specially (deleting all the elements bigger than the current added value, until I will reach lower one). Then I will print the HEAD of queue and in case it is going to be removed in next turn (it is the most left in the window), remove it... It is O(n), because every single element will be added once to the queue and also deleted once.
- mbriskar May 24, 2015bg2d I think you are wrong. You have several options to save the number into the slot, it doesn't need to be last. Maybe you look at the problem differently
The problem with the solution above is that f(0,k) must be defined as 0, otherwise you will count even solutions in which you didn't use all of the ranks..
Otherwise I think solution is quite good, it took me a while to understand why it works. The key idea here is it changes the question to "distribute k numbers into n slots, where every single number needs to be used." So thinking about Nth slot, you can give there one of k numbers and call it on smaller array.
The answer to the whole question is then sum of f(N, 1<=k<=N), complexity O(n^2)
I can add more description to that. Count the SUM of all volumes you have and then divide it by number of people K. You will get the best possible value that is SUM/K, but that's only a dream.
Now you can start the binary search by always trying to slice the cakes by some number x, 0<x<=SUM/K. In case there is not enough slices for people, you know the answer will be in the range 0<x. In case you have enough slices for people, memoize x and try to look for better in x<= SUM/K.
The only problem I see here is that we are counting with real numbers, so you may never stop. So after some time it may be good to start with already mentioned algorithms
Firsty I thought this cannot be done using DP, because local minimum might not mean best minimum. However I think I was wrong.
My thought was:
1, 50, 1 and -1, the best is to have 0,-1,0. However after having 1,50,1,100 and -1, the best is to have 0,0,0,-1.
Telling it just so you will know that this doesn't mean there is no DP.
When considering that there are only 4 answers, it is then simple:
a) Answer is 0 if source&target are at the same place
b) answer is infinite if they are on different color (sum of x+y is even for one and odd for the other one)
c) Answer is 1 if (x1+y1) == (x2+y2) || (x1-y1) == (x2-y2)
d) otherwise the answer is 2
I have to admit it is an interesting observation but it is not right however. Imagine two almost infinite branches that are making the diameter. Then you will start adding vertices to some other branch that is not part of this diameter. It will cause diameter to get bigger.
As an counterexample, try putting
System.out.println(d.addNode(0, 1));
System.out.println(d.addNode(0, 2));
System.out.println(d.addNode(1, 3));
System.out.println(d.addNode(3, 4));
System.out.println(d.addNode(4, 5));
System.out.println(d.addNode(5, 10));
System.out.println(d.addNode(10, 11));
System.out.println(d.addNode(1, 6));
System.out.println(d.addNode(6, 7));
System.out.println(d.addNode(7, 8));
System.out.println(d.addNode(8, 12));
System.out.println(d.addNode(12, 13));
System.out.println(d.addNode(2, 9));
System.out.println(d.addNode(9, 14));
Most of the algorithms are using the median checks that work only for the arrays of the same length.
For the arrays of different length you must use different approach, the one that is described http://www.drdobbs.com/parallel/finding-the-median-of-two-sorted-arrays/240169222?pgno=2 or in video here https://www.youtube.com/watch?v=_H50Ir-Tves (ignore the (3), there is a mistake because the guy also consider comparing medians to work for different arrays, even though it does not work).
However I think you cannot easily continue recursively in the subarrays as he says in the video, it's safer to just make the range a,b and a2,b2 always smaller instead (but not to forget A.length and B.length values). I don't have a proof though
Another problem here is that for every string you check every possible reversed substring and the complexity will be (n*k^2) because of this.
- mbriskar June 11, 2015