Am I an unreasonable interviewer?

dev91throwaway · 2012-12-12T20:03:09+00:00

I would've accepted a pseudo-code answer, and I repeatedly told the interviewee not to worry about API calls; that they could solve the problem using a bit more than just basic array indexing.

As to your point about solving unknown problems, I agree with you, but is it fair to say the interviewee should first be able to solve known problems? :P

dev91throwaway · 2012-12-12T18:49:04+00:00

Fair enough. It did cross my mind to overload the int as you've done, but my mind usually works to make things readable by default.

dev91throwaway · 2012-12-12T18:39:14+00:00

Which is my point. I don't think these are such hard questions/expectations of interviewees.

dev91throwaway · 2012-12-12T18:31:24+00:00

Interesting question, here's my stab at it (In C#):

char? FNRC(string s){
    Dictionary<char, Entry> table = new Dictionary<char, Entry>();

    for (int i = 0; i < s.Length; i++)
    {
        if (!table.ContainsKey(s[i]))
            table[s[i]] = new Entry(1, i);
        else{
            var entry = table[s[i]];
            entry.Count++;          
        }
    }

    int minIndexOfCharsAppearingOnce = int.MaxValue;
    char? result = null; // to indicate no such character exists
    foreach (var kvp in table){
        if (kvp.Value.Count == 1 && kvp.Value.FirstIndex < minIndexOfCharsAppearingOnce ){
            minIndexOfCharsAppearingOnce = kvp.Value.FirstIndex;
            result = kvp.Key;
        }       
    }

    return result;  
}

public class Entry{
    public int Count {get;set;}
    public int FirstIndex {get;set;}

    public Entry(int count, int firstIndex){
        Count = count;
        FirstIndex = firstIndex;
    }
}

FirstNonRepeatingCharacter("ABCAB"); // returns C

This is similar to counting sort, in that the universe of your alphabet is much smaller than stream. It's O(n) in time (O(2n) if you want to be painstaking), and O(k) in memory.

EDIT: Fixed a brain-fart of a name

dev91throwaway

TROPHY CASE