Skip to content

Instantly share code, notes, and snippets.

@mindyng
Created December 16, 2020 21:53
Show Gist options
  • Save mindyng/953bf230606dc35222a18f0d4edbcae9 to your computer and use it in GitHub Desktop.
Save mindyng/953bf230606dc35222a18f0d4edbcae9 to your computer and use it in GitHub Desktop.
TestDome Python "Basic" Practice Q's
#Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree.
# Write a function that, efficiently with respect to time used, checks if a given binary search tree contains a given value.
# For example, for the following tree:
# n1 (Value: 1, Left: null, Right: null)
# n2 (Value: 2, Left: n1, Right: n3)
# n3 (Value: 3, Left: null, Right: null)
# Call to contains(n2, 3) should return True since a tree with root at n2 contains number 3.
import collections
Node = collections.namedtuple('Node', ['left', 'right', 'value'])
def contains(root, value):
if value == root.value:
return True
if value > root.value:
if root.right != None:
return contains(root.right, value)
else:
if root.left != None:
return contains(root.left, value)
return False
n1 = Node(value=1, left=None, right=None)
n3 = Node(value=3, left=None, right=None)
n2 = Node(value=2, left=n1, right=n3)
# Implement a group_by_owners function that:
# Accepts a dictionary containing the file owner name for each file name.
# Returns a dictionary containing a list of file names for each owner name, in any order.
# For example, for dictionary {'Input.txt': 'Randy', 'Code.py': 'Stan', 'Output.txt': 'Randy'} the group_by_owners function should return {'Randy': ['Input.txt', 'Output.txt'], 'Stan': ['Code.py']}.
def group_by_owners(files):
result = {}
for file, owner in files.items():
result[owner] = result.get(owner, []) + [file]
return result
if __name__ == "__main__":
files = {
'Input.txt': 'Randy',
'Code.py': 'Stan',
'Output.txt': 'Randy'
}
print(group_by_owners(files))
# Implement the IceCreamMachine's scoops method so that it returns all combinations of one ingredient and one topping. If there are no ingredients or toppings, the method should return an empty list.
# For example, IceCreamMachine(["vanilla", "chocolate"], ["chocolate sauce"]).scoops() should return [['vanilla', 'chocolate sauce'], ['chocolate', 'chocolate sauce']].
class IceCreamMachine:
def __init__(self, ingredients, toppings):
self.ingredients = ingredients
self.toppings = toppings
def scoops(self):
res = []
for i in self.ingredients:
for j in self.toppings:
res.append([i,j])
return res
if __name__ == "__main__":
machine = IceCreamMachine(["vanilla", "chocolate"], ["chocolate sauce"])
print(machine.scoops())
# Implement the unique_names method. When passed two lists of names, it will return a list containing the names that appear in either or both lists. The returned list should have no duplicates.
# For example, calling unique_names(['Ava', 'Emma', 'Olivia'], ['Olivia', 'Sophia', 'Emma']) should return a list containing Ava, Emma, Olivia, and Sophia in any order.
def unique_names(names1, names2):
return list(set(names1+names2))
if __name__ == "__main__":
names1 = ["Ava", "Emma", "Olivia"]
names2 = ["Olivia", "Sophia", "Emma"]
print(unique_names(names1, names2)) # should print Ava, Emma, Olivia, Sophia
# Implement the function find_roots to find the roots of the quadratic equation: ax2 + bx + c = 0. The function should return a tuple containing roots in any order. If the equation has only one solution, the function should return that solution as both elements of the tuple. The equation will always have at least one solution.
# The roots of the quadratic equation can be found with the following formula: A quadratic equation.
# For example, find_roots(2, 10, 8) should return (-1, -4) or (-4, -1) as the roots of the equation 2x2 + 10x + 8 = 0 are -1 and -4.
import numpy as np
def find_roots(a, b, c):
input = [a, b, c]
return tuple(np.roots(input))
print(find_roots(2, 10, 8));
# Song
# Back to questions
# A playlist is considered a repeating playlist if any of the songs contain a reference to a previous song in the playlist. Otherwise, the playlist will end with the last song which points to None.
# Implement a function is_repeating_playlist that, efficiently with respect to time used, returns true if a playlist is repeating or false if it is not.
# For example, the following code prints "True" as both songs point to each other.
class Song:
def __init__(self, name):
self.name = name
self.next = None
def next_song(self, song):
self.next = song
def is_repeating_playlist(self):
"""
:returns: (bool) True if the playlist is repeating, False if not.
"""
songs = set()
next_song = self
while next_song:
if next_song.name in songs:
return True
else:
songs.add(next_song.name)
next_song = next_song.next or None
return False
first = Song("Hello")
second = Song("Eye of the tiger")
first.next_song(second)
second.next_song(first)
print(first.is_repeating_playlist())
# Write a function that, when passed a list and a target sum, returns, efficiently with respect to time used, two distinct zero-based indices of any two of the numbers, whose sum is equal to the target sum. If there are no two numbers, the function should return None.
# For example, find_two_sum([3, 1, 5, 7, 5, 9], 10) should return a single tuple containing any of the following pairs of indices:
# 0 and 3 (or 3 and 0) as 3 + 7 = 10
# 1 and 5 (or 5 and 1) as 1 + 9 = 10
# 2 and 4 (or 4 and 2) as 5 + 5 = 10
def find_two_sum(numbers, target_sum):
"""
:param numbers: (list of ints) The list of numbers.
:param target_sum: (int) The required target sum.
:returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
"""
taken = {}
for i, num in enumerate(numbers):
diff = target_sum - num
if diff in taken:
return i, taken[diff]
taken[num] = i
return None
if __name__ == "__main__":
print(find_two_sum([3, 1, 5, 7, 5, 9], 10))one
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment