gudujarlson
BAN USERI was asked a similar question and I had no idea what the interviewer expected from me. My first thought was to draw a diagram of the building, but I was pretty sure that was not what the interviewer had in mind. After an awkward question and answer exchange, I still had little idea what I was supposed to do. I ended up assuming I was designing a control system for fully automated parking garage.I drew some boxes that represented potential software and/or hardware modules (gate, sign, ticket vending machine, etc) and lines that represented dependencies between them. I received feedback that I failed this question. Does anyone have an example of a good answer to questions like this one?
- gudujarlson November 11, 2014My bad. I misinterpreted your solution.
- gudujarlson November 08, 2014The first part of your proof makes sense to me, but I'm not following the second part. You appear to be ignoring the distance each person has to move. I think the proof needs to prove that the minimum of this function occurs when i is the median.
cost(i) = sum { distance(i,j) - count(i,j) }
where
i = seat index that we move everyone towards
j = seat index of a particular person
distance(i,j) = abs(j-i)
count(i,j) = the number of people between seat i and j, not counting the person sitting at j.
This is similar to the enhanced merge sort, but is more concise or maybe not. Iterate over the array and insert each number into a binary search tree. At each node maintain the number of nodes in the branch of the tree. When inserting a node into the tree count the number of nodes with values that are greater than the value of the inserted node. There are n inserts into the binary tree each costing log(n) so the total time complexity is n*log(n). Space complexity is O(n).
int numberOfInversions(int a[]) {
int inversionCount = 0;
Node root = new Node();
root.v = a[0];
root.count = 1;
for (int i = 1; i < a.length; ++i) {
Node node = root;
while (true) {
node.count++;
if (a[i] < node.v) {
inversionCount += (node.right != null ? node.right.count : 0) + 1;
if (node.left == null) {
node.left = new Node();
node.left.v = a[i];
node.left.count = 1;
break;
}
else {
node = node.left;
}
}
else {
if (node.right == null) {
node.right = new Node();
node.right.v = a[i];
node.right.count = 1;
break;
}
else {
node = node.right;
}
}
}
}
return inversionCount;
}
static class Node {
public int v;
public Node left;
public Node right;
public int count;
}
By the way, I don't understand why the median method works, but I have not found a case where it doesn't. It requires some more thought to understand why it works.
- gudujarlson November 05, 2014This does not work in all cases. See my comment below.
- gudujarlson November 05, 2014This does not work in all cases. Take the example "xx.x.x....x". Your solution would result in the follow sequence of shifts:
xx.x.x....x
xxx..x....x
xxx.x.....x
xxxx......x
xxxx.....x.
xxxx....x..
xxxx...x...
xxxx..x....
xxxx.x.....
xxxxx......
And then output 9, however the correct answer is 8.
The correct answer is achieved by choosing the median person and then shifting everyone to the nearest empty seat. The correct sequence looks like this:
xx.x.x....x
x.xx.x....x
.xxx.x....x
.xxxx.....x
.xxxx....x.
.xxxx...x..
.xxxx..x...
.xxxx.x....
.xxxxx.....
A brute force solution is to, for each seat S, shift each person to the unoccupied seat closest to S and remember which choice of seat results in the minimum number of shifts. Complexity is O(n^2). A faster solution is to find the median person M and shift each person to the unoccupied seat closest to M. Complexity is O(n). Here are both solutions in Java.
// Brute force. For each chair, shift all people to it. Remember which chair requires the least shifts.
// O(n^2)
int minJumps(String s) {
int minCount = Integer.MAX_VALUE;
for (int i = 0; i < s.length(); ++i) {
int count = shift(s.toCharArray(), i);
if (count < minCount) {
minCount = count;
}
System.out.println(new String(s) + " " + count);
}
return minCount;
}
// Optimized. Find the median person and shift everyone to them.
// O(n)
int minJumpsOptimized(String s) {
int i = findMedian(s.toCharArray());
if (i == -1) {
return 0;
}
return shift(s.toCharArray(), i);
}
// Shifts each person the the unoccupied seat closest to seat i.
int shift(char s[], int i) {
int count = 0;
int j = 0;
int k = i;
while (j < k) {
if (s[j] == '.') {
j++;
}
else if (s[k] == 'x') {
k--;
}
else {
s[k] = s[j];
s[j] = '.';
count += k-j;
j++;
k--;
}
}
j = s.length - 1;
k = i;
while (j > k) {
if (s[j] == '.') {
j--;
}
else if (s[k] == 'x') {
k++;
}
else {
s[k] = s[j];
s[j] = '.';
count += j-k;
j--;
k++;
}
}
return count;
}
// Finds the median person.
int findMedian(char s[]) {
int count1 = 0;
for (char c : s) {
if (c == 'x') {
count1++;
}
}
if (count1 == 0) {
return -1;
}
count1 = (count1 + 1) / 2;
int count2 = 0;
for (int i = 0; i < s.length; ++i) {
if (s[i] == 'x') {
count2++;
if (count2 == count1) {
return i;
}
}
}
throw new RuntimeException("yuk!");
}
See an iterative version of this solution below.
- gudujarlson October 31, 2014Heh, ya, I was fooled too. I think I just wanted to practice a probability problem. In the end, all I calculated is the average number of children per couple given an infinite amount of time; which is irrelevant. Good practice though. I hadn't thought through that line of reasoning in a while.
- gudujarlson October 31, 2014There is a 1/2 chance that a couple will have a girl on the first try, 1/4 after 2 tries, 1/8 after 3 tries, etc. Therefore the probability a couple has n children is given by:
P(n) = 1/2^n
This can be seen by looking at the possible outcomes of boy and girl births. For example for 2 tries the possible outcomes are:
BB
BG
GB
GG
Only 1 of these 4 is possible and results in a girl on the 2nd try, because the couple stops once they have a girl. Therefore the probability of a couple having 2 children is 1/4.
The average number of children per couple is given by:
a = 1*P(1) + 2*P(2) + ... n*P(n) = 1/2 + 2/4 + ... n/2^n
This geometric series sums to 2, therefore the average number of kids per couple is 2. Since every couple has at least 1 girl, the ratio of boys to girls is 1.
Also, assuming I understand what you are trying to implement, I think the worst case complexity is O(n^2). Consider this input: {1,2,3,4,5,6,7,8,-1}. Your solution will walk up the full tree n times which will lead to n+(n-1)+(n-2)+...1 visitations. This can be fixed by using a stack to record the depth of each node as you walk up the tree. See my solution.
- gudujarlson October 30, 2014This solution walks up the tree to determine the depth of each node and remembers the maximum depth. To keep time complexity to O(n), the calculated depths are stored in an auxiliary array. Time O(n), Space O(n).
int height(int a[]) {
ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
int maxHeight = 1;
int height[] = new int[a.length]; // Cache of computed heights.
for (int i = 0; i < a.length; ++i) {
// If we have already calculated a height for this node, continue.
if (height[i] > 0) {
continue;
}
// Is this is the root node, record its height and continue;
if (a[i] == -1) {
height[i] = 1;
continue;
}
// Walk up the tree until we find a node with a known height.
int j = a[i];
while (j >= 0 && height[j] == 0) {
deque.push(j);
j = a[j];
}
// Walk back down the tree and record the height of each node.
int h = j >= 0 ? height[j] : 0;
while (deque.size() > 0) {
j = deque.pop();
height[j] = ++h;
}
height[i] = height[j] + 1;
// Remember the maximum height.
if (height[i] > maxHeight) {
maxHeight = height[i];
}
}
return maxHeight;
}
Your code returns 0 in all cases. Did you mean "cache[i] = depth;" instead of "cache[node] = depth;"?
- gudujarlson October 30, 2014Another pattern where it is impossible for player 1 to choose the n/2 highest is when the n/2 highest are in the center. For example:
1,3,4,2
Player 1 has to choose either 1 or 2 in this case.
Yes, there are cases where player 1 cannot choose the n/2 highest numbers no matter what order either player chooses, however experimentally I have seen that those case are rare. In cases where the n/2 highest are consecutive, player 1 can always choose all of them. For example,
1,2,3,4 => player 1 chooses 4,3
2,1,3,4 => player 1 chooses 4,3
Cases where it is not possible are some cases where the n/2 highest alternate left and right. For example:
12,10,8,6,4,2,1,3,5,7,9,11
CAVEAT: I didn't check this particular one but it follows the pattern.
No I think what the problem is asking is, "Regardless of the strategies chosen by the two players, what is best possible outcome for player 1?" Another problem might ask, "If both players use a strategy of choosing the number with the greatest possible outcome, what will player 1's score be?" Yet another problem might ask, "Is there a strategy that guarantees the best possible outcome?"
After playing with this problem more, I am starting to wonder if there is a O(n) solution. Experimentally I have seen that there is a high probability that that best outcome is the sum of the n/2 highest numbers (i.e. the set of numbers >= median).
Upon further reflection... It does not matter if the game is competitive or cooperative because we are simply looking for the best possible outcome for player 1 and that outcome occurs at the same time as the worst possible outcome for player 2. The strategy used by either player is irrelevant.
- gudujarlson October 29, 2014/**
* The naive solution is to enumerate all possible paths and pick the maximum.
* Complexity analysis of this solution is somewhat complicated,
* but with a little work one can see that their are nC1 + nC2 + ... nCn possible paths, where nCm means "n choose m".
* Think Pascal's Triangle.
*
* However there is a better way.
* This can be transformed into the longest path problem for a directed acyclic graph.
* The longest path problem has known solution with time complexity equal to the number of vertices. See wikipedia.
*
* 1) Consider graph A to be the input and graph B to be an auxiliary graph with the same structure as graph A.
* Graph B will store the maximum path weight possible for a path ending on that node.
* 2) Perform a breadth first traversal of A and store the sum of each node's weight and the maximum weight of its parents in graph B.
* 3) Starting at the bottom node of graph B with the maximum value, traverse B by navigating to the parent with maximum value.
* This path is the path with the maximum weight.
*
* Time O(n^2), Space O(n^2)
*/
int maxWeight(int a[][]) {
// Build graph B.
int max = 0;
int maxJ = 0;
int b[][] = new int[a.length][a.length];
for (int i = 0; i < a.length; ++i) {
for (int j = 0; j <= i; ++j) {
b[i][j] = a[i][j];
int up = 0;
int diagonal = 0;
if (i > 0) {
up = b[i-1][j];
if (j > 0) {
diagonal = b[i-1][j-1];
}
}
b[i][j] += Math.max(up, diagonal);
if (b[i][j] > max) {
max = b[i][j];
maxJ = j;
}
}
}
// Follow max path in B from bottom to top.
int weight = a[0][0];
int j = maxJ;
for (int i = a.length - 1; i > 0; --i) {
weight += a[i][j];
int up = b[i-1][j];
int diagonal = 0;
if (j > 0) {
diagonal = b[i-1][j-1];
}
if (diagonal > up) {
j--;
}
}
return weight;
}
And here is the memoized solution. Time complexity is O(n^2).
int maxGold(int a[]) {
int cache[][][] = new int[2][a.length][a.length];
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < a.length; ++j) {
for (int k = 0; k < a.length; ++k) {
cache[i][j][k] = -1;
}
}
}
return maxGold(a, 0, a.length - 1, true, cache);
}
int maxGold(int a[], int left, int right, boolean firstPlayer, int cache[][][]) {
int cachedMax = cache[firstPlayer ? 1 : 0][left][right];
if (cachedMax >= 0) {
return cachedMax;
}
int max = _maxGold(a, left, right, firstPlayer, cache);
cache[firstPlayer ? 1 : 0][left][right] = max;
System.out.println("(" + left + "," + right + "," + firstPlayer + ") = " + max);
return max;
}
int _maxGold(int a[], int left, int right, boolean firstPlayer, int cache[][][]) {
++iterations;
if (left == right) {
if (firstPlayer) {
return a[left];
}
else {
return 0;
}
}
int leftMax = maxGold(a, left+1, right, !firstPlayer, cache);
int rightMax = maxGold(a, left, right-1, !firstPlayer, cache);
if (firstPlayer) {
leftMax += a[left];
rightMax += a[right];
}
return Math.max(leftMax, rightMax);
}
It's unclear if the game is competitive or cooperative. If it's competitive, it's unclear if player 2 plays perfectly. I will assume it is either cooperative or that player 2 plays poorly. Here is a solution that simply iterates over the possible outcomes and picks the one with the max value. Time complexity is O(2^n)). Some memozation could speed it up.
int maxGold(int a[]) {
return maxGold(a, 0, a.length - 1, true);
}
int maxGold(int a[], int left, int right, boolean firstPlayer) {
int max = _maxGold(a, left, right, firstPlayer);
System.out.println("(" + left + "," + right + "," + firstPlayer + ") = " + max);
return max;
}
int _maxGold(int a[], int left, int right, boolean firstPlayer) {
if (left == right) {
if (firstPlayer) {
return a[left];
}
else {
return 0;
}
}
int leftMax = maxGold(a, left+1, right, !firstPlayer);
int rightMax = maxGold(a, left, right-1, !firstPlayer);
if (firstPlayer) {
leftMax += a[left];
rightMax += a[right];
}
return Math.max(leftMax, rightMax);
}
Nope. Take 5,12 for example. Player 1 can always win if they start with 3.
3,5,4 win
3,4,5 win
3,2,1,4,5 win
3,2,1,5,4 win
3,1,2,4,5 win
3,1,2,5,4 win
Oops, never mind about the worse case O(n) space. That was a early morning brain fart.
- gudujarlson October 23, 2014This is basically the same as my solution, except that you rescan for the first zero when shrinking the left side whereas I store that information in a deque. I like the simplicity of your solution.
- gudujarlson October 22, 2014This is similar to the max subarray problem and can be solved in O(n) time using something similar to Kadane's algorithm. The main idea is maintaining a sliding window that contains a continuous sequence of 1's as we iterate over the array. We extend the right side of the window if we encounter a 1 or the number of flips is less than m; otherwise we shrink the left side to one position to the right of the first zero. The last part forces us to maintain a list of the positions of the zeros. Thus O(m) space. Here a solution in Java.
int[] maximumContinuousOnes(int a[], int m) {
ArrayList<Integer> maxFlipIndices = innerMaximumContinuousOnes(a, m);
int result[] = new int[maxFlipIndices.size()];
for (int i = 0; i < maxFlipIndices.size(); ++i) {
result[i] = maxFlipIndices.get(i);
}
return result;
}
ArrayList<Integer> innerMaximumContinuousOnes(int a[], int m) {
int maxLength = 0;
int maxBegin = 0;
int maxEnd = 0;
int begin = 0;
ArrayDeque<Integer> flipIndices = new ArrayDeque<Integer>();
for (int i = 0; i < a.length; ++i) {
if (a[i] == 0) {
if (flipIndices.size() < m) {
flipIndices.addFirst(i);
}
else {
int length = i - begin;
if (length > maxLength) {
maxLength = length;
maxBegin = begin;
maxEnd = i;
}
begin = flipIndices.removeLast() + 1;
flipIndices.addFirst(i);
}
}
}
int length = a.length - begin;
if (length > maxLength) {
maxBegin = begin;
maxEnd = a.length;
}
ArrayList<Integer> maxFlipIndices = new ArrayList<Integer>();
for (int i = maxBegin; i < maxEnd; ++i) {
if (a[i] == 0) {
maxFlipIndices.add(i);
}
}
return maxFlipIndices;
}
It in fact returns 7 for that input.
@Test
public void test() {
Assert.assertEquals(7, maximumOnes(new int[] {1 ,0, 0,0, 0, 0, 1}));
}
Our solutions do not agree for the input 5,12. Mine returns true and your returns false. I believe mine is correct. If player 1 starts with 3 they can always win.
3,5,4 win
3,4,5 win
3,2,1,4,5 win
3,2,1,5,4 win
3,1,2,4,5 win
3,1,2,5,4 win
Your code does not work the cases 3,2, 3,3, and 3,5. It returns false for each, but the correct answer is true for each. Player 1 can win with perfect play in each case.
- gudujarlson September 30, 2014Your code returns true for the case 3,4, but I believe the correct answer is false because no matter what player 1 starts with, player 2 can win.
1,3 loss
2,2 loss
3,1 loss
I misread the problem statement. I thought the goal was to NOT reach the desired total. Here is the fixed code. I also added a support for the special case that neither player can win.
boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if ((maxChoosableInteger*maxChoosableInteger + maxChoosableInteger) / 2 < desiredTotal) {
// Neither player can win.
return false;
}
int[] numbers = new int[maxChoosableInteger];
for (int i = 0; i < maxChoosableInteger; ++i) {
numbers[i] = i + 1;
}
return canWin(numbers, desiredTotal);
}
boolean canWin(int[] numbers, int desiredTotal) {
if (desiredTotal <= 0) {
return false;
}
for(int i = 0; i < numbers.length; ++i) {
int newTotal = desiredTotal - numbers[i];
if (!canWin(remove(numbers, i), newTotal)) {
return true;
}
}
return false;
}
int[] remove(int[] a, int k) {
int[] b = new int[a.length-1];
for (int i = 0, j = 0; i < a.length; i++) {
if (i != k) {
b[j++] = a[i];
}
}
return b;
}
My bad. I read the problem statement backwards. I thought the goal of the game was to NOT be the player to reach the desired total. I switched my code and tests around and now both your solution and my solution pass all tests except for 15,100 where mine returns true but yours returns false. I don't have time to analyze it further at the moment.
- gudujarlson September 30, 2014RahulK, I don't know which solution you are referring to, but mine returns 5 for input 1 0 0 1 1 0.
- gudujarlson September 30, 2014Your code does not work for the simple cases canIWin(1, 1) and canIWin(2, 1). It returns true, but the correct answer is false.
- gudujarlson September 30, 2014This is a special case of the maximum subarray problem. It can be solved in O(n) with a modified version of Kadane's algorithm where 0's are treated as 1 and 1's as -1.
public int maximumOnes(int a[]) {
int onesCount = 0;
int maxEndingHere = 0;
int maxSoFar = 0;
for (int i = 0; i < a.length; ++i) {
if (a[i] == 1) {
onesCount++;
}
maxEndingHere += a[i] == 1 ? -1 : 1;
if (maxEndingHere <= 0) {
maxEndingHere = 0;
}
else if (maxEndingHere > maxSoFar) {
maxSoFar = maxEndingHere;
}
}
return onesCount + maxSoFar;
}
On third thought I think the complexity of the memoized algo would be 2^n because it has to visit all subsets in the worse case.
- gudujarlson September 26, 2014Actually, I think the complexity is way less than that, maybe even n*log(n).
- gudujarlson September 25, 2014Yes, I think some simple memoization is possible. The brute force algo searches all permutations of the possible numbers, however some of these are redundant. For example, the permutation that starts with 1,2 will have the same result as a permutation that starts with 2,1. In both cases the next call to the canIWIn() function will have the same inputs and thus the same output. The complexity analysis requires some thought. My first impression is (n/2)!.
- gudujarlson September 25, 2014Quick note: my algorithm is based on the logic that I can always win with perfect play if my opponent can not always win with perfect play starting on the next move.
- gudujarlson September 25, 2014I think this can be solved with a simple recursive algorithm. A cursory analysis suggests that the upper bound on complexity is O(n!) where n is the max choosable integer.
boolean canIWin(int maxChoosableInteger, int desiredTotal) {
int[] numbers = new int[maxChoosableInteger];
for (int i = 0; i < maxChoosableInteger; ++i) {
numbers[i] = i + 1;
}
return canWin(numbers, desiredTotal);
}
boolean canWin(int[] numbers, int desiredTotal) {
for(int i = 0; i < numbers.length; ++i) {
int newTotal = desiredTotal - numbers[i];
if (newTotal > 0) {
if (!canWin(remove(numbers, i), newTotal)) {
return true;
}
}
}
return false;
}
int[] remove(int[] a, int k) {
int[] b = new int[a.length-1];
for (int i = 0, j = 0; i < a.length; i++) {
if (i != k) {
b[j++] = a[i];
}
}
return b;
}
Anonymous, I don't understand why you go through steps 2-5, because you have a minimum weight tree after step 1. Why create a 2nd tree? In any case, this is a O(n*log(n)) solution, but there is a O(n) solution. See my solution below.
- gudujarlson January 09, 2014There is no need to insert the sorted array into a binary tree as the sorted array is already the correct binary tree representation.
- gudujarlson September 10, 2013O(n) Solution
The straight forward way to solve this problem is to sort the array and then calculate the tree weight. This has a complexity of O(n*log(n)). However we don't need to fully sort the array to produce a minimum weight tree. There are many other orderings that work because the order within each level does not matter. So there should be a way to solve the problem faster than fully sorting the array and perhaps even a way with less complexity than O(n*log(n)). And guess what, there is.
The basic idea is to find the 1st, 3rd, 7th, 15th, ... (n/2-1)th largest values in the array and then partition the array about those values. To do that we partition the array around its (n/2-1)th largest value, then recursively partition the left side about its (n/2-1)th largest value until no more partitions are possible. We use the selection algo to do each partition, but in this case, we don't care about the normal output of the selection algo: the kth largest element. Rather we care about the side effect of what it does to the input array, i.e. partitioning the array about its (n/2-1)th largest value. The end effect of this partitioning is a binary tree with minimum weight.
The selection algo has an average complexity of O(n) and it will be run log(n) times, but each time it is run n shrinks by a factor of 2 (n + n/2 + n/4 + n/8 ... = 2n), thus the overall complexity is O(n). CAVEAT: the worst case performance remains O(n^2) and depends on the choice of pivots.
int findMinimumWeight(int a[]) {
optimize(a);
return calculateWeight(a);
}
int calculateWeight(int a[]) {
int weight = 0;
int level = 0;
int nextLevel = 1;
for (int i = 0; i < a.length; i++) {
if (i == nextLevel) {
++level;
nextLevel = (1 << level) - 1;
}
weight += a[i]*(level+1);
}
return weight;
}
int[] optimize(int a[]) {
iterations = 0;
for (int k = a.length; k > 1; k /= 2) {
selectLargest(a, 0, k-1, k / 2 + 1);
}
System.out.println("n= " + a.length + " iterations=" + iterations + " efficiency=" + ((float)iterations / a.length) + " log(n)=" + Math.log(a.length));
return a;
}
// Selects the kth largest value from the array.
// As a side effect, it partitions the array around the kth largest value.
// O(n)
int selectLargest(int a[], int i, int j, int k) {
//System.out.println(i + "," + j + "," + k);
++iterations;
if (i == j) {
return k == 1 ? a[i] : -1;
}
int pivot = a[i + (j - i) / 2];
int pivotIndex = partition(a, i, j, pivot);
int kprime = pivotIndex - i + 1;
if (kprime == k) {
return pivot;
}
if (kprime < k) {
return selectLargest(a, pivotIndex + 1, j, k - kprime);
}
else {
return selectLargest(a, i, pivotIndex - 1, k);
}
}
int partition(int a[], int i, int j, int pivot) {
int k = i;
while (k <= j) {
++iterations;
if (a[k] == pivot) {
++k;
}
else if (a[k] > pivot) {
swap(a, i, k);
++i;
++k;
}
else {
swap(a, k, j);
--j;
}
}
return k - 1;
}
void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
Here is an implementation in Java of Miguel Oliveira's ideas.
public class DivideArrayAverage2 {
// Hash map of sum -> subset
HashMap<Key, int[]> map;
// Input array
int a[];
// Indices of current subset while recursing.
int b[];
// Half the sum of a.
int halfSum;
// Half the length of a.
int halfLength;
// How many iterations the algo has run.
int iterations;
class Key {
public int s;
public int n;
@Override
public boolean equals(Object obj) {
Key key = (Key)obj;
return s == key.s && n == key.n;
}
@Override
public int hashCode() {
return (s * 33) ^ n;
}
}
// Returns a single array that is a reordering of the input array where the first half has the same average as the second half; if such an array exists.
//
// Reduce problem to finding the subset with n/2 elements that sums to sum(a)/2.
// This problem is the subset sum problem with a fixed size, so use standard way of solving subset sum problem.
// Divide the array into 2 halves A and B. Calculate the sum of every subset in A and store them in a hash map [sum -> subset].
// There are 2^(n/2) subsets of A and it requires O(n) to create each subset, so the this step is O(n*2^(n/2)).
// Iterate over every subset in B and see if there is a subset in A with the same sum and correct length.
// This step is O(2^(n/2)), so the overall complexity is O(n*2^(n/2)).
int[] divide(int a[]) {
// If there are an odd number of elements, there is no solution.
if (a.length % 2 != 0) {
return null;
}
// If the sum of the elements is odd, there is no solution.
int sum = 0;
for (int i = 0; i < a.length; ++i) {
sum += a[i];
}
if (sum % 2 != 0) {
System.out.println("divide: n=" + a.length + " iterations=1");
return null;
}
// Store some stuff in member variables to that we don't have to push it onto the stack each recursion step.
this.halfSum = sum / 2;
this.halfLength = a.length / 2;
this.iterations = 0;
this.a = a;
this.map = new HashMap<Key, int[]>();
this.b = new int[halfLength];
// Build a hash map of the sums of all subsets of the 2nd half of the input array.
populateHashMap(halfLength, 0, 0);
// Iterate over all subsets of the 1st half of the input array and look for appropriate subsets in the hash map/
int tuplet[] = findSubset(0, 0, 0);
System.out.println("divide: n=" + a.length + " iterations=" + iterations);
if (tuplet != null) {
// tuplet contains indices of the input array. Use that info to construct the output array.
return tupletToResult(tuplet, a);
}
return null;
}
// O(n*2^(n/2))
void populateHashMap(int i, int s, int n) {
++iterations;
if (i == a.length) {
if (n > 0) {
Key key = new Key();
key.s = s;
key.n = n;
int subset[] = new int[n];
System.arraycopy(b, 0, subset, 0, n);
map.put(key, subset);
iterations += n;
}
return;
}
populateHashMap(i + 1, s, n);
b[n] = i;
populateHashMap(i + 1, s + a[i], n + 1);
}
// O(2^(n/2))
int[] findSubset(int i, int s, int n) {
++iterations;
if (i == a.length / 2) {
if (s == halfSum && n == a.length / 2) {
int subset[] = new int[n];
System.arraycopy(b, 0, subset, 0, n);
return subset;
}
if (n > 0) {
Key key = new Key();
key.s = halfSum - s;
key.n = halfLength - n;
int c[] = map.get(key);
if (c != null) {
int subset[] = new int[a.length / 2];
System.arraycopy(b, 0, subset, 0, n);
System.arraycopy(c, 0, subset, n, c.length);
return subset;
}
}
return null;
}
int result[] = findSubset(i + 1, s, n);
if (result != null) {
return result;
}
b[n] = i;
return findSubset(i + 1, s + a[i], n + 1);
}
// Converts an array of indices of a into the output array.
static int [] tupletToResult(int tuplet[], int a[]) {
int half = a.length / 2;
boolean b[] = new boolean[a.length];
for (int i = 0; i < half; ++i) {
b[tuplet[i]] = true;
}
int result[] = new int[a.length];
for (int i = 0, j = 0, k = half; i < a.length; ++i) {
if (b[i]) {
result[j++] = a[i];
}
else {
result[k++] = a[i];
}
}
return result;
}
None of the posted solutions appear to solve the problem with all of the following constraints:
O(n) time
O(1) space
maintain original order of positive and negative sequences
And after studying the problem, I do not think it is possible to solve it and satisfy all these constraints. In any case, here are solutions where one of the constraints is relaxed.
public class PositiveNegativeSort {
// Use an auxiliary array. Maintain 2 pointers into input array. Copy elements from input array to aux array.
// Maintains original order of positive and negative sequences.
// O(n) time, O(n) space
int sort1(int a[]) {
int b[] = new int[a.length];
int pos = 0;
int neg = 0;
int iterations = 0;
for (int i = 0; i < a.length; ++i) {
++iterations;
if (i % 2 == 0) {
for (; pos < a.length && a[pos] < 0; ++pos, ++iterations);
if (pos < a.length) {
b[i] = a[pos++];
}
else {
b[i] = a[neg++];
}
}
else {
for (; neg < a.length && a[neg] >= 0; ++neg, ++iterations);
if (neg < a.length) {
b[i] = a[neg++];
}
else {
b[i] = a[pos++];
}
}
}
System.arraycopy(b, 0, a, 0, a.length);
iterations += a.length;
return iterations;
}
// Iterate over array and swap invalid elements with valid elements.
// Does NOT maintain original order of positive and negative sequences.
// O(n) time, O(1) space.
int sort2(int a[]) {
int iterations = 0;
int nextPositive = 0;
int nextNegative = 0;
for (int i = 0; i < a.length; ++i) {
++iterations;
for ( ; nextPositive < a.length && (nextPositive <= i || a[nextPositive] < 0); ++nextPositive, ++iterations);
for ( ; nextNegative < a.length && (nextNegative <= i || a[nextNegative] >= 0); ++nextNegative, ++iterations);
if (a[i] >= 0) {
if (i % 2 != 0 && nextNegative < a.length) {
swap(a, i, nextNegative);
}
}
else {
if (i % 2 == 0 && nextPositive < a.length) {
swap(a, i, nextPositive);
}
}
}
return iterations;
}
// Iterate over array and select correct element for each position. Shift subsequent elements right to maintain original order.
// Maintains original order of positive and negative sequences.
// O(n^2) time, O(1) space.
int sort3(int a[]) {
int iterations = 0;
int nextPositive = 0;
int nextNegative = 0;
for (int i = 0; i < a.length; ++i) {
++iterations;
for ( ; nextPositive < a.length && (nextPositive <= i || a[nextPositive] < 0); ++nextPositive, ++iterations);
for ( ; nextNegative < a.length && (nextNegative <= i || a[nextNegative] >= 0); ++nextNegative, ++iterations);
if (a[i] >= 0) {
if (i % 2 != 0 && nextNegative < a.length) {
a[i] = shift(a, i, nextNegative);
iterations += nextNegative - i;
}
}
else {
if (i % 2 == 0 && nextPositive < a.length) {
a[i] = shift(a, i, nextPositive);
iterations += nextPositive - i;
}
}
}
return iterations;
}
// O(1)
void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
// O(j-i)
int shift(int a[], int i, int j) {
int next = a[i];
for (; i < j; ++i) {
int tmp = a[i+1];
a[i+1] = next;
next = tmp;
}
return next;
}
@Test
public void testSort11() {
int[] a = {1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12};
int iterations = sort1(a);
System.out.println("sort11: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1,-2,3,-4,8,-5,9,-6,4,-7,10,11,12}, a);
}
@Test
public void testSort12() {
int[] a = {-1, -2, -3, -4, -5, -6, 1, -7 ,2, 3, 4, 5, 6, 7};
int iterations = sort1(a);
System.out.println("sort12: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7}, a);
}
@Test
public void test13() {
int a[] = new int[64];
for (int i = 0; i < a.length / 2; ++i) {
a[i] = -i - 1;
}
for (int i = a.length / 2; i < a.length; ++i) {
a[i] = i - a.length / 2 + 1;
}
int iterations = sort1(a);
System.out.println("sort13: iterations=" + iterations);
check(a);
}
@Test
public void testSort21() {
int[] a = {1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12};
int iterations = sort2(a);
System.out.println("sort21: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1, -2, 3, -4, 8, -6, 9, -5, 4, -7, 10, 11, 12}, a);
}
@Test
public void testSort22() {
int[] a = {-1, -2, -3, -4, -5, -6, 1, -7 ,2, 3, 4, 5, 6, 7};
int iterations = sort2(a);
System.out.println("sort22: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1, -2, 2, -4, 3, -6, 4, -7, 5, -5, 6, -3, 7, -1}, a);
}
@Test
public void testSort23() {
int[] a = {-1, 1, -2, 2, -3, 3, -4, 4 ,-5, 5, -6, 6, -7, 7};
int iterations = sort2(a);
System.out.println("sort24: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6, 7, -7}, a);
}
@Test
public void test24() {
int a[] = new int[64];
for (int i = 0; i < a.length / 2; ++i) {
a[i] = -i - 1;
}
for (int i = a.length / 2; i < a.length; ++i) {
a[i] = i - a.length / 2 + 1;
}
int iterations = sort2(a);
System.out.println("sort23: iterations=" + iterations);
check(a);
}
@Test
public void testSort31() {
int[] a = {1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12};
int iterations = sort3(a);
System.out.println("sort31: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1,-2,3,-4,8,-5,9,-6,4,-7,10,11,12}, a);
}
@Test
public void testSort32() {
int[] a = {-1, -2, -3, -4, -5, -6, 1, -7 ,2, 3, 4, 5, 6, 7};
int iterations = sort3(a);
System.out.println("sort32: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7}, a);
}
@Test
public void test33() {
int a[] = new int[64];
for (int i = 0; i < a.length / 2; ++i) {
a[i] = -i - 1;
}
for (int i = a.length / 2; i < a.length; ++i) {
a[i] = i - a.length / 2 + 1;
}
int iterations = sort3(a);
System.out.println("sort33: iterations=" + iterations);
check(a);
}
void check(int a[]) {
for (int i = 0; i < a.length; ++i) {
Assert.assertTrue((i % 2 == 0 && a[i] >= 0) || (i % 2 !=0 && a[i] < 0));
}
}
}
I'm confused by this solution. If I follow the solution correctly, it does not work for these simple inputs:
1,-1
1,2
Here is the implementation in Java with tests:
import org.junit.Assert;
import org.junit.Test;
public class Foo {
@Test
public void test2Positive() {
int a[] = new int[] {1,1};
Assert.assertTrue(divide(a));
}
@Test
public void test2Negative() {
int a[] = new int[] {1,-1};
Assert.assertTrue(divide(a));
}
@Test
public void test2Null() {
int a[] = {1,2};
Assert.assertNull(divide(a));
}
boolean divide(int arr[]) {
int sum = 0;
for (int i=0; i < arr.length ; i++) {
sum += arr[i];
}
boolean SumTbl[] = new boolean[1024*1024];
SumTbl[0] = true;
for (int i=0; i < arr.length; i++) {
for (int j = sum - arr[i]; j >= 0; j--) {
if (SumTbl[j] != false) {
SumTbl[j + arr[i]] = true;
}
}
}
return SumTbl[sum/2];
}
}
It's not entirely clear, but it sounds like your algo would require O(N) space. This problem is solvable in O(1) space and O(N) time as per Anonymous' comment and my post.
- gudujarlson May 02, 2013msankith, I posted working code. You can also check out the wikipedia article on the Dutch National Flag problem.
- gudujarlson May 02, 2013Since no one has actually posted code for it, here is a solution using a 2 color Dutch National Flag algorithm. O(N) time, O(1) space
public class YahooPartitionArray {
public static void main(String[] args) {
int a[] = new int[] {4,5,2,4,3,9,8,1};
partition(a, new SomeInterface() {
@Override
public int someFunction(int i) {
if (i % 2 == 0) {
return 1;
}
else {
return 0;
}
}
});
System.out.println(Arrays.toString(a));
}
interface SomeInterface {
public int someFunction(int i);
}
// Use Dutch National Flag algorithm with 2 colors.
//
// O(N) time, O(1) space
static void partition(int a[], SomeInterface s) {
int i = 0, j = a.length - 1;
while (i < j) {
int result = s.someFunction(a[i]);
if (result == 0) {
i++;
}
else {
swap(a, i, j--);
}
}
}
static void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
The complexity is not 3^0 + 3^1 + 3^2... + 3^n. See complexity analysis of naiveMaximumPath() below.
- gudujarlson May 02, 2013
sv, I think you are missing the part that says you can only swap adjacent elements.
- gudujarlson March 31, 2015