Facebook Interview Question Software Engineer / Developers

  • facebook-interview-questions
    0
    of 0 votes
    37
    Answers

    An expression consisting of operands and binary operators can be written in Reverse Polish Notation (RPN) by writing both the operands followed by the operator. For example, 3 + (4 * 5) can be written as "3 4 5 * +".

    You are given a string consisting of x's and *'s. x represents an operand and * represents a binary operator. It is easy to see that not all such strings represent valid RPN expressions. For example, the "x*x" is not a valid RPN expression, while "xx*" and "xxx**" are valid expressions. What is the minimum number of insert, delete and replace operations needed to convert the given string into a valid RPN expression?

    Input: The first line contains the number of test cases T. T test cases follow. Each case contains a string consisting only of characters x and *.

    Output: Output T lines, one for each test case containing the least number of operations needed.

    Constraints: 1 <= T <= 100 The length of the input string will be at most 100.

    Sample Input:

    5
    x
    xx*
    xxx**
    *xx
    xx*xx**
    Sample Output:

    0
    0
    0
    2
    0
    Explanation:

    For the first three cases, the input expression is already a valid RPN, so the answer is 0. For the fourth case, we can perform one delete, and one insert operation: xx -> xx -> xx

    - dprediction on April 02, 2012 in United States Report Duplicate | Flag
    Facebook Software Engineer / Developer C

Country: United States


Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is my solution. I didn't find any case which is not covered by the below solution.
Will be waiting to get some testcases where this approach fails.
Below one is the perfect java code, you can place it in main and change the input string to the testcase and can be executed.

String input = "xxxxx";
		int xs = 0;
		int noOfReplaces = 0;
		int noOfdeletes = 0;
		int noOfInserts = 0;
		for (int i = 0; i < input.length(); i++) {
			if (input.charAt(i) == 'x')
				xs++;
			else {
				if (xs > 1) {
					xs--;
				} else if (xs == 1) {
					if (noOfdeletes > 0) {
						noOfReplaces++;
						noOfdeletes--;
					} else {
						// If this is last {
						if (i == input.length() - 1) {
							// Add one x at first
							noOfInserts++;
						} else {
							noOfdeletes++;
						}
					}
				} else {
					if (noOfdeletes > 1) {
						// As the 2 deletes can be replcaced with xs
						noOfdeletes = noOfdeletes - 2;
						noOfReplaces = noOfReplaces + 2;
					} else {
						noOfdeletes++;
					}
				}
			}

		}
		while (xs > 1) {
			if (xs > 2) {
				// Replace one x with *
				noOfReplaces++;
				xs = xs - 2;
			}
			if (xs == 2) {
				// Add one * at last
				noOfInserts++;
				xs--;
			}

		}
		
		System.out.println("deletes:" + noOfdeletes);
		System.out.println("insersts:" + noOfInserts);
		System.out.println("replaces:" + noOfReplaces);
		System.out.println("total:" + (noOfdeletes+ noOfReplaces + noOfInserts));

- Srikanth on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will fail for "x" resulting in 1

- Nitesh on July 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry it will run correctly for "x" resulting in 0

- Nitesh on July 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How did you come up with this solution? A quick description of your thought process would be great. As far as I can tell, it just.... magically works.

- Anon on August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I actually compiled the code on the interviewstreet site and it's failed for the two hidden tests..

- Rebecca on June 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I pasted to the online test compiler. This only passed 1/3 testcases, which got same results as mine.

- TFang.DU on July 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int FixExpressionOpCount(string expression)
{
    // Check for null and emptu
    if (expression == null || expression == '') return 0;

    // If the expression contains only one operand, there is nothing to fix
    if (expression.length <= 1) return 0;
    
    // Reudce a valid subexpression to an operand
    string reducedExpression = expression.replace('xx*', 'x');
    
    // if there was a valid sub-expression, this would have got reduced.
    if (reducedExpression.length < expression.length)
        return FixExpressionOpCount(reducedExpression);

    // If no reduction happened, get the number of times the operator '*' appears.
    // Each of these operators will need to be deleted and inserted to the end (i.e. 2 operations).
    return getCharCount(expression, '*') * 2;
}

int getCharCount(string str, char toFind)
{
    int count = 0;
    foreach (c in str)
        if (c == toFind) count++;

    return count;
}

- .w.h.i.m. on April 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code doesn't solve the problem.
First of all there are 3 operations: deletion, addition and replacement.
What your input string is *******?
I believe this needs a dynamic programming approach.

- dprediction on April 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

input string cannot be all* (*******) as it is not a valid input because any number of operations can not make it a proper RPN code

- Yash on April 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, you can use insertion Xs or replace *s with Xs in order to make that a valid RPN expression.

- Anon on August 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This seems to work. An evaluation stack is sufficient.

import java.util.Scanner;

class RPN {
	public static void main(String[] args) {
		RPN rpn = new RPN();
		Scanner scanner = new Scanner(System.in);
		int numLines = scanner.nextInt();
		for(int i = 0; i < numLines; ++i) {
			System.out.println(rpn.processExpression(scanner.next()));
		}
	}

	private int processExpression(String expression) {
		int length = expression.length();
		if(length == 0) {
			return 0;
		}
		int change = 0;
		int stackOperandCount = 0;
		for(int i = 0; i < length; ++i) {
			if(expression.charAt(i) == 'x') {
				stackOperandCount = stackOperandCount + 1;
			} else {
				if(stackOperandCount > 1) {
					stackOperandCount = stackOperandCount - 1;
				} else {
					change = change + 1;
				}
			}
		}
		if(stackOperandCount != 0) {
			change = change + stackOperandCount - 1;
		}
		return change;
	}
}

- smffap on April 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I do not think that this one will work either. Consider the case where we have "X**". Replacing the first occurrence of "*" with an "X" would yield "XX*". This would require only one replace operation, whereas your function would return 2.

- Ava on April 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Another case that I did not catch earlier is that "XXX" could be changed to "XX*" with just one replace operation. Your original code suggested that two operations were needed. Similarly "XXXX" could be changed to "XX*" with one replace operation and one delete operation. Your original code suggested that three operations were needed. I modified your code so that it takes into account the cases that I mentioned above. Some further testing is needed before I can say that it works in every case.

import java.util.Scanner;


class RPN {
	public static void main(String[] args) {
		RPN rpn = new RPN();
		Scanner scanner = new Scanner(System.in);
		int numLines = scanner.nextInt();
		for(int i = 0; i < numLines; ++i) {
			System.out.println(rpn.processExpression(scanner.next()));
		}
	}



private int processExpression(String expression) {
		int length = expression.length();
		if(length == 0) {
			return 0;
		}
		int change = 0;
		int stackOperandCount = 0;
		for(int i = 0; i < length; ++i) {
			if(expression.charAt(i) == 'x') {
				stackOperandCount = stackOperandCount + 1;
			} else {
				if(stackOperandCount > 1) {
					stackOperandCount = stackOperandCount - 1;
				} else {
					if (i+1 < length && expression.charAt(i) == '*') {
						// Instead of just adding or removing the operator (*) here
						// we can save one operation by replacing the operator (*) with an operand (X)
						stackOperandCount = stackOperandCount + 1;
					}
					change = change + 1;
				}
			}
		}
		if(stackOperandCount != 0) {
			// Suppose we have a lot of operands left in our stack; replacing one of the operands (X) with
			// an operator (*) will allow us to more bring the number of operands in the stack down to 1 more quickly.
			// If we have an odd number of operands left, we need to replace (stackOperandCount / 2) of them with operators.
			// If we have an even number of operands left, we need to replace ((stackOperandCount / 2) - 1) of them with operators, and 
			// remove one operand. In either case, this is (stackOperandCount / 2) operations.
			change = change + stackOperandCount / 2;
		}
		return change;
	}
}

- Anonymous on April 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Another case that I did not catch earlier is that "XXX" could be changed to "XX*" with just one replace operation. Your original code suggested that two operations were needed. Similarly "XXXX" could be changed to "XX*" with one replace operation and one delete operation. Your original code suggested that three operations were needed. I modified your code so that it takes into account the cases that I mentioned above. Some further testing is needed before I can say that it works in every case.

