<jupyter_start><jupyter_text>Basics of Algorithms & Coding Tests this notebook shows some essentials and practical python codes to help in your coding test like hackerrank or codility __Two most important things__ - remove all duplicates before any iterative processing - in a loop, when using if-else, set condition that allows elimination quickly without iterating the entire array __Prep__ - open empty jupyter notebook to test - have your cheatsheet by your side - remember all the useful functions in python - prepare to use regex__During the Test__ - After building your function, attempt using your own test scenarios to input arguments - Hackerrank should be fine as it gives a number of scenarios, but codility sometimes only gives 1 - hence the need to test a few more to check for bugs __Psychology__ - do not give up on a question, and switch to & fro; that only waste more time - prepare for a long extensive coding for each question - keep calm & analyse step by step __Next Step__ - learn about the various algorithims of cos! - dynamic programming, greedy algorithm, etc. - Codility gives a good guide  Big-O NotationThis can be applied to both space & time complexity. Considered a *CPU-bound Performance*  * O(1): *Constant Time* * O(log n): *Logarithmic* * O(n): *Linear Time* * O(n log n): *Loglinear* * O(n^2): *Quadratic*  Big-O Complexity<jupyter_code>from IPython.display import Image
Image("../img/big_o1.png", width=600)<jupyter_output><empty_output><jupyter_text>Data Structure Operations<jupyter_code>Image("../img/big_o2.png", width=800)<jupyter_output><empty_output><jupyter_text>Array Sorting<jupyter_code>Image("../img/big_o3.png", width=500)<jupyter_output><empty_output><jupyter_text>Example 1 * time complexity = O(n^2) * space complexity = O(1)<jupyter_code>counter = 0
for item in query:
    for item2 in query:
        counter += 1<jupyter_output><empty_output><jupyter_text>Example 2 * time complexity = O(n^3) * space complexity = O(n)<jupyter_code>counter = 0
list1 = []
for item in query:
    list1.append(item)
    for item2 in query:
        for item3 in query:
            counter += 1<jupyter_output><empty_output><jupyter_text>cProfilehow much time was spent in various levels of your application<jupyter_code>import cProfile
cProfile.run('print(10)')<jupyter_output>10
         35 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        3    0.000    0.000    0.000    0.000 iostream.py:180(schedule)
        2    0.000    0.000    0.000    0.000 iostream.py:284(_is_master_process)
        2    0.000    0.000    0.000    0.000 iostream.py:297(_schedule_flush)
        2    0.000    0.000    0.000    0.000 iostream.py:342(write)
        3    0.000    0.000    0.000    0.000 iostream.py:87(_event_pipe)
        3    0.000    0.000    0.000    0.000 threading.py:1062(_wait_for_tstate_lock)
        3    0.000    0.000    0.000    0.000 threading.py:1104(is_alive)
        3    0.000    0.000    0.000    0.000 threading.py:506(is_set)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
        1    [...]<jupyter_text>Remove Duplicates<jupyter_code>set = set([1,1,2,2,4,5,6])
set
# convert to list
list(set)<jupyter_output><empty_output><jupyter_text>Sort<jupyter_code>sort = sorted([4,-1,23,5,6,7,1,4,5])
sort
print([4,-1,23,5,6,7,1,4,5].sort())<jupyter_output>None<jupyter_text>Reverse Sort<jupyter_code># reverse
sort = sorted([4,1,23,5,6,7,1,4,5],reverse=True)
print(sort)

# OR
print(sort[::-1])<jupyter_output>[23, 7, 6, 5, 5, 4, 4, 1, 1]
[1, 1, 4, 4, 5, 5, 6, 7, 23]<jupyter_text>Basic List<jupyter_code>list1 = [1,2,3,4,5]
# last number
list1[-1]
# get every 2nd feature
list1[::2] 
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print(array[0])
print(array[-1])

print(array[0:2])
print(array[-3:-1])
# filling an empty array
empty = []

for i in range(10):
    empty.append(i)

empty
# remove item
empty.remove(1)
empty
# sum
sum(empty)<jupyter_output><empty_output><jupyter_text>Max & Min<jupyter_code>import math
list1 = [1,2,3,4,5]
print('max: ',max(list1))
print('min: ',min(list1))<jupyter_output>max:  5
min:  1<jupyter_text>Absolute<jupyter_code>abs(-10.1)<jupyter_output><empty_output><jupyter_text>Filling<jupyter_code>'-'.join('abcdef')<jupyter_output><empty_output><jupyter_text>Splitting<jupyter_code># individual split
[i for i in 'ABCDEFG']
import textwrap
textwrap.wrap('ABCDEFG',2)
import re
re.findall('.{1,2}', 'ABCDEFG')<jupyter_output><empty_output><jupyter_text>Permutations<jupyter_code>from itertools import permutations

# permutations but without order
list(permutations(['1','2','3'],2))
# permutations but with order
from itertools import combinations
list(combinations([1,2,3], 2))<jupyter_output><empty_output><jupyter_text>If Else<jupyter_code>test = 'a'

if test.isupper():
    print('Upper')
elif test.islower():
    print('Lower')<jupyter_output>Lower<jupyter_text>Loops Break, Continue, Pass - __break__ cuts the loop - __continue__ bypass entire code downwards in the current loop on condition - __pass__ ignores code within condition only<jupyter_code>for i in range(5):
    if i==2:
        break
    print(i)
for i in range(5):
    if i==2:
        continue
    print(i)
for i in range(5):
    if i==2:
        pass
    print(i)<jupyter_output>0
1
2
3
4<jupyter_text>While Loop<jupyter_code>i = 1
while i < 6:
    print(i)
    if i == 3:
        break
    i += 1<jupyter_output>1
2
3
{'fraction_non_alphanumeric': 0.1200567476502926, 'fraction_numerical': 0.0679198439439617, 'mean_word_length': 4.053763440860215, 'pattern_counts': {'":': 0, '<': 69, '<?xml version=': 0, '>': 68, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '18', 'dir': 'jupyter-structured-clean-dedup', 'id': '176718', 'license': 'MIT', 'n_tokens_mistral': 2243, 'n_tokens_neox': 2042, 'n_words': 546, 'path': 'python/Basics of Algorithms.ipynb', 'repo_name': 'mapattacker/cheatsheets', 'size': '5639'}