maksim.a.dmitriev
BAN USERThis is my implementation in Java
Node
package algo.printtree;
public class Node {
int mData;
Node mLeft;
Node mRight;
public Node(int data) {
mData = data;
}
public void setLeft(Node left) {
mLeft = left;
}
public void setRight(Node right) {
mRight = right;
}
@Override
public String toString() {
return Integer.toString(mData);
}
@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (!(obj instanceof Node)) {
return false;
}
Node other = (Node) obj;
return mData == other.mData;
}
@Override
public int hashCode() {
int result = 17;
result = 31 * result + mData;
return result;
}
}
BST
package algo.printtree;
import java.util.LinkedList;
public class BST {
private final Node mRoot;
public BST(int data) {
mRoot = new Node(data);
}
public void insert(int data) {
Node root = mRoot;
while (((root.mData > data) ? (root.mLeft) : (root.mRight)) != null) {
root = ((root.mData > data) ? (root.mLeft) : (root.mRight));
}
if (root.mData > data) {
root.mLeft = new Node(data);
} else {
root.mRight = new Node(data);
}
}
public void printTreeLevelbyLevel() {
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(mRoot);
queue.add(null);
while (!queue.isEmpty()) {
Node head = null;
while ((head = queue.remove()) != null) {
System.out.print(head + " ");
if (head.mLeft != null) {
queue.add(head.mLeft);
}
if (head.mRight != null) {
queue.add(head.mRight);
}
}
System.out.println();
if (!queue.isEmpty()) {
queue.add(null);
}
}
}
}
Test
package algo.printtree;
public class Main {
public static void main(String[] args) {
// http://www.careercup.com/question?id=6311899375337472
BST bst = new BST(100);
bst.insert(10);
bst.insert(5);
bst.insert(70);
bst.insert(1);
bst.insert(7);
bst.insert(6);
bst.insert(8);
bst.insert(150);
bst.insert(120);
bst.insert(170);
bst.insert(110);
bst.insert(125);
bst.printTreeLevelbyLevel();
}
}
This is my solution.
I create a set containing all the names which will be sought. Then I parse a string request. If it doesn't have any asterisk placeholders, I'll just call contains(request) on the set with the names.
If the request contains asterisk(s), I'll replace them with a, b, c, etc. and call contains(request) every time after replacing.
So if the input data is has**, the following strings will be checked:
- hasaa,
- hasab,
- hasac
...
- hasem is in the map. We're done.
- maksim.a.dmitriev February 28, 2015