import java.util.Scanner;


class RPN {
	public static void main(String[] args) {
		RPN rpn = new RPN();
		Scanner scanner = new Scanner(System.in);
		int numLines = scanner.nextInt();
		for(int i = 0; i < numLines; ++i) {
			System.out.println(rpn.processExpression(scanner.next()));
		}
	}



private int processExpression(String expression) {
		int length = expression.length();
		if(length == 0) {
			return 0;
		}
		int change = 0;
		int stackOperandCount = 0;
		for(int i = 0; i < length; ++i) {
			if(expression.charAt(i) == 'x') {
				stackOperandCount = stackOperandCount + 1;
			} else {
				if(stackOperandCount > 1) {
					stackOperandCount = stackOperandCount - 1;
				} else {
					if (i+1 < length && expression.charAt(i) == '*') {
						// Instead of just adding or removing the operator (*) here
						// we can save one operation by replacing the operator (*) with an operand (X)
						stackOperandCount = stackOperandCount + 1;
					}
					change = change + 1;
				}
			}
		}
		if(stackOperandCount != 0) {
			// Suppose we have a lot of operands left in our stack; replacing one of the operands (X) with
			// an operator (*) will allow us to more bring the number of operands in the stack down to 1 more quickly.
			// If we have an odd number of operands left, we need to replace (stackOperandCount / 2) of them with operators.
			// If we have an even number of operands left, we need to replace ((stackOperandCount / 2) - 1) of them with operators, and 
			// remove one operand. In either case, this is (stackOperandCount / 2) operations.
			change = change + stackOperandCount / 2;
		}
		return change;
	}
}

- Ava on April 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Another case that I did not catch earlier is that "XXX" could be changed to "XX*" with just one replace operation. Your original code suggested that two operations were needed. Similarly "XXXX" could be changed to "XX*" with one replace operation and one delete operation. Your original code suggested that three operations were needed. I modified your code so that it takes into account the cases that I mentioned above. Some further testing is needed before I can say that it works in every case.

import java.util.Scanner;


class RPN {
	public static void main(String[] args) {
		RPN rpn = new RPN();
		Scanner scanner = new Scanner(System.in);
		int numLines = scanner.nextInt();
		for(int i = 0; i < numLines; ++i) {
			System.out.println(rpn.processExpression(scanner.next()));
		}
	}



private int processExpression(String expression) {
		int length = expression.length();
		if(length == 0) {
			return 0;
		}
		int change = 0;
		int stackOperandCount = 0;
		for(int i = 0; i < length; ++i) {
			if(expression.charAt(i) == 'x') {
				stackOperandCount = stackOperandCount + 1;
			} else {
				if(stackOperandCount > 1) {
					stackOperandCount = stackOperandCount - 1;
				} else {
					if (i+1 < length && expression.charAt(i) == '*') {
						// Instead of just adding or removing the operator (*) here
						// we can save one operation by replacing the operator (*) with an operand (X)
						stackOperandCount = stackOperandCount + 1;
					}
					change = change + 1;
				}
			}
		}
		if(stackOperandCount != 0) {
			// Suppose we have a lot of operands left in our stack; replacing one of the operands (X) with
			// an operator (*) will allow us to more bring the number of operands in the stack down to 1 more quickly.
			// If we have an odd number of operands left, we need to replace (stackOperandCount / 2) of them with operators.
			// If we have an even number of operands left, we need to replace ((stackOperandCount / 2) - 1) of them with operators, and 
			// remove one operand. In either case, this is (stackOperandCount / 2) operations.
			change = change + stackOperandCount / 2;
		}
		return change;
	}
}

- Ava on April 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I just remember binary tree, using different traverse method. But can't remember the detail

- LF on April 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A binary tree having the leaves as the numerical value and the nodes as the binary operation, traversing such a tree in post order traversal results in a RPN expression.
For the given question, the number of operations would be the number of times, a value cannot be entered into the tree, and is inserted later, i.e 2 operations for every such value.
The value can or cannot be inserted is based on if the value is an operand then it should be added at the node, else it should be added at the leaf. If there end result is not a binary tree then the input sequence cannot be converted to RPN.

