## Uber Interview Question for Software Developers

Country: India
Interview Type: Written Test

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

``````// ZoomBA
/*
A replacement of '*' -> '(' implies +1
A replacement of '*' -> ')' implies -1
At any point, if the count is < 0, drop the path.
Finally, if the count is == 0, accept the path.
As we have three options, the choices can be made in ternary,
Thus, given k choice locations, there are 3 ** k options
Hence, we can reduce the recursion to iteration.
Using a mixture of imp/dec because of readability
*/

def count_options( s ){
num_stars = sum( s.value ) -> { \$.item == _'*' ? 1 : 0  }
options = set() ; len = #|s|
map = { _'0' : '',  _'1' : '(' , _'2' : ')' , _'(' : 1, _')' : -1 }
for ( select_pattern : [0: 3 ** num_stars ] ){
star_count = -1
ter_pattern = str( select_pattern , 3 )
ter_pattern = '0' ** ( #|ter_pattern | - num_stars ) + ter_pattern
transformed = fold( s.value ,'' ) -> {
\$.prev + ( \$.item == _'*' ? map[ter_pattern[ star_count += 1 ]] :  \$.item )
}
continue( transformed @ options ) // avoid unnecessary stuff
res = sum ( transformed.value ) -> {
break( \$.prev < 0 ){ -len } ; map[\$.item]
}
if ( res == 0 ){ options += transformed }
}
println( str( options,'\n' ) )
size( options ) // return size of options
}
println( count_options( '(*(*)*)' ) )``````

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

The given sample cases has issues. The possible combinations are wrong.
for first test case:
((()))
(()())
(())
(())()
()(())
()()()
For second test case:
(((())))
((()()))
((()))
((()))()
(()())
(())
(())()
()((()))
()(())
()(())()
()()
()()()
()()()()

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

Following is basic recursive working code :

``````#include <iostream>
#include <set>
#include <stack>

using namespace std;

bool balancedPara(string s)
{
stack<char> para;
if(s.size()==0)
return true;
para.push(s[0]);
int i=1;
while(i<s.size())
{
if(s[i] == '(')
para.push(s[i]);
else if(s[i] == ')')
{
if(!para.empty())
para.pop();
else
return false;
}
i++;
}

if(para.empty())
return true;
else
return false;
}

void buildstring(string s, string input ,int pos, int count,set<string> &combs)
{
if(pos<0)
{
if(balancedPara(s) == true)
{
combs.insert(s);
}
return;
}
else
{

int end = pos;
while(input[pos] != '*' && pos>=0)
pos--;
int len = end - pos;
if(count == 0)
{
string newS = input.substr(pos+1, len) + s;
buildstring(newS, input,pos-1, count, combs);
}
else
{
string newS = input.substr(pos+1, len)+ '(' + s;
buildstring(newS, input,pos-1, count-1, combs);
string newS_ = input.substr(pos+1, len)+ ')' + s;
buildstring(newS_, input,pos-1, count-1, combs);
string newS__ = input.substr(pos+1, len) + s;
buildstring(newS__, input,pos-1, count, combs);
}
}

}

void stringcombs(string input, set<string> &combs)
{
int count =0;
for(int i=0;i<input.size();i++)
{
if(input[i] == '*')
count++;
}
string s = "";
buildstring(s,input,input.size()-1, count,combs);
}

void combinations(string input)
{
set<string> comb;
stringcombs(input, comb);
set<string> ::iterator it;
for(it = comb.begin();it!= comb.end();it++)
{
cout<<*it<<endl;
}
}

int main() {
string input = "*(*(**)*";
combinations(input);
return 0;
}``````

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.