Facebook Interview Question: Providing an algorithm for co... | Glassdoor

Interview Question

Software Engineer Interview Menlo Park, CA

Providing an algorithm for combinations(n, k), not because

  of it's complexity, just because it took my the majority of the interview to understand that this was the problem I was solving - it was not made very clear at all.
Answer

Interview Answer

3 Answers

0

(anagrams in an array of strings)

public static void anagrams(String[] ss)
{
    Hashtable> words = new Hashtable>();
    for (String s : ss)
    {
        String k = s2u(s);
        ArrayList vals = words.get(k);
        if (null == vals) vals = new ArrayList();
        vals.add(s);
        words.put(k, vals);
    }
    for (String k : words.keySet())
    {
        ArrayList matches = words.get(k);
        if (matches.size() chars = new ArrayList();
    for (int i = 0; i < s.length(); i++)
    {
        chars.add(s.substring(i, i+1));
    }
    Collections.sort(chars);
    String o = "";
    for (String c : chars)
    {
        o = o + c;
    }
    return o;
}

Rahul on May 3, 2013
0

public static int numWays(int s)
{
    if (0 == s) return 1;
    int[] counts = new int[s+1];
    for (int i = 0; i 0) c += counts[i-3];
        if (i-5 > 0) c += counts[i-5];
        if (i-10 > 0) c += counts[i-10];
        counts[i] = c;
    }
    return counts[s];
}

Rahul on May 3, 2013
0

(combinations)

int combinations(int n, int k)
{
    int m = 1;
    for (int i = n; i > n - k; i--)
    {
        m *= i;
    }
    for (int i = 2; i <= k; i++)
    {
        m /= i;
    }
    return m;
}

Rahul on May 3, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.