Probable Mistake in Solution- First Repeated Character

Data Structures
1

First things first, this is the best course purchase of my professional career. And that is the reason why I’m pointing out this tiny mistake in the hope to make it perfect.

image
image921×518 64.1 KB

This will only work when the repeated characters are consecutive in the input string. But not for something like my name “Pratik Tripathy”.

For the logic to work we need to use 2 loops

        var set = new HashSet<char>();

        foreach (var ch in input.ToLower())
        {
            set.Add(ch);
        }

        foreach (var ch in input)
        {
            if (set.Contains(ch)) return ch;
        }
        return default;

Hope to complete the next 2 Data Structure courses this year.

Thanks,
Pratik

2

Actually this is more an example of bad requirement definition. What is “repeated” in this use case, what is “first”? What about case sensitivity? I’m not a native speaker but would understand that we should return the second “r” (case sensitive) or the second “T” (case insensitive) from your name because they are the first repetitions that we find.

This is quite an important lesson we’ve just learned. Always define the business rules unambigously. Terms in a problem domain sometimes have a subtly different meaning than in IT and customers often don’t see ambiguities in their requirements.

BTW: I see two problems in your solution:

  • Your first loop is case insensitive while your second is case sensitive. You won’t find a single repeated character in “AAAAAHHHH”.
  • You don’t search for repeated characters at all. I haven’t tested it but I’d say you return the first lower-case letter of the input string (which you could have done a lot easier :wink:)
3

Thanks for catching the bug. I should have spend more time on the code than on reporting the issue.
Yes, I missed converting the input to lower-case in the 2nd loop. Even without it did find all repeating lowercase characters.

That said, the meaning of “repeating” is pretty clear even for me.
Anyways, it is great course. Hope you had as much a great time taking it as I do.

4

I doubt that. What does your method return if you pass “Hello” to it?

5

Yes, so silly of me.

Following is the code that works. Guess you’ll need to use Dictionaryand not Set

        input = input.ToLower();
        var dict = new Dictionary<char, int>();

        foreach (var ch in input)
        {
            if (dict.ContainsKey(ch))
            {
                dict[ch]++;
                continue;
            }

            dict[ch] = 1;
        }

        foreach (var ch in input)
        {
            if (dict[ch] > 1) return ch;
        }
        return default;
1 Like
6

Just pointing out that is completely incorrect. Mosh’s solution would find the a’s in “abracadabra”. The problem is that the question is ambiguous because what should we return for “abcba”? Should it return “b” since it is the first time a character shows up for a second time or should it return “a” because it is the “first” character that shows up multiple times in the input. Mosh returned “b” which clarified his intention, but the problem was underspecified.

FYI: many employers will expect you to clarify the ambiguity when you are asked such a question (tests if you are able to deal with ambiguity). So you should ask the interviewer which one should be returned in the ambiguous case.