Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
I know that this solution is inefficient. But I think that it works, anyway. Execute it with the argument "3", e.g. ./a.out 3
#include <iostream>
#include <vector>
#include <tr1/unordered_set>
#include <string>
#include <cstdlib>
using namespace std;
using namespace std::tr1;
static unordered_set<string> parencomb(vector<string>& paren, int n) {
unordered_set<string> current, prev, result;
string null;
current.insert(null);
int level = 0;
while (level < n) {
for (unordered_set<string>::iterator i = current.begin();
i != current.end();
i++) {
for (vector<string>::iterator j = paren.begin();
j != paren.end();
j++) {
if (0 == i->size() || i->find((*j)[0]) == string::npos) {
prev.insert(*j + *i);
prev.insert(*i + *j);
prev.insert((*j)[0] + *i + (*j)[1]);
int size = i->size();
if (size != 0 && size % 2 == 0) {
int middle = size/2;
prev.insert(i->substr(0, middle) + *j + i->substr(middle, size-middle));
}
}
}
}
result.insert(prev.begin(), prev.end());
current = prev;
level++;
}
return result;
}
int main(int argc, char* argv[]) {
if (argc != 2) {
cout << argv[0] << " <level>" << endl;
exit(0);
}
int n = atoi(argv[1]);
vector<string> paren;
paren.push_back("{}");
paren.push_back("[]");
paren.push_back("()");
unordered_set<string> result = parencomb(paren, n);
for (unordered_set<string>::iterator i = result.begin();
i != result.end();
i++) {
cout << *i << endl;
}
}
static void doBracketPairs(StringBuilder sb, int chaves, int colchetes, int parentesis)
{
int i = 0;
do
{
if (parentesis != 0)
{
doBracketPairs(sb.Insert(i, "()"), chaves, colchetes, parentesis - 1);
sb.Remove(i, 2);
}
if (colchetes != 0)
{
doBracketPairs(sb.Insert(i, "[]"), chaves, colchetes - 1, parentesis);
sb.Remove(i, 2);
}
if (chaves != 0)
{
doBracketPairs(sb.Insert(i, "{}"), chaves - 1, colchetes, parentesis);
sb.Remove(i, 2);
}
} while (i++ < sb.Length);
if ((parentesis == 0) && (colchetes == 0) && (chaves == 0))
{
Console.WriteLine(sb);
}
}
static void BracketPairs(int chaves, int colchetes, int parentesis)
{
StringBuilder sb = new StringBuilder();
doBracketPairs(sb, chaves, colchetes, parentesis);
}
I guess you are given N=string length, where n1+n2+n3 = N/2.
- S O U N D W A V E October 08, 2013Solution is to backtrack-> modify a recent problem involving only n3 (yesterday).