Facebook

  www.facebook.com
Work in HR? Unlock Free Profile

Facebook Software Engineer Interview Question

I interviewed in Menlo Park, CA and was asked:
"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."
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 1,076 Facebook Interview Reviews

Answers & Comments

0
of 0
votes

(anagrams in an array of strings)

public static void anagrams(String[] ss)
{
    Hashtable<String, ArrayList<String>> words = new Hashtable<String, ArrayList<String>>();
    for (String s : ss)
    {
        String k = s2u(s);
        ArrayList<String> vals = words.get(k);
        if (null == vals) vals = new ArrayList<String>();
        vals.add(s);
        words.put(k, vals);
    }
    for (String k : words.keySet())
    {
        ArrayList<String> matches = words.get(k);
        if (matches.size() < 2) continue;
        for (String match : matches)
        {
                System.out.print(match + " ");
        }
        System.out.println();
    }
}

public static String s2u(String s)
{
    ArrayList<String> chars = new ArrayList<String>();
    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
of 0
votes

public static int numWays(int s)
{
    if (0 == s) return 1;
    int[] counts = new int[s+1];
    for (int i = 0; i <= s; i++)
    {
        int c = 0;
        if ((3 == i) || (5 == i) || (10 == i)) c++;
        if (i-3 > 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
of 1
vote

(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

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.