Nick N.
BAN USERIn preorder, parent node is visited before child node. The solution is to traverse the list left to right. Maintain the stack of traversed nodes, if a current node.parent is not equal to stack.peek(), pop the stack until found or stack is empty. If found. add current node. if stack is empty, meaning the current node.parent haven't visited, return false.
Below is the code snippet:
public boolean isPreorderedList(List<Tree.Node<Integer>> inList) {
Stack<String> parents = new Stack<String>();
for (Tree.Node<Integer> aNode : inList) {
// Add root node
if (aNode.getParentId() == null) {
parents.push(aNode.id());
continue;
}
while (!parents.isEmpty()) {
if (aNode.getParentId().equals(parents.peek())) {
parents.push(aNode.id());
break;
}
else {
parents.pop();
}
}
if (parents.isEmpty()) {
return false;
}
}
return true;
}
The solution is to customize the original BST search by:
Finding the diff when traversing the tree, if the new diff is less than the current min diff, update the return elements and min diff = new diff.
Below is the code snippet:
public Set<String> findNearest(Tree<Integer> tree, int num) {
int minDiff = Integer.MAX_VALUE;
Set<String> retVals = new HashSet<String>();
Tree.Node<Integer> curNode = tree.getRoot();
while (curNode != null) {
if (curNode.getVal() == num) {
retVals.clear();
retVals.add(curNode.id());
break;
}
else {
Tree.Node<Integer> nextNode = curNode.getVal() > num ? curNode.left() : curNode.right();
Set<String> curVals = new HashSet<String>();
if (nextNode != null) {
int curDiff = findNearestSub(curNode, nextNode, num, curVals);
if (curDiff <= minDiff) {
minDiff = curDiff;
retVals = curVals;
}
}
curNode = nextNode;
}
}
return retVals;
}
public int findNearestSub(Tree.Node<Integer> n1, Tree.Node<Integer> n2, int num, Set<String> retVals) {
int diff1 = Math.abs(n1.getVal() - num);
int diff2 = Math.abs(n2.getVal() - num);
if (diff1 > diff2) {
retVals.add(n2.id());
}
else if (diff1 < diff2) {
retVals.add(n1.id());
}
else {
retVals.add(n2.id());
retVals.add(n1.id());
}
return Math.min(diff1, diff2);
}
O(n) operation.
The soluton is not different from folks commented above. We will implement a sliding window. The window contains all required words, and start sliding from 0 to end of string.
public int findMinParagraph(String doc, Set<String> reqWords) {
int ii =0, jj=0;
int wcount = 0;
String curW = null;
int minLen = Integer.MAX_VALUE;
char[] docChars = doc.toCharArray();
Set<String> reqSet = new HashSet<String>(reqWords);
Map<String, Integer> countMap = new HashMap<String, Integer>();
for (String ww : reqWords) {
countMap.put(ww, 0);
}
for (jj = 0; jj < doc.length(); jj++) {
if (!reqSet.isEmpty()) {
curW = getWord(docChars, jj);
if (curW == null) {
continue;
}
// not null from here
if (reqSet.contains(curW)) {
reqSet.remove(curW);
}
if (countMap.containsKey(curW)) {
countMap.put(curW, countMap.get(curW) + 1);
}
wcount++;
}
jj = jj + curW.length();
if (reqSet.isEmpty()) {
for (; ii < doc.length() && ii <= jj; ii++) {
curW = getWord(docChars, ii);
if (curW == null) {
continue;
}
if (!countMap.containsKey(curW)) {
wcount--;
}
else {
int curCount = countMap.get(curW);
countMap.put(curW, --curCount);
if (curCount > 0) {
wcount--;
}
else {
// add this back for next walk
reqSet.add(curW);
break;
}
}
ii = ii + curW.length();
}
// found the lower bound
minLen = Math.min(minLen, wcount);
// move up ii for next walk
ii = ii + curW.length();
wcount--;
}
}
return minLen;
}
public String getWord(char[] docChars,int startIdx) {
StringBuffer buf = new StringBuffer();
while (startIdx < docChars.length) {
if ((docChars[startIdx] >= 'a' && docChars[startIdx] <= 'z') ||
(docChars[startIdx] >= 'A' && docChars[startIdx] <= 'Z')) {
buf.append(docChars[startIdx]);
}
else {
break;
}
startIdx++;
}
return (buf.length() == 0) ? null : buf.toString();
}
Find all substrings, find them in dictionary, if found, add to return list.
- Nick N. January 31, 2018