Algo 2 Flashcards
Get Average
Write a function that will accept any number of integer or
decimal arguments and return the average of those arguments.
evernote “meetup algorithms”
Time Conversion (HR)
Given a time string in 12-hour AM/PM format, convert it to 24-hour time.
Note: - 12:00:00AM on a 12-hour clock is 00:00:00 on a 24-hour clock.
12:00:00PM on a 12-hour clock is 12:00:00 on a 24-hour clock.
evernote “meetup algorithms”
What is Big O
What is runtime complexity
see Coding Interview Algorithms 1 in Word
What is the efficiency of your algorithm?
Describes how time taken or memory used scales with the amount of data it has to work on.
Big O describes the complexity of the program.
Common sense tells us that it takes longer for the program to run as there is more data.
What is runtime complexity?
Describes the performance of an algorithm.
How much processing time/power is required if we double the inputs.
Runtime complexity of string reversal - explain
see Coding Interview Algorithms 1 - Word
Each additional character one step through one loop
That would be N linear runtime
What is runtime complexity of steps algorithm - explain
see graph in Coding Interview Algorithms 1 - word
2 nested loops
As n increased by one, we had to do way way more stuff, or (n*n ) things total
this would be N^2, or quadratic runtime
List Big O options and explain
bring examples
see Coding Interview Algorithms 1 - word
Constant O(1)
Time taken is independent of the amount of data
Stack push, pop and peek, queue enqueue and dequeue, insert a node into a linked list
Linear O(n)
Time taken is directly proportional to the amount of data
Linear search; count items in a list; compare a pair of strings
Quadratic O(n^2)
Time taken is proportional to the amount of data squared
Bubble sort; selection sort, insertion sort, traverse a 2D array
Polynomial O(n^k)
Time taken is proportional to the amount of data raised to the power of a constant
Logarithmic O(log n)
Time taken is proportional to the logarithm of the amount of data
Binary search a sorted list; search a binary tree
Linearithmic O(n log n)
Time taken is proportional to the logarithm of the amount of data, multiplied by the amount of data
Merge sort: quicksort
Exponential O(k^n)
Time taken ins proportional to a constant raised to the power of the amount of data
n-Queens problem, travelling salesman
What is linear search and it’s complexity?
for graph see Coding Interview Algorithms 1
What is linear search?
Sometimes referred to as sequential search
An unordered list is searched for a particular value
Each value in the list is compared to the target value
Linear search implemented with a simple loop.
see graph PROCESSED - Coding Interview Algorithms 1 on word
Time taken is directly proportional to the amount of data
Linear search complexity
For n data items the time taken is equal to some constant multiplied by n.
The big time complexity is linear O(n)
Stack and stack complexity
for graph see Coding Interview Algorithms 1 - word
Items are pushed onto and popped off the top of a stack
Peek examines top item without removing it
Last in first out data structure (LIFO)
Constructed with an array and a pointer to the top item
we don’t actually remove item from the stack, it gets overwritten next time
Stack operations complexity
Increasing the amount of data makes no difference to the time taken by push or pop
Big O time complexity is constant O(1)
The dominant term
see Coding Interview Algorithms 1
what is bubble sort and it’s time complexity?
enhanced algorithm complexity?
best and worst case scenario?
see Coding Interview Algorithms 1
What are logarithms
see Coding Interview Algorithms 1
Binary search and complexity
see Coding Interview Algorithms 1
merge sort and complexity
see Coding Interview Algorithms 1
Identifying runtime complexity
see Coding Interview Algorithms 1
Constant space complexity examples
see Coding Interview Algorithms 1
