HackerRank study Flashcards
(153 cards)
1
Q
Data structures
If we have a tree of n nodes, how many edges will it have?
A
n-1
2
Q
Data Structures
Which of the following data structures can handle updates and queries in log(n) time on an array?
A
Segment Tree
3
Q
Data structures
Of the following data structures, which has a Last in First Out ordering?(LIFO) In other words, the one that came in last will be the first to be popped.
A
Stack
A stack works on the principle where the last element added is the first to be removed. It’s like a stack of plates; you remove the top plate first, which was the last one placed
4
Q
Data structures
Of the following data structures, which has a First In First Out (FIFO) ordering? In other words, the one that came in first will be the first to be removed.
A
Queue
In a queue, the element that is added first to the collection is the first one to be removed. This ordering is analogous to how people queue up for services, where the first person to line up is the first to receive service and leave.
5
Q
True or False: “/” is float division.
A
True
6
Q
True or False: “//” is integer division.
A
True
7
Q
What do you call this expression?
newlist = [expression for item in iterable if condition == True]
A
list comprehension
8
Q
Overloading
What is the output of the following Python code snippet?
class Printer:
def print_number(self, a, b=1):
return a + b
p = Printer()
output = p.print_number(5)
A
6
9
Q
What does method overloading refer to in Python?
A) Defining multiple methods outside the class with the same name
B) Defining multiple methods within the class with the same name but different parameters
C) Changing the behavior of built-in Python operators
D) Using multiple classes with the same method name
A
Defining multiple methods within the class with the same name but different parameters
10
Q
Which of the following is a correct way to simulate method overloading in Python?
A) Using multiple methods with the same name but different numbers of required parameters
B) Using default parameters in methods
C) Defining methods in different modules
D) Python supports method overloading by default
A
Using default parameters in methods
11
Q
overloading
Consider the following code:
class Display:
def show(self, message=”Hello”, times=1):
for _ in range(times):
print(message)
What happens when the method show is called as show(“Goodbye”, 3) on an instance of Display?
A) It prints “Hello” 1 time
B) It prints “Goodbye” 3 times
C) It prints “Goodbye” 1 time
D) It results in an error
A
It prints “Goodbye” 3 times
12
Q
Which statement about overloading in Python is true?
A) Python allows different methods in the same class to have the same name as long as their parameter types are different.
B) Overloading in Python can only be implemented using external libraries.
C) Python uses the last defined method if multiple methods have the same name and number of parameters.
D) Python natively supports method overloading like Java or C++.
A
Python uses the last defined method if multiple methods have the same name and number of parameters.
13
Q
Define O(1)
A
Constant Time: An algorithm is said to run in constant time if it requires the same amount of time regardless of the input size. For example, accessing any element in an array by index is an O(1) operation.
14
Q
Define O(n)
A
Linear Time: An algorithm runs in linear time when the execution time increases linearly with the input size. For example, finding the maximum element in an unsorted array requires looking at each element, resulting in O(n) time complexity.
15
Q
Define O(log n)
A
Logarithmic Time: Logarithmic time complexity occurs when the algorithm reduces the input data size by a constant factor (usually half) with each step. Binary search is a classic example, where each step cuts the search space in half, resulting in O(log n) time complexity.
16
Q
Define O(n^2)
A
Quadratic Time: This complexity arises when an algorithm involves a double loop over the data. For example, a simple bubble sort on an array has O(n^2) time complexity because it iterates over the array for each element.
17
Q
Define O(n log n)
A
This is often seen in more efficient sorting algorithms like quicksort and mergesort, where the algorithm divides the data (log n) and then performs linear work at each division (n).
18
Q
O(2^n) and O(n!)
A
These are seen in algorithms that grow extremely fast with input size, often making them impractical for large inputs. Examples include certain recursive algorithms like calculating Fibonacci numbers naively or solving the traveling salesman problem via brute force.
19
Q
What o notation is this
Accessing an Array Element
def get_first_element(array):
return array[0]
A
Accessing the first element is an O(1) constant time
20
Q
What o notation is this
Checking if a Dictionary is Empty
def is_empty(dictionary):
return not dictionary
A
Checking emptiness is O(1) because it’s a direct property check.
21
Q
What o notation is this
Incrementing a Number
def increment(number):
return number + 1
A
Incrementing a number is an O(1) operation.
22
Q
What o notation is this
Setting a Value in a Dictionary
def set_value(dictionary, key, value):
dictionary[key] = value
A
Setting an item in a dictionary is O(1) on average.
23
Q
What o notation is this
Return a Constant
def return_constant():
return 42
A
Returning a constant is an O(1) operation.
24
Q
What o notation is this
Checking a Boolean Flag
def check_flag(flag):
if flag:
return “True”
else:
return “False”
A
Checking a flag is an O(1) operation.
25
What o notation is this
Multiplying Two Numbers
def multiply(a, b):
return a * b
Multiplication of two numbers is O(1).
26
What o notation is this
Print a Static String
def print_message():
print("Hello, World!")
Printing a fixed message is an O(1) operation.
27
What o notation is this
Adding an Element to the Beginning of a List
def add_to_front_of_list(lst, element):
lst.insert(0, element)
Adding to the front of a list is O(1) in Python's list implementation.
28
What o notation is this
Swap Two Elements in an Array
def swap_elements(arr, index1, index2):
arr[index1], arr[index2] = arr[index2], arr[index1]
Swapping elements is an O(1) operation.
29
What is the time complexity of accessing any specific element in an array by index?
A) O(n)
B) O(1)
C) O(log n)
D) O(n^2)
O(1)
30
Which operation is an example of O(1) complexity?
A) Searching for an element in a sorted array using binary search
B) Calculating the sum of all elements in an array
C) Inserting a new node in a linked list, given a reference to the position
D) Returning the first element of a list
Returning the first element of a list
31
Setting a key-value pair in a Python dictionary is generally considered to have which time complexity?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
O(1)
32
What is the time complexity of printing a fixed string, regardless of input size?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
O(1)
33
Which of the following operations has O(1) space complexity?
A) Creating a new list proportional to input size
B) Incrementing an integer variable
C) Storing all input values in a new list
D) Appending elements to a list while iterating over another list of the same size
Incrementing an integer variable
34
What is the time complexity of checking if a number is even or odd?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
O(1)
35
Which of the following operations typically has a constant time complexity in a hash table?
A) Deleting a key-value pair
B) Searching for an element based on its key
C) Resizing the hash table when it is full
D) Iterating over all elements
Searching for an element based on its key
36
What is the time complexity of assigning a value to a variable in a program?
A) O(n)
B) O(1)
C) O(log n)
D) O(n log n)
O(1)
37
What o notation is this
Binary Search
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
O(log n)
38
What o notation is this
Balanced Binary Tree
def height_of_bst(node):
if node is None:
return 0
return 1 + max(height_of_bst(node.left), height_of_bst(node.right))
O(log n)
39
Calculating Power Using Exponentiation by Squaring
What o notation is this
def power(base, exp):
if exp == 0:
return 1
half = power(base, exp // 2)
if exp % 2 == 0:
return half * half
else:
return base * half * half
O(log n)
40
What o notation is this
Finding the Largest Power of 2 Less Than or Equal to N
def largest_power_of_two(n):
power = 1
while power * 2 <= n:
power *= 2
return power
O(log n)
41
What o notation is this
Binary Reduction of an Array Sum
def binary_reduction_sum(arr):
while len(arr) > 1:
new_arr = []
for i in range(0, len(arr), 2):
if i + 1 < len(arr):
new_arr.append(arr[i] + arr[i+1])
else:
new_arr.append(arr[i])
arr = new_arr
return arr[0]
O(n log n) — note: while this involves reducing the problem size by half each iteration, the overall complexity involves processing each element multiple times.
42
What o notation is this
Recursive Halving
def recursive_halving(n):
if n <= 1:
return n
return recursive_halving(n // 2)
O(log n)
43
What o notation is this
Iterative Log Base 2
def iterative_log_base2(n):
count = 0
while n > 1:
n //= 2
count += 1
return count
O(log n)
44
Which operation in a binary search tree (BST) generally has a time complexity of O(log n)?
A) Inserting an element in a balanced BST
B) Traversing all elements in a BST
C) Adding an element to an unbalanced BST
D) Deleting all elements from a BST
Inserting an element in a balanced BST
45
What is the time complexity of searching for an element in a sorted array using binary search?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
O(log n)
46
In a balanced binary tree, the time complexity to reach the deepest node is:
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
O(log n)
47
What o notation is this
Summing Array Elements
def sum_array(arr):
total = 0
for num in arr:
total += num
return total
O(n)
48
what o notation is this
Checking for Uniqueness in a List
def is_unique(lst):
seen = set()
for x in lst:
if x in seen:
return False
seen.add(x)
return True
O(n)
49
what o notation is this
Linear Search
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
O(n)
50
What o notation is this
Counting Characters in a String
def count_chars(s):
count = {}
for char in s:
if char in count:
count[char] += 1
else:
count[char] = 1
return count
O(n)
51
What o notation is this
Find Maximum in an Array
def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
O(n)
52
What o notation is this
Reverse a String
def reverse_string(s):
return ''.join(reversed(s))
O(n)
53
What O notation is this
Validate a Sequence
def validate_sequence(seq):
return all(seq[i] <= seq[i+1] for i in range(len(seq) - 1))
O(n)
54
What O notation is this
Print Elements
def print_elements(elements):
for element in elements:
print(element)
O(n)
55
What O notation is this
Calculate Fibonacci Using Iteration
def fib_iterative(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
O(n)
56
Big O notation
Filter Even Numbers
def filter_evens(numbers):
return [num for num in numbers if num % 2 == 0]
O(n)
57
What is the time complexity of finding the largest number in an unsorted list?
O(n)
58
Which of these operations has O(n) time complexity?
A) Searching for an element in a sorted array using binary search
B) Calculating the sum of all elements in an array
C) Inserting an element at the beginning of a linked list
D) Accessing an element by index in an array
B) Calculating the sum of all elements in an array
59
What is the time complexity of reversing a string of length n?
O(n)
60
What is the time complexity of checking if all elements in an array are unique?
O(n)
61
What is the time complexity of an algorithm that counts the frequency of each character in a string?
O(n)
62
Which of the following best describes the time complexity of printing each element in a list of n elements?
O(n)
63
What is the time complexity for a function that checks if a sequence of numbers is sorted in non-decreasing order?
O(n)
64
What is the time complexity of building a balanced binary search tree from a sorted array?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(n^2)
O(n log n)
65
Tim Sort, a hybrid stable sorting algorithm used in Python’s built-in sorted() function, primarily operates in what time complexity?
O(n log n)
66
What O notation is this?
Bubble Sort
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
O(n^2)
67
Which operation generally has O(n log n) time complexity due to the nature of repetitive division and combination?
A) Linear search
B) Binary search
C) Heap sort
D) Insertion sort
Heap sort
68
Which of the following scenarios would most likely exhibit O(n log n) time complexity?
A) Accessing an element in a hash table
B) Counting the number of inversions in an array using a modified merge sort
C) Checking if a string of parentheses is balanced using a stack
D) Finding the maximum element in an unsorted array
Counting the number of inversions in an array using a modified merge sort
69
What O notation is this?
Insertion sort
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >=0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
O(n^2)
70
What O notation is this?
Selection sort
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
O(n^2)
71
What O notation is this?
Checking for Duplicates in an Array
def check_duplicates(arr):
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j]:
return True
return False
O(n^2)
72
What O notation is this?
Calculating All Pair Sums
def all_pair_sums(arr):
sums = []
for i in range(len(arr)):
for j in range(len(arr)):
sums.append(arr[i] + arr[j])
return sums
O(n^2)
73
What O notation is this
Finding All Substrings of a String
def find_substrings(s):
substrings = []
for i in range(len(s)):
for j in range(i, len(s)):
substrings.append(s[i:j+1])
return substrings
O(n^2)
74
What O notation is this?
Printing All Pairs in Array
def print_all_pairs(arr):
for i in range(len(arr)):
for j in range(len(arr)):
print(f"Pair: ({arr[i]}, {arr[j]})")
O(n^2)
75
What O notation is this?
Nested Loops with Constant Work
def nested_loops(arr):
for i in range(len(arr)):
for j in range(len(arr)):
print(f"Processing element: {arr[i]}, {arr[j]}")
O(n^2)
76
Which of the following demonstrates O(n^2) complexity?
A) Finding the maximum element in an array
B) Printing all pairs in an array
C) Binary search
D) Inserting an element into a binary search tree
Printing all pairs in an array
77
What is the time complexity of selection sort regardless of input condition?
A) O(n)
B) O(n^2)
C) O(log n)
D) O(n log n)
O(n^2)
78
Calculating all substrings of a string typically has a time complexity of:
A) O(n)
B) O(log n)
C) O(n log n)
D) O(n^2)
O(n^2)
79
What is the time complexity of nested loops where each loop iterates through the same array?
A) O(n)
B) O(n^2)
C) O(n^3)
D) O(log n)
O(n^2)
80
What is the complexity of an algorithm that calculates the sum of every possible pair in an array?
A) O(n)
B) O(n^2)
C) O(n^3)
D) O(log n)
O(n^2)
81
What O notation is this?
3D Matrix Addition
def add_3d_matrices(A, B):
n = len(A) # Assuming cubic matrices for simplicity
C = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j][k] = A[i][j][k] + B[i][j][k]
return C
O(n^3)
82
What O notation is this?
Triple Nested Loop Sum
def triple_sum(arr):
n = len(arr)
result = 0
for i in range(n):
for j in range(n):
for k in range(n):
result += arr[i] + arr[j] + arr[k]
return result
O(n^3)
83
What O notation is this?
Naive Matrix Multiplication
def matrix_multiply(A, B):
n = len(A)
C = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j] += A[i][k] * B[k][j]
return C
O(n^3)
84
What O notation is this?
All Triple Combinations
def all_triples(arr):
triples = []
n = len(arr)
for i in range(n):
for j in range(n):
for k in range(n):
triples.append((arr[i], arr[j], arr[k]))
return triples
O(n^3)
85
What O notation is this?
def process_quartic_combinations(data):
n = len(data)
result = 0
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
for l in range(k+1, n):
# Process a combination of four different elements
result += data[i] * data[j] * data[k] * data[l]
return result
O(n^4)
85
What O notation is this?
def find_quadruple_sum(arr, target):
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
for l in range(k + 1, n):
if arr[i] + arr[j] + arr[k] + arr[l] == target:
return True
return False
O(n^4)
86
What O notation is this?
def complex_simulation(data):
n = len(data)
result = 0
for a in range(n):
for b in range(n):
for c in range(n):
for d in range(n):
# Hypothetical operation involving four factors
result += data[a] * data[b] - data[c] * data[d]
return result
O(n^4)
87
What O notation is this?
(Naive Recursive Approach)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
O(2^n)
88
What O notation is this?
Calculating Power Set (Generating All Subsets)
def power_set(s):
if len(s) == 0:
return [[]]
first = s[0]
rest = power_set(s[1:])
with_first = [[first] + r for r in rest]
return rest + with_first
O(2^n)
88
What O notation is this?
Tower of Hanoi
def tower_of_hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
tower_of_hanoi(n - 1, source, auxiliary, target)
print(f"Move disk {n} from {source} to {target}")
tower_of_hanoi(n - 1, auxiliary, target, source)
O(2^n)
89
What O notation is this?
All Possible Valid Parentheses Combinations
def generate_parentheses(n):
def generate(p, left, right, parens=[]):
if left: generate(p + '(', left-1, right)
if right > left: generate(p + ')', left, right-1)
if not right: parens.append(p)
return parens
return generate('', n, n)
O(2^n)
89
What O notation is this?
Permutations of a String
def permutations(string):
if len(string) == 1:
return [string]
perms = permutations(string[1:])
char = string[0]
result = []
for perm in perms:
for i in range(len(perm) + 1):
result.append(perm[:i] + char + perm[i:])
return result
O(2^n)
90
What O notation is this?
Counting Binary Strings Without Consecutive 1’s
python
def count_strings(n):
if n == 0:
return 1
if n == 1:
return 2
return count_strings(n-1) + count_strings(n-2)
O(2^n)
91
What O notation is this?
Find All Subsets That Sum to a Target
def find_subsets_that_sum_to_target(arr, target):
results = []
def find_subsets(index, path, target):
if target == 0:
results.append(path)
return
if target < 0:
return
for i in range(index, len(arr)):
find_subsets(i + 1, path + [arr[i]], target - arr[i])
find_subsets(0, [], target)
return results
O(2^n)
92
Tiling Problem (Count Ways to Cover a Distance)
def count_ways(n):
if n <= 1:
return 1
return count_ways(n-1) + count_ways(n-2)
O(2^n)
93
What is the primary characteristic of algorithms with O(2^n) complexity?
A) Linear recursion
B) Double recursion causing exponential growth
C) Polynomial nested loops
D) Logarithmic reductions
Double recursion causing exponential growth
94
Which of these scenarios is likely to have O(2^n) complexity?
A) Finding the shortest path in a graph
B) Calculating all possible subsets of a set
C) Merging two sorted lists
D) Performing a binary search
Calculating all possible subsets of a set
95
What O notation is this?
Generating All Permutations of a List
def permute(a, l, r):
if l == r:
print(a)
else:
for i in range(l, r + 1):
a[l], a[i] = a[i], a[l]
permute(a, l + 1, r)
a[l], a[i] = a[i], a[l] # backtrack
Example usage
arr = [1, 2, 3]
permute(arr, 0, len(arr)-1)
O(n!)
96
What O notation is this?
Calculating All Possible Combinations of a List
def all_combinations(arr):
def generate_combinations(current, remaining):
if not remaining:
print(current)
return
generate_combinations(current + [remaining[0]], remaining[1:])
generate_combinations(current, remaining[1:])
generate_combinations([], arr)
O(n!)
97
What O notation is this?
Heap's Algorithm for Generating Permutations
def heap_permutation(data, n):
if n == 1:
print(data)
return
for i in range(n):
heap_permutation(data, n - 1)
if n % 2 == 1:
data[0], data[n - 1] = data[n - 1], data[0] # swap
else:
data[i], data[n - 1] = data[n - 1], data[i] # swap
O(n!)
98
What O notation is this?
Full Permutations of String
def string_permutations(s):
if len(s) == 1:
return [s]
perms = string_permutations(s[1:])
char = s[0]
result = []
for perm in perms:
for i in range(len(perm) + 1):
result.append(perm[:i] + char + perm[i:])
return result
O(n!)
99
What O notation is this?
All Permutations of a Set of Values
def permute_values(values):
from itertools import permutations
return list(permutations(values))
O(n!)
100
What O notation is this?
All Permutations of Array Elements
def permute_array(arr, start=0):
if start == len(arr) - 1:
print(arr)
return
for i in range(start, len(arr)):
arr[start], arr[i] = arr[i], arr[start]
permute_array(arr, start + 1)
arr[start], arr[i] = arr[i], arr[start] # backtrack
O(n!)
100
What O notation is this?
Generate All Possible Friend Pairings
def friend_pairings(n):
if n <= 1:
return 1
if n == 2:
return 2
return friend_pairings(n-1) + (n-1) * friend_pairings(n-2)
O(n!)
101
Which algorithm inherently has a factorial time complexity due to generating all permutations?
A) Depth-first search
B) Quick sort
C) Heap's algorithm for permutations
D) Dijkstra's algorithm
Heap's algorithm for permutations
102
What O notation is this?
Generate All Possible Game Moves
def game_moves(options, positions):
if len(positions) == len(options):
print(positions)
return
for option in options:
if option not in positions:
game_moves(options, positions + [option])
O(n!)
103
What is the time complexity of finding all possible orderings of n distinct items?
A) O(n^2)
B) O(2^n)
C) O(n!)
D) O(n log n)
O(n!)
104
What o notation
if __name__ == '__main__':
n = int(input().strip())
if n % 2 != 0:
print("Weird")
elif n % 2 == 0 and 2<= n <= 5:
print ("Not Weird")
elif n % 2 == 0 and 6<= n <= 20:
print("Weird")
elif n % 2 == 0 and n > 20:
print("Not Weird")
O(1)
105
What o notation is this
if __name__ == '__main__':
a = int(input())
b = int(input())
sum_ab = a + b
differences = a - b
product = a * b
print(sum_ab)
print(differences)
print(product)
O(1)
106
Array Traversal
What does the find_maximum function do?
def find_maximum(arr):
max_value = arr[0]
for num in arr:
if num > max_value:
max_value = num
return max_value
A) Finds the minimum element in the array
B) Finds the maximum element in the array
C) Calculates the sum of the array
D) Returns the first element of the array
B) Finds the maximum element in the array
107
What does the is_sorted function check?
Array Traversal
def is_sorted(arr):
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False
return True
A) If the array is sorted in descending order
B) If the array has any duplicates
C) If the array is sorted in ascending order
D) The number of elements in the array
If the array is sorted in ascending order
108
Array Traversal
def reverse_array(arr):
return arr[::-1]
What is the outcome of calling reverse_array on an array?
A) Reverses the array in place
B) Returns a new array that is the reverse of the original
C) Doubles the size of the array
D) None of the above
Returns a new array that is the reverse of the original
109
Array Traversal
def sum_array(arr):
total = 0
for num in arr:
total += num
return total
What does the sum_array function compute?
A) The average of the array elements
B) The total number of elements in the array
C) The sum of the array elements
D) The product of the array elements
The sum of the array elements
110
Array Traversal
def find_element(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
What does the find_element function return?
A) True if the target is found, else False
B) The index of the target if found, else -1
C) The value of the target if found
D) The number of times the target appears in the array
The index of the target if found, else -1
111
Basic Subclassing
class Animal:
def speak(self):
return "Some sound"
class Dog(Animal):
def speak(self):
return "Woof"
Usage
dog = Dog()
print(dog.speak())
uestion 1: What is the output of dog.speak()?
A) Some sound
B) Woof
C) No output
D) Error
Woof
112
Constructor Overriding (subclassing)
class Vehicle:
def __init__(self, brand):
self.brand = brand
class Car(Vehicle):
def __init__(self, brand, model):
super().__init__(brand)
self.model = model
Usage
car = Car("Toyota", "Corolla")
print(car.brand, car.model)
What is printed by the print(car.brand, car.model) statement?
A) Toyota Corolla
B) Error
C) None
D) Toyota, Corolla
Toyota, Corolla
113
Subclassing
Method Extension
class Base:
def greet(self):
return "Hello"
class Child(Base):
def greet(self):
return super().greet() + ", World!"
Usage
child = Child()
print(child.greet())
What does child.greet() return?
A) Hello
B) Hello, World!
C) World!
D) None
Hello, World!
113
Subclassing
Attribute Extension
class Product:
def __init__(self, name):
self.name = name
class Book(Product):
def __init__(self, name, author):
super().__init__(name)
self.author = author
Usage
book = Book("1984", "George Orwell")
print(book.name, book.author)
What does print(book.name, book.author) output?
A) 1984 George Orwell
B) George Orwell 1984
C) 1984, George Orwell
D) Error
1984, George Orwell
114
Subclassing
Polymorphism with Subclassing
class Shape:
def area(self):
return 0
class Circle(Shape):
def __init__(self, radius):
self.radius = radius
def area(self):
return 3.14 * self.radius ** 2
Usage
circle = Circle(5)
print(circle.area())
What is the result of circle.area()?
A) 0
B) 78.5
C) 25
D) 3.14
78.5
115
Subclassing
Using Multiple Subclasses
class Parent:
def msg(self):
return "Parent"
class Child1(Parent):
def msg(self):
return "Child1"
class Child2(Parent):
def msg(self):
return "Child2"
Usage
child1 = Child1()
child2 = Child2()
print(child1.msg(), child2.msg())
What is printed by print(child1.msg(), child2.msg())?
A) Parent Parent
B) Child1 Child2
C) Parent Child1
D) Parent Child2
Child1 Child2
116
Subclassing
Abstract Classes and Subclassing
from abc import ABC, abstractmethod
class Computer(ABC):
@abstractmethod
def compute(self):
pass
class Laptop(Computer):
def compute(self):
return "Computing on a laptop"
Usage
laptop = Laptop()
print(laptop.compute())
What does laptop.compute() return?
A) Computing on a laptop
B) Computing
C) None
D) Error
Computing on a laptop
117
Subclassing
Subclassing with Property Overriding
class Rectangle:
def __init__(self, width, height):
self.width = width
self.height = height
def area(self):
return self.width * self.height
class Square(Rectangle):
def __init__(self, side):
super().__init__(side, side)
Usage
square = Square(4)
print(square.area())
What is the output of square.area()?
A) 16
B) 8
C) 4
D) None
16
118
Constructor and Destructor Subclassing
class Base:
def __init__(self):
print("Base Constructor")
def __del__(self):
print("Base Destructor")
class Derived(Base):
def __init__(self):
super().__init__()
print("Derived Constructor")
def __del__(self):
print("Derived Destructor")
super().__del__()
Usage
derived = Derived()
del derived
What is the sequence of prints when the object derived is deleted?
A) Derived Constructor, Base Constructor, Derived Destructor, Base Destructor
B) Base Constructor, Derived Constructor, Derived Destructor, Base Destructor
C) Base Constructor, Derived Constructor, Base Destructor, Derived Destructor
D) Derived Constructor, Base Constructor, Base Destructor, Derived Destructor
Base Constructor, Derived Constructor, Derived Destructor, Base Destructor
119
Multi-level Inheritance (subclassing)
class Grandparent:
def home(self):
return "Grandparent's home"
class Parent(Grandparent):
def home(self):
return "Parent's home"
class Child(Parent):
def home(self):
return super().home()
Usage
child = Child()
print(child.home())
What does child.home() return?
A) Grandparent's home
B) Parent's home
C) Child's home
D) None
Parent's home
120
What is subclassing in Python?
Subclassing in Python is a fundamental aspect of object-oriented programming (OOP) that allows you to create a class based on another class, thus inheriting attributes and behaviors from the base (or parent) class while enabling the addition or modification of new attributes and behaviors.
121
Basic Syntax of Subclass
class BaseClass:
pass
class DerivedClass(BaseClass):
pass
Subclasses can modify behaviors from the base class. This is known as overriding. When you override a method, the subclass version of the method is called instead of the base class version.
class Bird:
def fly(self):
print("Some birds can fly.")
class Ostrich(Bird):
def fly(self):
print("Ostriches cannot fly.")
122
What is super()
super() is used to call methods from the superclass in the subclass. This is especially useful in the constructor methods or when overriding methods.
class Bird:
def __init__(self, species):
self.species = species
class Parrot(Bird):
def __init__(self, species, color):
super().__init__(species)
self.color = color
123
Multiple Inheritance
Python supports multiple inheritance, where a subclass can inherit from more than one base class.
class WaterBird:
def swim(self):
print("This bird swims.")
class FlyingBird:
def fly(self):
print("This bird flies.")
class Duck(WaterBird, FlyingBird):
pass
daffy = Duck()
daffy.swim()
daffy.fly()
124
Abstract Classes
Python allows the creation of abstract classes using the abc module, which can define methods that must be implemented by any subclass.
from abc import ABC, abstractmethod
class Bird(ABC):
@abstractmethod
def fly(self):
pass
class Sparrow(Bird):
def fly(self):
print("Sparrow flies.")
125
What is a binary search tree?
A Binary Search Tree (BST) is a fundamental data structure in computer science used for storing data in an organized manner. It facilitates efficient searching, insertion, and deletion operations.
binary tree where each node has a key (value), and each node's key is:
Greater than all the keys in the node's left subtree.
Less than or equal to all the keys in the node's right subtree
126
Binary Search Tree
Inserting a Node into a BST
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
Time Complexity: Average O(log n), Worst O(n)
127
Binary Search Tree
Searching for a Node in a BST
def search(root, key):
if root is None or root.val == key:
return root
if root.val < key:
return search(root.right, key)
return search(root.left, key)
Time Complexity: Average O(log n), Worst O(n)
128
Binary Search Tree
Finding Minimum Value in a BST
def find_min(root):
current = root
while current.left is not None:
current = current.left
return current.val
Time Complexity: Average O(log n), Worst O(n)
129
Binary Search Tree
Finding Maximum Value in a BST
def find_max(root):
current = root
while current.right is not None:
current = current.right
return current.val
Time Complexity: Average O(log n), Worst O(n)
130
Binary Search Tree
Deleting a Node from a BST
def delete_node(root, key):
if root is None:
return root
if key < root.val:
root.left = delete_node(root.left, key)
elif(key > root.val):
root.right = delete_node(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
temp = find_min(root.right)
root.val = temp.val
root.right = delete_node(root.right, temp.val)
return root
def find_min(node):
current = node
while(current.left is not None):
current = current.left
return current
Average O(log n), Worst O(n)
131
Binary Search Tree
In-Order Traversal of a BST
def inorder_traversal(root):
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right) if root else []
Time Complexity: O(n)
132
Binary Search Tree
Pre-Order Traversal of a BST
def preorder_traversal(root):
if root:
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
Time Complexity: O(n)
133
Binary Search Tree
Post-Order Traversal of a BST
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val)
Time Complexity: O(n)
134
Which of the following data structures can erase from its beginning or its end in O(1) time?
Deque
135
What feature allows different methods to have the same name and argument type, but a different implementation is called?
Method Overriding
136
what will this overriding print?
class Animal:
def make_sound(self):
print("Some generic sound")
class Dog(Animal):
def make_sound(self):
print("Bark")
class Cat(Animal):
def make_sound(self):
print("Meow")
Using polymorphism
animals = [Dog(), Cat()]
for animal in animals:
animal.make_sound()
Bark
Meow
137
Consider a linked list of n, elements. What is the time taken to inset an element at a position that is pointed to by some pointer?
O(1)
138
You are given an array arr[] which contains N integers. The task is to count the number of valid pairs present in the array. A valid pair is any two indices i and j where
i
hash map
139
What is the output of the following code?
class Animal:
def __init__(self, name):
self.name = name
def speak(self):
return "Unknown sound"
class Dog(Animal):
def speak(self):
return "Barks"
class Cat(Animal):
def speak(self):
return "Meows"
animal = Animal("Generic Animal")
dog = Dog("Buddy")
cat = Cat("Whiskers")
print(animal.speak(), dog.speak(), cat.speak())
Unknown sound Barks Meows
140
What is the time complexity of the following recursive function that calculates the nth Fibonacci number?
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
O(2^n). This is because the function employs a simple recursion method where each call generates two additional calls, except for the base cases
fibonacci(n-1) and fibonacci(n-2). Each of those calls, in turn, makes two more calls, leading to a binary tree of recursive calls.
141
Python implements hash maps as dictionaries. Here's how you can use a Python dictionary:
#Create a hash map
hash_map = {}
#Add items to the hash map
hash_map['name'] = 'John Doe'
hash_map['age'] = 30
hash_map['email'] = 'johndoe@example.com'
#Accessing an item
print(f"Name: {hash_map['name']}")
#Removing an item
del hash_map['email']
#Checking if a key exists
if 'age' in hash_map:
print(f"Age: {hash_map['age']}")
#Iterating over items
for key, value in hash_map.items():
print(f"{key}: {value}")
141
What is a hashmap
hashmap also known as a hash table or dictionary, is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash map uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
142
Given the root of a complete binary tree, return the number of the nodes in the tree.
Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
143
def print_space_elements(space_dict):
for key, value in space_dict.items():
print(f"{key}: {value}")
Example usage
space_data = {
"Mercury": "The smallest planet",
"Venus": "The hottest planet",
"Earth": "Our home",
"Mars": "The Red Planet",
"Jupiter": "The largest planet",
"Saturn": "Known for its rings",
"Uranus": "An ice giant",
"Neptune": "The farthest planet",
"Pluto": "A dwarf planet"
}
print_space_elements(space_data)
144
Pre Order Traversal
def preOrder(root):
if root:
# First print the data of node
print(root.info, end=' ')
# Then recur on left child
preOrder(root.left)
# Finally recur on right child
preOrder(root.right)
145
Post Order Traversal (binary)
def postOrder(root):
if root:
postOrder(root.left)
postOrder(root.right)
print(root.info, end=" ")
146
inOrder Traversal (binary)
def inOrder(root):
if root:
inOrder(root.left)
print(root.info, end = " ")
inOrder(root.right)
147
height of binary tree
def height(root):
if root is None:
return -1 # Return -1 for an empty tree
else:
left_height = height(root.left)
right_height = height(root.right)
return max(left_height, right_height) + 1