- Jaiprakash on April 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

According to your logic XX* will give output as 6 but its already in RPN. Correct me if i am missing something here.

- Anonymous on April 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is similar to the famous edit distance problem..

- Anirudh on April 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My suggestion: Simply go through the string and count x's and stars. When 'x' found, simply increase x-count. When star found, then: if there are at least 2 x's on the stack, decrease x count by one (because two x's and one star produced one x), otherwise inc error count by one (there might be two cases: x = 0 or x = 1, both solved by one operation: when no x, delete the star; when 1 x, add another and together with star we're ok).
Finally, add to errors all stars (needed to be deleted) and x's/2 (for each 2 x's one star insert).

Long story short (C#):
private int PolishErrors(string s)
{
int x = 0;
int o = 0;
int err = 0;

foreach(char c in s)
{
if (c == 'x') ++x;
else
{
if (x >= 2)
{
x-=1;
}
else
{
err++;
}
}

}

err += x/2 + o;

return err;
}

- Pz on April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

And I forgot to add 1 in case that there is odd number of remaining x's. So that last but one line should be:

err += x/2 + (x%2) + o;

- Pz on April 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Aaand even that is not right, shoot. How about these two lines in the end?

err += x/2 + o;
	if (x>1) err += (x%2);

- martin.pz.cech on April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
    
public class Solution {

    public static void main(String[] args) throws IOException {
        int step = test("xxx*");
        System.out.println(step);
    }
    
    public static int test(String s) {
        int step = 0;
        int operands = 0;
        
        while(s.indexOf("xx*") == 0 || s.indexOf("*x*") == 0 ||
        		s.indexOf("x**") == 0 || s.indexOf("*xx") == 0 ||
        		s.indexOf("**x") == 0 || s.indexOf("x*x") == 0 
        		|| s.indexOf("***") == 0) {
        
	        if (s.indexOf("xx*") == 0) {
	        	s = s.replaceFirst("xx\\*", "x");
	        	continue;
	        }
	        
	        if (s.indexOf("*x*") == 0) {
	        	s = s.replaceFirst("\\*x\\*", "x");
	        	step++;
	        	continue;
	        }
	        
	        if (s.indexOf("x**") == 0) {
	        	s = s.replaceFirst("x\\*\\*", "x");
	        	step++;
	        	continue;
	        }
	        
	        if (s.indexOf("x*x") == 0) {
	        	s = s.replaceFirst("x\\*x", "xx");
	        	step+=1;
	        	continue;
	        }
	        
	        if (s.indexOf("*xx") == 0) {
	        	s = s.replaceFirst("\\*xx", "xx");
	        	step+=1;
	        	continue;
	        }
	        
	        if (s.indexOf("**x") == 0) {
	        	s = s.replaceFirst("\\*\\*x", "x");
	        	step+=2;
	        	continue;
	        }
	        
	        if (s.indexOf("***") == 0) {
	        	s = s.replaceFirst("\\*\\*\\*", "x");
	        	step+=2;
	        	continue;
	        }
        }
        
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c != 'x') {
            	if (operands == 0) {
            		step ++; //delete
            	} else if (operands == 1) {
            		step ++; //delete
            	} else {
            		operands--;
            	}
            } else {
                operands++;
            }
        }
        
        if (operands >= 2) {
            step += (operands - 2 > 0) ? (operands - 2) : 1;
        }
        
        return step;
    }
}

- Dzung Bui on April 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
    
public class Solution {

    public static void main(String[] args) throws IOException {
        int step = test("xxx*");
        System.out.println(step);
    }
    
