TWO Sigma
3.3 of 5
www.twosigma.com New York, NY 50 to 149 Employees

TWO SigmaSystems Developer Interview Question

I interviewed in New York, NY and was asked:
"1. You have two strings. A test string and a glob Test string can have a & b, any number of times, any location. Glob can have a, b, ? and *, any number of times, any location. E.g. test= {a,b,a,a,a,a,b,b,b,b,b,b} glob = {a,?, *, b} Now, ? means ANY character, single occurrence. So it's either a or b, one time * means ANY OR NO character, any number of occurrences. E.g. the above glob and test actually match. Problem is: write an algorithm to match glob with test. You MAY NOT use regular expressions :D 2. The input is any string of any length of any characters. Write a program to generate ALL unique permutations of those characters. Unique. You may not store in an array or list, due to memory constraints. e.g. for input of abc your program should give 6 permutations but for aba your program should give 3. Hint: make the list alphabetical."
 Tags: ,   See less 8

Part of a Systems Developer Interview Review - one of 80 TWO Sigma Interview Reviews

3
of 3
public class perm {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input = "abcdefg";
permutation(input, "");
}

private static void permutation(String input, String sofar) {
// TODO Auto-generated method stub

if (input.equals("")) {
System.out.printf("%s,", sofar);
}
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (input.indexOf(c, i + 1) != -1)
continue;
permutation(input.substring(0, i) + input.substring(i + 1), sofar+c);
}
}

}
- Anonymous on Dec 11, 2012 Flag Response
0
of 0
#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

void str_permute(char *str, int start, int end) {
if (start == end) {
cout << str << endl;
return;
}

bool char_set[256];
memset(char_set, 0, sizeof(char_set));

for (int i = start; i != end; ++i) {
if(char_set[str[i]]) {
continue;
}
char_set[str[i]] = true;
swap(str[start], str[i]);
str_permute(str, start+1, end);
swap(str[start], str[i]);
}
}

int main(int argc, char **argv) {
str_permute(argv[1], 0, strlen(argv[1]));
return 0;
}
- Wei Wang on Feb 25, 2013 Flag Response