Big O & runtime analysis
What is the runtime of linear search?
O(n)
If you know that you will frequently need to search whether an element is within a dataset, what is the best data structure to use?
Hash table
What is the following binary number in decimal?
101010
42
What is the analog in C to a Python list? Give one way in which the Python list is more powerful.
Array. Python lists are dynamic and can store multiple types.
Give the runtime of the following code.
def analyze(str):
for char in str:
for char in str:
print("Hello")
O(n^2)
Describe in the two steps required to add an element into a linked list. Make sure they are in the correct order. If it helps, you can use "new" to refer to the new node and "head" to refer to the pointer at the head of the list.
1. new.next -> head
2. head = new
In most versions of C, an integer is 4 bytes, or 32 bits. In this case, what is the maximum value that you can store in a C int?
2^31 but will accept 2^32.
What is the return type of malloc()?
Pointer
Give the time complexity of the following code.
int a = 0, int i = N;
while (i > 0) {
a += i;
i /= 2;
}
O(log n)
What is the difference between a stack and a queue?
A queue is First In First Out, while a stack is Last In First Out.
What is a primary key in a database and why is it useful?
It's the ID of each row that is guaranteed to be unique - it's useful because it ensures that we have an easy and reliable way of referencing rows.
dct = {"name": "Julian", "id": 1}
for element in dct:
print(element)
No - you can't loop through a raw dictionary. You have to insert dct.keys or dct.items.
Give the time complexity of the following code.
def analyze (str1, str2):
for char in str1:
print("Hello")
for char in str2:
print("Goodbye")
O(n + m), where n, m are lengths of str1 and str2
Within the next 60 seconds, implement a hash table in Python.
table = {}
What function does the following compute?
def mystery(n):
if n == 1:
return 1
else:
return n * mystery (n - 1)
mystery computes the factorial function.
What should be the type of the parameter x in order for the below Python function to execute successfully?
def confused(x):
a = 0
a = "0"
return x + a
string