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