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

I think the original question is right.

In the first input you mention `(()())` as one of the solution which is not possible to be achieved in `{*{*}*}`

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

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

A simple to understand recursive solution, it will solve for one line in the text file.

``````import java.util.*;

class WildCardCombinations {

// We use this string to maintain each expression constructed (May be valid or invalid) by
// assuming some value to '*'. If the result is valid we add this to the hashSet for deduping it.
private static String currentPattern;
// We add each valid solution to this hashSet for deduping.
private static Set<String> hashSet;

private static void solution(char[] input,int idx, int openBraces) {
// Hitting this condition means that we have processed all characters in input
// by assuming some value ['(',')',''] for each of the '*'
if(idx == input.length) {
// If no openBraces pending we have a balanced braces solution for this combination.
if(openBraces == 0) {
}
return;
}
//Process each character one by one.
switch(input[idx]) {
// We got an open brace add to the currentPattern and recurse with
// increased open brace count
case '{':
currentPattern += "{";
solution(input,idx+1,openBraces+1);
return;
// We got an ending Brace, we should be able to consume one opening brace
// now, if not we have reached an invalid pattern already, else proceed
// by recursing and decreasing the open brace count.
case '}':
if(openBraces > 0) {
currentPattern += "}";
solution(input, idx+1,openBraces-1);
}
return;
// We got a '*', so we try to consume it in 3 ways.
// 1. Do Nothing, so that its treated as being removed.
// 2. Treat as '{'
// 3. Treat as '}'
case '*':
// We cache the currentPattern so that we preserve the values processed
// till now, when moving to subsequent iteration.
String temp = new String(currentPattern);
// 1
solution(input,idx+1,openBraces);
// 2
currentPattern = temp + "{";
solution(input,idx+1,openBraces+1);
// 3
if(openBraces > 0) {
currentPattern = temp + "}";
solution(input, idx+1, openBraces-1);
}
}
}

public static void main(String[] args) {
String input = "{*{*}*}"; //"*{*{**}*";
currentPattern = "";
hashSet = new HashSet<String>();

solution(input.toCharArray(),0,0);

for(String s : hashSet) {
System.out.println(s);
}
System.out.println("Total " + hashSet.size() + " Solutions");
}
}``````

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.