## Five tough Python interview questions: Anagram, Palindrome, Minimum Spanning Tree, Binary Search Tree, Linked Lists

Posted onMy Udacity mentor said the following about my final Python project: “Peter, to be honest, you are one of the very few students who attempted and passed (the technical interview questions) part (of the DAND+ nanodegree). In fact, I took a look at your (Python) code. It is really good.”

# coding: utf-8

# Final Interview Questions 1- 5 // Peter Bakke

######################

# Question 1 | Anagram

######################”’

Given two strings s and t, determine whether some anagram of t is a substring of s.

For example: if s = “udacity” and t = “ad”, then the function returns True. Your function definition

should look like: question1(s, t) and return a boolean True or False.

”’def question1(s,t):

# Do edge tests

if type(s) != str:

return “>>>Error: s must be a string”if type(t) != str:

return “>>>Error: t must be a string”if len(t) == 0:

return “>>>Error: t must have at least 1 character”if len(s) == 0 :

return “>>>Error: s must have at least 1 character”# Remove any single or multiple spaces in s and t

s = “”.join(s.split())

t = “”.join(t.split())if len(s) < len(t):

return “>>>Error: t must have equal or fewer characters (excluding spaces) than s”# Sort the strings

s_sorted = sorted(s.lower())

t_sorted = sorted(t.lower())if s_sorted == t_sorted: # if true, then exact length anagram match

return True

else:len_t = len(t)

count = 0

for i in range(0, len(t)):find = t[i]

if find in s:

s = s.replace(t[i], “”) # remove all chars from s to solve issue of duplicate chars in s

count += 1if count == len_t:

return True

else:

return Falsedef test1():

# Some edge test cases:

print “######################”

print “# Question 1 | Anagram”

print “######################”,’\n’s = 123

t = ‘ad’

print “s = number… Expect Error: s not a string:”

print question1(s,t),’\n’s = ‘Udacity’

t = 123

print “t = number… Expect Error: t not a string:”

print question1(s,t),’\n’s = ”

t = ‘ad’

print “s is empty… Expect Error:”

print question1(s,t),’\n’s = ‘Udacity’

t = ”

print “t is empty… Expect Error:”

print question1(s,t),’\n’s = ‘Udacity’

t = ‘yticadux’

print “Expect Error: t is longer than s:”

print question1(s,t),’\n’# Valid input test cases:

s = ‘Udacity’

t = ‘ad’

print “s =”,s,”t =”,t,”…Expect True, short anagram quiz case:”

print question1(s,t),’\n’s = ‘Udacity1’

t = ‘city1 dau’

print “s =”,s,”t =”,t,”…Expect True, space in ‘t’:”

print question1(s,t),’\n’s = ‘Udacity’

t = ‘cityb’

print “s =”,s,”t =”,t,”…Expect False:”

print question1(s,t),’\n’s = ‘Udacity’

t = ‘uu’

print “s =”,s,”t =”,t,”…Expect False:”

print question1(s,t),’\n’s = ‘Doctor Who’

t = ‘Torchwood’

print “s =”,s,”t =”,t,”…Expect True, full length anagram with 2 spaces in ‘s’:”

print question1(s,t),’\n’#########################

# Question 2 | Palindrome

#########################”’Given a string a, find the longest palindromic substring contained in a.

Your function definition should look like question2(a…), and return a string.

”’# Function twice called from below to expand through string,looking for palins

# Called for both odd and even palin searches. Note that palins can be even and odd numbered in length.

# Recall that ‘aba’ (len of 3) is a palin. Single letters, the ‘odd’ letter, in that case, ‘b’, are palins, too.

def search_palin(s,len_s,low,hi,start,maxLenFound):# expand outward from hi,low indexes as long as chars match and stay within string’s boundries.

while low >= 0 and hi < len_s and s[low] == s[hi] :

if hi – low + 1 > maxLenFound:

# found a longer palin