    public static int test(String s) {
        int step = 0;
        int operands = 0;
        
        while(s.indexOf("xx*") == 0 || s.indexOf("*x*") == 0 ||
        		s.indexOf("x**") == 0 || s.indexOf("*xx") == 0 ||
        		s.indexOf("**x") == 0 || s.indexOf("x*x") == 0 
        		|| s.indexOf("***") == 0) {
        
	        if (s.indexOf("xx*") == 0) {
	        	s = s.replaceFirst("xx\\*", "x");
	        	continue;
	        }
	        
	        if (s.indexOf("*x*") == 0) {
	        	s = s.replaceFirst("\\*x\\*", "x");
	        	step++;
	        	continue;
	        }
	        
	        if (s.indexOf("x**") == 0) {
	        	s = s.replaceFirst("x\\*\\*", "x");
	        	step++;
	        	continue;
	        }
	        
	        if (s.indexOf("x*x") == 0) {
	        	s = s.replaceFirst("x\\*x", "xx");
	        	step+=1;
	        	continue;
	        }
	        
	        if (s.indexOf("*xx") == 0) {
	        	s = s.replaceFirst("\\*xx", "xx");
	        	step+=1;
	        	continue;
	        }
	        
	        if (s.indexOf("**x") == 0) {
	        	s = s.replaceFirst("\\*\\*x", "x");
	        	step+=2;
	        	continue;
	        }
	        
	        if (s.indexOf("***") == 0) {
	        	s = s.replaceFirst("\\*\\*\\*", "x");
	        	step+=2;
	        	continue;
	        }
        }
        
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c != 'x') {
            	if (operands == 0) {
            		step ++; //delete
            	} else if (operands == 1) {
            		step ++; //delete
            	} else {
            		operands--;
            	}
            } else {
                operands++;
            }
        }
        
        if (operands >= 2) {
            step += (operands - 2 > 0) ? (operands - 2) : 1;
        }
        
        return step;
    }
}

- Dzung Bui on April 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define MAX 100

int validRPN(char *s)
{
    int n=strlen(s),i,res=0,counter=0;
    for(i=0;i<n;i++)
        if(s[i]=='x')
            counter++;
        else
        {
            if(counter>1)
                counter--;
            else
                res++;
        }
    while(counter>1)
    {
        res++;
        counter--;
    }
    return res;
}

void RPN()
{
    char s[MAX];
    gets(s);
    int t=atoi(s);
    while(t>0)
    {
        gets(s);
        printf("%d\n",validRPN(s));
        t--;
    }
}

- coder007 on August 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a valid RPN should have n operands with n-1 operators, and at every postion i of the RPN, Num of operands from the 0 to i should always be larger than num of operators from 0 to i.
So we can first count the number of operands and operators, if num(operands) < num(operators) +1, start from the beginning flip num(operators) +1 - num(operands) of operators to operands. else if num(operands) > num(operators) +1, start from the end flip num(operands) -1 - num(operators) of operands to operators.

Then start validate the RPN, loop from beginning to end, at every step validate if num(operands) == num(operators) +1. If not, fix by flipping(between operand and operator), while maintain num(operands) == num(operators) +1.

this should be able to generate a valid RPN, but may not be least steps

- hl on February 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RPN {
	
	public static boolean isValidRPN(String expr){
		
		char arr[] = expr.toCharArray();
		int x = 0;
		
		for(char c: arr){
			
			if ( c == 'x'){
				x++;
			}
			else if ( c == '*'){
				
				if ( x >= 2){
					x--;
				}
				else {
					return false;
				}
			}
		}
		
		if ( x == 1){
			return true;
		}
		
		return false;
	}
	
	//Think of RPN recursively as x(RPN)*
	//The remaining code is self explanatory
	private static int computeToRPN(String expr){
		
		int length = expr.length();
		
		if ( length == 1 ){
		   if (expr.equals("x")){
			   return 0;
		   }
		   else if ( expr.equals("*")){
			   return 1;
		   }
		}
		
		if ( length == 2){
			
			if ( expr.equals("xx") || expr.equals("*x") || expr.equals("x*")){
				return 1;
			}
			else if ( expr.equals("**")){
				return 2;
			}
		}
		
	    char startChar = expr.charAt(0);
	    char endChar = expr.charAt(expr.length()-1);
	    
	    if ( startChar == 'x' ){
	    	
	    	if ( endChar == 'x'){
	    		return 1 + compute2RPN(expr.substring(1,length-1));
	    	}
	    	else if ( endChar == '*'){
	    		return compute2RPN(expr.substring(1,length-1));
	    	}
	    }
	    
	    return 2 + compute2RPN(expr.substring(1, length-1));
	    
	    
	}
	
	public static int compute2RPN(String expr){
		
		if ( isValidRPN(expr) ) return 0;
		else return computeToRPN(expr);
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(compute2RPN("xx*"));
		System.out.println(compute2RPN("xxx**"));
		System.out.println(compute2RPN("xxxx"));
		System.out.println(compute2RPN("*xx"));
		System.out.println(compute2RPN("xxxx*"));
		System.out.println(compute2RPN("**xx"));
		System.out.println(compute2RPN("xx*xx**"));

	}

}

- vin.bitr on October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Gives incorrect answer for x**x. Should be two -- replace first * and add another * at the end. Yours gives 3. (** = 2 + 1 for a string beginning and ending with an x.)

- Alex on January 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you tell me what's wrong witht the following simple algorithm?

s := given string
stack st := empty
for each token t in s 
  if ( t is x)
    push t
  else
    if ( st is empty )
      delete t
    else if st has only one element
      add an 'x' and push it
      pop two 'x's and push one 'x' 
    else
      pop two 'x's and push one 'x'
    endif
endfor

while st is not empty
    if st has only one element
      add 'x' and pushs it 
    endif
    add a '*'
    pop two 'x's and push a 'x'
endwhile

- Hmm on November 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is actually very simple

int minOperations(string input)
	{
		int o = 0;
		int c = 0;
		for(int i=0; i<input.length(); i++)
		{
			if (input[i] == 'X')
			{
				c++;
			}
			else
			{
				if (c< 2)
				{
					o++; // remove '*'
				}
				else
				{
					o -= 1; // caculate new number XX* => X
				}
			}
		}
		return o + c-1;
	}

- BIN on December 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To be a valid RPN, there should be one operand in the stack (as the result of all previous operations).

t[i][k] = number of modifications on the substring of length k to get i operands in the stack
t[1][size-1] gives the answer.

* decreases the number of operands in the stack by one.
x increases the number of operands in the stack by one.

When we read a character at k, we have to decide if we should let it as it is, or if we should delete it, or insert x or insert *.

#include "string.h"
#include "stdio.h"
#include "limits.h"


int min_4(int a, int b, int c, int d){
    int m = a;
    if (b<m)
        m=b;
    if (c<m)
        m=c;
    if (d<m)
        m=d;
    return m;
}

int compute(const char *str){
    printf("%s\n", str);
    size_t size = strlen(str);
    int t[size+1][size];
    memset(t, INT_MAX, sizeof(int)*(size+1)*size);

    t[0][0] = 1;

    char first_char = str[0];
    for (int i=1; i<size+1; i++){
        t[i][0] = (first_char == '*') ? i : i-1;
    }
    for (int k=1; k<size; k++){
        char cur_char = str[k];
        for (int i=0; i<size; i++){
            if (cur_char == '*'){
                t[i][k] = min_4(
                    i+1 >= 2 ? (0 + t[i+1][k-1]) : INT_MAX,
                    i-1 >= 0 ? (1 + t[i-1][k-1]) : INT_MAX,
                               (1 + t[i  ][k-1])          ,
                    i+2 >= 2 ? (1 + t[i+2][k-1]) : INT_MAX 
                );
            } else if (cur_char == 'x'){
                t[i][k] = min_4(
                    i-1 >= 0 ? (0 + t[i-1][k-1]) : INT_MAX,
                    i+1 >= 2 ? (1 + t[i+1][k-1]) : INT_MAX,
                               (1 + t[i  ][k-1])          ,
                    i-2 >= 0 ? (1 + t[i-2][k-1]) : INT_MAX
                );
            }
        }
    }

    return t[1][size-1];
}


int main(){

    printf("result = %d\n", compute("xx*x**xx*x**x**xxx*xxx***x*x*x**xxx*xx**xxxxx**xxxxxx*x*xx*xxxx*xxx**x*xxxx**xxx*xx*xxx*xx"));
    printf("result = %d\n", compute("x"));
    printf("result = %d\n", compute("xx*"));
    printf("result = %d\n", compute("xxx**"));
    printf("result = %d\n", compute("*xx"));
    printf("result = %d\n", compute("xx*xx**"));


}

- on.celebi on August 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <string>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
//---------- macros ----------
#define fp(i,a,b) for(int i=a; i<b; i++)
#define fm(i,a,b) for(int i=a; i>b; i--)

using namespace std;

string reduce(string s)
{
int n = s.length();
for(int i=0; i < n; i++)
if (s[i]=='*')
{
if(i>=2 && s[i-1]=='x' && s[i-2]=='x'){ s.erase(i-1,2);
i=i-2; }
}
return s;
}

int main()
{
int n;
cin >> n;
while(n--)
{
string s;
cin >> s;
int c = 0;
s=reduce(s);
while(s!="x")
{
int firstStar = (int)s.find('*');
if(s.size()==2)
{
if(s=="**")
c = c+2;
else // "x*", "*x", "xx"
c++;
s = "x";
}
else
{
if(firstStar>=0)
{
if((int)s.find('x')<0) // all *'s
{
c = c+s.size()/2+1;
s = "x";
}
else
{
c++;
s[firstStar]= 'x';
}
}
else // all x's replace 1/2 by *.. if odd replace delete last one
{
c = c+s.size()/2;
s = "x";
}
if(s!="x")
s=reduce(s);
}
}
cout << c << endl;
}




//-----------------------------
cout << endl;
// system("pause");
return 0;
}

- ediston on April 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We define
S[i][j] to be the minimum number of operations required to convert substring a[i] .. a[j] into RPN.

Now we have the following recursive formulation of S[i][j]

S[i][j] =
min { (0, if i == j & a[i] is an operand),
          (1, if i == j & a[i] is an operator [either delete it or replace with operand, both have same cost, if they would have been different we would have chosen the minimum]),
          (S[i][j-1] + 1,  [just delete a[j] and convert a[i] .. a[j-1] into RPN]),
          (min_(i<=k<j-1){S[i][k] + S[k+1][j-1]},  if a[j] is an operator [if we convert S[i][k] and S[k+1][j-1] into RPN, and just use the operator a[j] we have a valid RPN, minimize over all such k]),
          min{
                  (min_(i<=k<j-1){S[i][k] + S[k+1][j-1]} + 1,  if a[j] is an operand [if we convert S[i][k] and S[k+1][j-1] into RPN, and convert a[j] into operator we have a valid RPN, minimize over all such k]),
                  (min_(i<=k<j){S[i][k] + S[k+1][j]} + 1,  if a[j] is an operand [if we convert S[i][k] and S[k+1][j] into RPN, and insert an operator we have a valid RPN, minimize over all such k])
                  }
        }

- gimli on April 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Elegant explanation . . . . Thanks gimli :)
Will try to code it . . .

- Saif Hasan on November 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Gimli! Hi! Dont you think that in the step you minimize over k, it isnt a valid RPN? I mean you have a valid RPN in S[i][k] and in S[k+1][j-1] but that does not mean S[i[j-1] is a valid RPN. Say S[i][k] was xx* and S[k+1][j-1] was xxx** then you would say that [xx*][xxx**][*] is a valid RPN?

- samyak on August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

isn't it very simple???

int idx = 0, res = 0;
while (cin >> ch) if (ch == '*') {
     if (idx >= 2) idx -= 1; // remove two from stack top, then push a new one
     else if (idx == 0) res++; // nothing on the stack, remove '*', otherwise will need more moves
     else res++; // we can either add a 'x' or remove the '*', and either way won't affect the stack status.
} else idx++;
if (idx == 0)
    cout << res + 1;
else
    cout << res + idx - 1;

why every body is writing that long?

- Anonymous on April 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yours is wrong because it doesn't work for '*x*'.

- Anonymous on April 15, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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