Python

Question 1

Data Structure: deque

import

Answer 1

from collections import deque

Question 2

Data Structure: deque
method(s): append & appendleft

usage with space & time complexity

Answer 2

append(val) & appendleft(val) - adds item

Time: O(1)
Space: O(1)

Question 3

Data Structure: deque
method(s): pop & popleft

usage with space & time complexity

Answer 3

pop() & popleft() - removes and returns item

Time: O(1)
Space: O(1)

Question 4

Data Structure: deque
method(s): index

usage with space & time complexity

Answer 4

index(ele, beg, end) - returns first index of value

Time: O(n)
Space: O(1)

Question 5

Data Structure: deque
method(s): insert

usage with space & time complexity

Answer 5

insert(i, a) - This function inserts the value mentioned in arguments(a) at index(i) specified in arguments.

Time: O(n)
Space: O(1)

Question 6

Data Structure: deque
method(s): remove

usage with space & time complexity

Answer 6

remove(val) - This function removes the first occurrence of the value mentioned in arguments.

Time: O(n)
Space: O(1)

Question 7

Data Structure: deque
method(s): count

usage with space & time complexity

Answer 7

count(val) - This function counts the number of occurrences of value mentioned in arguments.

Time: O(n)
Space: O(1)

Question 8

Data Structure: deque
method(s): extend & extendleft

usage with space & time complexity

Answer 8

extend(iterable):- add multiple values at the right end of the deque.
extendleft(iterable):- add multiple values at the left end of the deque. Order is reversed as a result of left appends.

Time: O(K)
Space: O(1)

Question 9

Data Structure: deque
method(s): reverse

usage with space & time complexity

Answer 9

reverse():- This function is used to reverse the order of deque elements.

Time: O(n)
Space: O(1)

Question 10

Data Structure: deque
method(s): rotate

usage with space & time complexity

Answer 10

rotate():- This function rotates the deque by the number specified in arguments. If the number specified is negative, rotation occurs to the left. Else rotation is to right.

Time: O(K)
Space: O(1)

Question 11

Data Structure: OrderedDict

import

Answer 11

from collections import OrderedDict

Question 12

Data Structure: OrderedDict
method(s): get item

usage with space & time complexity

Answer 12

dict[key] - returns value

Time: O(1)
Space: O(n)

Question 13

Data Structure: OrderedDict
method(s): set item

usage with space & time complexity

Answer 13

dict[key] = value

Time: O(1)
Space: O(n)

Question 14

Data Structure: OrderedDict
method(s): popitem

usage with space & time complexity

Answer 14

popitem() - used to delete an item from the beginning
popitem(last=True) - used to delete an item from the end

Time: O(1)
Space: O(n)

Question 15

Data Structure: OrderedDict
method(s): move_to_end

usage with space & time complexity

Answer 15

move_to_end(key, last = True) - move an existing key of the dictionary in the end or beginning

Time: O(1)
Space: O(1)

Question 16

Data Structure: LifoQueue

import

Answer 16

from queue import LifoQueue

Question 17

Data Structure: LifoQueue
method(s): instantiate

usage

Answer 17

queue = LifoQueue(maxsize=3)

Question 18

Data Structure: LifoQueue

methods

Answer 18

qsize() - gets the max size of the stack
get() - gets the latest element on the stack
put(val) - adds an element on the stack
full() - displays if the stack is full
empty() - displays if the stack is empty

Question 19

Data Structure: List

array concat/extend with space & time complexity

Answer 19

”+” method - O(n) space & time where n is all items in both lists
extend() - appends multiple items in O(n) time, where n is the new list items

Question 20

Data Structure: List
method(s): copy

usage with space & time complexity

Answer 20

array.copy() - move an existing key of the dictionary in the end or beginning

Time: O(n)
Space: O(n)

Question 21

Data Structure: List
method(s): append

usage with space & time complexity

Answer 21

array.append(val) - adds item to end of array

Time: O(1)
Space: O(1)

Question 22

Data Structure: List
method(s): pop

usage with space & time complexity

Answer 22

array.pop(i) - removes item from end of array or at specific index

Time: O(1) at end or O(n) intermediate
Space: O(1)

Question 23

Data Structure: List
method(s): insert

usage with space & time complexity

Answer 23

array.insert(i, val) - inserts an item at the specified position in the array

Time: O(n)
Space: O(1)

Question 24

Data Structure: List
method(s): remove

usage with space & time complexity

Answer 24

array.remove(val) - removes the first matching item in the array

Time: O(n)
Space: O(1)

Question 25

Algorithm: bubble sort

steps with space & time complexity

Answer 25

while loop with pointer at end
iterate over the array until the pointer
swap elements to “bubble up” the highest value to the end
move the pointer inward

Time: O(n^2)
Space: O(1)

Question 26

Algorithm: cycle sort

steps with space & time complexity

Answer 26

while loop with pointer at start
value corresponds to the expected position
if the value is not equal its expected, then swap

Time: O(n)
Space: O(1)

Question 27

Algorithm: select sort

steps with space & time complexity

Answer 27

• 2 pointers to track progress
• track smallest, starting with assumption of first value
• compare the value with the next value
• if its less, then swap
• if less than smallest, update that
• if the pointer is at the end, move smallest to start, update progress pointers, and reset smallest

Time: O(n^2)
Space: O(1)