# var ‘start’ saves low index which equals start of palin stretching forwrd for maxLenFound chars

start = low

maxLenFound = hi – low + 1 # set the max len of the current palin

low -= 1 # Move left one char in the string

hi += 1 # Move right one char in the string

return (start, maxLenFound)# Find the longest palindromic substring. It can even or odd in length.

def question2(s):if type(s) != str:

return “>>>Error: Input is not a string”len_s = len(s)

if len_s == 0:

return “>>>Error: Input string is empty”if len_s < 2:

return smaxLenFound = 1

start = 0

len_s = len(s)# Loop through string one char at atime, searching for palins

for i in range(1, len_s):# Do ‘even’ palin processing: Find the longest even length palin using starting indexes of ‘i-1’ and ‘i’.

# We are using an iter of ‘i’ = 1 with zero indexing, so we are not going to exceed lower bound.

low = i – 1

hi = i

start,maxLenFound = search_palin(s,len_s,low,hi,start,maxLenFound)# There may also be odd-numbered palins in the string: Do ‘odd’ palin processing.

# Search for any odd length palindromes with a center point of ‘i’ that are longer than we may have found

# in the ‘even’ search above.

# Start the indexes on either side of ‘i’. Since we set the loop iter ‘i’ to 1 and we are using 0 indexing,

# we are fine and will not violate the lower bound. Proceed for search as above in the ‘even’ processing

low = i – 1

hi = i + 1

start,maxLenFound = search_palin(s,len_s,low,hi,start,maxLenFound)return s[start:start + maxLenFound]

def test2():

print “#########################”

print “# Question 2 | Palindrome”

print “#########################\n\n”print “Test case 10101 (expect error: not a string):\n”, question2(10101)

print “\nTest case ” (expect error: an empty string):\n”, question2(“”)

print “\nTest single char ‘a’ (expect ‘a’):\n”, question2(“ab”)

print “\nTest two char ‘bb’ (expect ‘bb’):\n”, question2(“bb”)

print “\nTest no conventional palin in the string. Return first char of string : ‘abcd’ (expect: ‘a’):\n”, question2(“abcd”)

print “\nTest for odd numbered palindrome ‘radararadar’ (expect ‘radararadar’):\n”, question2(“radararadar”)

print “\nTest for two palins in string, one even, other odd, and where odd-length palin is longer ‘aabbb’ (expect: ‘bbb’):\n”,question2(“aabbb”)##################

# Question 3 | MST

##################import Queue as Q

import pprint

from collections import defaultdict”’Given an undirected graph G, find the minimum spanning tree within G. A minimum spanning tree connects

all vertices in a graph with the smallest possible total weight of edges. Your function should take in

and return an adjacency list structured like this:{‘A’: [(‘B’, 2)],

‘B’: [(‘A’, 2), (‘C’, 5)],

‘C’: [(‘B’, 5)]}Vertices are represented as unique strings. The function definition should be question3(G)

”’

class Node(object):

def __init__(self, value):

# ‘Name’ of node

self.value = value

self.edges = []class Edge(object):

def __init__(self, value, node_from, node_to):

# Value = ‘Weight’

self.value = value

self.node_from = node_from

self.node_to = node_toclass Graph(object):

def __init__(self, nodes=[], edges=[]):

self.nodes = nodes

self.edges = edgesdef insert_node(self, new_node_val):

new_node = Node(new_node_val)

self.nodes.append(new_node)def insert_edge(self, new_edge_val, node_from_val, node_to_val):

# New code: Don’t insert B,A if A,B already in the graph

dup = False

for edge_object in self.edges:if ((edge_object.node_from.value == node_to_val) and (edge_object.node_to.value == node_from_val)) or (edge_object.node_from.value == node_from_val) and (edge_object.node_to.value == node_to_val):

dup = True

breakif dup == False: # No duplicate found, insert this edge into graph

from_found = None

to_found = None

for node in self.nodes:

if node_from_val == node.value:

from_found = node

if node_to_val == node.value:

to_found = node

if from_found == None:

from_found = Node(node_from_val)

self.nodes.append(from_found)

if to_found == None:

to_found = Node(node_to_val)

self.nodes.append(to_found)

new_edge = Edge(new_edge_val, from_found, to_found)

from_found.edges.append(new_edge)

to_found.edges.append(new_edge)

self.edges.append(new_edge)def get_edge_list(self):

e_list = []

for e_object in self.edges:

e = (e_object.value, e_object.node_from.value, e_object.node_to.value)

e_list.append(e)

return e_list# For use in pushing and popping edges to/from a PriorityQueue

class edge_q_entry(object):

def __init__(self, weight, nodes_in):

self.weight = weight

self.nodes = nodes_in# I tried to remove the following, but it is needed in Py versions < 3

def __cmp__(self, other):

return cmp(self.weight, other.weight)###################

### Question 3 main

###################def question3(G):

if type(G) != dict:

return “>>>Error: Input must be a dict.”if len(G) <= 1:

return “>>>Error: Input needs more than 1 vertex”# Insert edges into graph from input adjacency matrix … weight, node1, node2

graph = Graph()for key in G:

for each in G[key]:

graph.insert_edge(each[1], key, each[0])edge_q = Q.PriorityQueue()

edge_list = graph.get_edge_list()

# Create edge priority queue

for edg in edge_list:

# break edge string into edge weight edg[0] and edge nodes ie edg[1:]

# and push into the priority queue

edge_q.put(edge_q_entry(edg[0], edg[1:]))vertex_set = set(edge_list)

MST = []

vertex_set = [set(node) for node in G.keys()]

# loop through edges until MST created

for edg in edge_list:edg = edge_q.get() # pop the PriorityQueue which will have the next edge with a minimum weight

# Get current indexes in vertex_set of both nodes for this edge:

# Note that len(vertex_set) changes as nodes are placed in MST

for index in range(len(vertex_set)):

if edg.nodes[0] in vertex_set[index]:

index1 = index

if edg.nodes[1] in vertex_set[index]:

index2 = index# Store the union of node subsets into the smaller node subset and remove the larger node subset

# e.g., [(set[‘A’, ‘B’]), set([‘C’, ‘D’])] becomes [(set[‘A’, ‘B’, ‘C’, ‘D’])]

# Store the edge in MST.

if index1 < index2:

vertex_set[index1] = set.union(vertex_set[index1], vertex_set[index2])

vertex_set.pop(index2) # Often one of the indexes is not in the list, so use set.pop instead of set.remove

MST.append(edg)

if index1 > index2:

vertex_set[index2] = set.union(vertex_set[index1], vertex_set[index2])

vertex_set.pop(index1)

MST.append(edg)# Exit early when all vertices are in MST. Vertex sets reduced from n sets to 1 final set (= MST)

if len(vertex_set) == 1:

break#

# End process MST

## Create the output graph matrix from the MST

graph_matrix = {}

for edge in MST:# Append A,B

if edge.nodes[0] in graph_matrix:

graph_matrix[edge.nodes[0]].append((edge.nodes[1], edge.weight))

else:

graph_matrix[edge.nodes[0]] = [(edge.nodes[1], edge.weight)]# Also append B,A when necessary

if edge.nodes[1] in graph_matrix:

graph_matrix[edge.nodes[1]].append((edge.nodes[0], edge.weight))

else:

graph_matrix[edge.nodes[1]] = [(edge.nodes[0], edge.weight)]pp = pprint.PrettyPrinter(indent=4)

pp.pprint(graph_matrix)def test3():

pp = pprint.PrettyPrinter(indent=4)

print “\n##################”

print “# Question 3 | MST”

print “##################\n\n”print “Test for input is not a dictionary: Expecting an error msg here: ”

print question3(123),’\n\n’print “Test for input of an empty dictionary: Expecting an error msg here: ”

print question3({}),’\n\n’D = {‘A’: [(‘B’, 2)],

‘B’: [(‘A’, 2), (‘C’, 5)],

‘C’: [(‘B’, 5)]}print “Test the quiz case. Expecting: ”

pp.pprint(D),’\n\n’print “\nAnswer:\n”

question3(D)N = {‘A’: [(‘B’, 2), (‘D’, 5)],

‘B’: [(‘A’, 2)],

‘C’: [(‘D’, 3), (‘E’, 5)],

‘D’: [(‘C’, 3), (‘A’, 5)],

‘E’: [(‘F’, 2), (‘C’, 5)],

‘F’: [(‘E’, 2)]}print “\n\nTest non-trivial case. Expecting: ”

pp.pprint(N),’\n\n’print “\nAnswer:\n”

question3(N)

##################

# Question 4 | LCA

##################”’

Find the least common ancestor between two nodes on a binary search tree.

The least common ancestor is the farthest node from the root that is an ancestor of both nodes.

For example, the root is a common ancestor of all nodes on the tree, but if both nodes are descendents

of the root’s left child, then that left child might be the lowest common ancestor. You can assume that

both nodes are in the tree, and the tree itself adheres to all BST properties. The function definition

should look like question4(T, r, n1, n2), where T is the tree represented as a matrix, where the index

of the list is equal to the integer stored in that node and a 1 represents a child node, r is a non-negative

integer representing the root, and n1 and n2 are non-negative integers representing the two nodes

in no particular order. For example, one test case might bequestion4([[0, 1, 0, 0, 0],

[0, 0, 0, 0, 0],

[0, 0, 0, 0, 0],

[1, 0, 0, 0, 1],

[0, 0, 0, 0, 0]],

3,

1,

4)

and the answer would be 3.”’

# Define Binary Node class

class BNode(object):def __init__(self, value):

self.value = value

self.left = None

self.right = None# Define Binary Search Tree class

class BST(object):def __init__(self, root):

self.root = BNode(root)def insert(self, new_val): # From Udacity class

self.insert_helper(self.root, new_val)def insert_helper(self, node, new_val): # From Udacity class

if node.value != new_val: # If same as an entry already in BST, skipif new_val > node.value:

if node.right:

self.insert_helper(node.right, new_val)

else:

node.right = BNode(new_val)

else:

if node.left:

self.insert_helper(node.left, new_val)

else:

node.left = BNode(new_val)def search(self, find_val):

return self.search_helper(self.root, find_val)def search_helper(self, current, find_val):

if current:

if current.value == find_val:

return True

elif current.value < find_val:

return self.search_helper(current.right, find_val)

else:

return self.search_helper(current.left, find_val)

return False#########

# Step 1 Create BST from input matrix

# Step 2 Validate inputs

# Step 3 Find LCA

#########def question4(T,r,n1,n2):

# Check if matrix T is well-formed and represents a valid BST. Are other inputs valid and in bounds?

# Is T an n x n matrix and does each row have a max of two 1’s, i.e. sum of each row = 0 | 1 | 2.error = False

error_msg = ”# Determine if r, n1 & n2 are integers

if type(n1) != int:

error = True

error_msg = ‘>>>ERROR: node 1 is not an integer… value = {0}’.format(n1)

elif type(n2) != int:

error = True

error_msg = ‘>>>ERROR: node 2 is not an integer… value = {0}’.format(n2)

elif type(r) != int:

error = True

error_msg = ‘>>>ERROR: root is not an integer… value = {0}’.format(r)

# is r within range of matrix?

elif (r < 0) or (r > len(T)-1):

error = True

error_msg = ‘>>>ERROR: root out of range… value = {0}’.format(r)

else:

# Check for my definition of well-formed T, which = n x n matrix

for i in range(len(T)): # By row

# Check for n x n . If ANY rows are longeror shorter, error and quit

