Data AnalysisDigital Marketing

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

My 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.”

udacity-Peter-bakke

# 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 += 1

if count == len_t:
return True
else:
return False

def 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 s

maxLenFound = 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_to

class Graph(object):
def __init__(self, nodes=[], edges=[]):
self.nodes = nodes
self.edges = edges

def 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
break

if 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 be

question4([[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, skip

if 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.value

else:
return error_msg # at least one n is not in tree
else:
return error_msg # Tree format error or other input error

def 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 = 3

3
/ \
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 = None

class LinkedList(object):

def __init__(self, head=None):
self.head = head # Init head node to None

def 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_element

def circular_check(self, head):

# Start at head
node1 = head
node2 = head

while 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 False

if node1 is node2:
return True

return 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 += 1

else:
# No, just set the head value
self.head = new_element

return 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.head

for i in range(length – m):
#print current.value
current = current.next

return 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[ ]: