## Twitter Interview Question for SDE1s

Country: United States

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

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

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

Has anyone solved this question? I have a very lengthy approach for this question but was wondering if it can be done in more feasible ways.

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

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

String[] myList=allExpressionsInLine(test6);

for(String expression: myList){

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) {
simplified=true;
} else if (allOperations[index] == 'R' || allOperations[index] == 'r') {
} else {

}
index++;
}
}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){

if(expression.charAt(0) =='(') {
}

if(totalNests>1) {
return result;
}

}

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){

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

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

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

Ignore the lol at the end. But I passed 3/4 Test Cases with that.

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

Couldnt think of a way to do it that wasn't lengthy. So Came up with what I think is an easy to read solution. No Idea why I was failing the last test case though. Feel Free to blow my mind with whats wrong with it

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

an alternative approach using an AST.

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

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.

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