if (len(T[i]) != len(T)) :

error = True

error_msg = ‘Row ‘,i,’indicates not a n x n matrix’

# and check that sum of T inner arrays <= 2, ie only 2 children allowed

elif (sum(T[i]) > 2):

error = 1

error_msg = ‘Row ‘,i,’indicates more than 2 children’if error == False: # Continue, n1 & n2 are int() AND tree is well formed

root = T[r]

# Create an instance of binary search tree

tree = BST(r)# Create Btree from matrix:

# First, process the root from the matrix T

for j in range(len(T)): # Loop thru items in root row

if T[r][j] == 1:

#print “……………insert”,j

tree.insert(j) # insert the value into the BST# Process all other matrix rows, skipping root done above

for i in range(len(T)):

if i == r: # Skip root row, already processed

continue

else:

for j in range(len(T)): # Loop thru items in row

#print “j:”, j, “…value:”, T[i][j]

if T[i][j] == 1:

#print “……………insert”,j

tree.insert(j) # insert the value into the BST# Determine if n1 & n2 are in the tree

if tree.search(n1) == False:

error = True

error_msg = ‘>>>ERROR: n1 not in BST… value = {0}’.format(n1)

else:

if tree.search(n2) == False:

error = True

error_msg = ‘>>>ERROR: n2 not in BST… value = {0}’.format(n2)#

# No validation or edge errors, OK to find LCA

#

if error == False:# Start with the root. We know from above tests that T is well formed and

# that both n1 and n2 are integers in the BTree

node = tree.root

while node.left != None or node.right != None: # We still have a path# if both vales are less than the current node, we go to the left

if node.value > n1 and node.value > n2:

node = node.left# if both vales are greater than the current node, we go to the right

elif node.value < n1 and node.value < n2:

node = node.right# we find the answer, return it

else:

return node.valueelse:

return error_msg # at least one n is not in tree

else:

return error_msg # Tree format error or other input errordef test4():

print “\n\n##################”

print “# Question 4 | LCA”

print “##################\n”print “# Format = question4(T,r,n1,n1)\n# Where:\n# T = ancestry matrix, r = root, n1 & n2 = comparison nodes\n\n”

# Quiz case:

T =[[0, 1, 0, 0, 0],

[0, 0, 0, 0, 0],

[0, 0, 0, 0, 0],

[1, 0, 0, 0, 1],

[0, 0, 0, 0, 0]]”’

Root = 33

/ \

0 4

\

1”’

print ‘Edge cases: \n’

print ‘Expect error for root not an integer: question4(T,1.1111,0,4):\n’, question4(T,1.1111,0,4), ‘\n’

print ‘Expect error for root not in BST: question4(T,14,0,4):\n’, question4(T,14,0,4), ‘\n’

print ‘Expect error for node 1 not in BST: question4(T,3,22,4):\n’, question4(T,3,22,4), ‘\n’

print ‘Expect error for node 2 not in BST: question4(T,3,0,32):\n’, question4(T,3,0,32), ‘\n\n’print “T =[[0, 1, 0, 0, 0], \n”

print ” [0, 0, 0, 0, 0],\n”

print ” [0, 0, 0, 0, 0],\n”

print ” [1, 0, 0, 0, 1],\n”

print ” [0, 0, 0, 0, 0]]\n”print ‘\n Root = 3\n\n’

print ‘ 3\n’

print ‘ / \ \n’

print ‘ 0 4\n’

print ‘ \ \n’

print ‘ 1 \n’print ‘Quiz case: Expect correct answer of 3 for question4(T,3,1,4):\n’, question4(T,3,1,4), ‘\n’

print ‘Quiz case: Expect correct answer of 0 for question4(T,3,0,1):\n’, question4(T,3,0,1), ‘\n’##########################

# Question 5 | Linked List

##########################”’Find the element in a singly linked list that’s m elements from the end. For example,

