donnemartin / interactive-coding-challenges Goto Github PK

The bitwise add 2 integers solution will hit infinite loop for negative integers. The carry will keep increasing if the bit length is not bounded.
Proposed solution:

	def sum_two(self,a,b):
                #max bit length, change to 32 for 32bit
		max_positive = 2 ** 64
		min_negative = -2 ** 64

		while b != 0:
			if b == max_positive:
				return a ^ min_negative
			a,b = a ^ b,(a&b)<<1
		return a

List of Jupyter Notebook supported languages.

If you are interested in contributing challenges with languages other than Python, please share your thoughts on how we could best approach topics such as:

• Repo structure
• README challenge list
• Installation instructions
• Etc

Are there any plans for SQL or numpy df questions (or any sort of query)?
In software engineering interviews for data infra or science teams, I've been asked these.

I would like to start contributing some common ones I've faced if this repository aligns with these type of questions as well.

The following solution does not work:

class ReverseStringAlt(object):

    def reverse_string_alt(string):
        if string:
            return string[::-1]
        return string

    def reverse_string_alt2(string):
        if string:
            return ''.join(reversed(string))
        return string

hi, I noticed that test case below is not a valid binary search tree, it might be valid if we delete the node 6, but in your challenge notebook marked it as valid. I'm not sure I should delete the node 6 and send a pr or just submit an issue, so I just submit an issue.
Valid:

      5
    /   \
   5     8
  / \   /
 4   6 7

Notebooks contain some minor PEP8 issues, mostly related to whitespace.

When I do:

pip install -r requirements.txt

and install ipython[notebook]

I have this problem when I open a terminal in ubuntu and Debian.

Traceback (most recent call last):
File "/usr/lib/python2.7/runpy.py", line 162, in _run_module_as_main
"main", fname, loader, pkg_name)
File "/usr/lib/python2.7/runpy.py", line 72, in _run_code
exec code in run_globals
File "/usr/local/lib/python2.7/dist-packages/virtualenvwrapper/hook_loader.py", line 16, in
from stevedore import ExtensionManager
File "/usr/local/lib/python2.7/dist-packages/stevedore/init.py", line 11, in
from .extension import ExtensionManager
File "/usr/local/lib/python2.7/dist-packages/stevedore/extension.py", line 17, in
import pkg_resources
File "/usr/local/lib/python2.7/dist-packages/pkg_resources/init.py", line 72, in
import packaging.requirements
File "/usr/local/lib/python2.7/dist-packages/packaging/requirements.py", line 59, in
MARKER_EXPR = originalTextFor(MARKER_EXPR())("marker")
TypeError: call() takes exactly 2 arguments (1 given)
virtualenvwrapper.sh: There was a problem running the initialization hooks.

If Python could not import the module virtualenvwrapper.hook_loader,
check that virtualenvwrapper has been installed for
VIRTUALENVWRAPPER_PYTHON=/usr/bin/python and that PATH is
set properly.

This error happen twice in a Deban virtual machine and in an Ubuntu

Hi Everyone,

I'll be temporarily unavailable starting April 17 and won't be able to respond to issues or pull requests. I'm hoping I'll be available in a couple of weeks, but I might not be responsive for several weeks.

Sorry for the inconvenience.

cc: @wchargin @rockybutler @eamanu @Duroktar @gmazzola @betterin30days

-Donne

In some of the challenges (ex: hash_map), Python Lists are referred as being the same as linked lists.
In fact, Python Lists are implemented using arrays of pointers (that explains random access and O(1) appends).

You can see this FAQ: https://docs.python.org/2/faq/design.html#how-are-lists-implemented
Or a short explanation on: http://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented

In compress_challenge, the problem is specified as:

Problem: Compress a string such that 'AAABCCDDDD' becomes 'A3BC2D4'. Only compress the string if it saves space.

However, the last three test cases test for:

assert_equal(func('AAABCCDDDDE'), 'A3BC2D4E')
assert_equal(func('BAAACCDDDD'), 'BA3C2D4')
assert_equal(func('AAABAACCDDDD'), 'A3BA2C2D4')

shouldn't they be:

assert_equal(func('AAABCCDDDDE'), 'A3BCCD4E')
assert_equal(func('BAAACCDDDD'), 'BA3CCD4')
assert_equal(func('AAABAACCDDDD'), 'A3BAACCD4')

since compressing 2 repeated characters doesn't save space?

Broken:

• Check out the template challenge and solution notebooks to help you get started
• Share your thoughts in this issue.

Although not broken, the sample authors link to actual GitHub members, need to link to just GitHub.com:

• This notebook was prepared by Joe and Jane. Source and license info is on GitHub.

