Twitter Interview Question
SDE1sCountry: United States
public class TwitterProblem {
public static void main(String args[] ) throws Exception {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
ArrayList<String> allStringsToManipulate = new ArrayList<String>();
String test1="(AB)C/";
String test2="(AB)C/S";
String test3="(AB)C/RS";
String test4="A(BC)/RS";
String test5="A(BC)/RSR";
String test6= "(AB)C((DE)F)A(BC)/RSR";
String test7= "(AB)C/S\nA(BC)/RSR";
//String test7= "(AB)C((DE)F)/SSSS";
allStringsToManipulate.add(test1);
allStringsToManipulate.add(test2);
allStringsToManipulate.add(test3);
allStringsToManipulate.add(test4);
allStringsToManipulate.add(test5);
allStringsToManipulate.add(test6);
String[] myList=allExpressionsInLine(test6);
for(String expression: myList){
String answer = stripEverythingAfterBackslash(expression);
char[] allOperations = operations(expression);
if(expression!=null || expression.length()>0){
expression=expression.trim();
expression = expression.replaceAll("\\s","");
boolean simplified=false;
int index = 0;
while (index < allOperations.length) {
if (allOperations[index] == 'S' &&!simplified|| allOperations[index] == 's' &&!simplified) {
String result = simplify(answer);
answer = result;
simplified=true;
} else if (allOperations[index] == 'R' || allOperations[index] == 'r') {
answer = reverse(answer);
} else {
}
index++;
}
System.out.println(answer);
}else{
System.out.println("");
}
}
}
static String[] allExpressionsInLine(String line){
String lines[] = line.split("(\r\n|\r|\n)", -1);
return lines;
}
static char[] operations(String expression){
int counter=0;
boolean begin =false;
for(int i=0;i<expression.length(); i++){
if(begin){
counter++;
}
if(expression.charAt(i)=='/'){
begin=true;
}
}
char[] allOperations = new char[counter];
begin=false;
int index=0;
for(int i=0;i<expression.length(); i++){
if(begin){
allOperations[index]= expression.charAt(i);
index++;
}
if(expression.charAt(i)=='/'){
begin=true;
}
}
return allOperations;
}
static String simplify(String expression){
String answer=expression;
int totalNests = isItWorthSimplifying(answer);
if(expression.charAt(0) =='(') {
answer= removeFirstPairOfParanthesis(expression);
}
if(totalNests>1) {
String result = removeNestedParanthesis(answer, totalNests);
return result;
}
return answer;
}
static int isItWorthSimplifying(String expression){
Stack<Character> openParan = new Stack<>();
int maxNest=0;
for(int i=0;i<expression.length();i++){
char currLetter= expression.charAt(i);
if(currLetter == '('){
openParan.push('(');
}else if(currLetter ==')'){
openParan.pop();
}else{
if(maxNest<openParan.size()){
maxNest=openParan.size();
}
}
}
return maxNest;
}
static String removeNestedParanthesis(String expression, int maxNest){
Stack<Character> openParan = new Stack<>();
StringBuilder word = new StringBuilder("");
int index=0;
while(index<expression.length()){
char currLetter= expression.charAt(index);
if(currLetter == '(' && openParan.size()+1<maxNest){
openParan.push('(');
word.append(currLetter);
}else if(currLetter ==')'){
if(openParan.size()!=maxNest){
word.append(currLetter);
}
openParan.pop();
}else{
if(currLetter == '(' && openParan.size()+1==maxNest){
openParan.push('(');
}else{
word.append(currLetter);
}
}
index++;
}
return word.toString();
}
static String removeFirstPairOfParanthesis(String s){
StringBuilder answer= new StringBuilder("");
boolean firstOpen=false;
boolean firstClosed=false;
for(int i=0; i<s.length(); i++){
if(s.charAt(0)=='(' && !firstOpen){
firstOpen=true;
}else if(s.charAt(i)== ')' && !firstClosed){
firstClosed=true;
}else{
answer.append(s.charAt(i));
}
}
return answer.toString();
}
static String stripEverythingAfterBackslash(String expression){
int end=expression.indexOf('/');
if(end!=-1) {
String newExpression = expression.substring(0, end);
return newExpression;
}
return expression;
}
static String reverse(String expression){
StringBuilder word = new StringBuilder("");
for(int i=expression.length()-1; i>=0; i--){
if(expression.charAt(i)=='(') {
word.append(")");
}else if(expression.charAt(i)==')'){
word.append("(");
}else{
word.append(expression.charAt(i));
}
}
return word.toString();
}
}
. lolol
an alternative approach using an AST.
Where was this question from? Looks like from a contest.
/*
the productions of the expression are
RootExpression = {Term}*
Term = Variable | Expression
Expression = '(' Term ')'
Variable = [a-zA-Z]
the following structs represent a syntax tree, I omitted
access levels to have shorter code
the application of the transformation can be optimized as
SRRS = S
SRSRSRS = SRS
RSS = RS
etc...
*/
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;
struct Term
{
Term() { }
virtual void simplify() { };
virtual void reverse() { };
virtual void print(ostream& os) = 0;
};
struct Variable : Term
{
char name_;
Variable(char name) : name_(name) { }
void print(ostream& os) override { os << name_; }
};
struct Expression : Term
{
vector<Term*> terms_;
// parses and creates expression structure
Expression(istream& is) {
char chr;
while (is.get(chr)) {
if (chr == '(') terms_.push_back(new Expression(is));
else if (chr == ')') break;
else terms_.push_back(new Variable(chr));
}
}
// reverses
void reverse() override {
std::reverse(terms_.begin(), terms_.end());
for (Term* t : terms_) t->reverse();
}
// simplifies
void simplify() override {
Expression *ex = dynamic_cast<Expression*>(*terms_.begin());
if (ex != nullptr) {
ex->simplify();
terms_.erase(terms_.begin());
terms_.insert(terms_.begin(), ex->terms_.begin(), ex->terms_.end());
}
for (Term* t : terms_) t->simplify();
}
// print
void print(ostream& os) override { os << "("; printSubExprs(os); os << ")"; }
void printSubExprs(ostream& os) { for (Term* t : terms_) t->print(os); }
};
struct RootExpression : Expression {
RootExpression(istream& is) : Expression(is) { }
void print(ostream& os) override { printSubExprs(os); }
};
void transformAndPrintExpression(const string& expression, const string& transformation)
{
RootExpression expr = RootExpression(stringstream(expression));
// optimize transformation string
bool reverse = false;
bool simplify = false;
bool simplifyReversed = false;
for (char t : transformation) {
if (t == 'S') {
simplify |= !reverse;
simplifyReversed |= reverse;
} else if (t == 'R') {
reverse = !reverse;
}
}
// apply
if (simplify) {
expr.simplify();
}
if (simplifyReversed) {
expr.reverse();
reverse = !reverse;
expr.simplify();
}
if (reverse) {
expr.reverse();
}
expr.print(cout);
cout << endl;
}
int main()
{
transformAndPrintExpression("(AB)(C(DE))", "SS"); // AB(C(DE))
transformAndPrintExpression("(((AB)C)D)E", "SS"); // ABCDE
transformAndPrintExpression("(((AB)C)D)E", "SR"); // EDCBA
transformAndPrintExpression("(AB)C((DE)F)", "SRS"); // FEDCBA
transformAndPrintExpression("(AB(CD((EF)G)H))(IJ)", "SRS"); // JI(H(GFE)DC)BA
transformAndPrintExpression("(A(B(C)D)E(FGH(IJ)))", "SRRSSRSSRRRSSRS"); // JIHFGE(D(C)B)A
transformAndPrintExpression("(A(B(C)D)E(FGH(IJ)))", "SRS"); // JIHFGE(D(C)B)A
transformAndPrintExpression("(A(BC(D(E((Z)K(L)))F))GH(IJK))", "S"); // A(BC(D(E(ZK(L)))F))GH(IJK)/S
}
Ya even I failed the last test case and my friend who got this question also failed the last test case... Has anyone passed all test cases???
- AT August 27, 2017