notebook.community

Edit and run

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 Notation

This 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





In [13]:



    


from IPython.display import Image
Image("../img/big_o1.png", width=600)



    


















    
Out[13]:

Data Structure Operations





In [17]:



    


Image("../img/big_o2.png", width=800)



    


















    
Out[17]:

Array Sorting





In [21]:



    


Image("../img/big_o3.png", width=500)



    


















    
Out[21]:

Example 1

  • time complexity = O(n^2)
  • space complexity = O(1)




In [ ]:



    


counter = 0
for item in query:
    for item2 in query:
        counter += 1

Example 2

  • time complexity = O(n^3)
  • space complexity = O(n)




In [ ]:



    


counter = 0
list1 = []
for item in query:
    list1.append(item)
    for item2 in query:
        for item3 in query:
            counter += 1

cProfile

how much time was spent in various levels of your application





In [5]:



    


import cProfile
cProfile.run('print(10)')



    


















    






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    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        2    0.000    0.000    0.000    0.000 {built-in method posix.getpid}
        3    0.000    0.000    0.000    0.000 {built-in method posix.urandom}
        3    0.000    0.000    0.000    0.000 {method 'acquire' of '_thread.lock' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Remove Duplicates





In [2]:



    


set = set([1,1,2,2,4,5,6])
set



    


















    
Out[2]:








{1, 2, 4, 5, 6}

















In [3]:



    


# convert to list
list(set)



    


















    
Out[3]:








[1, 2, 4, 5, 6]

Sort





In [13]:



    


sort = sorted([4,-1,23,5,6,7,1,4,5])
sort



    


















    
Out[13]:








[-1, 1, 4, 4, 5, 5, 6, 7, 23]

















In [106]:



    


print([4,-1,23,5,6,7,1,4,5].sort())



    


















    






None

Reverse Sort





In [32]:



    


# reverse
sort = sorted([4,1,23,5,6,7,1,4,5],reverse=True)
print(sort)

# OR
print(sort[::-1])



    


















    






[23, 7, 6, 5, 5, 4, 4, 1, 1]
[1, 1, 4, 4, 5, 5, 6, 7, 23]

Basic List





In [15]:



    


list1 = [1,2,3,4,5]



    











In [18]:



    


# last number
list1[-1]



    


















    
Out[18]:








5

















In [85]:



    


# get every 2nd feature
list1[::2]



    


















    
Out[85]:








[1, 3, 5]

















In [97]:



    


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])



    


















    






0
9
[0, 1]
[7, 8]

















In [100]:



    


# filling an empty array
empty = []

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

empty



    


















    
Out[100]:








[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

















In [101]:



    


# remove item
empty.remove(1)
empty



    


















    
Out[101]:








[0, 2, 3, 4, 5, 6, 7, 8, 9]

















In [103]:



    


# sum
sum(empty)



    


















    
Out[103]:








44

Max & Min





In [21]:



    


import math



    











In [23]:



    


list1 = [1,2,3,4,5]
print('max: ',max(list1))
print('min: ',min(list1))



    


















    






max:  5
min:  1

Absolute





In [34]:



    


abs(-10.1)



    


















    
Out[34]:








10.1

Filling





In [63]:



    


'-'.join('abcdef')



    


















    
Out[63]:








'a-b-c-d-e-f'

Splitting





In [72]:



    


# individual split
[i for i in 'ABCDEFG']



    


















    
Out[72]:








['A', 'B', 'C', 'D', 'E', 'F', 'G']

















In [88]:



    


import textwrap
textwrap.wrap('ABCDEFG',2)



    


















    
Out[88]:








['AB', 'CD', 'EF', 'G']

















In [71]:



    


import re
re.findall('.{1,2}', 'ABCDEFG')



    


















    
Out[71]:








['AB', 'CD', 'EF', 'G']

Permutations





In [79]:



    


from itertools import permutations

# permutations but without order
list(permutations(['1','2','3'],2))



    


















    
Out[79]:








[('1', '2'), ('1', '3'), ('2', '1'), ('2', '3'), ('3', '1'), ('3', '2')]

















In [76]:



    


# permutations but with order
from itertools import combinations
list(combinations([1,2,3], 2))



    


















    
Out[76]:








[(1, 2), (1, 3), (2, 3)]

If Else





In [62]:



    


test = 'a'

if test.isupper():
    print('Upper')
elif test.islower():
    print('Lower')



    


















    






Lower

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




In [47]:



    


for i in range(5):
    if i==2:
        break
    print(i)



    


















    






0
1

















In [46]:



    


for i in range(5):
    if i==2:
        continue
    print(i)



    


















    






0
1
3
4

















In [48]:



    


for i in range(5):
    if i==2:
        pass
    print(i)



    


















    






0
1
2
3
4

While Loop





In [108]:



    


i = 1
while i < 6:
    print(i)
    if i == 3:
        break
    i += 1



    


















    






1
2
3

References





In [ ]:

Content source: mapattacker/cheatsheets

Similar notebooks:

notebook.community | gallery | about