vairaghi
BAN USERclass Node
{
String string;
Node prefixNode; // this node represents a node which the value such that it is largetPrefix of string, which is a suffix of string[1...]
}
class trie
{
Node root;
public void processPrefixesForNodes()
{
//perform a BFS on the trie
if(node == first level nodes)
node.setPrefixNode = root;
else
{
Node parent = node.parent();
Node parent's prefixNode = parent.prefixNode()
for(Node candidatePrefixNode : parentsPrefixNode.children)
if(candidatePrefixNode.lastChar() = node.lastChar())
{
node.prefixNode = candidatePrefixNode;
break;
}
}
}
public List<SearchHit> search(String string, Trie trie)
{
int index = 0;
Node prefixNode = root;
List <SearchHit> hits = new ArrayList<SearchHit>();
while(index < string.length)
{
for(Node candidateNode:prefixNode.children)
{
if(candidateNode.lastChar() = string.charAt(index))
{
if(candidateNode == leafNode)
{
hits.add(new SearchHit(i - candidateNode.getString().length), candidateNode.getString()),
prefixNode = node.getPrefixNode();
}else
prefixNode = candidateNode;
break;
}
}
// no match in trie. look for a different node in trie.
prefixNode = node.getPrefixNode()
}
}
}
This is my solution
public List<Path> findPaths(int value)
{
List <Path> candidatePaths = findPaths(root, value);
List <Path> paths = new ArrayList<Path>();
for(Path candidatePath:candidatePaths)
{
if(candidatePath.isComplete())
paths.add(candidatePath);
}
return paths;
}
public List <Path> findPaths(Node node, int value)
{
// this returns completed paths of value or incomplete paths of lesser value
if(node == null)
return null;
List <Path> paths = new ArrayList<Path>();
List <Path> leftPaths = null;
List <Path> rightPaths = null;
Path thisPath = new Path(node);
if(node.getValue() == value)
thisPath.setCompleted(true);
paths.add(thisPath);
if(node.getLeft() != null)
{
leftPaths = findPaths(node.getLeft(), value);
}
if(node.getRight() != null)
{
rightPaths = findPaths(node.getRight(), value);
}
if(leftPaths != null)
{
for(Path path:leftPaths)
{
path = (Path)path.clone();
if(path.isComplete())
{
paths.add(path);
continue;
}
path.insertRight(node);
if(path.getCount() == value)
path.setCompleted(true);
paths.add(path);
}
}
if(rightPaths != null)
{
for(Path path:rightPaths)
{
path = (Path)path.clone();
if(path.isComplete())
{
paths.add(path);
continue;
}
path.insertLeft(node);
if(path.getCount() == value)
path.setCompleted(true);
paths.add(path);
}
}
if(leftPaths != null && rightPaths != null)
{
for(Path path:leftPaths)
{
if(path.isComplete() != true)
{
for(Path rightPath:rightPaths)
{
if(rightPath.isComplete() != true)
{
if(path.getCount() + node.getValue() + rightPath.getCount() == value)
{
Path newPath = (Path)path.clone();
newPath.insertRight(node);
newPath = newPath.mergeRight(rightPath);
newPath.setCompleted(true);
paths.add(newPath);
}
}
}
}
}
}
return paths;
}
class Path implements Cloneable
{
private List <Node> nodeList;
private int count = 0;
boolean completed = false;
public Path()
{
nodeList = new ArrayList<Node>();
}
public Path(Node node)
{
nodeList = new ArrayList<Node>();
nodeList.add(node);
count += node.getValue();
}
public boolean isComplete()
{
return completed;
}
public void setCompleted(boolean completed)
{
this.completed = completed;
}
public Node getLeftNode()
{
if(nodeList.size() > 0)
return nodeList.get(0);
else
return null;
}
public Node getRightNode()
{
if(nodeList.size() > 0)
return nodeList.get(nodeList.size() - 1);
else
return null;
}
public void insertLeft(Node node)
{
nodeList.add(0, node);
count += node.getValue();
}
public void insertRight(Node node)
{
nodeList.add(nodeList.size() - 1, node);
count += node.getValue();
}
public int getCount()
{
return this.count;
}
public Object clone()
{
Path clone = new Path();
clone.nodeList.addAll(this.nodeList);
//Collections.copy(clone.nodeList, this.nodeList);
clone.count = this.count;
clone.setCompleted(this.completed);
return clone;
}
public Path mergeRight(Path rightPath)
{
Path newPath = (Path)this.clone();
newPath.nodeList.addAll(rightPath.nodeList);
newPath.count += rightPath.getCount();
return newPath;
}
}
It was a phone interview. i proposed using a hash table with the priority as the key and each cell storing a queue of nodes. I could not solve the dequeue part in O(1) time. The interviewer mentioned that i was almost there. i havent figured out the answer though.
- vairaghi December 12, 2007
Repkylieblindner, abc at ASAPInfosystemsPvtLtd
Hello, I am Kylie. I am working in a store as Supply chain managers promote the design, development, and implementation ...
Rep
couple of observations. the numbers which contribute zeros are powers of 2 and powers of 5. say n > 125 then n! = 1.2..4.5....8...25...125..... n. every multiple of 5. has atleast one preciding multiple of 2, every multiple of 25 (5 ^ 2), has a preciding multiple of 4(2 ^ 2).. and so on. So all an multiple of 5, and not of higher powers of 5, will contribute one zero (2 * 5), multiple of 25 will contribute 2 (4 * 25 = 100),multiple of 125 will contribute 3, (125 * 8 = 1000) and so on.
so every multiple of 5, contributes a zero, every multiple of 25 will contribute one more(in addition to the the 5 contributed), 125 will contribute one more (in addition to 5 and 25s).
so the code for this would be
- vairaghi February 23, 2008