if a linked list has 5 elements, the 3rd element from the end is the 3rd element.

The function definition should look like question5(ll, m), where ll is the first node of a linked list

and m is the “mth number from the end”. You should copy/paste the Node class below to use as a

representation of a node in the linked list. Return the value of the node at that position.class Nodell(object):

def __init__(self, data):

self.data = data

self.next = None

”’class Node_ll(object):

def __init__(self, value):

self.value = value

self.next = Noneclass LinkedList(object):

def __init__(self, head=None):

self.head = head # Init head node to Nonedef append(self, new_element):

# Start at the head

current = self.head

# does the head have a pointer in it?

if self.head:

# Yes, move thru linked list

while current.next:

current = current.next# Got to the end of the singly linked list, ie current.next = None

current.next = new_element

else:

# No, just set the head value

self.head = new_elementdef circular_check(self, head):

# Start at head

node1 = head

node2 = headwhile node2 != None:

#print “\n——n1:”,node1.next.value,”n2:”,node2.next.value

node1 = node1.next

#print “++n1:”,node1.next.value,”n2:”,node2.next.value

if node2.next != None:

node2 = node2.next.next

#print “……. n1:”,node1.next.value,”n2:”,node2.next.value

else:

return Falseif node1 is node2:

return Truereturn False

def get_length(self,lst):

if self.circular_check(lst) == True:

return “Linked List is circular”r = 1

# Start at the head

current = self.head

# does the head have a pointer in it?

if self.head:

# Yes, move thru linked list

while current.next:

current = current.next

r += 1else:

# No, just set the head value

self.head = new_elementreturn r # ‘r’ being the length

def question5(llist, m):

error = ”

# Is m an integer?

if type(m) != int:

error = “>>> ERROR: m = ” + str(m) + ” … is not an integer.”

return error# Do we have a Linked List?

if type(llist) != LinkedList:

error = “>>> ERROR: The input list is not a linked list”

return error# is the linked list circular?

if llist.circular_check(llist.head) == True:

error = “>>> ERROR: The linked list is circular”

return error# get the length of ll

length = llist.get_length(llist.head)# Check boundry conditions

if m <= 0 :

error = “>>> ERROR: m = ” + str(m) + ” … m must be greater than 0″

return error

elif m >= length:

error = “>>> ERROR: m = ” + str(m) + ” … m must be less than the length of the linked (list – 1) = ” + str(length-1)

return error# Get the m’th element from end of ll

current = llist.headfor i in range(length – m):

#print current.value

current = current.nextreturn current.value

# Testing

def test5():print “##########################”

print “# Question 5 | Linked List”

print “##########################\n\n”# Test case

# Set up some Elements

n1 = Node_ll(1)

n2 = Node_ll(2)

n3 = Node_ll(3)

n4 = Node_ll(4)

n5 = Node_ll(5)# Set up the Linked List

ll = LinkedList(n1)ll.append(n2)

ll.append(n3)

ll.append(n4)

ll.append(n5)print “question5(ll, 1.1) should generate error, ‘m is not an integer’.\n'”, question5(ll, 1.1), “‘\n”

print “question5(123, 4) should generate error, ‘the input list is not a node-based linked list’.\n'”, question5(123, 4), “‘\n”

print “question5(ll, 0) should generate error, m out of bounds.\n'”, question5(ll, 0), “‘\n”

print “question5(ll, 5) should generate error, m out of bounds.\n'”, question5(ll, 5), “‘\n”

print “question5(ll, 4) should successully return result of 2 :\n”, question5(ll, 4), “\n”

# Test for Circular LL… point last node to first node to create circular linked List

# Error msg should be printed indicating circular list.

n5.next = n1

print “question5(ll, 4) after linking n5 to n1, function should generate error, ‘The linked list is circular’:\n”, question5(ll, 4), “\n”if __name__ == “__main__”:

test1()

test2()

test3()

test4()

test5()# In[ ]: