Will_In_Seattle
BAN USERI agree with Sathiya (except the white balls need to be included in the second bag as well).
- Will_In_Seattle January 24, 2013Can you provide the method's signature to perform this task? In what form is the integer provided?
- Will_In_Seattle January 24, 2013My program doesn't handle negative numbers? I haven't tried it out, but why wouldn't it? Also, where is the word "set" in the question? Intersection of data does not imply set.
- Will_In_Seattle January 23, 2013Nope, don't think you need it. I took it out. Thanks for catching it!
- Will_In_Seattle January 22, 2013If we were talking about sets with respect to their mathematical definition or the way that Java defines them, then I would say that discarding them is alright. However, since we are talking about data and the question doesn't specify to discard any data, then we should assume that the data is relevant and not discard it.
- Will_In_Seattle January 22, 2013nitingupta180's answer is close, but doesn't handle the scenario where there are duplicates. This answer is O(n) time complexity. The additional step required is to decrement the values in the hash table until they hit zero while checking the elements for existence (from the second array).
Here is the source for the complete answer as well as a test scenario:
public class Main {
public static ArrayList<Integer> findIntersection(ArrayList<Integer> s1, ArrayList<Integer> s2) {
Hashtable<Integer, Integer> hashTable = new Hashtable<Integer, Integer>();
ArrayList<Integer> intersection = new ArrayList<Integer>();
for(int i = 0; i < s1.size(); i++) {
if(s1.get(i) != null) {
if(hashTable.get(s1.get(i)) != null) {
hashTable.put(s1.get(i), hashTable.get(s1.get(i)) + 1);
} else {
hashTable.put(s1.get(i), 1);
}
}
}
for(int i = 0; i < s2.size(); i++) {
int s2Val = s2.get(i);
int value;
if(hashTable.get(s2Val) != null) {
value = hashTable.get(s2Val);
} else {
continue;
}
if(hashTable.get(s2Val)!= 0) {
hashTable.put(s2Val, value - 1);
intersection.add(s2Val);
}
}
return intersection;
}
public static void main(String[] args) {
//Test list and tree
ArrayList<Integer> a1 = new ArrayList<Integer>();
a1.add(1);
a1.add(1);
a1.add(1);
a1.add(4);
ArrayList<Integer> a2 = new ArrayList<Integer>();
a2.add(2);
a2.add(2);
a2.add(2);
a2.add(1);
a2.add(4);
ArrayList<Integer> a3 = findIntersection(a1, a2);
System.out.println(a3.toString());
}
This is a standard preorder traversal. Every node is visited exactly one time. When I say "visited", for this problem, I mean it is examined, the value of the path is calculated, and the currentMax is updated. This is, indeed, O(n) time complexity. If you're not convinced, drop my program in Eclipse and set a break at "int sumAtCurrentNode = n.getValue() + currentSum;". It will be hit n times.
- Will_In_Seattle January 20, 2013The time complexity is O(n), which is what I believe the interviewer was asking for. I don't think it is possible to store all possible combinations of LinkedLists to each node with storage space of O(n). Consider the case where every node is equal to zero.
- Will_In_Seattle January 20, 2013You're right. I specified at the end to be sure to store away the path to the node with the maxSum and to be prepared to store multiple paths. You'd just pass a linked list (with a getTail() method) as you went through the traversal along with the currentSum. And you would need a way to distinguish two nodes that had the same value, so you would want to make sure that each node had a unique identifier. Either that, or you could just store an array of directions like "Left Right Right".
- Will_In_Seattle January 19, 2013Every node in the tree has exactly one path. The trick here for best time complexity is to calculate the sum at each node as you're traversing. Preorder traversal seems like the best option. Here is a solution you can test out. This includes updates for all three of the requirements of the problem.
The time complexity of this algorithm is O(n). Required space will be equal to the size of the binary tree plus the size of each max path. The worst (and rare) case for space requirements would be if all nodes in the tree were equal to zero, as a linked list must be stored for every path.
public class Main {
public static class ListNode {
public int value;
public ListNode nextLink;
//Link constructor
public ListNode(int d1) {
value = d1;
}
//Print ListNodedata
public void printLink() {
System.out.print(value + " ");
}
}
public static class LinkedList {
private ListNode first;
//LinkedList constructor
public LinkedList() {
first = null;
}
//Returns true if list is empty
public boolean isEmpty() {
return first == null;
}
//Inserts a new ListNode at the first of the list
public void insert(int d1) {
ListNode link = new ListNode(d1);
link.nextLink = first;
first = link;
}
//Deletes the ListNode at the first of the list
public ListNode delete() {
ListNode temp = first;
first = first.nextLink;
return temp;
}
//Prints list data
public void printList() {
ListNode currentLink = first;
while(currentLink != null) {
if(currentLink.nextLink != null)
currentLink.printLink();
currentLink = currentLink.nextLink;
}
System.out.println("");
}
}
public static class TreeNode {
public TreeNode leftChild = null;
public TreeNode rightChild = null;
int mValue;
TreeNode(int v) {
mValue = v;
}
public int getValue() {
return mValue;
}
}
public static class BinaryTree {
public TreeNode root;
public int currentMax = 0;
public ArrayList<LinkedList> pathsToMax;
public BinaryTree(int rootValue) {
root = new TreeNode(rootValue);
/* Test case */
fillTestTree();
pathsToMax = new ArrayList<LinkedList>();
}
public void fillTestTree() {
root.leftChild = new TreeNode(4);
root.rightChild = new TreeNode(-1);
root.leftChild.leftChild = new TreeNode(1);
root.rightChild.leftChild = new TreeNode(5);
root.leftChild.rightChild = new TreeNode(0);
root.rightChild.rightChild = new TreeNode(6);
}
public LinkedList appendToNewList(LinkedList l, int value) {
LinkedList newList = new LinkedList();
ListNode currentLink = l.first;
while(currentLink != null) {
newList.insert(currentLink.value);
currentLink = currentLink.nextLink;
}
newList.insert(value);
return newList;
}
public void printPaths() {
System.out.println("Max paths are: ");
for(int i = 0; i < pathsToMax.size(); i++) {
pathsToMax.get(i).printList();
}
}
public void getMaxSum(TreeNode n, int currentSum, LinkedList l) {
//Visit current node
if(n == null) {
//throw...
}
int sumAtCurrentNode = n.getValue() + currentSum;
if(sumAtCurrentNode >= currentMax) {
if(sumAtCurrentNode > currentMax) {
pathsToMax = null;
pathsToMax = new ArrayList<LinkedList>();
}
currentMax = sumAtCurrentNode;
//Blow away our current set of paths due to the new max
pathsToMax.add(appendToNewList(l, n.getValue()));
}
//Traverse left
if(n.leftChild != null) {
getMaxSum(n.leftChild, sumAtCurrentNode, appendToNewList(l, n.leftChild.getValue()));
}
//Traverse right
if(n.rightChild != null) {
getMaxSum(n.rightChild, sumAtCurrentNode, appendToNewList(l, n.rightChild.getValue()));
}
}
}
public static void main(String[] args) {
//Test list and tree
BinaryTree btree = new BinaryTree(-1);
LinkedList l = new LinkedList();
btree.getMaxSum(btree.root, 0, btree.appendToNewList(l, -1));
btree.printPaths();
System.out.println("Max sum is: " + btree.currentMax);
}
}
Are we assuming no duplicates? Could you walk through an example of this, for instance, if A = {1,1,1, 2} and B = {1,1,1, 2}?
- Will_In_Seattle January 17, 2013It is synonymous with late binding and dynamic binding. Virtual binding enables polymorphism and allows for choosing the correct method at runtime. Note that this is NOT the same thing as method overloading where the method choice is determined statically at compile time.
- Will_In_Seattle January 10, 2013Thanks to Anonymous for pointing out at error in my my original and to S.Abakumoff for pointing out that the original algorithm requires at least one positive number. This solution addresses both comments:
Kadane's algorithm is the go-to solution for the maximum subarray problem. It is an iterative solution which runs in O(n) time. It finds largest subarray at each index i of array A, starting at index zero and iterates through the entire array. By using the knowledge of the previous largest subarray in combination with the knowledge that a previous subarray's sum can only be increased with a positive number at the next contiguous index, we can find the maximum contiguous subarray of A.
Consider the integer array A of size n where A contains at least one positive number (I'll handle the case where it doesn't at the end). To do this, we need to track 2 things: the current maximum subarray's sum and the maximum subarray which ends at index i. We’ll call them overallMax and maxEndingHere, respectively.
For each index, we set maxEndingHere equal to A[i] + the previous index's maxEndingHere. If it's not positive, we reset maxEndingHere equal to 0. Finally, we compare the value of maxEndingHere with overallMax and take the larger of the two numbers for our new overallMax. Note that in the actual algorithm, we would want to keep track of the current set of indices representing the overallMax. We would also make sure that array was not empty.
Here is a simple example: {6,-10,12}
overallMax =0
maxEndingHere=0
Start
A[0]:
maxEndingHere =Math.max(0, maxEndingHere + A[0]) =Math.max(0, 0 + 6)=6
overallMax=Math.max(overallMax, maxEndingHere)=Math.max(0,6)=6
A[1]:
maxEndingHere =Math.max(0, maxEndingHere + A[1]) =Math.max(0,6-10)=0
overallMax=Math.max(overallMax, maxEndingHere)=Math.max(0,6)=6
A[2]:
maxEndingHere=Math.max(0, 0 + A[2])=Math.max(0,12)=12
overallMax=Math.max(overallMax, maxEndingHere)=Math.max(6,12)=12
End
In the scenario where there are all negative numbers, I believe we could temporarily make all the numbers positive and use Math.min instead of Math.max to achieve the same result.. Then, at the end, we could return all the numbers to negatives and find the sum of the values given by our negative numbers between the indices of our max subarray.
Just double checked - my solution handles negative numbers. Thanks for your comments.
- Will_In_Seattle January 24, 2013