In /stacks_queues/sort_stack/sort_stack_solution.ipynb there's a small phrasing issue on the line:
"While buffer is empty or buffer top is > than temp\n".

It should be "While buffer is not empty or buffer top is > than temp\n" as implied in the code below:

class MyStack(Stack):

    def sort(self):
        buff = MyStack()
        while not self.is_empty():
            temp = self.pop()
            while not buff.is_empty() and buff.peek() > temp:
                self.push(buff.pop())
            buff.push(temp)
        return buff

in ./recursion_dynamic/fibonacci/fibonacci_challenge.ipynb

Test Cases
n = 0 -> 0
n = 1 -> 0
n > 1 -> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

should be

Test Cases
n = 0 -> 0
n = 1 -> 1
n > 1 -> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

The current solution could be spooked with 2 inputs : "ABCDFE" and "FOOBCDBCDE". The logic will create a map that will still end up having the last letter E in sequence.

According to Wikipedia , they are filling in 0 instead of taking the max (left, above) for characters that aren't matched.

It fails for a tree like this:

                3
           /        \
       2              5
     /             /        \
  1             4          6
                                \
                                 7

This is not a balanced tree, but the solution returns True.

When you start the IPython/Jupyter notebook at the top-level of the repo, as suggested by the readme, it presents the directory listing and it is not clear where to start and which directories contain challenges and which do not (e.g. the templates directory).

If you go into a challenge category directory, again, it is not clear in which (suggested) order the challenges (if any) should be tackled.

I suggest naming the category and challenge directories with a two-digit number prefix, so that they are ordered like in the readme. Example:

Categories:

01_arrays_strings
02_linked_lists
....

Challenges:

01_unique_chars
02_permutation
...

Hints could be provided to help users incrementally arrive at the desired solution. Users could %load these hints into the Challenge Notebook when needed.

Hints

Run the following cell(s) for a hint:

%load hint1.txt

%load hint2.txt

Running the cell(s) would would load the contents of the accompanying hint file:

# %load hint1.txt
Consider a brute force solution that scans each 
element and compares it with every other element.

# %load hint2.txt
The brute force solution has a time complexity of O(n^2).  
A hash map lookup could help make this linear.

For instance:

    # Partition = 10
    # Input: 4, 3, 13, 8, 10, 1, 10, 12
    # Output: 4, 3, 8, 1, 10, 10, 13, 12

fails.

Why not include the stack pointer at the top of each stack so you can do this with a single num_stacks * (stack_size + 1) array?

Also, it is not clear why abs_index is part of the interface (as that is not part of the stack interface). Its purpose should be made clear in the challenge notebook.

In http://nbviewer.ipython.org/github/donnemartin/interactive-coding-challenges/blob/master/arrays_strings/rotation/rotation_challenge.ipynb, I think that for better compressing single characters may be left as they are. For example "AAABCCDDDD" is expected to be compressed as "A3B1C2D4"; however, "A3BCCD4" looks like to me a better compressing.

I'm not sure this is necessarily an issue: The current solution of linked_list_challenge.ipynb uses an iterative approach to getting the length of a linked list, resulting in an O(n) time complexity for that method. Another solution could be to have an instance variable, updating this variable whenever we insert_to_front(), append(), or delete() and return this variable whenever we call the length method (thus O(1)) . I'm not a python expert, so I don't know how "Pythonic" this solution is, but I got it working in my notebook and can submit a PR if this is appropriate

I didn't find anywhere about the flashcard gen script, could you share it?

If the script was outdated, I'm glad to update the script if you could kindly provide the script.

https://en.wikipedia.org/wiki/Longest_common_substring_problem

