Facebook Interview Question for Software Engineer / Developers


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 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 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 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 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 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 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. 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 August 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinCostToValidRPN {

	
	public MinCostToValidRPN() {
	}

	final static char VALUE = 'x';
	final static char OPERATOR = '*';
	
	static int evaluate(String s){
		if(s == null){
			throw new IllegalArgumentException();
		}
		
		int n = s.length();
		char[] sc = s.toCharArray();
		
		int result = 0;
		
		// base case
		if(n == 0){
			result = 1;
		} else if (n == 1){
			if(sc[0] == VALUE){
				result = 0;
			} else {
				result = 1;
			}
		} else {
			
			int cost[][][] = new int[n][n][3];
			
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					cost[i][j][0] = j-i+1;
					cost[i][j][1] = j-i+1;
					cost[i][j][2] = j-i+1;
				}
			}
			
			// fill diagonal
			for(int i = 0; i < n; i++){
				char c = sc[i];
				if(c == VALUE){
					cost[i][i][0] = 0;
					cost[i][i][1] = 1;
					cost[i][i][2] = 1;
				} else {
					cost[i][i][0] = 1;
					cost[i][i][1] = 0;
					cost[i][i][2] = 1;
				}
			}
			
			// compose solution for larger span
			for(int length = 2; length < n; length++){
				for(int i = 0; i < n-length; i++){
					helper(sc, cost,i,i+length);
				}
			}
			
			result = cost[0][n-1][0];
		}
		
		return result;
	}
	
	/**
	 * start at i end at j-1
	 */
	  private static void helper(char[] sc, int[][][] cost, int i, int j) {
		  // base - delete until left with X
		  boolean containsValue = false;
		  for(int k = i; k < j; k++){
			  if(sc[k] == VALUE){
				  containsValue = true;
				  break;
			  }
		  }
		  
		  int y = j - i + 1;
		  if(containsValue){
			  y = y-1;
		  }
		  
		for(int k = i-1; k<j-1; k++){
			for(int l = k+1; l<j; l++){
				int c1 = 1;
				if(k>=i){
					c1 = cost[i][k][0];
				}
				
				int c2 = cost[k+1][l][0];
				
				int c3 = 1;
				if(l+1 <=j ){
					c3 = cost[l+1][j][1];
				}
				
				if(c1+c2+c3<y){
					y = c1+c2+c3;
				}
			}
		}
		
		boolean containsOp = false;
		  for(int k = i; k < j; k++){
			  if(sc[k] == OPERATOR){
				  containsOp = true;
				  break;
			  }
		  }
		  
		  int z = j-i+1;
		  if(containsOp){
			  z = z-1;
		  }
		
		  cost[i][j][0] = y;
		  cost[i][j][1] = z;
	}

	public static void main(String[] args){
		   MinCostToValidRPN wrapper = new MinCostToValidRPN();
		   String[] testcase = { "x" , "*" , "xxx**" , "*xx" };
		   
		   for(String s : testcase){
			   System.out.println(s);
			   int c = wrapper.evaluate(s);
			   System.out.println("cost " + c);
		   }
	   }
}

- just_do_it April 08, 2015 | 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 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 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 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 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 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 April 15, 2012 | Flag


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