Facebook Interview Question SDE1s
Country: United States
public TreeNode Build(String s) {
Char exp= s.toCharArray();
if (expr.length == 0) {
return null;
}
TreeNode root = new TreeNode(expr[0]);
Stack<TreeNode> stack = new Stack<>();
for (int i = 1; i < expr.length; i += 2) {
TreeNode node = new TreeNode(expr[i + 1]);
if (expr[i] == '?') {
stack.peek().left = node;
}
if (expr[i] == ':') {
stack.pop();
while (stack.peek().right != null) {
stack.pop();
}
stack.peek().right = node;
}
stack.push(node);
}
return root;
}
public TreeNode convert(String s) {
char[] expr= s.toCharArray();
if (expr.length == 0) {
return null;
}
TreeNode root = new TreeNode(expr[0]);
Stack<TreeNode> stack = new Stack<>();
for (int i = 1; i < expr.length; i += 2) {
TreeNode node = new TreeNode(expr[i + 1]);
if (expr[i] == '?') {
stack.peek().left = node;
}
if (expr[i] == ':') {
stack.pop();
while (stack.peek().right != null) {
stack.pop();
}
stack.peek().right = node;
}
stack.push(node);
}
return root;
}
Explanation: Consider an example of a?b?c:d:e
1. We will keep on traversing the string and make a new node for every character.
2. If we get next character as '?' we update the string and call the recursive build function for left child of the node.
3. If we get next character as ':' we just update the string and return so that the remaining string can be added as the right child of the upper node.
//Given tree node
class TreeNode{
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
public class TernaryToBinaryTree {
//Taking a static variable to maintain the state of the given string traversed till now.
static String str;
public static TreeNode build(String s){
str = s;
return buildUtil();
}
//Recursive function which first builds a new node and then creates a left child
//on the occurrence of '?' and return the node on occurrence of ':', so that the
//remaining string can be treated as the right child for upper node.
public static TreeNode buildUtil(){
if(str==null || str.isEmpty())
return null;
char ch = str.charAt(0);
TreeNode tn = new TreeNode(ch);
if(str.length() > 1 && str.charAt(1)=='?') {
str = str.substring(2);
tn.left = build(str);
tn.right = build(str);
}else if(str.length() > 1 && str.charAt(1)==':'){
str = str.substring(2);
}
return tn;
}
//Inorder traversal of the tree
public static void inorder(TreeNode treeNode){
if(treeNode==null)
return;
inorder(treeNode.left);
System.out.print(treeNode.val+" ");
inorder(treeNode.right);
}
public static void main(String[] args) {
String s = "a?b?c:d:e";
TreeNode treeNode = build(s);
inorder(treeNode);
}
}
public TreeNode build(String s)
{
return build(s,0,s.length()-1);
}
public TreeNode build(String s, int l, int r)
{
if(s.length()==0)
return null;
if( l > r)
return null;
TreeNode node = new TreeNode(s.charAt(l));
node.left = build(s, l+2, r-2);
if(r != l)
node.right = new TreeNode(s.charAt(r));
return node;
}
package hashmaps.careercup.facebook;
import trees.Node;
import trees.TreeTraversals;
import java.util.Scanner;
/**
* Created by Sibendu Dey on 6/5/17.
*/
public class TernaryToBinary {
public static void main( String args[]) {
Scanner sc = new Scanner(System.in);
String ternaryExpression = sc.next();
Node root = constructTree(ternaryExpression);
// Takes care of displaying the tree in-order fashion
TreeTraversals.inOrderStringDisplay(root);
}
private static Node constructTree(String ternaryExpression) {
return constructTreeTernary(ternaryExpression);
}
private static Node constructTreeTernary(String ternaryExpression) {
int questionIndex = ternaryExpression.indexOf('?');
Node node = null;
if ( questionIndex == -1)
node = new Node(ternaryExpression);
else
node = new Node(ternaryExpression.substring(0 , questionIndex));
// It means this is a leaf node. No need for further recursive operation
if ( questionIndex == -1)
return node;
// This indices takes care of dividing the strings into two parts for recursive operations.
int firstExpressionStartIndex = questionIndex + 1;
int secondExpressionStartIndex = ternaryExpression.lastIndexOf(':');
node.setleftNode(constructTreeTernary(ternaryExpression.substring(firstExpressionStartIndex , secondExpressionStartIndex )));
node.setRightNode(constructTreeTernary(ternaryExpression.substring(secondExpressionStartIndex + 1)));
return node;
}
}
My solution tested with a?b?c:d:e, a?b:c?d:e and a?b?c:d:e?f:g
Node ConstructTreeHelper(string expression)
{
if(expression == null || expression.Length == 0) {
return null;
}
//Console.WriteLine("Expression is " + expression);
if(expression.Length == 1)
return new Node(expression);
int questionIndex = expression.IndexOf("?");
var root = expression.Substring(0, questionIndex);
//Console.WriteLine("\tRoot is " + root);
var lhsEnd = FindLeftResultLength(expression.Substring(questionIndex+1));
//Console.WriteLine("\tFirst Result Length is " + lhsEnd);
var lhs = expression.Substring(questionIndex + 1, lhsEnd);
var rhs = expression.Substring(lhsEnd+3);
//Console.WriteLine("\tLHS is " + lhs);
//Console.WriteLine("\tRHS is " + rhs);
var rootNode = new Node(root);
rootNode.Left = ConstructTreeHelper(lhs);
rootNode.Right = ConstructTreeHelper(rhs);
return rootNode;
}
int FindLeftResultLength(string expression)
{
int questionIndex = expression.IndexOf("?");
int lastColonIndex = expression.LastIndexOf(":");
int firstColonIndex = expression.IndexOf(":");
if(firstColonIndex == 1)
return 1;
var charArray = expression.ToCharArray();
var pairCount = 0;
int i =1;
for(; i< charArray.Length; i++)
{
if(charArray[i] == '?')
pairCount++;
if(charArray[i] == ':')
pairCount--;
if(pairCount == 0 && (i == charArray.Length || charArray[i+2] == ':'))
return i+2;
}
return -1;
}
Consider string s consists of 'character-command’ pairs:
For example, ‘a?b:c’ -> a,b,c are characters and ?,: are commands
and the sequences are ‘a?’, ‘b:’,’c:’ (the end of string is assumed as ‘:’ to make the process consistent)
we maintain two stacks: node_stack and leaf_stack.
- For command ‘?’: make a node and push to the node_stack
- For command ‘:’ : it differs whether it is the first(odd) or the second(even)
- if it is the first: make a node and push to the leaf_stack
- if it is the second:
pop a node from the node_stack and,
node.right = new node from the current character
node.left = a leaf node popped from the leaf_stack
push back the node to the leaf_stack
- After the end of the string expression clean up the residuals (if any in node_stack)
- pop a node from the node_stack
- set node.left and node.right from leaf_stack
- push back the node to the leaf_stack
- Finally, the (only one) first node of the leaf_stack is the result tree.
My code is as follows
- build is the main logic
- print_level is for testing: to print the tree by level-order
class TreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def print_level(root):
if not root: return
wqueue = [root, None]
while len(wqueue) > 0:
node = wqueue.pop(0)
if node:
if node:
print(node.val, end=" ")
if node.left:
wqueue.append(node.left)
if node.right:
wqueue.append(node.right)
else: # means the new level
if len(wqueue) > 0:
wqueue.append(None)
print("")
def build(strexp):
if not strexp: return
node_stack = []
leaf_stack = []
is_second = False
s = list(strexp)
s.append(':') # to make the process consistent at the end
index = 0
buffer = ''
while index < len(s):
if s[index] == '?':
new_node = TreeNode(buffer)
node_stack.append(new_node)
elif s[index] == ':':
if is_second: # build a tree
node = node_stack.pop()
node.right = TreeNode(buffer)
node.left = leaf_stack.pop()
leaf_stack.append(node)
else:
new_node = TreeNode(buffer)
leaf_stack.append(new_node)
is_second = not is_second
else: # it is a character
buffer = s[index]
index += 1
# clean up the residuals
while len(node_stack) > 0:
node = node_stack.pop()
node.right = leaf_stack.pop()
node.left = leaf_stack.pop()
leaf_stack.append(node)
return leaf_stack[0]
if __name__ == '__main__':
str1 = "a?b:c"
str2 = "a?b?c:d:e"
str3 = "a?b?c:d:e?f:g"
root = build(str1)
print_level(root)
print("--")
root = build(str2)
print_level(root)
print("--")
root = build(str3)
print_level(root)
public class TernaryTree {
public static void main(String[] args) {
String s = "a? b?c:d : e?f:g";
TreeNode root = build(s);
}
public static TreeNode build(String s) {
s = s.replaceAll(" ", "");
Map<Integer, Integer> colonMap = new HashMap<>();
Stack<Integer> stack = new Stack<>();
int cur = 0;
while (cur < s.length()) {
char c = s.charAt(cur);
if (c == '?') {
stack.push(cur);
}
if (c == ':') {
colonMap.put(stack.pop(), cur);
}
cur++;
}
int i = s.indexOf('?');
TreeNode root = new TreeNode(s.charAt(i - 1));
build(colonMap, root, s, i + 1, colonMap.get(i), s.length() - 1);
return root;
}
public static void build(Map<Integer, Integer> colonMap, TreeNode parent, String s, int l, int m, int e) {
TreeNode left = null;
if (m - l > 1) {
int i = s.indexOf('?', l);
int mid = colonMap.get(i);
left = new TreeNode(s.charAt(i - 1));
build(colonMap, left, s, i + 1, mid, m - 1);
} else if (m - l == 1) {
left = new TreeNode(s.charAt(l));
}
TreeNode right = null;
if (e - m > 1) {
int i = s.indexOf('?', m);
int mid = colonMap.get(i);
right = new TreeNode(s.charAt(i - 1));
build(colonMap, right, s, i + 1, mid, e);
} else if (e - m == 1) {
right = new TreeNode(s.charAt(e));
}
parent.left = left;
parent.right = right;
}
static class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
}
Recursive solution
public static TreeNode build(String s) {
if(s == null || s.length() == 0) {
return null;
}
if(s.length() == 1) return new TreeNode(s.charAt(0));
String root = s.substring(0, s.indexOf("?"));
String lhs = s.substring(s.indexOf("?") + 1, s.lastIndexOf(":"));
String rhs = s.substring(s.lastIndexOf(":") + 1);
TreeNode rootNode = new TreeNode(root.charAt(0));
rootNode.left = build(lhs);
rootNode.right = build(rhs);
return rootNode;
}
- Alex May 09, 2017Node *Build(string const s, int &idx) { if (idx >= s.size()) { return NULL; } Node *n = new Node(s[idx]); idx += 2; if (idx < s.size() && s[idx - 1] != ':') { n->left_ = Build(s, idx); n->right_ = Build(s, idx); } return n; }