according to wikipedia, because the substring is contiguous, we should end up with something like:
(I don't know python, sorry)

// preamble omitted
  let mut res = 0;
  for i in 0..a.len()+1 {
    for j in 0..b.len()+1 {
      if i == 0 || j == 0 { dist[i][j] = 0; }
      else if a[i - 1] == b[j - 1] {
        dist[i][j] = 1 + dist[i - 1][j - 1];
        res = std::cmp::max(res, dist[i][j]);
      }
      else {
        dist[i][j] = 0;
      }
    }
  }

Other solutions I've found also do something similar: http://www.geeksforgeeks.org/longest-common-substring/

However, the longest common substring implemented here does:

# preamble omitted
        for i in range(num_rows):
            for j in range(num_cols):
                if i == 0 or j == 0:
                    T[i][j] = 0
                elif str0[j - 1] != str1[i - 1]:
                    T[i][j] = max(T[i][j - 1],
                                  T[i - 1][j])
                else:
                    T[i][j] = T[i - 1][j - 1] + 1

despite stating:

Is a substring a contiguous block of chars?
Yes

It looks as though the solution is modelling the recurrence relation for subsequence not substring. Have a look at the geeksforgeeks solution for subsequence:

http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

It's very similar to this repo's implementation of 'substring'

in the delete method of graphs_trees/trie/trie_solution.ipynb:

while parent is not None:
# As we are propagating the delete up the
# parents, if this node has children, stop
# here to prevent orphaning its children.
# Or
# if this node is a terminating node that is
# not the terminating node of the input word,
# stop to prevent removing the associated word.
if node.children or node.terminates:
return
del parent.children[node.key]
node = parent
parent = parent.parent

When you traverse from child to parent, the parent will always at least contain one child. Thus the parent.children[node.key] will never be deleted.

In the chellenge compress there are tests:

assert_equal(func(None), None)
        assert_equal(func(''), '')
        assert_equal(func('AABBCC'), 'AABBCC')
        assert_equal(func('AAABCCDDDDE'), 'A3BC2D4E')
        assert_equal(func('BAAACCDDDD'), 'BA3C2D4')
        assert_equal(func('AAABAACCDDDD'), 'A3BA2C2D4')

The question states compress only if saves space but while a test is not changing the 2 consecutive letters as seen:

assert_equal(func('AABBCC'), 'AABBCC')

While the other exemples such as this one:

assert_equal(func('AAABCCDDDDE'), 'A3BC2D4E')

compresses it.

If this is not intended and if I'm not terribly wrong 😄 then some of the tests must be changed.

I would kindly offer my help to change them and open a PR if you would kindly point which ones need change (again if I'm correct)

Thank you for your awesome challenges.

I am new to python, I know there is print and pdb.set_trace().

1. Could you tell me where is the printed message?
2. And how to make pdb.set_trace() work?

Calls such as:

print('One element')
data = [5]
func(data)
assert_equal(sorted_data, [5])

Should be:

print('One element')
data = [5]
sorted_data = func(data)
assert_equal(sorted_data, [5])

I'm using python3.6 and when I ran pip install -r requirements.txt to install all required packages the notebook did not work properly. When opening a notebook from the project I got this error:
/usr/bin/python: no module named ipykernel_launcher

Upon googling this issue I found the advice to reinstall this packages so I ran:

pip3 uninstall ipykernel_launcher
pip3 install ipykernel_launcher

This fixed that import issue, but when I proceeded to open a notebook I got this error:
ImportError: cannot import name 'generator_to_async_generator'

This did not have an easy fix on the internet, so I basically uninstalled all installed packages by running:

pip3 uninstall -r requirements.txt
and proceeded to install jupyter notebook with pip by running:

pip3 install jupyter

This seems to have fixed the issue, all notebooks I have tried so far have worked without issue. But I feel this should be added in the README or did I do something wrong?

源码地址

In the stack challenge (stacks_queues/stack/stack_challenge), more specifically in the pop() method, shouldn't we be removing references from the node we want to pop? Only updating the top reference doesn't remove the reference the old top (popped item) has to the new top.

The wording makes it sound like installing the notebook dependencies is an optional step. The command is actually needed to run the notebooks.

Before

Or if you want to also get the dependencies for the IPython Notebook:

pip install "ipython[notebook]"

After

Install the dependencies for the IPython Notebook:

pip install "ipython[notebook]"

It might be helpful to have a folder in the repo containing challenges that need some minor tweaks or polishing.

The following anchors don't go to the correct sections due to case issues:
If you need to install Nose, see the Nose Installation section.
If you need to install IPython/Jupyter Notebook, see the Notebook Installation section.

https://github.com/donnemartin/interactive-coding-challenges/blob/master/linked_lists/linked_list/linked_list_solution.ipynb

When self.head == None, the node returned is not the node assigned to self.head. self.head should be assigned node.

I just found that the delete method also has a bug. When self.head.data == data, self.head is set to None and that deletes the whole linkedlist and not just the head... self.head should be set to self.head.next in that case.

Reference the following issue:

#11

Space is listed as O(log n), which is the case if the tree is balanced. If the tree is not balanced it can perform similar to a linked list with O(n) in the worst case.

Instead, space should be listed as O(h), where h is the height of the tree.

https://mybinder.org/ Should I make a binder ? :) Or if there is a binder link, it's well hidden.

Input:

Input 1: 6->5->4
Input 2: 9->8->7->9->9

Expected:

Result: 5->4->2->0->0->1

Actual:

Result: 5->4->2->0->1

Longest Common Subsequence algorithm solution doesn't work on.

Here is the test case from Tushar Roy's video on Longest Common Subsequence (https://www.youtube.com/watch?v=NnD96abizww).

class TestLongestCommonSubseq(object):
    def test_another(self):
        str_comp = StringCompare()
        str0 = 'ABCDAF'
        str1 = 'ACBCF'
        expected = 'ABCF'
        assert_equal(str_comp.longest_common_subseq(str0, str1), expected)

The solution says

     13                 if i == 0 or j == 0:
     14                     T[i][j] = 0
---> 15                 elif str0[j - 1] != str1[i - 1]:
     16                     T[i][j] = max(T[i][j - 1],
     17                                   T[i - 1][j])

IndexError: string index out of range

You are using sum of prime numbers logic for checking anagrams which might result in inconsistent results like for example aa and b are my inputs which are not anagram to each other . In your case of addition the result will come as both are anagrams to each other.

Hence please fix the logic to product than using sum.

For your reference —-
https://forum.cosmoquest.org/showthread.php?167873-Using-Prime-Numbers-to-Check-if-Two-Words-are-Anagrams
https://hastebin.com/adazekoyet.swift
https://stackoverflow.com/questions/13215789/comparing-anagrams-using-prime-numbers

• https://nose.readthedocs.io/en/latest/#note-to-users

  Nose has been in maintenance mode for the past several years and will likely cease without a new person/team to take over maintainership. New projects should consider using Nose2, py.test, or just plain unittest/unittest2.

I think there are some mistakes in sort_stack's pseudocode and test cases description.

The test cases section says:

• Empty stack -> None

But it should be returning an empty stack, not None.

Under the algorithm section, it says

" * While buffer is not empty or buffer top is > than temp\n",

but the code says

while not buff.is_empty() and temp < buff.peek():

so that should be an and, not an or.

It also says

"* Our buffer will hold elements in reverse sorted order, smallest at the top\n",

but the buffer stores elements in sorted order, largest at the top. Otherwise, how could we return buffer as our answer when the output should have the largest element at the top?

I also suggest changing

"* Store the current top element in a temp variable\n",

to

" * Pop the current top element of stack into a temp variable\n",

This clarifies that the top element is not just copied to a temp variable, but rather popped off into the temp variable. Also this happens within the outer while loop, not before.

Here's the code version of the solution for reference:

class MyStackSimplified(Stack):

    def sort(self):
        buff = MyStack()
        while not self.is_empty():
            temp = self.pop()
            while not buff.is_empty() and temp < buff.peek():
                self.push(buff.pop())
            buff.push(temp)
        return buff

I've submitted pull request #263 for this issue.

Discussion also found in this Stack Overflow post.

Solution is:

pip uninstall ipython
pip install "ipython[all]"

It may be worth including a requirements.txt to this repository so that it's easy to install all the necessary dependancies in a virtualenv.

The compress_string notebook as the following test cases:

• None -> None
• '' -> ''
• 'AABBCC' -> 'AABBCC'
• 'AAABCCDDDD' -> 'A3B1C2D4'

Shouldn't the third test case result be A2B2C2?
If not then the description of this challenge needs some more details on how this result is consistent with the last test result.

If you run Tools -> Check Media in Anki, the following files are reported as missing:

dijkstra.gif
selection_sort.gif
eratosthenes.gif
quicksort_wikipedia.gif
merge_sort.gif
insertion_sort.gif

    def test_two_sum(self):
        solution = Solution()
        assert_raises(TypeError, solution.two_sum, None, None)
        assert_raises(ValueError, solution.two_sum, [], 0)
        target = 7
        nums = [1, 3, 2, -7, 5]
        expected = [2, 4]
        assert_equal(solution.two_sum(nums, target), expected)
        print('Success: test_two_sum')

[4, 2] should also be a valid answer. Unittest has an assertItemsEqual method, I'm not sure if nose has that too. I'm happy to write a PR for this, it's trivial to fix.

"Hi, i am trying to open quick_sort_solution.ipynb code. and i am getting this text
"" Sorry, something went wrong. Reload?"" instead of the code."

The solution for bst_validate won't work if the tree has a node with the value of -sys.maxsize.

A suggested tweak would be to use None instead of sys.maxsize and -sys.maxsize.

 class BstValidate(Bst):

    def validate(self):
        if self.root is None:
            raise TypeError('No root node')
        return self._validate(self.root)

    def _validate(self, node, minimum=None, maximum=None):
        if node is None:
            return True

        if not ((minimum is None or node.data>minimum) and (maximum is None or node.data<=maximum)):
            return False

        if not self._validate(node.left, minimum, node.data):
            return False

        if not self._validate(node.right, node.data, maximum):
            return False
        
        return True

I would be happy to prepare a PR if this makes sense to you.