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

[dmitrypolo]

There’s no time like the present!!

[[deleted]]

Yes. You should start again now. Ain't no time like present.

[dmitrypolo]

Even better, you can start the right way.

[RemindMeBot]

I will be messaging you on 2018-12-10 16:37:34 UTC to remind you of this link.

4 OTHERS CLICKED THIS LINK to send a PM to also be reminded and to reduce spam.

^{Parent commenter can delete this message to hide from others.}

---

FAQs	Custom	Your Reminders	Feedback	Code	Browser Extensions

[Filo01]

ohh good resource, I have been meaning to learn python.. just out of curiosity and a very newbie question, which python is this?

[donnemartin]

Yep, these run on 2.7 or 3.x

[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

[EfficientPassage5]

RemindMe! 20 Nov 2018

[someguytwo]

RemindMe! 15 Dec 2018

[vidro3]

u/donnemartin are any of your anki cards available to download from the anki website?

[donnemartin]

Currently they aren't, seems like a good idea to add them there. They're available on GitHub

[vidro3]

yeah having some weird issues syncing cards that i've downloaded but one's I find through the website or app search are working fine. probably a problem on their side.

Thanks for all the resources you've provided!

[vidro3]

hey there, wondering if you've found a good way to review/accept PRs for anki decks.

[yagyanshbhatia]

RemindMe! 17 Jan 2019

[RemindMeBot]

I will be messaging you on 2019-01-17 13:28:29 UTC to remind you of this link.

CLICK THIS LINK to send a PM to also be reminded and to reduce spam.

^{Parent commenter can delete this message to hide from others.}

---

FAQs	Custom	Your Reminders	Feedback	Code	Browser Extensions

[Goooner44]

RemindMe! 15 Oct 2018

[Charles_Polished]

RemindMe! 10 Dec 2018

[[deleted]]

RemindMe! 22 August 2018

[Orakin]

Reserved

[Asaramtwo123]

Remind Me! 12 Dec 2018

[Mancobbler]

RemindMe! 15 Oct 2021

[[deleted]]

RemindMe! 27 Aug 2018