Facebook

www.facebook.com

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<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

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

(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.