Python Basics

Hi there! I have my first programming interview coming up, so natrually, I’m really nervous going to do a few practice problems to get more comfortable.

I think I’ll be interviewing in Python since my wise and talented friend (who reads my blog heh) advised me to do so. It’ll probably allow me to write fewer lines of code and make fewer mistakes, but I’ve only started writing Python a few months ago so I definitely need to practice.

• Note: This guide is not complete*

  Note: Much of this content comes from python 3 documentation and the open soruce(!) Runstone Interactive Python Guide which is amazing. I honestly can’t recommend it enough. This blog post is basicaly information from both sources put together in a format that’ll be quicker for me to review in the future. Seriously though, all of the lovely tables are from the runestone guide

##Topics Covered

1. Basics and Arithmetic
2. Control Statements
3. Basic Data Structures/Collections
   • Built-in
     • Lists
     • Strings
     • Tuples - Sets - Dictionaries
     • List Comprehension
   • Other fun - Queues
     • Stacks
     • Deques
   • When should I use what? (Efficiency)
4. Functions
   • Generators / Generator functions
5. Classes
6. Sorts and Searches
7. Error Handling
8. Style

Basics and Arithmetic

###Things to remember:

• Division always returns a float even if it’s a whole number.
• Use // for int division. Always rounds towards minus infinity
• Use ** for powers
• divmod(x,y) returns the pair x//y , x %y. Might be useful for functions like converting numbers to a different base.
• Multiple Assignmentis wonderful x,y = y,x without a temp variable. Easy swapping especially for implementing sorts.
• Use and, not, or instead of &&, || (this ain’t C++, girl!)

##Control Statements Selection Here’s an example. Similar to other languages.

def shouldIWakeUp(time):
	if time < 5:
    	print("Omg go back to sleep ungodly hour")
    elif time < 9:
    	print("You could probably wake up")
    else:
    	print("You're probably late. Look what you did.")  

Iteration Here’s two exampes (while and for). Similar to other languages. Note the use of range() with the for loop.

while true:
	print("This is an infinite loop and" 
    "probably not the greatest example"
    "But at least I'm demonstrating string concatination!")

 for x in range(10, 0, -1):
 	print("Counting down:" + str(x) + "seconds to go!")

##Basic Data Structures/Collections ###Built-in ###The Sequential (Ordered) Collections - Lists, Strings, Tuples

credit to Runestone Interactive

Lists

Strings are immutable (remember this!)

Methods

