Sunny
BAN USERMy idea (like almost everyone else) is to merge the 2 sorted lists. During each iteration, we either advance the first or second list's pointer. Specifically, there are 4 cases. Define "first value" as the value of first list's current node, and similarly for "second value".
(1) Second list is empty: copy all elements in remaining first list
(2) First value < second value: copy first list's current node and advance its pointer
(3) First value > second value: advance second list's pointer
(4) First value == second value: advance first list's pointer. Do not advance second list's pointer because there might be duplicates.
At the end, return the third list.
/*
class Node {
int value;
Node next;
}
*/
Node subtract(Node first, Node second) {
Node head = new Node(-1); // dummy head
Node third = head;
while(first != null) {
if(second == null || first.value < second.value) {
third.next = new Node(first.value);
third = third.next;
first = first.next;
} else if(first.value > second.value) {
second = second.next;
} else {
first = first.next;
}
}
return head.next;
}
I agree that this hashmap approach isn't taking advantage of the lists being sorted, and while it works, might not impress the interviewer too much. On the other hand, I don't understand why we cannot use DataStructure libraries or Java API calls? If the question asks to reverse a string, then sure you can't get away with StringBuilder's reverse() method. But if the question requires hashing or sorting, I don't think we are supposed to implement all those DS from scratch either.
- Sunny December 22, 2012Intuitively this doesn't seem correct, because in this case if a>b, and b>c, it's not necessarily true that a>c, yet quicksort (or any sort) will build on the assumption that ">" is transitive.
I couldn't come up have a counter-example yet. I did write the following code to help generate all possible arrangements between 5 players and report which of them is valid. Initialize the won[i][j] matrix if you want player i to win player j.
import java.util.*;
class Test {
static boolean won[][] = new boolean[5][5];
static void printValid(int[] arr, int p, boolean[] used) {
if(p>=arr.length) {
System.out.println();
for(int i : arr)
System.out.print((char)(i+'a'));
for(int i=1; i<=3; i++) {
if(invalid(arr[i-1], arr[i]) || invalid(arr[i], arr[i+1]))
return;
}
System.out.print(" -> VALID");
} else {
for(int i=0; i<5; i++) {
if(used[i])
continue;
arr[p] = i;
used[i] = true;
printValid(arr, p+1, used);
used[i] = false;
}
}
}
static boolean invalid(int prev, int curr) {
return (prev == curr || won[curr][prev]);
}
public static void main(String[] args) {
// set won[i][j] if you want player #i to win player #j
printValid(new int[5], 0, new boolean[5]);
}
}
How come no one mentioned the "negate" approach? For each a[i], which we know is between 1 and n, check if a[a[i]] is negative. If not, set it to negative to indicate that we just seen a[i]. If it is negative, we know a[i] is a repeated number. Use a separate array to keep the m repeated elements, hence the O(m) space constraint. At the end, traverse the array and undo the negations to restore the array.
- Sunny December 22, 2012The prime factors of each number in the sequence should be either 3, 5 or 7. So 6 and 14 etc shouldn't be in the sequence, because their prime factors include 2. I think the original sequence proposed in this post is correct (except for the initial 0):
3, 5, 7, 9, 15, 21, 25, 27, 35,
Took me a while to understand the solution. First of all, note that we have to preserve the relative order of the positive & negative numbers. Here's my understanding of the solution. Use a "posStartIndex" to mark the index of the first zero. As you traverse the array, if you encounter a number <= 0, then we want to inject it at the "posStartIndex". To do so, of course we need to first copy each element after the "posStartIndex" one to the right. Finally, if the number we are injecting is < 0, then we increment the "posStartIndex".
Several notes if my understanding is correct:
(1) posStartIndex throws me off because it sounds like the index of the first positive number, which zero isn't
(2) I think checking "A[i] < 0" at the end is a bug because by then A[i] isn't the number we are injecting anymore. Should use "temp" instead.
Given (1) & (2), I am not sure whether I understand his algorithm correctly.
Since most solutions here are so long I will try to post a shorter one:
// assuming arrays are the same length
static boolean allow(int[] code, int[] input) {
int len = code.length;
boolean seenError = false;
for(int i=0; i<len; i++) {
if(input[i] == code[i])
continue;
if(!similar(input[i], code[i]) || seenError)
return false;
else seenError = true;
}
return true;
}
static boolean similar(int i, int j) {
i--;
j--;
int ci = (i%3);
int ri = (i/3);
int cj = (j%3);
int rj = (j/3);
return (Math.abs(ci-cj) <= 1 || Math.abs(ri-rj) <= 1);
}
My implementation of this idea. The code is fairly long even when I am assuming there are no duplicates :(
class Element implements Comparable<Element> {
int value;
int position;
public Element(int _value, int _position) {
value = _value;
position = _position;
}
public int compareTo(Element e2) {
return value - e2.value;
}
}
class ElementComparator implements Comparator<Element> {
public int compare(Element e, Element e2) {
return e.position - e2.position;
}
}
class ConsecutiveGroups {
// O(n) solution probably exists, but is troublesome
// instead, we will simply sort the numbers (along with their indices)
// identify the consecutive groups from the sorted list, and sort each
// group again by their indices
static ArrayList<ArrayList<Element>> group(int[] arr) {
int len = arr.length;
Element[] elements = new Element[len];
for(int i=0; i<len; i++) {
elements[i] = new Element(arr[i], i);
}
Arrays.sort(elements);
ArrayList<ArrayList<Element>> groups = new ArrayList<ArrayList<Element>>();
ArrayList<Element> group = new ArrayList<Element>();
for(int i=0; i<len; i++) {
Element element = elements[i];
if(i>0 && element.value != elements[i-1].value + 1) {
groups.add(group);
group = new ArrayList<Element>();
}
group.add(element);
}
groups.add(group);
for(ArrayList<Element> aGroup : groups) {
Collections.sort(aGroup, new ElementComparator());
}
return groups;
}
public static void main(String[] args) {
ArrayList<ArrayList<Element>> groups = group(new int[]{8,2,4,7,1,0,3,6});
for(ArrayList<Element> group : groups) {
for(Element element : group)
System.out.print(" " + element.value);
System.out.println();
}
}
}
The original order can be preserved because after first sorting the numbers, we can sort each group of consecutive numbers by their indices again.
After sorting, you can divide the consecutive numbers into groups by simply noting which element isn't followed by element+1. However, this solution didn't address the case when there are duplicates, which is the tricky part. For instance, given "789123789", the sorted list is "123778899", and you now have 2 groups of "789"...
It's because they (including me) are assuming that the method can't return anything. In that case, if the method signature is something like "void flip(Node head)", I don't think you can flip the nodes with the head pointer referencing the new head of the list. Like if head is "a", then you can flip the "a" and "b" etc, but head will still point at "a", leaving "b" inaccessible.
Then I realized we can always make the method return the new head of the list instead...
I think this might create dangling pointers. For instance, after swapping the first 2 nodes ("a" and "b"), the original head pointer now points at "a", but it won't be able to access the "b" in front anymore. Similarly, after the first recursive call, we have swapped "c" and "d", but now the no one is pointing at "d".
I didn't actually test the code, so sorry if my logic turns out incorrect.
I don't think you can do it with just 3 pointers to the tails. Consider {0, 0, 0, 2, 2, 2, 1}. After traversing through the 0s & 2s, p0 & p2 will point to the last 0 and 2, respectively. So how can you point 1 to the first 2? That's why you also need pointers to the heads.
Nice graphics & explanations though :)
I think every solution here will be O(n), so that's not the differentiating factor here. For this problem, I think solutions will be evaluated based on how much memory it uses, how many passes it requires, whether the list can be modified in-place, and just to be picky, whether the original order can be preserved.
- Sunny December 20, 2012If you are implementing his idea word for word then it won't work. Consider {5,7,6,8} and {5,7,8,6}. The sequence of numbers larger than the root are different, yet the trees are identical. As someone pointed out in another comment, you can't just compare with the root...
- Sunny December 20, 2012{3, 1, 6} and {3, 6, 1} would yield the same trees. Both have 3 as the root and 1 and 6 as its children.
On the other hand, {3, 1, 6, 2} and {3, 6, 2, 1} would yield different trees. In the first one, 1 and 6 are children of 3, while 2 is right child of 1. In the second one, 6 and 2 are children of 3, while 1 is left child of 2.
My idea is same as everyone else:
(1) Find the position of the maximum with modified binary search. Call this the "climax".
(2) Perform binary search from beginning to climax
(3) Perform binary search from climax to end
Each is O(logn) so altogether still O(logn). Note that I am also accommodating for the case when the climax is at the beginning or end of the array.
static int search(int[] arr, int n) {
int climax = findMax(arr);
int p = binarySearch(arr, n, 0, climax);
if(p >= 0)
return p;
else return binarySearch(arr, n, climax, arr.length-1);
}
static int findMax(int[] arr) {
int start = 0;
int end = arr.length-1;
while(start <= end) {
int middle = (start+end)/2;
boolean gtLeft = (middle == 0 || arr[middle] > arr[middle-1]);
boolean gtRight = (middle == arr.length-1 || arr[middle] > arr[middle+1]);
if(gtLeft && gtRight)
return middle;
if(gtLeft && !gtRight) {
// ascending
start = middle+1;
} else {
// descending
end = middle-1;
}
}
// shouldn't happen
return -1;
}
static int binarySearch(int[] arr, int n, int start, int end) {
boolean ascending = (start == 0);
while(start<=end) {
int middle = (start+end)/2;
if(arr[middle] == n)
return middle;
if(ascending) {
if(arr[middle] < n)
start = middle+1;
else end = middle-1;
} else {
if(arr[middle] < n)
end = middle-1;
else start = middle+1;
}
}
return -1;
}
I used a similar approach, except I cheated a little by storing the node values instead. That way I don't have to modify the pointers at all and can just update the values of the even nodes. I also used a FIFO queue instead of a LIFO stack.
void reverse(Node n, boolean even, ArrayDeque<Integer> queue) {
if(n == null) {
return;
} else if(even) {
queue.addFirst(n.value);
reverse(n.next, false, queue);
n.value = queue.removeLast();
} else {
reverse(n.next, true, queue);
}
}
Actually I am not really sure if we are supposed to sort the list, or always return the list with the order of the even nodes reversed. The example given is ambiguous, but I suspect it's the latter, otherwise the question doesn't need to explicitly assume that the even nodes are in decreasing order.
- Sunny December 20, 2012It's sad that I actually have to read your solution to understand what the question is asking about. Sounds like it should be "closest greater element" instead of "closest greatest element".
Anyways, sounds like you don't really need the max variable here. You can just pop until the top element is greater than A[i].
I have to say I was entertained by all those abs(whatever - 0) statements... I guess they either increase readability or optimize performance. Having said that, I did doubt for a while whether (anything - 0) is always equal to anything, which I think still holds.
- Sunny December 19, 2012Here's my tail recursive version, which doesn't require first finding the lengths, first reversing, converting the lists to numbers, or using additional data structures such as Stack etc. It won't handle the case of overflow, so I might be solving an easier version of this problem.
The approach is to use 2 additional parameters (num & num2) to keep track of the current values we have seen for both lists. Code should be self-explanatory enough...
static int sum(Node n, Node n2, int num, int num2) {
if(n == null && n2 == null)
return num+num2;
else if(n == null)
return sum(null, n2.next, num, 10*num2 + n2.value);
else if(n2 == null)
return sum(n.next, null, 10*num + n.value, num2);
else return sum(n.next, n2.next, 10*num + n.value, 10*num2 + n2.value);
}
No one seems to have suggested the bottom-up approach of constructing a list of possible numbers until we either reach or exceed n. The list is {0} initially and gradually grows, such as {0, 6, 9, 12, 18, 20, 24, 27...}. In each iteration, we use 3 different indices to keep track of the numbers in the list to which we should add 6, 9 and 20 to. We then add their minimum to the list, and increment the relevant indices. We need to make sure we don't add numbers that are already in the list by checking that this minimum is actually greater than the maximum of the list.
static boolean possible2(int n) {
ArrayList<Integer> numbers = new ArrayList<Integer>();
numbers.add(0);
int p6 = 0;
int p9 = 0;
int p20 = 0;
// compiler complains if we use while(true) here
for(int i=0; i<n; i++) {
int a = numbers.get(p6) + 6;
int b = numbers.get(p9) + 9;
int c = numbers.get(p20) + 20;
int min = min3(a, b, c);
if(min == n)
return true;
if(min > n)
return false;
if(min > numbers.get(numbers.size()-1))
numbers.add(min);
if(a == min)
p6++;
if(b == min)
p9++;
if(c == min)
p20++;
}
return false;
}
static int min3(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
My Java version leverages the PriorityQueue and the natural ordering of Strings:
String largest(int[] arr) {
PriorityQueue<String> heap = new PriorityQueue<String>();
for(int i : arr) {
heap.add("" + i);
}
String longest = "";
while(!heap.isEmpty()) {
longest = heap.poll() + longest;
}
return longest;
}
This problem is similar to the one where you have to compute an arithmetic expression, where the operator (+) is always in the front and the 2 single-digit operands are always behind the operator. In other words, the whole expression is composed of "+DD", such as "+12", "+1+23" and "++12+3+45".
There are 2 ways to solve this, one by recursion and the other by using the same reverse+stack approach here. I like that other question better, because in this one it's unclear how to rebuild the binary tree with just L & N but without the actual values.
So what's the answer, assuming the question is asking about the number of different ways to form a sum < 10000 (eg. 1+3+4 and 1+2+5 are two different ways)? I had a hard time with the DP recurrence and initial conditions so I am not sure whether my answer (5841289763241281300) is right or not....
- Sunny December 17, 2012Like most of the other code, I am using tail recursion. When numDigits is 0, I will just print what I have so far in the "curr" argument. Otherwise I will construct the new "curr" argument by multiplying it by 10 and adding the next digit to it. My only "innovation" is the use of the ones-digit to determine the minimum digit I should start iterating from.
static void printAll(int numDigits, int curr) {
if(numDigits == 0) {
System.out.println(curr);
return;
}
int min = 1 + (curr > 0 ? curr%10 : 0);
for(int d=min; d<=9; d++) {
printAll(numDigits-1, curr*10 + d);
}
}
I struggled with understanding the topological sort approach, so was very happy to come across this simpler one. Seems to work for the cases I can think of, so thanks a lot.
Now that I know how to solve this, I can go back and try to understand the topological sort approach again.
I think you need to accomodate for the odd & even cases differently. I tried implementing this, and would stop inserting into the stack as soon as the faster pointer is null (even) or that its "next" is null (odd). In the even case, since the slow pointer is already pointing past the mid-point, I would need to immediately check it against the top element of the stack. Details might vary based on your implementation though but the idea works.
Having said that, I think this solution is good since it's only 1-pass. But if we are allowed to use so much memory then I might as well traverse the whole list to create a string then work off the string instead.
Since we are merely negating some elements, we can always save the duplicate once we find it, then restore the array by setting each element to its absolute value, and finally returning the duplicate. Hopefully no one will argue that we can't save the answer because we aren't even allowed to use O(1) space.
- Sunny December 16, 2012
It's rather inefficient if we have to consider all possible windows. For instance, suppose K=3 and we have the following occurrences:
- Sunny December 23, 2012{1}
{2}
{3, 4, 5, 6, 7}
If we hold the occurrence of the first two words constant (ie. 1 & 2), we shouldn't have to consider all those 4,5,6,7 once we have considered 3 for the last word...