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)
