Author Archives: Mark Faridani

Python Basics – A quick python review

by

I have been working with Python since 2007 on various projects. I have mostly used it on prototyping projects, some web development and some data analysis work. Python has changed a lot. However I still need to sometimes go and review the basics. Here are some useful notes that I have taken over many years. In case you also like to remind yourself of some of the basic operations and techniques in Python these might come in handy. I am also interested to know some of the simple Python principles and techniques that you find useful

Python Variables

Assignments
Python
1
2
# Python variable
a = [1,'cow', True]

For deleting a variable you can use delete

Assignments
Python
1
2
# delete variables
del a, b

Python style guide uses underscores for specific purposes _ is used for a throw away variable or for referring to the previous results in the interactive Python. Leading __var__ are usually used for reserved variables. Leading single underscore is usually used for internal variables _var.

 

Keys in Dictionaries
Python has a very easy to use dictionary data structure. Dictionaries are highly efficient that provide O(1) insertion and read operations (as opposed to O(n) in a list). However, it is very easy to accidentally degrade your dictionary to a list and dramatically impact its efficiency. Let’s assume you like to check to know whether your dictionary contains a key. There are two ways to do that. The first method is checking key in dict and the second one is key in dict.keys(). Both will return the correct value. However, the second method is dramatically slower than the first since dict.keys() is in fact a list and not a dictionary anymore

Dictionaries
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
>>> d = {'a':1, 'b':2}
>>> d['a']
1
>>> d['b']
2
>>> 'a' in d         #this is the correct way of looking up keys in dictionaries ( O(1) complexity )
True
>>> 'a' in d.keys()  #this is the incorrect way of looking up keys in dictionaries ( O(n) complexity )
True
>>> type(d.keys())
<type 'list'>
>>> type(d)
<type 'dict'>

IF Statements 

Unlike other programing languages there is no multi branching in Python (no “case” and “switch” statements). Python also uses “elif” for else if

Assignments
Python
1
2
3
4
5
6
7
8
# Flow control
a = 1234
if a == '4321':
    # do this
elif a == 1234:
    # do this
else:
    # do this

Various Assignment Operations

Assignments
Python
1
2
3
4
5
# various assignment operations in Python
a = 1234
a, b = 1234, 4321
a, b = b, a #switching variables without using a third variable
[a, b] = [1234,4321]

Zip and Map

Zip and Map are two of the most useful functions in Python. Zip allows you to make tuples of data from lists. Map allows you to apply functions to tuples.

Assignments
Python
1
2
3
4
5
6
7
8
9
10
11
12
# Zip and Map
a = [1, 2, 3]
b = [3, 2, 1]
c = zip(a,b)
print c
 
[(1,3), (2,2), (3,1)]
 
# map allows us to apply a function to each Tuple
map(sum, zip(a,b))
 
[4, 4, 4]

You can define your own function by using lambda. Below is the same sum function

lambda
Python
1
2
map(lambda pair:sum(pair), zip(a,b))
[4, 4, 4]


Python Classes

In Python the __init__ method is called automatically at the instantiation stage. Every time Python instantiates an object it will call this method.

List Comprehensions in Python
List comprehensions are one of the most elegant language constructs in Python. Let’s assume we want to produce a list of all numbers between 0 and 100 that are divisible by both 5 and 3. This can be done by the following code

List Comprehensions
Python
1
2
3
>>> [x for x in range(0,101) if ( (x%3)==0 and (x%5)==0)]
 
[0, 15, 30, 45, 60, 75, 90]

List Slicing in Python
Python has excellent syntaxt for working with its lists. Lists in Python are all zero-indexed so the first element of a list a = [1,2,3] can be found by a[0]. You can also take a range of elements, for example if you like to take the second element all the way to the end you would use a[1:]. Interestingly if you like to take the second element until the end but excluding the last element you would use a[1:-1]. List slicing notation also accepts steps, for example if you like to take the former list but slip every other element, the you would use a[1:-1:2]. You can also use negative steps. See this link for more.

The following code sample allows you to generate bigrams for a sentence

bigrams
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>>> sentence = " the quick brown fox jumps over the lazy dog "
>>> a = b = sentence.split()
>>> c = zip(a[0:-1],b[1:])
>>> c
 
[('the', 'quick'), ('quick', 'brown'), ('brown', 'fox'), ('fox', 'jumps'), ('jumps', 'over'), ('over', 'the'), ('the', 'lazy'), ('lazy', 'dog')]
 
>>> d = map(list, c)
>>> d
 
[['the', 'quick'], ['quick', 'brown'], ['brown', 'fox'], ['fox', 'jumps'], ['jumps', 'over'], ['over', 'the'], ['the', 'lazy'], ['lazy', 'dog']]
 
>>> e = map(' '.join, d)
>>> e
 
['the quick', 'quick brown', 'brown fox', 'fox jumps', 'jumps over', 'over the', 'the lazy', 'lazy dog']

Object Serialization in Python
Python has two modules for serialization cPickle and Marshal. You can compress each serialized object by using the gzip module.

