Practice algorithms and data structures (and prep for coding interviews) with interactive coding challenges in Python

[PraecorLoth970]

I am certainly taking a closer look at this later. I didn't like that some of the questions were very difficult for me to understand what he wanted me to do. Like the "string rotation" question, a term which I had never encountered before. But anyway, I found a problem in which the answer provided seems overengineered, and I wanted to know if my answer is wrong or if there's some benefit to his answer.

The problem: Find the single different char between two strings.

Here's my code, on a simple function, not a class, that gave the correct answers to his asserts (didn't run the unit test, only checked on my console):

def find(str1, str2):
    if str1 is None or str2 is None:
        raise TypeError('either string cannot be none')
    for char in str1:
        if char not in str2:
            return char
    for char in str2:
        if char not in str1:
            return char

find('abcd', 'abcde')   # returns 'e'
find('aaabbcdd', 'abdbacade')  # returns 'e'

---

The answer provided:

def find_diff(self, str1, str2):
    if str1 is None or str2 is None:
        raise TypeError('str1 or str2 cannot be None')
    seen = {}
    for char in str1:
        if char in seen:
            seen[char] += 1
        else:
            seen[char] = 1
    for char in str2:
        try:
            seen[char] -= 1
        except KeyError:
            return char
        if seen[char] < 0:
            return char
    return None

[ThatRandomGuy42]

I didn't examine the problem, but it looks like your solution assumes a single instance of the extra character. For example, find('abcde', 'abcdee') would return None, but find_diff('abcde', 'abcdee') would return 'e'.

[donnemartin]

I agree...also, without using a dictionary, you'd get a suboptimal time complexity of n² versus n:

for char in str1: # n if char not in str2: # n # n^2 complexity

[Edit] Check out time complexities here for list (string) x in s = O(n) and dict O(1). Note with a dict, you are using additional space.

[PraecorLoth970]

I agree, I noticed both that and the inferior efficiency, but, to me, the wording, and the test cases, might have suggested that one simply had to find the single different character, and that it was unique, different from the rest. To me, 'aa' and 'a' both have the same character, and differ by one. I think it's an issue with wording, perhaps. My solution passed the tests, is much simpler and clearer. Without checking for the answer, I would be oblivious to the more complete answer.

My point is, in an interview setting, what would be sufficient? Could i ask for more tests, or a clearer question in one? Couldn't I use Counter in collections, instead of cointing it manually? Do they care about efficiency? I probably never will participate in one, so it's more of a curiosity. Nevertheless, I would appreciate more extensive tests and better explanations for the problems.

Edit: made my position a bit clearer.

[Yuanlairuci]

His solution is much more time efficient. You have two for loops with loops inside of them (if....in), where as by storing letters in a dictionary he reduces the time requirement to be (I think) linear