Sunny
BAN USERChecking things like sum, sum of powers, xor, plus length/min/max etc don't really work, not to mention proving it can be a pain. The only method I am aware of for positive integers is product of primes, where we would use the 1st prime to represent 1 and 2nd prime to represent 2 etc. But that certainly doesn't help us in this problem either.
- Sunny December 13, 2012"Swap" in this question means putting an element at the back of the array. It doesn't mean swap in the normal sense of swapping 2 elements. So for 8796 you simply need 3 swaps to put 7, 8 and 9 at the back of the array.
On the other hand, I don't know if buffalo's algorithm is right or not. If nothing else, the "j = 1 to n" certainly bothers me when i starts from 0...
Here's some code which hopefully is implementing his idea properly. The initial call should pass 0 for argument "start" and order.length for argument "to".
ArrayList<Node> trees(int[] order, int start, int to) {
ArrayList<Node> trees = new ArrayList<Node>();
if(start > to) {
trees.add(null);
return trees;
}
int len = order.length;
for(int i=start; i<=to; i++) {
ArrayList<Node> leftTrees = trees(order, start, i-1);
ArrayList<Node> rightTrees = trees(order, i+1, to);
for(Node left : leftTrees) {
for(Node right : rightTrees) {
Node parent = new Node(order[i]);
parent.left = left;
parent.right = right;
trees.add(parent);
}
}
}
return trees;
}
So are you saying first find the expected sums & xor of [min..max] and then see if they are the same as the subarray with the same min & max?
If so, consider {1 2 2 5 5 6}. I think it will produce the same sum & xor, assuming my program below works properly. Basically given a min & max, my program will try to generate a random array with numbers between min & max, then explicitly set the first element to min and last element to max. Then it computes their sum & xor and checks if it's unique.
I have seen others suggest computing sum of squares etc as well, which also don't work. Even if they do, trying to prove that it works will probably be very difficult during an interview.
static void test(int min, int max) {
int expectedSum = 0;
int expectedBits = 0;
for(int i=min; i<=max; i++) {
expectedSum += i;
expectedBits ^= i;
}
int diff = max-min;
int len = diff+1;
int arr[] = new int[len];
Random r = new Random();
while(true) {
for(int i=1; i<len-1; i++) {
arr[i] = r.nextInt(diff) + min;
}
arr[0] = min;
arr[arr.length-1] = max;
int sum = 0;
int bits = 0;
for(int i=0; i<len; i++) {
sum += arr[i];
bits ^= arr[i];
}
if(sum == expectedSum && bits == expectedBits) {
HashSet<Integer> set = new HashSet<Integer>();
for(int i : arr) {
set.add(i);
}
if(set.size() != len) {
for(int i : arr)
System.out.print(" " + i);
break;
}
}
}
}
1st approach (Greedy):
Consider array={1 99 100} and S=198. I think your code will return 99 while the optimal answer is 2. So basically greedy doesn't work.
2nd approach:
Consider array={2} and S=4.
table[1] will be Integer.MAX_VALUE and so when computing table[3] your 1+table[1] would result in overflow
Questions states that each row is sorted in descending order, so the matrix above should have been this instead:
10000
11000
11100
00000
11111
Having said that, we are asked to find the maximum number of 1s (unless the question was asking for 0s originally). So once we find the last 1 in the first row and start moving downwards, if we encounter another 1 again, why would you want to move left again? Shouldn't you move right instead?
Every once in a while I come across a comment that I just can't resist not responding to. What's so bad about these variable names?
(1) "a" for array
(2) "i" for index
(3) "sum" - self explanatory
(4) "l" for length
The "l" for length is the only one I had problem with, because it so resembles a 1. The "i" isn't so bad because it's a typical variable for iteration. The C/C++ camp just likes to use abbreviations while Java likes to spell the whole word out...
If the interviewer says you can assume the array has only 5 elements, I actually think this is a very legitimate solution. Why over-engineer? Who cares if it's O(2^n) vs O(n) when it's only 5 elements? If the interviewer cared so much about the time complexity, then he just shouldn't have said the array is 5 elements in the first place, which he probably will right after you offer this recursive version.
- Sunny December 11, 2012Someone gave an example below {-2 -3 -4 -5} where the max product should be the product of the smallest 3 numbers. I actually missed that case myself. So I think we also need to keep track of the 3rd smallest number and check if their product is greater than the current max.
- Sunny December 10, 2012If you already know the node's value is greater than the target value, then you shouldn't need to check the right subtree at all because they all will be farther from the target value than the node. Similarly for the opposite case.
This is true because the question says it's a binary search tree. If it were just a binary tree, then of course you have to check both subtrees as well.
This problem is probably different than the one you had in mind. Basically all the repeated characters will be contiguous already without sorting. Plus the sorting approach won't work if the problem is like (id=12514668) where "aabbbaaaa" => "a2b3a4" instead of "a6b3", which is what I suspect you are trying to do.
- Sunny December 10, 2012@Eugene, oh I certainly wasn't talking about you. I was referring to the first few Anonymous who simply said that the solution was wrong etc without showing how. That sort of comment isn't that valuable to the user nor to the rest of us, but perhaps they did it intentionally since the person who proposed the solution was rather sloppy himself.
Sorry about the confusion. I read many of your comments on this website before and know you usually have something better to say :)
I suspect the difference between this problem and the summation one is more than that. Consider {-1 2 3}. The output should be 6.
In the summation one, you can reset the current sum to 0 whenever it's negative. This problem seems harder because you can't do the same here due to input like {-2 -2}
I wish people who claim an idea or code is incorrect would either provide a counter-example or explain briefly what's wrong with it. Sure it helps by telling the person he's wrong, but it would help even more if you would be nice enough to help him understand what's wrong.
- Sunny December 09, 2012Not to mention sometimes the question is ambiguous intentionally in order for interviewer to evaluate how good the candidate is in clarifying or negotiating the requirements. Then on top of that the person who posted the question on this website probably forgot some of the requirements or couldn't express well enough with English.
- Sunny December 09, 20121. First duplicate the input array
2. Use the same approach as if you are solving the array version of this problem. That means iterate through the array and keep a running sum. Add this sum to current element and compare that to the current maximum. If sum < 0 then reset it to 0.
3. Avoid including an element in the running sum twice by keeping track of the starting index of the running sum, and subtracting the element at the starting index from the running sum if necessary.
int maxSum(int[] circle) {
int len = circle.length;
// duplicate the input "array"
int[] arr = new int[2*len];
System.arraycopy(circle, 0, arr, 0, len);
System.arraycopy(circle, 0, arr, len, len);
int max = Integer.MIN_VALUE;
int start = 0;
int curr = 0;
for(int i=0; i<2*len; i++) {
curr += arr[i];
if(i - start >= len) {
curr-=arr[start++];
}
if(curr > max) {
max = curr;
} else if(curr < 0){
curr = 0;
}
if(curr == 0)
start = i+1;
}
return max;
}
I think your comment is a good starting point in clarifying what we are supposed to do here. I find the question itself ambiguous. It doesn't specify whether we should find just 1 or all of the possible ways to add spaces to the input. It doesn't even really say each tokenized word needs to be present in the dictionary. Not to mention if there are multiple interpretations then how should we pick the best like you suggested.
Having said that, most people seem to assume that we are supposed to find just 1 interpretation such that each tokenized word must be in the dictionary.
Basically same approach as the top-rated one above, except hopefully cleaner:
(1) First, push all the elements from root to the left-most leaf node onto a stack. Do this for both trees
(2) Peek at the top element of each stack (if non-empty) and print the smaller one.
(3) Pop the element off the stack that contains the element we just print
(4) Add the right child of the element we just popped onto the stack, as well as all its left descendants
void printSorted(Node n, Node n2) {
Stack<Node> nodes = new Stack<Node>();
Stack<Node> nodes2 = new Stack<Node>();
insertNodes(n, nodes);
insertNodes(n2, nodes2);
while(!nodes.isEmpty() || !nodes2.isEmpty()) {
int a = (nodes.isEmpty() ? Integer.MAX_VALUE : nodes.peek().value);
int b = (nodes2.isEmpty() ? Integer.MAX_VALUE : nodes2.peek().value);
if(a < b) {
System.out.print(a);
insertNodes(nodes.pop().right, nodes);
} else {
System.out.print(b);
insertNodes(nodes2.pop().right, nodes2);
}
}
}
void insertNodes(Node n, Stack<Node> nodes) {
while(n != null) {
nodes.push(n);
n = n.left;
}
}
My Java version (even though it feels weird doing this in Java). Nothing fancy, just that I use Math.log10 instead of sprintf to figure out the count, and that rather than checking forward I check backwards for when to print.
void compress(char[] s) {
int i = 0;
int count = 0;
char prev = s[0];
for(char ch : s) {
if(ch == prev) {
count++;
} else {
s[i++] = prev;
if(count > 1) {
int numDigits = 1 + (int)Math.log10(count);
for(int j=numDigits-1; j>=0; j--) {
s[i+j] = (char)('0' + (count % 10));
count /= 10;
}
i+=numDigits;
}
count = 1;
}
prev = ch;
}
s[i] = '\n';
}
Was gonna post my Java version until I saw how compact your code is. Although the terse coding style might make it slightly harder to read, I think it's valuable when one has to write the solution on the whiteboard. Plus the interviewer will be so familiar with the solution that he should get it just by glancing at it.
- Sunny December 08, 2012I suspect you meant "...replace the min with the current element" at the end.
If so, here's a counter-example:
Input: 1 2 4 5 3
k=3
Sort: (1, 0) (2, 1) (3, 4) (4, 2) (5, 3)
We won't add (4, 2) or (5, 3) because the index is smaller than that of (3, 4).
If anyone thinks I misinterpreted the algorithm please let me know.
First of all, since the problem mentions sub-arrays, I think this isn't the same Balanced Partition problem that many have assumed it is. So it's actually much simpler and can be solved in O(n).
First, we iterate once to find the total. Then we iterate again, this time comparing the difference between the left and the right sub-arrays, and see if this difference is the smallest we have seen so far. At the end, we return the index associated with the minimum difference. The index is the index of the last element that we should include in the left sub-array.
int findEquilibrium(int[] arr) {
int total = 0;
for(int n : arr) {
total += n;
}
int min = Integer.MAX_VALUE;
int equilibrium = 0;
int left = 0;
int right = total;
for(int i=0; i<arr.length; i++) {
left += arr[i];
right -= arr[i];
int diff = Math.abs(left-right);
if(diff < min) {
equilibrium = i;
min = diff;
}
}
return equilibrium;
}
Here's a O(n) solution that's similar to some of those posted already, except I tried to address the following:
(1) When all numbers are negative, it should still work
(2) Return the list of numbers, rather than just the maximum itself
(3) Avoided using a separate array to do it the DP way
Algorithm is:
(1) Keep a running sum, call it curr
(2) Whenever it exceeds the current max, set max to it. Also set end to the current array index so we can reproduce the sequence from it
(3) If running sum is below 0, we will just reset it to 0 because there's no reason to add onto a negative running sum
static ArrayList<Integer> maxSequence(int[] arr) {
int max = arr[0];
int end = 0;
int curr = 0;
for(int i=0; i<arr.length; i++) {
curr += arr[i];
if(curr > max) {
max = curr;
end = i;
} else if(curr < 0) {
curr = 0;
}
}
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i=end; max!=0; i--) {
result.add(0, arr[i]);
max-=arr[i];
}
return result;
}
In that ideal case, if the array is size n, you can also just subtract (n+1)*(n+2)/2 from the total of the elements.
Example:
{1,3,5,7,9,2,4,6,10}
Here n=9 and the number 8 is missing. The sum of numbers from 1-10 is 10*11/2 = 55 and the total in this array is 47 so the result is 8 as expected.
Search for "young tableau" and look for a link with title "CSE 3358 Problem Set 5..." The solution to problem 1c describes this idea in more details and also gives pseudo-code
Having said that, the user who asked this question mentioned that the interviewer said you can't modify the matrix nor use heap etc, so maybe the interviewer has another algorithm in mind
After reading through a bunch of these "solutions", I realized there are 3 common mistakes people make. You might want to make sure that none of these applies to your solution before posting it.
(1) Order is important. In other words, you can't just check whether A & B form an anagram of C
(2) If the next character in A & B both match that of C, you can't just automatically advance the position in either A or B and move on. Consider A="ca" and B="cb". Your solution should return true for both C="cacb" and C="cbca".
(3) If the next character in A & B both match that of C, you can't just insert this character into a queue and try to use it up, then advance the position in both A & B. Consider A="ca", B="cb" and C="cabc". If you insert 'c' into the queue and advance the position in both A & B, you will be able to match the subsequent 'a' and 'b' incorrectly.
The first sentence says "...we can deduce that the next largest palindrome would be one with its central most digit incremented". I admit I haven't read the whole paragraph enough times, but I wonder whether that statement is true already given numbers like 23123, where the next palindrome should be 23132, where the middle digit (1) didn't need to be incremented.
- Sunny December 14, 2012