## Facebook Interview Question Software Engineer / Developers

- 0of 0 votes
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

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.

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

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

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.

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

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

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.

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

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

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

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.

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;

}

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;

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

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

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

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

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

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

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

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

}

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

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?

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.

- Srikanth on May 17, 2012 Edit | Flag Reply