Uber Interview Question
Software DevelopersCountry: India
Interview Type: Written Test
The given sample cases has issues. The possible combinations are wrong.
for first test case:
((()))
(()())
(())
(())()
()(())
()()()
For second test case:
(((())))
((()()))
((()))
((()))()
(()())
(())
(())()
()((()))
()(())
()(())()
()()
()()()
()()()()
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;
}
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.
// add to the hashSet.
if(openBraces == 0) {
hashSet.add(currentPattern);
}
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");
}
}
- NoOne October 29, 2016