Python Basics Flashcards
Use only heapush and heappop
from heapq import heappush, heappop
heappussh(pq, (x1,x1))
heappoop(pq)
import collections and use deque
from collections import deque
dq. append(4)
dq. appendleft(5)
dq. pop()
dq. popleft()
Subarray ony [2, 3, 4] from
a = [1, 2, 3, 4, 5, 6, 7, 8]
a[1:4]
How to imported
Sorted list,dictionary, set in python
> > > from sortedcontainers import SortedList
sl = SortedList([‘e’, ‘a’, ‘c’, ‘d’, ‘b’])
sl
SortedList([‘a’, ‘b’, ‘c’, ‘d’, ‘e’])
> > > from sortedcontainers import SortedDict
sd = SortedDict({‘c’: 3, ‘a’: 1, ‘b’: 2})
sd
SortedDict({‘a’: 1, ‘b’: 2, ‘c’: 3})
> > > from sortedcontainers import SortedSet
ss = SortedSet(‘abracadabra’)
ss
SortedSet([‘a’, ‘b’, ‘c’, ‘d’, ‘r’])
Count all letter in “abaaaaaafadfs” and put in map
from collections import Counter
my_str = "Mary had a little lamb" counter = Counter(my_str)
print counter[‘a’]
Elucid algorithm for base conversion
num, n, ans = 134, 0, 0
while num > 0:
bit = num % 2
ans = ans | (bit << n)
num = num // 2
n += 1
print(ans)
Notes: Elucid with the bit on the 0th index
- take the base and mod to get the lowest bit
- divide num = num/base
- go to the next largest bit
Check if the element is in an array eg.
[ “3”, “5”, “”] check if empty string in array
if “” in arr:
pass
Reverse string or array
string1 = string1[::-1]
Block comment
def increase_salary(sal,rating,percentage):
“”” increase salary base on rating and percentage
rating 1 - 2 no increase
rating 3 - 4 increase 5%
rating 4 - 6 increase 10%
"""
String is number
String is letter
> > > ‘A’.isalpha()
True
> > > > ‘3’.isnumber()
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist.
Input: [1,3,4,2,2]
Output: 2
ans = 0
for i in range(32):
a,b = 0,0
for num in nums:
if num & (1 << i) > 0:
a += 1
for index in range(1,len(nums)):
if index & (1 << i) > 0:
b += 1
if a > b:
ans |= 1 << i
return ans
SortedCollection SortedDict
A) add element B) update element value C) Remove element D) Index position based on key E) pop smallest element F) pop largest element
sorted_dict = SortedDict()
SortedDict({‘a’: 4, ‘aa’: 4, ‘abb’: 4, ‘abc’: 5, ‘abd’: 2})
A) add
sorted_dict[“abc”] = 1
B) update
sorted_dict[“abc”] = 5
C) delete
del sorted_dict[“abc”]
D) index
sorted_dict.index([“abc”])
==> 3
F)
>>> sl = SortedList('abcde')
>>> sl.pop()
'e'
>>> sl.pop(-1)
'c'
>>> sl
SortedList(['a', 'b', 'd'])
Deep Copy an array
Array copy:
old_list.copy()
old_list[:]
“12334” or “123ayu456” is a number
string = ‘123ayu456’
print(string.isnumeric())
=> False
string = ‘123456’
print( string.isnumeric())
=> True
datetime_str = ‘09/19/18 13:55:26’ to date time
from datetime import datetime
atetime_object = datetime.strptime(datetime_str, “%m/%d/%y %H:%M:%S”)
Random
random.randrange(a,b)
Union find 1D O(n)*log**(n)
A) what is data structure of pi array
B) what does lookup function return
C) what does union by rank code look like
A)
pi = [[-1,0], [-1.1],[-1,2]…..[-1,n]
for i in range(len(nums)):
index[nums[i]] = i
pi.append([-1, 1])
B) Lookup will take an index of an element in the array and return the index of parent
def lookup(self, pi, index):
currIndex = index
children = []
while pi[currIndex][0] != -1:
currIndex = pi[currIndex][0]
children.append(currIndex)
for childIndex in children:
pi[childIndex][0] = currIndex
return currIndex
C)
idx1, idx2 = index[num], index[num+1]
p1, p2 = self.lookup(pi, idx1), self.lookup(pi, idx2)
if p1 != p2:
if pi[p1][1] >= pi[p2][1]:
pi[p1][1] += pi[p2][1]
pi[p2][0] = p1
else:
pi[p2][1] += pi[p1][1]
pi[p1][0] = p2
Given vowels = [‘a’, ‘e’, ‘i’, ‘o’, ‘i’, ‘u’]
get infex of “e”
# vowels list vowels = ['a', 'e', 'i', 'o', 'i', 'u']
# index of 'e' in vowels
index = vowels.index('e')
print('The index of e:', index)
Sort array
arr = [3, 30, 34, 5, 9]
using sorted and a lambda that take 2 arguments
A) what library and function should be used
B) what does -1 vs 1 vs 0 mean
# sort array using lambda from functools import cmp_to_key arr = [3, 30, 34, 5, 9] res1 = sorted(arr, key=cmp_to_key(lambda x, y: -1 if x > y else x < y or 0), reverse=False) print(res1)
Convert bytes to an int
int.from_bytes(buffer, byteorder=’big’, signed=False)
Given index i , j find the exact middle
- how is
mid = i + (j-i)//2
SortedCollection SortedDict
A) left most insert pos of new element
B) right most insert pos of new element
C) Iterate though the indexes and values
D) get keys
E) get values
F) get items in a tuple
G) get a subsection
- three largest element in the set
- three smallest elements in set
H) Get first item by index (ie smallest item)
A)»_space;> sl = SortedList([10, 11, 12, 13, 14])
»> sl.bisect_left(12)
2
B)»_space;> sl = SortedList([10, 11, 12, 13, 14])
»> sl.bisect_right(12)
3
C)»_space;> sl = SortedList(‘abcdefghij’)
»> it = sl.irange(‘c’, ‘f’)
»> list(it)
[‘c’, ‘d’, ‘e’, ‘f’]
D) list(sorted_dict.keys())
»_space;> [‘a’, ‘aa’, ‘abb’, ‘abd’]
E) list(sorted_dict.values())
»> [4, 4, 4, 2]
F) [(‘a’, 4), (‘aa’, 4), (‘abb’, 4), (‘abd’, 2)]
»> this is opposite of enumerate
G) list(sorted_dict.islice(1,4))
»> [‘aa’, ‘abb’, ‘abd’]
H)
»> sd = SortedDict({‘a’: 1, ‘b’: 2, ‘c’: 3})
»> sd.peekitem()
(‘c’, 3)
power
import math
2**4 or math.pow(2,4)
Enumerate an array
words = [a,b,d,e,g]
for i, word1 in enumerate(words):
print(i, “, “, word1)
math square root
import math
math.sqrt(4)
what is answer for “/”.split()
how to remove the any empty spaces
str1 = “/”
str2 = “/a/b/c
“/”.split() –> [””,””]
res1 = [”/”] + list(filter(str.split()))
—> []
res2 = [”/”] + list(filter(str2.split())
—–> [”/”,”b”,”c”]
casting to int, float, string
int(“9”)
float(“232.32”)
str(1323)
A) What is a usecase for cmp_to_key
B) How is is used with labmda
C) Can you used a regular function instead of a lambda as parameter to cmp_to_keys
A/B) cmp_to_keys is used in a complex sort to wrap a 2 param function its in the functools library
C) A regular function can also be passed into the cmp_to_keys methods
res2 = sorted(arr, key=cmp_to_key(lambda x,y: -1 if x < y else x > y or 0))
print(res2)
Sys constants
import sys
sys. maxsize-1
- sys.maxsize
String is digit
For alphabet
|»_space;> ‘A’.isdigit()
heapq
import heapq
heapq. heapify(self.pool)
heapq. heappush(self.pool, (val, index))
heapq. heappop(self.pool)
Python foor loop from 9 to 0 print each char
for i in range(9,0,-1):
print(i)
Split a linked list in half
slow = head fast = head
while fast != None and fast.next != None and fast.next.next != None:
slow = slow.next
fast = fast.next.next
Dijkstra O(log(V) *E) average case O(N^2) worst case
- with visited set
while len(pq) > 0:
uw,u = heapq.heappop(pq)
if u in visited:
continue
visited.add(u)
for v, vw in graph[u]:
if weights[v] > uw + vw:
weights[v] = uw + vw
heapq.heappush(pq, (weights[v], v))
Bellman For algorithm A) use case? B) edge weight restrictions? C) Time complexity (V*|E|) D) Code
cost = [sys.maxsize] * n
cost[src] = 0
for k in range(K):
for u, v, cost_u_to_v in flights:
if cost[u] == sys.maxsize:
continue;
if cost[v] > costt[u] + cost_u_to_v:
cost[v] = cost[u] + cost_u_to_v
return cost[dst] if cost[dst] != sys.maxsize else -1
Bellman For algorithm A) use cases? B) edge weight restrictions? C) Time complexity V^3 D) Code
for i, j, w in edges:
dis[i][j] = dis[j][i] = w
for i in xrange(n):
dis[i][i] = 0
for k in xrange(n):
for i in xrange(n):
for j in xrange(n):
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
Day difference between date-time objs
diffInDays = datetime.now() - datetime_object
Dijkstra O(N^2)
- no visited set
heapq.heappush(pq,(0, K))
while len(pq) > 0:
uw,u = heapq.heappop(pq)
for v, vw in graph[u]:
if weights[v] > uw + vw:
weights[v] = uw + vw
heapq.heappush(pq, (weights[v], v))
A) What is GCD
B) GCD formula
The greatest common divisor (also known as greatest common factor, highest common divisor or highest common factor) of a set of numbers is the largest positive integer number that devides all the numbers in the set without remainder.
GCD = (a*b) / LCM(a,b)
Strip a string
strVar.strip()
Split word
word = ‘geeks:for:geeks’
print(word.split(‘:’))
Simple date-time constructor
from datetime import datetime
x = datetime(2020, 5, 17)
Open a file and write to a new file
with open(“python-mini.jpg”, “rb”) as fr:
with open("py-cp2.jpg", "wb") as fw:
chunk_size = 4
buffer = fr.read(chunk_size)
print(buffer)
intval = int.from_bytes(buffer, byteorder='big', signed=False)
print(intval)
Sort an array by: planet name, size asc
myList = [ {“planet”: “earth”, “size”: 3},
{ “planet”: “saturn”, “size”: 3},
{“planet”: “venus”, “size”: 2},
{“planet”: “pluto”, “size”: 1},
{“planet”: “neptune”, “size”: 4}
]
planetName = lambda planet: planet["planet"] planetsize = lambda planet: (planet["size"], planet["planet"])
list1 = sorted(myList, key=planetsize, reverse=False)
print(list1)
A) What is LCM
B) code for LCM
- subtracion method
- mod method
the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b
a = 342 b = 46
def lcm(a,b):
if a == 0 or b == 0:
return a
return lcm(b, a%b)
Take smaller number from larger and keep swapping
Turn a = [[1,3,4],[5,4,0]] into a tuple and add it to a set
a = [[1,3,4], [5,4,0]]
print((tuple(a[0]), tuple(a[1])))
===> ((1, 3, 4), (4, 5, 0))
mySet.add(myTuple)
