errr basic python theory Flashcards
sorts + data structures + oop
What is the time complexity of quicksort, mergesort, insertion sort, bubble sort and bogosort?
quicksort + mergesort: O(nlogn)
insertion + bubble sort: O(n^2)
bogosort: O((n+1)!) (just trolling)
What is the time complexity of linear search and binary search?
linear search: O(n)
binary search: O(logn)
what is the best and worst case of quicksort?
best case: pivot in the middle
worst case: almost sorted + pivot is the start
What is the order for Stacks and its operations?
- Last In, First Out
- push(), pop(), peek()
What is the order for a Queue and its operations?
- First In, First Out
- enqueue(), dequeue(), peek()
What is the advantages of a linked list?
- flexible in allocating memory
- memory can be reused
What are the disadvantages of a linked list?
- High time complexity when traversal
- High space complexity
How to find the depth of a binary tree?
The length of the longest chain of nodes - 1
What are the orders of output for the different traversals of a BST?
- preorder traversal: print, left, right
- inorder traversal: left, print, right
- postorder traversal : left, right, print
What is the definition of recursion?
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
What is the definition of data validation?
Data validation is the process of ensuring that the data is clean, correct and useful
What are some types of data validation?
Presence, type, length, range, format, restricted value, check digit (weighted modulus)
What are some errors?
Syntax error, logic error, runtime error
What are some ways of program testing?
- Blackbox Testing - testing from perspective of a user (time efficient, no need code access, limited coverage)
- White Box Testing - testing from perspective of developer (not time efficient, need code access, max coverage
What is inheritance and its advantages? (OOP)
Inheritance is when the subclass will acquire the properties and behaviours of its superclass.
advantages: can reuse code and save time
Key things to take note of when looking at a UML diagram? (unified modelling language)
- make sure the arrow is an EMPTY HEAD ARROW
- the subclasses have the common attributes of the superclass
What is a/characteristics of a Primary Key (PK), Composite Key (CK) and a Foreign Key (FK)?
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
What is all the boring data confirmation thingy? (data redundancy etc)
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)
What is the definition of normalisation?
The process of organising the tables in a database to reduce data redundancy and inconsistency
What are the conditions for the different Normal Forms?
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.
What is open addressing?
if there’s collision, use probing methods to search for the next empty slot ( linear, quadratic probing)
What is closed addressing?
if there’s collision, will use another separate data structure to hold the data (like a linked list etc)
What is collision?
collision occurs when 2 different inputs produce the same output. This is usually resolved by using collision resolution scheme such as linear probing
What is clustering?
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)
