Facebook Interview Question for Developer Program Engineers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
2
of 4 vote

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:

import java.util.ArrayList;
import java.util.Scanner;


// Used 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 K for (0,1,...K),(K+1,....N-2)*
// 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.
public class Solution2 {
	ArrayList<String> strs = new ArrayList<String>();
	int[][] valueArray;
	
	public static void main(String[] args) {
		Solution2 solution = new Solution2();
		Scanner scanner = new Scanner(System.in);
		int num = Integer.parseInt(scanner.nextLine());
		for (int i = 0; i < num; i++) {
			solution.strs.add(scanner.nextLine());
		}
		for (int i = 0; i < num; i++) {
			solution.makeEmptyArray(i);
			int res = solution.solve(i);
			System.out.println(res);	
		}
		
	}

	private int solve(int index) {
		return solve(strs.get(index),0,this.strs.get(index).length()-1);
		
	}
	private int solve(String str, int begin, int end){
		//already this branch is solved!
		if(valueArray[begin][end] != Integer.MAX_VALUE){
			return valueArray[begin][end];
		}
		
		// length 1
		if( begin == end ){
			if(str.charAt(begin) == '*'){
				valueArray[begin][end] = 1;
				return valueArray[begin][end];
			}else{
				valueArray[begin][end] = 0;
				return valueArray[begin][end];
			}
		}
		
		// length 2
		if(begin == end -1){
			String temp = str.substring(begin, end+1);
			if(temp.equals("xx")){
				valueArray[begin][end] = 1;
				return valueArray[begin][end];
			}
			if(temp.equals("x*")){
				valueArray[begin][end] = 1;
				return valueArray[begin][end];
			}
			if(temp.equals("**")){
				valueArray[begin][end] = 2;
				return valueArray[begin][end];
			}
			if(temp.equals("*x")){
				valueArray[begin][end] = 1;
				return valueArray[begin][end];
			}
			System.out.println("Error in solve");
			return -1;
		}
		
		// find the best k where solve(begin,k) + solve(k+1,end-1) is the best
		if(str.charAt(end) == '*'){
			int min = Integer.MAX_VALUE;
			for (int i = begin; i < end-1; i++) {
				int temp = solve(str,begin,i) + solve(str,i+1,end-1);
				if(temp < min)
					min = temp;
			}	
			valueArray[begin][end] = min;
			return min;
		}
		else{ // str.charAt(end)='x'
			int min = Integer.MAX_VALUE;
			
			//replace it with *: similar to the previous, except that there is the cost of 1 for replacement of x with *.
			for (int i = begin; i < end-1; i++) {
				int temp = solve(str,begin,i) + solve(str,i+1,end-1) + 1;
				if(temp < min)
					min = temp;
			}
			
			//insert, insert an asterisk at the end and try to find the best k where solve(begin,k) + solve(k+1,end) is the best
			//since an asterisk is added, the last character has to be involved in the following calculations.
			for (int i = begin; i < end; i++) {
				int temp = solve(str,begin,i) + solve(str,i+1,end) + 1;
				if(temp < min)
					min = temp;
			}
			
			//delete x and solve the problem for the rest.
			int temp = solve(str,begin,end-1) + 1;
			if(temp < min)
				min = temp;
			
			valueArray[begin][end] = min;
			return min;
		}
		
		
	}

	public void makeEmptyArray(int index) {
		valueArray = new int[strs.get(index).length()][strs.get(index).length()];
		for (int i = 0; i < valueArray.length; i++) {
			for (int j = 0; j < valueArray.length; j++) {
				valueArray[i][j] = Integer.MAX_VALUE;
			}
			
		}
	}
	
	
}

- mahdi.oraei March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is correct. Although, the there seems to be lot more code than one really needs. Java sucks.

- memo March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the complexity?

- Anonymous March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n^3)

- mahdi.oraei March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

*x -> delete star -> RPN

- mahdi.oraei April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- byteattack May 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- T_Dog October 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

//
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;
}

- AbhishekA August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, AbhishekA,

Thanks for sharing your solution. But do you know whether this algorithm can get the minimum number of operations? Thanks.

- T_Dog October 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- S O U N D W A V E March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- mahdi.oraei March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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????

- S O U N D W A V E March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- mahdi.oraei March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- S O U N D W A V E March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- mahdi.oraei March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not very clear about the question.. especially with respect to the input , are we talking about levenshtein distance here? even then can you provide more clarity?

- jayswami March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
	}
}

- Anonymous March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Would you please explain how your code works? Also please let me know if it works fast enough for length 100.

- mahdi.oraei March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Anonymous March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mahdi.oraei, good solution. Was this asked in facebook interview. This is tough for a hour interview.

- Anonymous March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes it was asked in the programming interview. I had two hours, and I failed :D

- mahdi.oraei March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mahdi.oraei, it's not your fault.. it's not your fault.. :)

- Anonymous March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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*

- Ehsan March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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!

- mahdi.oraei March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ehsan March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ehsan March 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Eric March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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*/

}
}

- Eric March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- byteattack May 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
   }

- Naresh Pote June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Naresh Pote June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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*")

- anantpushkar009 November 03, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More