Two Sigma Interview Question: 1. You have two strings. A te... | Glassdoor

Interview Question

Systems Developer Interview New York, NY

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:
technical, brain teaser, analytical, algorithm
Answer

Interview Answer

3 Answers

5

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
2

#include
#include
#include

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
0

As for the "regex" question, one way to go about solving this would be to create an NFA (non-deterministic finite automaton), turn it into a DFA (deterministic finite automaton), and manually parse the string. If the glob has length L and the query string has length M, constructing the DFA takes O(2^L) time and O(2^L) space while running the query through the DFA takes O(M) time.

Anonymous on Oct 7, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.