Raising an Exception in Python
If you like to manually raise an arbitrary exception then you can do the following

exceptions
Python
1
raise Exception("An error occurred!")

Python: Reversing the order of words in a string and in place

by

Question: Say we want to write a function in Python that takes a string and reverses the order of the words in place. How would you do it?

Answer: In python, C# and Java (and many other languages) strings are immutable so this is not possible to do. But let’s say we use the list representation of the string and want to reverse the order of words in place. The following is the shortest code that I can come up with.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def reverse(si):
s = list(reversed(si))
s.append(" ")
l = len(s)
prevspace = 0
for i in range(0, l):
if s[i]==" ":
s[prevspace:i] = reversed(s[prevspace:i])
prevspace = i+1
 
return "".join(s[:-1])
 
print reverse(" this is a test")
print reverse("this is   another test")
print reverse("   this is the final  t est   ")

Merge Sort in Python

by

Below is the most compact merge sort function that I can come up with in Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Merge sort in python
 
def mergesort(arr):
# base case
if len(arr) <=1:
return arr
# devide and conquer
arr1 = mergesort(arr[0:len(arr)/2])
arr2 = mergesort(arr[len(arr)/2:])
# combine stage
pointer1 = 0
pointer2 = 0
out_arr = []
while (pointer1<len(arr1)) and (pointer2<len(arr2)):
if arr1[pointer1]<arr2[pointer2]:
out_arr.append(arr1[pointer1])
pointer1 += 1
else:
out_arr.append(arr2[pointer2])
pointer2 += 1
out_arr += arr1[pointer1:] + arr2[pointer2:]
 
return out_arr

And the following are the unit tests for it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# unit testing mergesort
tests = 100
maxlength = 100
 
from random import randrange, random
for i in range(0, tests):
tmp = [random() for j in range(0, randrange(0,maxlength))]
print tmp
a = tmp[:]
b = tmp[:]
print a
print b
c = mergesort(a)
d = sorted(b)
if c != d:
print "b: ", d
print "a: ", c
raise ValueError('test failed '+ tmp)
a = [i for i in range(11,1,-1)]
print a
print mergesort(a)
print mergesort([1,2])
print mergesort([])
print mergesort([6,5,4,3,3,3,1])
print mergesort([4, 65, 2, -31, 0, 99, 99, 83, 782, 1])

Quick Sort in Python

by

Below is the most compact implementation of the quick sort algorithm that I could come up with

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Quick sort in python
 
def qsort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)/2]
smaller, larger, equal =[], [], []
for i in arr:
if i<pivot:
smaller.append(i)
elif i > pivot:
larger.append(i)
else:
equal.append(i)
return qsort(smaller) + equal + qsort(larger)

And below are its unit tests

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
tests = 100
maxlength = 100
 
from random import randrange, random
for i in range(0, tests):
tmp = [random() for j in range(0, randrange(0,maxlength))]
print tmp
a = tmp[:]
b = tmp[:]
print a
print b
c = qsort(a)
d = sorted(b)
if c != d:
print "b: ", d
print "a: ", c
raise ValueError('test failed '+ tmp)
a = [i for i in range(11,1,-1)]
print a
print qsort(a)
print qsort([1,2])
print qsort([])
print qsort([6,5,4,3,3,3,1])
print qsort([4, 65, 2, -31, 0, 99, 99, 83, 782, 1])

atoi() in Python

by

Sometimes in an interview question you might be asked to implement the atoi() function that exists in C. Below is the most compact version of atoi() that I can come up with. atoi() taks an string and converts that to an integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def atoi(s):
n, notnegative = 0, 1
if s[0]=="-":
notnegative = -1
s = s[1:]
for i in s:
n = n*10 + ord(i)-ord("0")
return notnegative*n
 
# __tests__
print atoi("0")
print atoi("-10")
print atoi("-4001")
print atoi("23124341")

Find the maximum depth of nested parentheses in a string

by

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
S = "( a(b) (dd) (a) (d(e(f((((())))))g)h) I (j(k)l)m)";
 
 
# with stack
stack = []
maxdepth = 0
for ch in S:
    if ch == "(":
        stack.append("(") #O(1)
        maxdepth = max(maxdepth, len(stack)) #len: O(1), comparison O(2)
    elif ch == ")":
        stack.pop()
print maxdepth
 
# without using stack
currentdepth = 0
maxdepth = 0
for ch in S:
    if ch == "(":
        currentdepth +=1
    elif ch ==")":
        currentdepth -=1
    maxdepth = max(maxdepth, currentdepth)    
print maxdepth

Pairs of elements that add up to n

by

Question: find all the elements in a list or array that add up to n

Answer:

1
2
3
4
5
6
7
8
9
def findallpairs(mylist, n):
mydict = set({})
for i in mylist:
if (max(i, n-i), min(i, n-i)) in mydict:
print (max(i, n-i), min(i, n-i))
else:
mydict.add((max(i, n-i), min(i, n-i)))
 
print findallpairs([1,2,3,4,5,6,7], 8)