Data Structures and Algorithms in Python | Arrays and Strings

2022-07-24 289 words 2 minutes

In this series and in the next few weeks, I will show you Data Structures and Algorithms in Python by some classic interview solutions. Please take a pen, whiteboard, and your laptop. Let’s start learning!

Cheat sheet to Arrays and Strings. And some heads up for you.

Creating a Matrix in Python without numpy

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
new_matrix  = [ [None]*height ] *  width

This way, all the inner list will be pointed to the same address, i.e.

test_list = [[]]*5  
id(test_list[0]) == id(test_list[1])

Do something like this instead.

new_matrix = []  
i = 0  
while i < width:  
    new_matrix.append([]) # add a row  
    j = height - 1  
    while j >= 0:  
        new_matrix[i].append(matrix[j][i])

See example Data-Structures-and-Algorithms-in-Python/Rotate Matrix.py at main · chienhsiang-hung/Data-Structures-and-Algorithms-in-Python (github.com)

Unittest Heads Up

‘in-place’ function

When doing unittest for ‘in-place’ function, remember to deepcopy the test set for looping tests, i.e.

1
2
from copy import deepcopyfor (_input, _output) in  self.test_cases:  
    _input = deepcopy(_input) # don't forget this line, because it changes original input that make your right answer to be wrong

1
2
3
4
5
6
7
8
for text, expected in self.test_cases:  
    _input = deepcopy(text) # don't forget this line, because it changes original input that make your right answer to be wrong  
    for func in self.testable_functions:  
        start = time.perf_counter()  
        func(_input)  
        assert(  
            _input == expected  
        ), f'{func.__name__} failed for value: {text}, output={_input}, expected={expected}'

1
2
3
for (_input, _output) in test_cases:  
    _input_copy = _input.copy()  
    assert zero_matrix(_input_copy) == _output

See example

Test your script: Hsiang | PyScript Hello World (chienhsiang-hung.github.io)

Contact me: Hung, Chien-Hsiang (chienhsiang-hung.github.io)