DSA Mock Interview Flashcards
How might you determine the efficiency of an algorithm?
Determined by the Big O notation
Why is the Big O Notation important?
So that we can have the code as smooth as possible. Speed is important.
What categories of complexities are described in Big O Notations
Time complexity: How long code will take to execute as data increases
Space complexity: How much space is needed and how efficiently it is used
More space = less time and the other way around
What is O(1)
O(1) = Constant Time
examples:
- setting a variable once
- performing a calculation
- determining if an integer is even or odd
Basically a flat line on a graph. Easy to plan for.
What is O( n )
O( n ) = Linear Time
examples:
- basic non-nested for loops
- finding smallest or largest item in an unsorted array
Basically a 45 degree line on graph, still easy to plan for, scaling probably won’t run away from you.
What is O( n^2 )?
O( n^2 ) = N squared
- basic nested for loops, bubble sort, insertion sort.
Starts to get harder to plan for as data sets increase dramatically.
What is O( log n )
O( log n ) = Log N (Logarithmic Time)
- binary search - when you can easily eliminate large sections of data on each iteration.
Means that scaling large data sets won’t dramatically increase the output time.
Describe 3 differences between a linked list and an array
LINKED LIST:
- Non-contiguous space requirement.
e. i. Data doesn’t HAVE to be in same space on disk. - Can be more efficient for memory allocation. Easier to resize.
- Can be less efficient for caching (not contiguous)
- No “find by index” feature, so accessing individual elements can be slower
- Easier to add elements (insert nodes) to various positions within list.
ARRAY:
- Must be in same contiguous disk space.
- Harder to resize. Also, increasing length may require moving the array in memory to a larger space.
- Better caching - all addresses are contiguous
- Fast access for reading when searching by index
- Harder to insert new elements to front and within the array as you then have to shift existing elements after the new element is added.
What’s the difference between a Binary Tree and a Binary Search Tree
BST: All left descendants are less than or equal to node, and all right descendants are greater than node.
BST (Binary Search Tree): All left descendants are less than or equal to node, and all right descendants are greater than node
Q: describe the 3 types of BST traversal:
25
/ \
10 32
In-order (from the smallest number to the biggest) (ex: 10, 25, 32)
Visit left branch, then current node, then right branch. Visits all nodes in ascending order on a BST.
Pre-order (looks like the ““ sign) (branches first, node last) (ex: 10, 32, 25)
Visits left branch, then right branch, then current node. Root node is always last visited. Useful for language processors
Q: Algorithms for searching through arrays and trees
Linear search
Binary search
Depth-first search
Breadth-first search
Linear search
Look through an array one-by-one until you find what you are looking for
Binary search
Narrow it down by always guessing in the middle of the range
Depth-first search
Traverse as far as you can down the tree before back-tracking
e.i. check if a person related to a past royal relative has the right to be a king
Breadth-first search
Search works across the rows of a tree (the top row will be handled first, then the second row, and so on)
e.i check if multiple people from the same generation are part of the royal family
Q: Array sorting methods
Merge sort Bubble sort Quick sort Selection sort Insertion sort Heap sort Bucket (bin) sort
Merge sort
- DIVIDE THE UNSORTED LIST INTO N SUBLISTS, each containing 1 element (a list of 1 element is considered sorted).
- repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
Bubble sort
REPEATEDLY SWAPPING the adjacent elements if they are in wrong order.
Quick sort
- DIVIDE AND CONQUER algorithm. It creates two empty arrays to hold elements less than the pivot value and elements greater than the pivot value, and then recursively sort the sub arrays. There are two basic operations in the algorithm, swapping items in place and partitioning a section of the array.
Selection sort
- REPEATEDLY FINDING THE MINIMUM ELEMENT (considering ascending order) from unsorted part and putting it at the beginning
Insertion sort
- Begin at the left-most element of the array and invoke Insert to INSERT EACH ELEMENT ENCOUNTERED INTO ITS CORRECT POSITION.
- The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of indices already examined.
Heap sort
- Involves preparing the list by first TURNING IT INTO A MAX HEAP (a complete Binary Tree represented as an array)
- then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap.
Bucket (bin) sort
- sorting algorithm that works by DISTRIBUTING THE ELEMENTS OF AN ARRAY INTO A NUMBER OF BUCKETS.
- each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.
- sort each non-empty bucket.
Q: What are the arrays sorting methods by speed
The slowest is selection, then bubble, then insertion, then shell, then merge, then heap, then quick, then quick3
Q: What is faster than a bubble sort?
Insert, Shell, Heap, Merge, Quick and Quick3
Possible coding challenge
Create an algorithm for counting how many times a word appears in a document.
Computational Complexity
O(1) - constant time
O(log n) - logarithmic time
O(n) - linear time
