careercup / ctci-6th-edition-python Goto Github PK

I think failedPoints should be a set instead of a list so that the lookup time is O(1). Also in the book, it's a hash table.

The solution fails for the following test case lqxwL9 2T5wSg1YKd9Z3iOFL___ (_ is used to represent space at the end).

The response needs to be lqxwL9%202T5wSg1YKd9Z3iOFL but is instead

AssertionError: Lists differ: ['l', 'l', 'q', 'x', 'w', 'L', '9', '%', '2', '0[82 chars] 'L'] != ['l', 'q', 'x', 'w', 'L', '9', '%', '2', '0', '2[77 chars] 'L']

Here's a simpler solution using list comprehension:
Assumes that excess spaces are always at the end

def urlify(url, length):
    return list(''.join(['%20' if char == ' ' else char for char in string[:length]]))

Not sure if such a solution would be acceptable in an interview, though I can't see why not. This is also faster than the original solution.

The solution provided at problem_4.2 is giving the following output for this array:

testArray = [1,2,3,4,8,12,13,99]

print(initiateArrayToBinary(testArray))
(((:L V:1 R:):L V:2 R:(:L V:3 R:)):L V:4 R:((:L V:8 R:):L V:12 R:(:L V:13 R:(:L V:99 R:))))

This will make node 8 to be the right child of root (4) and the left child of another root (12).

There is atleast one failed test case, what would the problem be?

Hi,

I was trying to understand your solution, when I dried run your code on some examples it failed for these kind of test cases.
[1,2,2,3,3,null,null,4,4]

I think general solution required to

`   def isBalanced(self, root):
        if not root:
            return True

        return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)

    def getHeight(self, root):
        if not root:
            return 0

        return 1 + max(self.getHeight(root.left), self.getHeight(root.right))`

  Time complexity will be O(n**2) but will work in all test cases.

Reference :- https://github.com/careercup/CtCI-6th-Edition-Python/blob/master/chapter_04/p02_minimal_tree.py

Can we use this code as an alternative solution for this problem

def print_perms(n):
    result = []
    letter_count_map = {'(':n,')':n}
    print(letter_count_map)
    print_perms_inner(letter_count_map, "", n+n, result)
    return result



def print_perms_inner(letter_count_map, prefix, remaining, result):
    # base case Permutation has been completed
    if remaining == 0:
        # if prefix[0]=='(' and prefix[5]==')':
        result.append(prefix)
        return
    # try remaining letter for next char, and generate remaining permutations
    for character in letter_count_map:
        count = letter_count_map[character]
        if count > 0 and letter_count_map['(']<=letter_count_map[')']:
            letter_count_map[character] -= 1
            print_perms_inner(
                letter_count_map, prefix + character, remaining - 1, result
            )
            letter_count_map[character] = count

I have just changed some part in code of 8.8 permuations with dups

Noticed the question didn't have any tests. Hope this helps!

shared = LinkedList()
shared.add_multiple([1,2,3,4])

a = LinkedList([10,11,12,13,14,15])
b = LinkedList([20,21,22])

a.tail.next = shared.head
a.tail = shared.tail
b.tail.next = shared.head
b.tail = shared.tail

# should be 1
print(intersection(a,b))

In Chapter 2 file 8_Loop_Detection.py there is a bug

This will never advance:

    fast = slow = ll.head

    while fast and fast.next and fast is not slow:

https://github.com/careercup/CtCI-6th-Edition-Python/blob/master/Chapter%202/8_Loop_Detection.py

Here's my version:

from linkedList import LinkedList

class Solution(object):
	def detect_loop(self, ll) -> bool:
		"""
		get node at intersection of cycle
		"""
		
		slow, fast = ll.head, ll.head
		if fast and fast.next:
			fast = fast.next.next
		
		while fast and fast.next and slow is not fast:
			slow, fast = slow.next, fast.next.next

		if fast is None or fast.next is None:
			return None

		slow = ll.head
		fast = fast.next.next
		while fast is not slow:
			fast = fast.next
			slow = slow.next

		return fast


def main(): 
	print()
	s = Solution()
	tests = [
			(LinkedList(), None),
			((LinkedList((3,1,5,9,7,2,1))), None),
			 ]
	ll_a = LinkedList([3,1,5,9,7,2,1])
	ll_a.tail.next = ll_a.head.next.next
	
	tests.append( ((ll_a), 5) )
	for t in tests:
		input_, output = t
		
		# print(input_)
		ret = s.detect_loop(input_)
		# print(ret)
		if ret == output:
			# print(ret)
			print('PASS')
		else:
			print('FAIL')
			# print(input_)
			print('expected:')
			print(output)
			print('got:')
			print(ret)


if __name__ == '__main__':
	main()
	

In the book (p. 90) it specifies that we are to code for an input being a string. Yet this code seems to "cast" into a list before passing into URLify.py.

I would think this converting string to list should be handled by the interviewee, since the question specifies input is of form string.

Can we either :

