donnemartin / interactive-coding-challenges Goto Github PK
View Code? Open in Web Editor NEW120+ interactive Python coding interview challenges (algorithms and data structures). Includes Anki flashcards.
License: Other
120+ interactive Python coding interview challenges (algorithms and data structures). Includes Anki flashcards.
License: Other
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.
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
...
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.
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.
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
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
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.
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.
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'
Hints could be provided to help users incrementally arrive at the desired solution. Users could %load these hints into the Challenge Notebook when needed.
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.
The compress_string notebook as the following test cases:
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.
https://mybinder.org/ Should I make a binder ? :) Or if there is a binder link, it's well hidden.
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.
The wording makes it sound like installing the notebook dependencies is an optional step. The command is actually needed to run the notebooks.
Or if you want to also get the dependencies for the IPython Notebook:
pip install "ipython[notebook]"
Install the dependencies for the IPython Notebook:
pip install "ipython[notebook]"
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)
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
Notebooks contain some minor PEP8 issues, mostly related to whitespace.
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.
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 am trying to open quick_sort_solution.ipynb code. and i am getting this text
"" Sorry, something went wrong. Reload?"" instead of the code."
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.
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.
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
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 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.
Discussion also found in this Stack Overflow post.
Solution is:
pip uninstall ipython
pip install "ipython[all]"
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:
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...
Test Cases
n = 0 -> 0
n = 1 -> 1
n > 1 -> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
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
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
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.
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.
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
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.
For instance:
# Partition = 10
# Input: 4, 3, 13, 8, 10, 1, 10, 12
# Output: 4, 3, 8, 1, 10, 10, 13, 12
fails.
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
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?
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
Broken:
Although not broken, the sample authors link to actual GitHub members, need to link to just GitHub.com:
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?
Reference the following issue:
Thank you for your awesome challenges.
I am new to python, I know there is print
and pdb.set_trace()
.
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.
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.
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])
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
It might be helpful to have a folder in the repo containing challenges that need some minor tweaks or polishing.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.