Facebook Interview Question
Developer Program EngineersCountry: United States
Interview Type: Written Test
This is correct. Although, the there seems to be lot more code than one really needs. Java sucks.
if(temp.equals("*x")){
valueArray[begin][end] = 1;
return valueArray[begin][end];
}
How come for this case " valueArray[begin][end] = 1" ? I can't think of any case where one operation that would transform *x to RPN.
stackoverflow dot com questions 10013933/conversion-to-proper-postfix-notation-in-minimum-number-of-steps
seems like facebook is looking at stackoverflow to copy exact question..my friend gave fb interview last week and he said they are all 45 minute rounds on site (may extend to 1 hr max) never more than 1 hr. In rare instances can you solve this question in 35 - 40 minutes with all the stress. (10 minutes are spent to ask about other questions) I find it hard to believe this was asked in an interview.
I made my own version of DP codes and here are some results:
===========================================
Now test len 2
The min operations for xx is 1
The min operations for ** is 2
The min operations for x* is 1
The min operations for *x is 1
===========================================
Now test len 3
The min operations for *x* is 1
The min operations for *** is 2
The min operations for **x is 2
The min operations for x*x is 2
The min operations for x** is 1
===========================================
Now test len 4
The min operations for **** is 3
The min operations for x**x is 2
The min operations for *x*x is 2
The min operations for xx** is 1
The min operations for x*** is 2
The min operations for **xx is 3
The min operations for xxxx is 2
===========================================
Now test len 5
The min operations for x**xx is 2
The min operations for ***xx is 3
The min operations for x*xxx is 3
The min operations for x*x*x is 2
The min operations for **xx* is 2
The min operations for *x*xx is 2
............
===========================================
Now test len 96
The min operations for ***xx*xx*x*x******xxxx*xxxx*xxx***xxxx*x**xxx**xx*xxx***xxxx*xxx***xx***x**xxx*x*x*xxxxx**x**xxx is 13
The min operations for x**xxx*****x**x*xxxx*x***xxxx***xx***xx****x**xx*xx**x**x****xx*xx**x*x*xx*x*x******x**x***xxx*x is 10
The min operations for x**xxx**x*xx***xx*xx***x*x*x*xxxxx*xxx*****xxxxx*xxxx***x*x***x**x***xx***x*x*xxx***x*xxxx*xxxx* is 5
The min operations for *x**x*xx**x***xx*xx**x***xxxxxxxx**xxxxxxx*xx****xxx*x***x**x*******xx**x*xx**x*xx***xx**xx*xxxx is 7
The min operations for *x***xx*x****x**x*****x***xx*x*x*xxxx*x*x**xxx*x*x*x*xx**x*xxxx**xx**x*x****xxxx**x*xx**x**x**** is 8
The min operations for *xxxxxxx***xx****x*xxx*xx*xx*xx******x*x*xx**xxx*xxx***x***x*xx******xxxxx*xx*x**x***xx****x*xxx is 4
The min operations for ***xx*x*x*x**xxxx*xx*x***x*x**xx*xx*x*xx*xxxxxx*xx*x*xxx*xxx*xx**xx*xxxx*xxx***x**xx***x*xx**x*x is 11
The min operations for **x****x**x**xxxx*******xx**xxx*x**x***x***x*x*xx*x*x***x*xx**x**x*xxx*****xxx*x*x**xx**xxxxx**x is 12
The min operations for x**x**x*x*****x****x**x***********xxxxx*xxx**x**x**xx***xxx**xxx*xx**xx*x*x**x*xx*xxx*x**xxxx*x* is 16
//
An RPN string will be made of series of constituent RPN strings. Or RPN=(RPN)(RPN)*. Thus, problem has recursive nature. Use a stack as we normally use to evaluate an RPN string. Whenever we see violation, we apply appropriate operation(to make uptil the currently visited string RPN) so that we can continue with our RPN evaluation until we hit the end of string. Pseudocode:
string input = "xx*x*xxxx*x*";
int i = 0;
int num_operations_req = 0;
void calc_number_of_operations_req(string input, int i, int &num_operations_req){
stack s;
while(i < input.length()){
if(input[i] == "*"){
if (s.size < 2) {
// we can either delete present * or add an x to stack, both one operation
num_operations_req++;
calc_number_of_operations_req(input,i+1,num_operations_req);
return;
}
else{
s.pop(); // two pops and one push equivalent to one pop for algo
}
}
else{
s.push("x");
}
i++;
}
if (s.size != 1){ // meaning our stack has n x's in it, n>1
num_operations_req += s.size()-1; //we need these many *'s more in the input string at end so the we have RPN
}
return;
}
0. Open algorithm book to pages explaining Shunting Yard and Edit Distance... then..
1. Use Dijkstra's Shunting Yard Algorithm to convert from infix to postfix
2. Return Edit Distance (DP) {with costs 1, 1, 1 for three operations} between infix and posfix
I guess you misunderstood. The given string is neither postfix nor infix. It is just a random string which contains x's and *'s. Your algorithm should take that and then make it postfix using delete, replace, and insert. The minimum number of these operations is the output of the program.
You didn't type your question properly to begin with. Many ambiguities:
1) Do all the x's denote the SAME operand?
2) How can you guarantee that a unique postfix RPN form exists?
Some inputs will have none, some will have multiple.
xxx** and xx*x* are both valid RPNs that can be mutated from **xxx
What does "how many (mutation operations) are needed to make the string follow _the_ RPN" mean? "the" RPN????
1) Yes, they are all the same operand. *'s are all the same operations!
2) There is no unique postfix RPN form. Your algorithm should find the closest one.
All inputs can be transformed into RPN: for example delete all x's and *'s and insert a x which costs (String's length + 1) is one way to make RPN from all inputs.
The challenge is to find the minimum number of insertion, deletion, and replacements needed to make the input Ù‹correct postfix form.
If I can guess the details...
A first solution is to build all valid RPN strings and do Edit Distance on each and keep track of min.
{Note a valid input string should have 1 more operand than operator}
You can build all valid RPN strings from right to left using backtracking.
You have two total variables numoperators, numoperands (we know numoperators == numoperands-1 for valid inputs).
Now everytime you place an operator, decrement numoperators, similarly do for operands.
You can only place an operator if numoperators > 0.
You can only place an operands if numoperands > numoperators+1.
I almost did the same thing, but when it comes to 75 or 100, this way is too slow. Time limit was 5 seconds I guess (They did not tell me what was the time limit, but I could see my program fails after almost 5 seconds).
Making all valid RPN from right to left using backtrack is exponential....
I guess this question was one of the hard ones.
Exhaustive searching, this code chokes for length = 100
bool isValid(string str){
if( str.length() < 3 )
return false;
stack<char> stk;
int i = 0;
while(i < str.length()){
if( str[i] == 'x'){
stk.push('x');
}
else{
if( stk.size() < 2)
return false;
char first = stk.top();
stk.pop();
char second = stk.top();
stk.pop();
if( first == 'x' && second == 'x'){
stk.push( 'x' );
}
}
i++;
}
return (stk.size() == 1 && stk.top() == 'x');
}
struct stringDepth{
int depth;
string str;
stringDepth(string s, int d):str(s),depth(d){}
};
int minDistance(string str){
queue<stringDepth> bfsQueue;
unordered_set<string> duplicateFinder;
bfsQueue.push( stringDepth(str,0));
while( bfsQueue.size() > 0 ){
stringDepth front = bfsQueue.front();
bfsQueue.pop();
if( duplicateFinder.find(front.str) == duplicateFinder.end()){
int nextDepth = front.depth + 1;
const string currString = front.str;
//Delete Each element
for( int i = 0 ; i < currString.length() ; i++){
string newStr;
if( i == 0 )
newStr = currString.substr( 1, currString.length() - 1 );
else if( i == currString.length() - 1){
newStr = currString.substr( 0, currString.length() - 1 );
}
else{
string first = currString.substr(0,i);
string second = currString.substr(i+1, currString.length()-(i+1));
newStr = first + second;
}
if(isValid( newStr ))
return nextDepth;
bfsQueue.push(stringDepth(newStr,nextDepth));
}
// Replace Each element
for( int i = 0 ; i < currString.length() ; i++){
string newStr = currString;
newStr[i] = (newStr[i] == 'x' ? '*' : 'x');
if(isValid( newStr ))
return nextDepth;
bfsQueue.push(stringDepth(newStr,nextDepth));
}
//Append newChar
// Replace Each element
for( int i = 0 ; i < currString.length() ; i++){
string newStr = currString.substr(0,i+1) + 'x' + currString.substr(i+1, currString.length() - (i+1));
if(isValid( newStr ))
return nextDepth;
bfsQueue.push(stringDepth(newStr,nextDepth));
newStr = currString.substr(0,i+1) + '*' + currString.substr(i+1, currString.length() - (i+1));
if(isValid( newStr ))
return nextDepth;
bfsQueue.push(stringDepth(newStr,nextDepth));
}
duplicateFinder.insert(currString);
}
bfsQueue.pop();
}
}
Would you please explain how your code works? Also please let me know if it works fast enough for length 100.
@madhi.oraei, this is not efficient for longer strings
It basically tries out all possibilities
say the input is 'xxx'
it checks if xxx is valid if it is not valid
checks each string after deleting each character { xx , xx , xx }
Check after replacing each character *xx , x*x, xx*
checks appending each character xxxx, *xxx, xxxx, x*xx, xxxx, xx*x, xxxx, xxx*
Repeats the step until it finds an answer
I used a queue and did sort of something similar to bfs.
Assume xxx as the node, find all possible states from xxx. check if those states are valid and keep going.
I see. Well, I have written my idea in the next comment. You can read it. I had the same idea as your idea, but my friend revised it to a dynamic programming approach which works way better.
@mahdi.oraei, good solution. Was this asked in facebook interview. This is tough for a hour interview.
It is a stack question. The correct question is when you have multiple operators and some have precedence, so you will need to include paranthesis. For this one, assuming only the "*" operator, a simple code will do it:
A) Go through the sequence and push operands in one stack, and operators in another
B) Pop an operator, pick a new operand and if we already have one from before, then attach them as the new operand. If we don't have an operand from before, just pop another one from operand stack
Python code running in O(N = number of operands + number of operators)
s = "x*X*Y*y*Career*Cup*Facebook"
operand_stack = []
operator_stack = []
operators = "*"
t = ''
for c in s:
if c in operators:
operand_stack.append(t)
operator_stack.append(c)
t = ''
else:
t = t + c
operand_stack.append(t)
txt = ''
v1 = ''
vinmem = False
while len(operand_stack) > 0:
op = operator_stack.pop(len(operator_stack) - 1)
# take two variables
if vinmem == False:
v1 = operand_stack.pop(len(operand_stack) - 1)
vinmem = True
v2 = operand_stack.pop(len(operand_stack) - 1)
term = '(' + v1 + v2 + op + ')'
v1 = term
print v1
nopar = v1.replace('(', '')
nopar = nopar.replace(')', '')
print nopar
Result:
((((((FacebookCup*)Career*)y*)Y*)X*)x*)
FacebookCup*Career*y*Y*X*x*
This question is not about how to change infix to postfix! Input can be any random string of xs and *s! What is the minimum number of delete, replace, and insert to make the given string postfix!
you are right. I did not read the second part well. Regardless you need to know the post fix before transformation. Now you can apply DP for matching strings. Ill post the code soon.
Here is the DP solution. It involves O(N) iterations. In each iteration I make O(1) operations. This is true if we assume the string is a linked list so that we can delete, replace, and insert in O(1). However, I am not implementing like this and the way I am doing it right now, each iteration also takes O(N). So overall O(N^2).
To know which position I am doing these operations, I use the state variable "pos". When at some stage "pos = n" it means that the first "n" characters of generated string are "matched".
Python:
str1 = "xx**xxxxx*"
str2 = "xx*x*"
strings = []
prevdec = []
costs = []
pos = []
max_itr = 2 * (len(str1) + len(str2))
action_txt = ['pass', 'insert(x)', 'insert(*)', 'replace', 'delete']
K = -1
N = -1
best_cost_overall = 1000
BIG_CONSTANT = 10
def costOf(d):
return 0 if d == 0 else 1
def other(c):
return ('x' if c == '*' else '*')
def drawState(ds, length):
for row in range(0, len(ds[0])):
r = str(row) + ':'
for ns in range(0, len(ds)):
x = str(ds[ns][row])
if len(x) < length:
rr = [' ' for m in range(0, length - len(x))]
rr = ''.join(rr)
r = r + rr + x
print r
def nextString(s, action, pos):
global str2
if action == 1:
return (s[0:pos] + 'x' + s[pos:], pos)
if action == 2:
return (s[0:pos] + '*' + s[pos:], pos)
# For delete and replace assert len(s) > 0
if pos < len(s):
if action == 3:
s = s[0:pos] + other(s[0]) + s[pos + 1:]
elif action == 4:
s = s[0:pos] + s[pos + 1:]
ml = min(len(s), len(str2))
if pos >= ml:
return (s, pos)
while True:
if s[pos] == str2[pos]:
pos += 1
else:
break
if pos >= ml:
break
return (s, pos)
def diffCost(s1, s2, p):
ext_cost = max(len(s2), len(s1))
ext_cost -= p
return ext_cost
for k in range(0, max_itr):
next_str = ['' for n in range(0, 5)]
next_pos = [0 for n in range(0, 5)]
prev_dec = [0 for n in range(0, 5)]
cost = [0 for n in range(0, 5)]
if k == 0:
for n in range(0, 5):
next_str[n], next_pos[n] = nextString(str1, n, 0)
prev_dec[n] = 0
cost[n] = costOf(n)
else:
for n in range(0, 5):
best_str = ''
best_dec = 0
best_pos = 0
best_cost = 100000
for m in range(0, 5):
s, p = nextString(strings[k - 1][m], n, pos[k - 1][m])
cop = costOf(n) + diffCost(s, str2, p) * BIG_CONSTANT
if cop < best_cost:
best_cost = cop
best_pos = p
best_dec = m
best_str = s
next_str[n] = best_str
next_pos[n] = best_pos
cost[n] = costOf(n) + costs[k - 1][best_dec]
prev_dec[n] = best_dec
costs.append(cost)
strings.append(next_str)
prevdec.append(prev_dec)
pos.append(next_pos)
for n in range(0, 5):
if diffCost(strings[k][n], str2, pos[k][n]) == 0:
if costs[k][n] < best_cost_overall:
best_cost_overall = costs[k][n]
K, N = k, n
def getOps(K, N):
global action_txt, prevdec, pos
action = ''
n = N
for k in range(K, -1, -1):
action = action_txt[n] + "@[" + str(pos[k][n]) + "]" + action
n = prevdec[k][n]
action = action_txt[n] + "@[" + str(pos[k][n]) + "]" + action
return action
print "COST OF CHANGE = ", best_cost_overall
print getOps(K, N)
#print drawState(strings, 20) ==> to view the dynamic programming table
Umm, there's a quick O(n) solution.
Here's the idea: Anything you do to edit the string either adds an x (which is the same as removing a *) or adds a * (which is the same as removing an x). Also, we can assume that the x is added to the left and the * is added to the right. Going from right to left through the string, find the #x - #*'s at each point. Whatever the min is, (say m), then we need to put m-1 *'s on the right side. Then, we need total #x = total # star +1, so add the appropriate number of x's .
The reason this works is because this is very similar to catalan numbers with balanced parenthesis.
Here's a short solution in O(n):
import java.util.*;
public class Polish {
int best(String s) {
char[] a = s.toCharArray();
int sum = 1;
int min = 1;
//Intentionally not including the last one.
for(int i = a.length-1; i>0; i--) {
if (a[i]=='x')
sum--;
else
sum++;
if (sum < min)
min = sum;
}
if (a[0]=='x')
sum--;
else
sum++;
int numStars = 1 - min;
int numX = sum + numStars;
return numStars + numX;
}
public static void main(String[] args) {
Polish s = new Polish();
System.out.println(s.best("xx*xx**"));
System.out.println(s.best("x"));
System.out.println(s.best("*"));
System.out.println(s.best("***"));
System.out.println(s.best("*xx*"));
System.out.println(s.best("x*x"));
System.out.println(s.best("xx*"));
/* Output:
0
0
2
4
3
2
0*/
}
}
This is not a facebook interview question, EXACT same question exists on Stackoverflow asked 2 years ago. The answer over there explains the solution in a very nice manner and it is a LENGTHY question. Unless you are super smart you can't answer this in 35 minutes ( rest of 10 - 15 minutes used for other discussions in the interview). Not a good judge of candidates ability.
All the code above does not look elegant ..
One thing to note is that if we have n x's then there are n-1 *'s in postfix expression
find all valid combinations of postfix expressions like below by scanning the input for x's
and pass in below the values of x and ops one less then it.
public void postfixcombinations(int x, int op, List out, StringBuffer postfix) {
if (x == 0 && op == 0) {
out.add(postfix);
}
if (x > 0) {
postfixcombinations(x-1, op, out, postfix.append('x');
postfix.deleteCharAt(postfix.lenght() -1));
}
if (op > x) {
postfixcombinations(x, op - 1, out, postfix.append('*');
postfix.deleteCharAt(postfix.lenght() -1));
}
}
Then find edit distance of input to each of this combination
public int editDistance (String s1, String s2) {
int[][] table = new int[s1.length][s2.length];
for(int i = 0; i < s1.length; i++)
table[0][i] = 0;
for(int i = 0; i < s1.length; i++)
table[i][0] = 0;
for(int i = 1; i <s1.length; i++)
for(int j = 1; j <s2.length; j++)
if (s1.charAt(i) == s2.charAt(j))
table[i][j] = table[i-1][j-1] + 1;
else
table[i][j] = Math.max(table[i][j-1], table[i-1, j]);
return table[s1.length-1][s2.length-1];
}
Keep the one which is minimum
public void findEditDistance(String input) {
int x= 0;
for(int i =0; i < input.length; i++){
if (input.chatAt(i) == 'x') x++;
}
List<String> out = new ArrayList<>();
postfixcombinations(x, x-1, out, new StringBuffer());
int min = 0;
String possibility;
for(String s : out) {
int n = editDistance (input, s);
if (n < min) {min = n; possibility = s;}
}
return min;
}
Doesn't the code above look convincing to google and facebookers. It looks for finding possibility of applying natual recursive logic to find all good combinations of x's and *s which make valid postfix expressions. and find the one which best minimum edit distance to the input..
Note : above code was typed in notepad, so dont compain directly, the point is use the logic..
change it a little bit and it should start working.
Any comments
Idea very similar to the others, but a more precise implementation in Python:
import sys
class Solver:
def get_min(self , start , end):
min_dist = sys.maxint
for i in xrange(start+1 , end):
dist = self.eval_exp(start , i) + self.eval_exp(i,end)
min_dist = min(min_dist , dist)
return min_dist
def eval_exp(self , start , end):
if self.lookup[start][end]!=-1:
return self.lookup[start][end]
if self.exp[end-1] == "*":
self.lookup[start][end] = min( self.get_min(start,end-1) , self.get_min(start , end)+1 , self.eval_exp(start,end-1)+1)
else:
self.lookup[start][end] = min( self.get_min(start,end-1)+1 , self.get_min(start , end)+1 , self.eval_exp(start,end-1)+2)
return self.lookup[start][end]
def get_dist(self , s):
self.exp = s
n = len(s)
self.lookup = [[-1 for i in xrange(n+1)] for j in xrange(n+1)]
for i in xrange(n):
self.lookup[i][i+1] = 0 if s[i]=='x' else 1
return self.eval_exp(0,n)
s = Solver()
print s.get_dist("*x*")
One of my friends helped me to solve this problem. The idea is dynamic programming!
Step A: for having RPN, it is enough to have (RPN)(RPN)*, so find the best K where (0,1,...K),(K+1,....,N-1)* is RPN (N is the length of the string).
If the last character is x, you can delete it and find the best answer for (0,....,N-1)
or replace it with an asterisk and go to Step A,
or add an asterisk to the end and find the best K where (1,0,...K),(K+1,....N)* is RPN.
I have written the code for it and works perfectly even for the string size 200. Here is the code:
- mahdi.oraei March 04, 2014