1. in errata or future versions, clarify this in the question or
2. in the code, properly pass in the test cases as a type str and allow the user to convert in their algorithm?

Thanks in advance!!

I think the solution for 1.6 fails to return the correct answer when string = "aabb" (the answer a2b2 but returns aabb)

Can someone upload python solutions to a lot of the missing chapters/questions? Why must Java have all the solutions and not python?

Hello All,

I just wrote my solution to 2_8. I think m solution is correct and much simpler (however uses O(N) space) But neither the question nor the answer specifies any limitation on the space complexity. I was surprised that my approach was not even mentioned. I've pasted my code below, have I done something wrong?
(I'm also hosting the code at https://gitlab.com/amirha97/coding-practice-project/blob/master/python/chapter2/c2_8.py, more comments there)

def startOfLoop(n):
    d = set()
    while n is not None:
        if n in d:
            return n
        else:
            d.add(n)
        n = n.next

And my Node definition:

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

Update:
The solution to 2_7 also seems to ignore this approach. ( I'm rusty on my Java, but I think java also allows comparing references directly, so this approach should also work) [In case anyone's interested in how I did that: https://gitlab.com/amirha97/coding-practice-project/blob/master/python/chapter2/c2_7.py]

The output liked list is in reverse order. It is the solution to the follow-up.

def rotate_matrix(a):
return map(list, zip(*a[::-1]))

Incorporating a README.txt for relevant problems that require more skill (i.e. linear algebra, trig, Gauss/Zenos summation and calculus) and some numerical analysis know how would make this is a more complete series unto itself. This would incorporate general defenitions, examples, and explanations.

Hi Community,

What is the rule to set up name branch that I can give to my own. Thanks for your answers.

Here is what I got:

def URLify(string, true_len):
newstring = ""
for i in range(true_len):
if string[i] != " ":
newstring = newstring + string[i]
else:
newstring = newstring + "%20"
print(newstring)

URLify("Mr John Smith ",13)

The algorithm in the book us much more complicated than this. Why would this not work instead?

When I try to run somechapter_04 scripts like python chapter_04/p10_check_subtree.py or python3 chapter_04/p10_check_subtree.py, I got an error message like ModuleNotFoundError: No module named 'chapter_04'. This also happens when I try to run python(python3) chapter_04/p09_bst_sequences.py. And I double-checked that I run from the parent directory(CtCI-6th-Edition-Python). What is the problem?

For clarification, my IDE

• Python 3.8.2
• Visual Studio Code
• Using black

This repository is used by a decent amount of people, so pretty sure this is not a mistake or anything and I misunderstood something. Please clarify that for me (or maybe other beginners).

the solution does not makes all the elements of row as 0.
for eg if array is =
[[1,2,3,4,0],
[2,3,4,5,6,8,9,1,0],
[1,2,3,4,5,6,7,8,9,10,11,0]]

then output coming is:
[[0, 0, 0, 0, 0],
[2, 3, 4, 5, 0, 8, 9, 1, 0],
[1, 2, 3, 4, 0, 6, 7, 8, 9, 10, 11, 0]]

although all the rows and columns in this solution should be 0, as mentioned in question.

At this point, it generates random LinkedList and prints out.

Wouldn't it be better to come up with some test cases with solutions to check?

I was wondering that since we know that mask has only one bit, can we use

r = r ^ mask

as opposed to

r &= ~mask

In this method:

def is_palindrome_bit_vector(phrase):
    """checks if a string is a permutation of a palindrome"""
    r = 0
    for c in clean_phrase(phrase):
        val = ord(c)
        mask = 1 << val
        if r & mask:
            r &= ~mask
        else:
            r |= mask
    return (r - 1) & r == 0

What do you think about this one?

from LinkedList import LinkedList


def kth_to_last(ll, k):
    if k <= 0:
        return None

    current = ll.head

    for i in range(k):
        current = current.next

    return current


ll = LinkedList()
ll.generate(10, 0, 99)
print(ll)
print(kth_to_last(ll, ll.__len__() - 2))

Isn't this wrong? What am I missing here?

Hello%20World%20of%20.%20.%20.

while gives:

%

I think the true length is not needed at all, that's how I've written it in the first attempt and it seems to be working fine:

def urlify_algo(string, length):
    isOnSpace = False
    index = 0
    out = ""
    for ch in string:
        if ch == " ":
            isOnSpace = True
            continue
        if isOnSpace:
            out += "%20"
            isOnSpace = False
        out += ch
        index = index + 1
    return out

I could've solved it with split and string.join(list) too, but I just wanted to go old-school.
Your solution might be right, because I've seen a similar solution somewhere else too, but I don't know what I'm missing :)

For palindromes that consist of an even number of characters, such as "No x in Nixon", the algorithm in PalindromePermutation.py does not correctly identify permutations as being permutations of a palindrome.

For example, the code below should evaluate to True, but it actually evaluates to None (and the same goes for any permutation of the input, all of which should evaluate to True):

pal_perm("no x in nixon")

Am I misunderstanding the problem? In any case, it should evaluate to a boolean value. Currently, it will evaluate to None.

Referring to this solution.

I think the current solution may be incorrect. Consider the following tree, which is unbalanced:

I can implement this tree and test if it is balanced with the following code. I just added it to the bottom of the example() function.

tree = BinaryNode(1)
tree.left = BinaryNode(2)
tree.right = BinaryNode(9)
tree.right.left = BinaryNode(10)
tree.left.left = BinaryNode(3)
tree.left.right = BinaryNode(7)
tree.left.right.right = BinaryNode(5)
tree.left.left.left = BinaryNode(6)
tree.left.right.left = BinaryNode(12)
tree.left.right.left.left = BinaryNode(16)
tree.left.right.left.right = BinaryNode(0)
print(is_balanced(tree)) # Should return False

However, this returns True.

OneAway will fail the following tests:

# Check if a string can be converted to another string with a single edit:
data = [
    ('ples', 'pales', True),
    ('pale', 'pas', False) 
]

Is there any specific reason that there isn't a direct string comparison being done and instead a character by character comparison is?

Solution assumes type str is mutable in python when it is obviously immutable. How can this be the solution when it tries to mutate a string?

I was under the impression that python strings are immutable as well. I tried compiling this code and it did indeed fail. In my own working solution I had to create a separate string and return that.

I took a more forward approach rather than the reverse route because of this:

def urlify(str, str_size):
    url_encoded

    for k,v in enumerate(str):
        if k < str_size:
            #size marks end of string
            if v == ' ':
                url_encoded += '%20'
            else:
                url_encoded += v
        else:
            break

    return url_encoded

it doesnt show if the solution correct or not,,it just runs

Hi, in 1.1 Is Unique problem, its mentioned that there should not be a usage of additional data structures. However we have used a list as a hash table to check duplicates. How should we solve without using additional data structure?

Hi,

I am trying to solve this problem using a DoubleLinkedList and moving pointers one from head and one from tail.

The problem is that node.value (node.data in my implementation) is returning a memory allocation instead of the value stored. Here is the code:

from linked_list import LinkedList, DoubleLinkedList

def is_palindrome(l):
    
    ll = DoubleLinkedList(list(l))
    runner1 = ll.head
    runner2 = ll.tail
    print('LIST:')
    print(ll) # -> **prints "1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1"**
    
    for _ in range(len(ll) // 2):
        
        r1, r2 = runner1.data, runner2.data
        print('R1: {},  R2: {}'.format(r1, r2))  **# -> this prints the two integers (1) would return True**
        if r1 != r2: **# this is comparing two <linked_list.Node object at 0x1244aab70> and returns False**
            return False
        
        else:
            runner1 = runner1.next
            runner2 = runner2.prev
    return True

ll_true = LinkedList([1, 2, 3, 4, 5, 4, 3, 2, 1])
print(is_palindrome(ll_true))

I have checked that head and tail acts different as current nodes:

ipdb> runner1
<linked_list.Node object at 0x1244aadd8>

ipdb> runner1.data
<linked_list.Node object at 0x1244aab70>


ipdb> runner1.data.data
1

Why is that?

The solution given for Chapter 3, Problem 2 is the solution for Chapter 3, Problem 1 (MultiStack).
On line 4 in file 32StackMin.py, the solution begins with class MultiStack:

I liked to contribute to this repository by adding more answers, however, I am not sure if all of the code is in Python2 or Python3 and tested with which version. If you can clarify it or add it to README.md it would be great.

@mmermerkaya

Hi , why would you iterate over the sorted string ?
Could I just write the following code?

def check_permutation_by_sort(s1, s2):
    if len(s1)!=len(s2):
        return False
    return sorted(s1)==sorted(s2)

Hey,

I found the following Problem with the solution of 2.1.
If we create a duplicate at the end of the linked list, the tail is removed and the add method does not work anymore.

l1 = LinkedList()
l1.add_multiple([1,2,3,2])
l1 = removeDups(l1)
l1.__str__()
l1.add(4)
l1.__str__()

When trying those lines, you will find, that the 4 is not added the Linked List.

I suggest the following changes:

def removeDups(ll):
    if ll.head is None:
        return
    
    current = ll.head
    found = set([current.value])
    while current.next:
        if current.next.value in found:
            if current.next is ll.tail:
                ll.tail = current
            else:
                current.next = current.next.next
        else:
            found.add(current.next.value)
            current = current.next
    
    return ll

and

def removeDups_FollowUp(ll):
    if ll.head is None:
        return
    
    current = ll.head
    while current:
        runner = current
        while runner.next:
            if runner.next.value == current.value:
                if runner.next is ll.tail:
                    ll.tail = runner
                else:
                    runner.next = runner.next.next
            else:
                runner = runner.next
        current = current.next
    
    return ll

What do you think?

Best regards

F

I would love to be able to contribute missing solutions in Python to some of the chapters.
Can I create a PR for such things?