errr basic python theory Flashcards

sorts + data structures + oop

1
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what is the best and worst case of quicksort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the order for Stacks and its operations?

A
  • Last In, First Out
  • push(), pop(), peek()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the order for a Queue and its operations?

A
  • First In, First Out
  • enqueue(), dequeue(), peek()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the advantages of a linked list?

A
  • flexible in allocating memory
  • memory can be reused
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the disadvantages of a linked list?

A
  • High time complexity when traversal
  • High space complexity
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How to find the depth of a binary tree?

A

The length of the longest chain of nodes - 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A
  • preorder traversal: print, left, right
  • inorder traversal: left, print, right
  • postorder traversal : left, right, print
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the definition of recursion?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the definition of data validation?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are some types of data validation?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are some errors?

A

Syntax error, logic error, runtime error

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are some ways of program testing?

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is inheritance and its advantages? (OOP)

A

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

advantages: can reuse code and save time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

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

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

A

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

18
Q

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

A

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)

19
Q

What is the definition of normalisation?

A

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

20
Q

What are the conditions for the different Normal Forms?

A

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.

21
Q

What is open addressing?

A

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

22
Q

What is closed addressing?

A

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

23
Q

What is collision?

A

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

24
Q

What is clustering?

A

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)

25
Q

How to prevent clustering?

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

how to calculate the load factor of a hashtable?

A

number of filled keys / number of slots

27
Q

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

A

RPN is Reversed Polish Notation
why? idk

28
Q

What to take note when dealing with RPN?

A

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)

29
Q

What is polymorphism?

A

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

30
Q

What is encapsulation?

A

bundling attributes and data to a specific class.