johndifini
BAN USER- 0of 0 votes
AnswersGiven a binary tree & the following TreeNode definition, return all root-to-leaf paths.
Definition of TreeNode:public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = this.right = null; } }
EXAMPLE
Given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: [ "1->2->5", "1->3" ]
From Lint Code - http://www.lintcode.com/en/problem/binary-tree-paths/
- johndifini in United States| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm
Well done, Lucas! For those who would like an explanation of the logic, here's an example:
0 1 2 3 4 5
{-4, -1, -1, 0, 1, 2}
i=0/-4
leftIdx=1/-1 (always start w/ the least # that we haven't checked yet (ie i+1))
rightIdx=5/2 (always start w/ the greatest # (ie index 5))
sum=-3 (we need to increase the sum, so we need to increase the least # (ie increment leftIdx))
i=0/-4 (no change)
leftIdx=2/-1
rightIdx=5/2 (no change)
sum=-3 (we need to increase the sum, so we need to increase the least # (ie increment leftIdx))
i=0/-4 (no change)
leftIdx=3/0
rightIdx=5/2 (no change)
sum=-2
i=0/-4 (no change)
leftIdx=4/1
rightIdx=5/2 (no change)
sum=-1 (exhausted all possibilities with 0/-4 (ie increment i))
i=1/-1
leftIdx=2/-1 (always start w/ the least # that we haven't checked yet (ie i+1))
rightIdx=5/2 (always start w/ the greatest # (ie index 5))
sum=0 (BINGO! We are done with 1/-1 b/c if we increment leftIdx,
we incr. the sum & if we decrement rightIdx, we decr. the sum)
i=2/-1
leftIdx=3/0 (always start w/ the least # that we haven't checked yet (ie i+1))
rightIdx=5/2 (always start w/ the greatest # (ie index 5))
sum=1 (we need to decrease the sum, so we need to decrease the greatest # (ie decrement rightIdx))
i=2/-1 (no change)
leftIdx=3/0 (no change)
rightIdx=4/1
sum=0 (BINGO! (see prev. BINGO explanation))
i=3/0
leftIdx=4/1 (always start w/ the least # that we haven't checked yet (ie i+1))
rightIdx=5/2 (always start w/ the greatest # (ie index 5))
sum=3 (DONE! We exhausted all possibilities)
Here's an opportunistic approach. If the arrays don't have any overlap, then the algo will have looped through each array just once. View the complete solution with comments, considerations, and test cases here - https://github.com/johndifini/javaAlgos/blob/master/ArrayIntersector.java
public static List<Integer> findIntersection(ArrayList<Integer> a, ArrayList<Integer> b) {
// @todo Validate input (e.g. check for null & empty)
// Data Structure Choice:
// Since the results must be unique, let's use a Set.
// In addition, let's use an ordered Set (TreeSet) so that we can short
// circuit the searching if we find that the lists don't overlap.
TreeSet<Integer> setA = new TreeSet<Integer>(a);
TreeSet<Integer> setB = new TreeSet<Integer>(b);
// Since we already got rid of dupes by using a set,
// we can use a List for the results.
// Note: We can't assume a minimum size for initialization?
List<Integer> result = new ArrayList<Integer>();
// If the "highest" of one set is less than the "lowest" of the other,
// nothing to do (i.e. no overlap)
// e.g. a=[1,2,3]; b=[4,5] or a=[11,22,33]; b=[1,1,1]
if(setA.last() < setB.first() || setB.last() < setA.first()) {
System.out.println("nothing for us to do");
return result;
}
// For each elem in the smaller Set, check if it exists in the other set
if(setA.size() < setB.size()) {
for(int elem : setA) {
if(setB.contains(elem)) {
result.add(elem);
}
}
}
else {
for(int elem : setB) {
if(setA.contains(elem)) {
result.add(elem);
}
}
}
return result;
}
Here's what I came up with. View the complete solution with comments, considerations, and test cases here - https://github.com/johndifini/javaAlgos/blob/master/Stripper.java
/**
* Naming Convention - ExocticEngineer was too long for a class name :-)
*/
public class Stripper {
/**
* By putting the unique lines into fixed-sized chunks, this approach
* will use significantly less mem if the file contains a lot of dupes.
* If the file doesn't contain any dupes, we'll waste some processing time.
*/
public static void removeDupes(String filename, int chunkSize) throws IOException {
//@todo Validate user input. Filename can't be null; Chunk size has to be >=1
// Note - BufferedReader is NOT loading the entire file into mem
BufferedReader reader = new BufferedReader(new FileReader(filename));
Set<String> uniqueLines = new HashSet<String>(chunkSize);
List<Set<String>> chunks = new ArrayList<Set<String>>();
String line;
while((line = reader.readLine()) != null) {
uniqueLines.add(line);
if(uniqueLines.size() == chunkSize) {
// Save a copy of the lines using copy constructor
chunks.add(new HashSet<String>(uniqueLines));
uniqueLines.clear();
}
}
reader.close();
// If size of uniqueLines is not equal to chunkSize, we haven't saved it yet
if(uniqueLines.size() != chunkSize) {
chunks.add(new HashSet<String>(uniqueLines));
uniqueLines.clear();
}
// Although the final list could be smaller than chunkSize,
// it's a good approximation of the minimum size of the final set
Set<String> consolidated = new HashSet<String>(chunkSize);
for(Set<String> buff : chunks) {
consolidated.addAll(buff);
}
for(String congo : consolidated) {
System.out.println("<"+congo+">");
}
}
}
Here's what I came up with. View the complete solution with comments, considerations, and test cases here - https://github.com/johndifini/javaAlgos/blob/master/BinaryTreePaths.java
public class BinaryTreePaths {
private Deque<String> deque = new ArrayDeque<String>();
private List<String> result = new ArrayList<String>();
/**
* @param root the root of the binary tree
* @return all root-to-leaf paths
*/
public List<String> binaryTreePaths(TreeNode root) {
// Write your code here
if(root == null) return result;
deque.add(Integer.toString(root.val));
// If we reached the end of a leaf, save it to the results
if(root.left == null && root.right == null) {
// @todo Verify requirement of "->" as the delimiter. Can it be ", " instead?
String joined = String.join("->", deque);
result.add(joined);
}
else {
if(root.left != null) {
binaryTreePaths(root.left);
}
if(root.right != null) {
binaryTreePaths(root.right);
}
}
// We are done processing this node, so crawl back up the tree
deque.removeLast();
return result;
}
/**
* Clear the results to reuse a BinaryTreePaths instance
*
* @todo What if the caller forgets to call clear before he calls binaryTreePaths again? Can we make this class more foolproof?
*/
public void clear() {
result.clear();
}
}
Nice use of a level-order traversal. From Wikipedia, here is helpful pseudocode for level-order traversal:
- johndifini November 06, 2016