errr basic python theory

Question 1

What is the time complexity of quicksort, mergesort, insertion sort, bubble sort and bogosort?

Answer 1

quicksort + mergesort: O(nlogn)
insertion + bubble sort: O(n^2)
bogosort: O((n+1)!) (just trolling)

Question 2

What is the time complexity of linear search and binary search?

Answer 2

linear search: O(n)
binary search: O(logn)

Question 3

what is the best and worst case of quicksort?

Answer 3

best case: pivot in the middle
worst case: almost sorted + pivot is the start

Question 4

What is the order for Stacks and its operations?

Answer 4

• Last In, First Out
• push(), pop(), peek()

Question 5

What is the order for a Queue and its operations?

Answer 5

• First In, First Out
• enqueue(), dequeue(), peek()

Question 6

What is the advantages of a linked list?

Answer 6

• flexible in allocating memory
• memory can be reused

Question 7

What are the disadvantages of a linked list?

Answer 7

• High time complexity when traversal
• High space complexity

Question 8

How to find the depth of a binary tree?

Answer 8

The length of the longest chain of nodes - 1

Question 9

What are the orders of output for the different traversals of a BST?

Answer 9

• preorder traversal: print, left, right
• inorder traversal: left, print, right
• postorder traversal : left, right, print

Question 10

What is the definition of recursion?

Answer 10

Recursion is a method of program design that repeatedly breaks down a problem into smaller subproblems until one or more terminating cases are reached.

A recursive function is one which calls itself

Question 11

What is the definition of data validation?

Answer 11

Data validation is the process of ensuring that the data is clean, correct and useful

Question 12

What are some types of data validation?

Answer 12

Presence, type, length, range, format, restricted value, check digit (weighted modulus)

Question 13

What are some errors?

Answer 13

Syntax error, logic error, runtime error

Question 14

What are some ways of program testing?

Answer 14

1. Blackbox Testing - testing from perspective of a user (time efficient, no need code access, limited coverage)
2. White Box Testing - testing from perspective of developer (not time efficient, need code access, max coverage

Question 15

What is inheritance and its advantages? (OOP)

Answer 15

Inheritance is when the subclass will acquire the properties and behaviours of its superclass.

advantages: can reuse code and save time

Question 16

Key things to take note of when looking at a UML diagram? (unified modelling language)

Answer 16

• make sure the arrow is an EMPTY HEAD ARROW
• the subclasses have the common attributes of the superclass

Question 17

What is a/characteristics of a Primary Key (PK), Composite Key (CK) and a Foreign Key (FK)?

Answer 17

PK: unique values, can have one or many, not null
CK: 2 or more attributes which can help to uniquely identify each record
FK: an attribute which references the PK of another table

Question 18

What is all the boring data confirmation thingy? (data redundancy etc)

Answer 18

data integrity: data is accurate and up to date
data privacy: data is only available to authorised users
data redundancy: data is stored more than once in the database
data dependency: extent to which a program is exposed to changes made to that external data source (wtv this means)

Question 19

What is the definition of normalisation?

Answer 19

The process of organising the tables in a database to reduce data redundancy and inconsistency

Question 20

What are the conditions for the different Normal Forms?

Answer 20

1NF: all attributes have an atomic values
2NF: All non-key attributes are functionally dependent on the primary key
3NF: No non-key attributes are transitively dependent.

Question 21

What is open addressing?

Answer 21

if there’s collision, use probing methods to search for the next empty slot ( linear, quadratic probing)

Question 22

What is closed addressing?

Answer 22

if there’s collision, will use another separate data structure to hold the data (like a linked list etc)

Question 23

What is collision?

Answer 23

collision occurs when 2 different inputs produce the same output. This is usually resolved by using collision resolution scheme such as linear probing

Question 24

What is clustering?

Answer 24

A region of the hashtable is filled up due to linear probing (idk, this was my answer for CT3 and i got it correct, idk how reliable)

Question 25

How to prevent clustering?

Answer 25

• use double hashing
• try not to use quadratic probing as it can cause secondary clustering

Question 26

how to calculate the load factor of a hashtable?

Answer 26

number of filled keys / number of slots

Question 27

idk if this is useful but what is RPN? and why is this tested?

Answer 27

RPN is Reversed Polish Notation
why? idk

Question 28

What to take note when dealing with RPN?

Answer 28

the operations is done with the earlier index value
etc “1,2,3,+,*” (aka [1,2,3])
first operation is
2 + 3, NOT 3 + 2 (will matter if its divide and minus)

Question 29

What is polymorphism?

Answer 29

ability for methods to be modified while having the same function name

Question 30

What is encapsulation?

Answer 30

bundling attributes and data to a specific class.