For this project, you will be given five technical interviewing questions on a variety of topics discussed in the technical interviewing course. You should write up a clean and efficient answer in Python, as well as a text explanation of the efficiency of your code and your design choices. A qualified reviewer will look over your answer and give you feedback on anything that might be awesome or lacking—is your solution the most efficient one possible? Are you doing a good job of explaining your thoughts? Is your code elegant and easy to read?

Answer the following questions:

Question 1

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.

In [29]:
# issubset() is used to check whether one set is a subset of the other set
def question1(s,t):
    return set(list(t)).issubset(list(s)) # Complexity Class O(len(t))

s1 = 'udacity'
t1 = 'ad'
s2 = 'udacity'
t2 = 'da'
s3 = 'udacity'
t3 = 'xyz'

print question1(s1,t1), question1(s2,t2), question1(s3,t3)
True True False

Case1 : t1 is a subset of s1

Case2 : t2 is a subset of s2

Case3 : t3 is a subset of s3

Case4 : t4 is not a subset of s4

Question 2

Given a string a, find the longest palindromic substring contained in a. Your function definition should look like question2(a), and return a string.

In [27]:
"""
Question 2
Given a string a, find the longest palindromic substring contained in a.
Your function definition should look like question2(a), and return a string.
"""
# @param {string} s input string
# @return {bool} if string is palindrome or not
def isPalindrome(s):
    if not s:
        return False
    # reverse compare
    return s == s[::-1]

# @param {string} s input string
# @return {string} the longest palindromic substring
def question2(s):
    if not s:
        return ""

    n = len(s)
    longest, low, high = 0, 0, 0
    for i in xrange(0, n):
        for j in xrange(i + 1, n + 1):
            substr = s[i:j]
            if isPalindrome(substr) and len(substr) > longest:
                longest = len(substr)
                low, high = i, j
    # construct longest substr
    result = s[low:high]
    return result

print question2("aaabc")
print question2("forgeeksskeegfor")
print question2(None)
aaa
geeksskeeg

Question 3

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)

In [44]:
"""
Gained intuitions from these videos:
Disjoint Sets : https://www.youtube.com/watch?v=UBY4sF86KEY
Kruskal Algorithm : https://www.youtube.com/watch?v=5xosHRdxqHA
"""
parent = {}
rank = {}

# initialize disjoint sets. each set contains one vertice. rank is used to keep the 
# tree MST flat as much as possible for faster search.
def make_set(vertice):
    parent[vertice] = vertice
    rank[vertice] = 0

# find the set to which this vertice belongs
def find(vertice):
    if parent[vertice] != vertice:
        parent[vertice] = find(parent[vertice])
    return parent[vertice]

# merge the sets represented by these two given root nodes
def union(vertice1, vertice2):
    root1 = find(vertice1)
    root2 = find(vertice2)
    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root1] = root2
            if rank[root1] == rank[root2]: rank[root2] += 1

# perform kruskal algorithm to find mst
def kruskal(vertices, edges):
    minimum_spanning_tree = set()
    for vertice in vertices:
        make_set(vertice)

    # sort edges by increasing weights
    edges = sorted(edges, key=lambda x : x[2])
    
    for edge in edges:
        vertice1, vertice2, wt = edge
        if find(vertice1) != find(vertice2):
            union(vertice1, vertice2)
            minimum_spanning_tree.add(edge)
            
    return minimum_spanning_tree

# main
def question3(G):
    
    graph = G
    vertices = []
    edges = []
    
    # pre process given input graph and extract all vertices and edges
    for vertice in graph.keys():
        # collect vertices
        vertices.append(vertice)
        # build edge tuples
        verticeEdges = graph[vertice]
        for verticeEdge in verticeEdges:
            fromNode = vertice
            toNode, weight = verticeEdge
            edges.append((fromNode, toNode, weight))
        
    # perform Kruskal algo
    ms_tree = kruskal(vertices, edges)
    
    # post process results into the required output format
    output = {}
    for node in ms_tree:
        fromNode, toNode, weight = node
        
        if toNode < fromNode:
            fromNode = node[1]
            toNode = node[0]
            
        if fromNode in output:
            output[fromNode].append((toNode, weight))
        else:
            output[fromNode] = [(toNode, weight)]
            
    return output

print question3({})
print question3({'A': [('B', 2)],
 'B': [('A', 2), ('C', 5)], 
 'C': [('B', 5)]})
print question3({'A': [('B', 2), ('C', 7)],
     'B': [('A', 1), ('C', 5), ('D', 3), ('E', 4)],
     'C': [('C', 7), ('D', 7), ('E', 6)],
     'D': [('B', 3), ('C', 4), ('E', 2)],
     'E': [('B', 4), ('D', 5)],
    })
{}
{'A': [('B', 2)], 'B': [('C', 5)]}
{'A': [('B', 1)], 'C': [('D', 4)], 'B': [('D', 3)], 'D': [('E', 2)]}

Question 4

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.

In [53]:
head = None

class Node(object):
    def __init__(self, data):
        self.data = data
        self.right = None
        self.left = None

# Function to insert a new node at the beginning
def push_right(node, new_data):
    new_node = Node(new_data)
    node.right = new_node
    return new_node

# Function to insert a new node at the beginning
def push_left(node, new_data):
    new_node = Node(new_data)
    node.left = new_node
    return new_node

# Function to find LCA of n1 and n2. The function assumes
# that both n1 and n2 are present in BST
def lca(head, n1, n2):
    # Base Case
    if head is None:
        return None

    # If both n1 and n2 are smaller than root, then LCA
    # lies in left
    if(head.data > n1 and head.data > n2):
        return lca(head.left, n1, n2)

    # If both n1 and n2 are greater than root, then LCA
    # lies in right
    if(head.data < n1 and head.data < n2):
        return lca(head.right, n1, n2)

    return head.data


def question4(mat, root, n1, n2):
    global head
    # Make BST
    head = Node(root)
    head.left, head.right = None, None
    node_value = 0
    tmp_right, tmp_left = None, None
    node_list = []
    for elem in mat[root]:
        if elem:
            if(node_value>root):
                node_list.append(push_right(head, node_value))
            else:
                node_list.append(push_left(head, node_value))
        node_value += 1

    tmp_node = node_list.pop(0)
    while tmp_node != None:
        node_value = 0
        for elem in mat[tmp_node.data]:
            if elem:
                if(node_value>tmp_node.data):
                    node_list.append(push_right(tmp_node, node_value))
                else:
                    node_list.append(push_left(tmp_node, node_value))
            node_value += 1
        if node_list == []:
            break
        else:
            tmp_node = node_list.pop(0)

    return lca(head, n1, n2)

# Main program
print 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)
3

Question 5

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 Node(object):
  def __init__(self, data):
    self.data = data
    self.next = None
In [22]:
head = None

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None

# Function to insert a new node at the beginning
def push(new_data):
    global head
    new_node = Node(new_data)
    new_node.next = head
    head = new_node

def question5(head, n):
    main_ptr = head
    ref_ptr = head
    count  = 0

    if(head is not None):
        while(count < n ):
            if(ref_ptr is None):
                print "%d is greater than the no. of nodes in list" %(n)
                return

            ref_ptr = ref_ptr.next
            count += 1

    while(ref_ptr is not None):
        main_ptr = main_ptr.next
        ref_ptr = ref_ptr.next

    return main_ptr.data


# Main program
def main():
    global head
    # Make linked list 10->20->30->40->50
    push(50)
    push(40)
    push(30)
    push(20)
    push(10)
    print question5(head, 4)

if __name__ == '__main__':
    main()
20