## Facebook Interview Question Software Engineer / Developers

• 0

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

Country: United States

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

This is similar to the famous edit distance problem..

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));``````

Comment hidden because of low score. Click to expand.
0

it will fail for "x" resulting in 1

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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) == '*') {
// 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;
}
}``````

Comment hidden because of low score. Click to expand.
0

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) == '*') {
// 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;
}
}``````

Comment hidden because of low score. Click to expand.
0

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) == '*') {
// 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;
}
}``````

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

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 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;
}

Comment hidden because of low score. Click to expand.
0
of 0 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])
}
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0
of 0 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?

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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;

Comment hidden because of low score. Click to expand.
0

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);``````

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

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

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

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

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

}

}``````

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
endif
pop two 'x's and push a 'x'
endwhile``````

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.

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