• str.find(char) and str.find(char, start, end) to find the index of a char in a string (between start and end which are optional). str.rfind() works similarly but finds highest index.
• str.split() splits a string on whitespace or a string argument if supplied.
• str.lower() and str.upper() return str in upper or lowercase.
• Use variabes in strings like so: `print (“Hello I’m %n and %a years old” % (name, age))

There are also some useful constants like string.ascii_lowercase etc.

Tuples are similar to lists but are immutable (even though they can contain mutable objects, like lists). They consist of values seperated by commas and as output are surrounded by ().

Example Code:

t1 = 123, '24', True # make a tuple
x, y, z = t1 # sequence unpacking example
t2 = () # make empty tuple
t3 = ('cats' ,) # note the comma, tuple with one element

###Unordered Collections (Dictionaries and Sets)

Sets

Sets are unordered and denoted using {}. You can use them similarly to sets in the mathematical sense. Similar to mathematical sets, they only contain unique elements. They’re very useful!

*You can also use |, &, - and <= for these operations respectively.

Dictionaries

Dictionaries use hashing to store key:value pairs.

List Comprehension

Note: You can also do this with sets, and dictionaries.

Python lets you iterate through lists in a very nice one-line format. For example l = [ x for x in range(0, 100) if x % 2 == 0] gives a list of even integers between 0 and 99.

Nested List Comprehension

One tip that helps me is to ask what the nestest list statement would be written out in loop form. Here’s a general form for nested loop comprehension:

[ expression
	for x in y if  predicate(x)
    for y in z]

corresponds to

for y in z:
	for x in y:
    	if predicate(x):
        	list.append(expression)

The ordering is pretty similar except for that the expression is before everything else.

Other fun

Stacks

Stacks are FILO (first in last out) structures. You can use a list for a stack (simply use pop() and append() since these are O(1) for lists).

Queues

Queues are FIFO (first in first out) and while you can implement one with a list (.pop(0) and .append()), it’s probably not the best idea since once you pop the first term, all of the other term are shfted over in O(n) time.

Thankfully you can import queue and create one using queue.Queue(). Use q.put(element) and q.get().

####Deques Can function as both queues and stacks.

###When should I use what? (Efficiency)

TODO

Functions

basics

Here’s an example:

def foo(argument):
	result = []
    #do something
    return result #if you want

advanced topics

• You can have optional arguments by assigning a default value for them. (Watch out these are evaluated at the definition of the function, not at each function call).
• You can also have an arbitrary number of arguments by using * or **
• To get command line arguments use sys.argv.

Examples:

def foo(title = "Untitled" , *names, **capitals):
	print (title)
    #names is a tuple of your inputs
    for n in names:
    	print n
     #capitals is a dictionary
   	return capitals.keys() 

Classes

How to define a class

#Basic Class Example
class Animal():
    def  __init__(self, name):
        self.name = name
        self.greet()

    def greet(self):
        print("Hi my name is " + self.name)

#Polymorphism example
class Chicken(Animal):
    def __init__(self, name):
        super().__init__(name)
        self.__eggsLaid = 0 #"private" member variable

    def greet(self):
        print("Cluck! My name is " + self.name)
        
    def layEgg(self):
		self.__eggsLaid += 1
        
class Cow(Animal):
    def greet(self):
        print("Moo! My name is " + self.name)

Private

To make things “private” add double underscores. Note that this isn’t exactly like private in other languages like Java or C++. The underscores just “mangle” the name of the variable so it’s harder to access.

Sample Output:

>>> a = Animal("Annie")
Hi my name is Annie"
>> ch = Chicken("Betty")
Cluck! My name is Betty

Multiple Inheritance and super()

Let’s update our above example. Remember that in Python, multiple polymorphism is depth-first, left to right. This means it will search the first base class (and it’s related clases) first for the attribute and if it’s not found it will go to the next base class.

class FlyingThings:
    def __init__ (self):
        self.inAir = False
        self.greet()

    def greet(self):
        print("Vrooom!")

    def fly(self):
        print("Look at me fly!")
        self.inAir = True


class Chicken(Animal, FlyingThings):
    def __init__(self, name):
        super().__init__(name)
        self.__eggsLaid = 0 #"private" member variable

    def greet(self):
        print("Cluck! My name is " + self.name)
        
    def layEgg(self):
		self.__eggsLaid += 1

Sample Code:

>>> c = Chicken("Betty") 
Cluck! My name is Betty
>>> c.fly()
Look at me fly!

##Searches and Sorts

###Searches ####Linear Simply iterate along until you find your desired object or reach the end. O(n) time worst case.

 def linearSearch(lst, obj):
 	for x in range(0, len(lst)-1):
    	if lst[x] == obj:
        	return True
    return False

####Binary This allows you to search an ordered list in O(log n). First compare to a midpoint value. There are 3 cases:

1. It’s your value (congrats)
2. Your value is less than the midpoint (In which case you know if your value is in the list it falls in the first half of the list so you should search that)
3. Your value is greater than the midpoint (In which case you know if your value is in the list it falls in the second half of the list so you should search that)

Implementation:

def binarySearch(lst, obj):
	# Using iteration since it will take up less space (fewer function frames)
    start, end = 0, len(lst)
    while start != end:
    	midpoint = (start + end -1) // 2
        if obj == lst[midpoint]:
        	return True
        elif obj <= lst[midpoint]:
            end = midpoint - 1
        else 
        	start = midpoint + 1
    return False

###Sorts

I’m just going to write my implementations of them here and a brief summary to review for my interview. However, there are some great explainations and vizualizations out there if you’re starting from scratch.

####Bubble

A pretty simple sort. Compare adjacent terms and swap if they’re in the wrong order. Worst case: $O(n^2)$

def bubSort(lst):
	for i in range(len(lst)-1, 0, -1):
    	for j in range(i):
        	if lst[j] > lst[j+1]:
            	lst[j], lst[j+1] = lst[j+1], lst[j]
     return lst

####Selection

Another simple sort. Make n passes over a list and each time select the largest term and swap it into it’s proper location. Worst case: $O(n^2)$

def selSort(lst):
	for i in range(len(lst), 0, -1):
    	#find the index of the largest in the pass
        indexLargest = 0
    	for j in range(i):
        	if lst[j] > lst[indxLargest]:
            	indexLargest = j
        #swap the largest to the correct spot
        lst[indexLargest], lst[i-1] = lst[i-1], lst[indexLargest] 
    return lst

####Insertion

With insertion sort, we start off with a “sorted” sublist of length 1. With each pass we look at the next element and insert it into the right place, shifting as appropriate. (This increases the length of the sorted sublist by 1 until it emcompasses all elements of the list.) Worst case: $O(n^2)$

def insSort(lst):
    for next in range(1,len(lst)):
        nextElt = lst[next]
        for j in range(next-1, -1, -1):
            if lst[j] > nextElt:
                lst[j+1] = lst[j]
                if j is 0:
                    lst[j] = nextElt
           else:
                lst[j+1] = nextElt
                break
    return lst

#####Merge

Things start to get fun/tricky here! This sort method uses a ‘divide and conquer’ approach to split the list into halves repeatedly, sort the halves and merget them together in order. Let’s give this a go:

note: I went out of my way to try to avoid slicing as an challenge on the RunseStone Interactive page (by passing in start and end indicies) though I ended up using one to make a copy of a list anyways. :(

def mergeSort(lst, start = 0, end = None):
    if end is None:
        end = len(lst)
    if end - start > 1:
        midpoint = (start + end) //2
        mergeSort(lst, start, midpoint)
        mergeSort(lst, midpoint, end)
        # merge the two halves
        copy = lst[:]
        leftIndex = start
        rightIndex = midpoint
        for x in range(start, end):
            if rightIndex >= end or copy[leftIndex] < copy[rightIndex]:
                lst[x] = copy[leftIndex]
                leftIndex += 1
            else:
                lst[x] = copy[rightIndex]
                rightIndex += 1
    return lst

Interesting link on making merge sort more efficient/tail recursive in Python: here

#####Quick

Oy! I’m jetlagged been awake since 3:30 am so I’m going to write this one later!

#####Radix and Bucket

Error Handling

TODO

Style

From the Google Python Style Guide

Naming Conventions I usually Ignore because Underscores smh

• We always use the three double-quote “”” format for doc strings (per PEP 257). A doc string should be organized as a summary line (one physical line) terminated by a period, question mark, or exclamation point, followed by a blank line, followed by the rest of the doc string starting at the same cursor position as the first quote of the first line.

• In Python, pydoc as well as unit tests require modules to be importable. Your code should always check if if __name__ == '__main__': before executing your main program so that the main program is not executed when the module is imported. All code at the top level will be executed when the module is imported. Be careful not to call functions, create objects, or perform other operations that should not be executed when the file is being pydoced.

	def main():
    	  ...

	if __name__ == '__main__':
    	main()