Data Structure and Algorithms Flashcards
What’s an algorithm?
An algorithm is a set of instructions to complete a task. When writing code, you can give the computer a set of instructions to achieve a task.
Algorithm speed isn’t measured in time but in big O notation.
Instead, we talk about how quickly the run time of an algorithm increases as the size of the input increases.
What’s log2(n), explain it’s meaning?
Log can be explained using exponent. For example 4^2 = 16.
Then log2 of 16 is 4.
Log2(n) is the number of times you can divide n by 2 before you reach 1. For example log2 of 16 = 4. You can divide 16/2 four times before you reach 1.
Log2(n) is faster than searching linearly because if you are searching for a number between 1-16, it may take you up to 16 steps if you do it linearly meaning if you look at each number to find what you are looking for. If you search for it binarily, you can get there in 4 steps.
What’s a binary search?
Binary search is a method of searching through a list of ordered items. Instead of checking each item individually, we start by looking at the midpoint. If the searched item is too low, we immediately eliminate half of the options and continue searching within the remaining half. We repeat this process until we find the desired item.
Suppose you are guessing a number between 1 and 100. Each time you guess, you are told whether your guess is too high or too low. Using binary search, you can start by guessing 50, which eliminates half of the possible numbers. You then repeat the process until you find the correct number.
Explain Big O Notation
Big O notation is a way to describe the time complexity (number of operations) and space complexity (amount of memory) of an algorithm as a function of the input size. It provides an upper bound on the growth rate of an algorithm’s resource usage (time or space) as the input size increases. Essentially, it helps predict how the algorithm’s performance will scale when dealing with larger data sets.
Big O helps us to understand the worst-case scenario and how the algorithm behaves as the input size grows toward infinity
Some Big O notation run times
O(n) Time Complexity (Linear Time), O(n²) Time Complexity (Quadratic Time), O(log n) Time Complexity (Logarithmic Time)
How does memory work?
Memory in a computer is like a set of drawers. When you store an item, you place it in a specific drawer and receive an address that tells you where it was stored. This address helps you retrieve the item later.
If you need to store multiple items, you can use an array or a list, which organizes data in a structured way, making it easier to access and manage.
What’s an array? Give advantages and disadvantages.
An array is a way to store data in memory. The items in an array are placed next to one another, which means you need a contiguous block of memory large enough to store all the elements.
Advantages of Arrays
One advantage of an array is that it offers fast searching because it is index-based. If you know the index of the item you are looking for, accessing it is very quick.
Disadvantages of Arrays
One disadvantage of an array is that you can run out of space. For example, if you need to store two items, you must have a memory block large enough to hold both because arrays require contiguous memory.
Another disadvantage is that inserting an element anywhere except at the end is expensive. If you insert an element in the middle or at the beginning, you must shift existing elements to make space, which increases the time complexity of the operation.
What’s a linked list? Give advantages and disadvantages.
Linked Lists vs. Arrays
Linked lists are different from arrays. Unlike arrays, which store elements in a contiguous block of memory, a linked list can store elements in different memory locations. Each element (called a node) contains a reference (or pointer) to the next node, allowing the list to be dynamically allocated.
Advantages of Linked Lists
- Efficient Insertions and Deletions: You can quickly insert or delete items without shifting elements, unlike arrays. This makes linked lists useful when frequent insertions or deletions are needed.
Disadvantages of Linked Lists
- Slower Searching: Unlike arrays, where you can access an element in O(1) time using an index, searching in a linked list requires O(n) time because you have to iterate through the list to find an element.
Explain selection sort
Selection Sort Explained
Selection sort is a sorting algorithm that repeatedly iterates over a list to find the largest (or smallest) element and moves it to its correct position. This process is repeated N times until the entire list is sorted.
How Selection Sort Works
- Find the maximum (or minimum) element in the unsorted part of the list.
- Swap it with the last (or first) element in the unsorted part.
- Reduce the unsorted portion of the list and repeat the process until fully sorted.
Performance and Complexity
- Time Complexity (Worst & Average Case): O(n2)O(n2)O(n^2)
- Space Complexity: O(1) (Sorts in-place, without extra memory)O(1)O(1)
- Inefficient for large datasets due to its quadratic time complexity.
What is recursion?
Recursion is a function that calls itself. Every recursive function has two cases: a recursive case, which calls the function again, and a base case, which stops the recursion and exits the function.
What is a stack?
A stack is a data structure that follows the Last In, First Out (LIFO) principle. It supports two primary operations:
- Push – Adds data to the top of the stack.
- Pop – Removes and returns the last item added to the stack.
In programming, function calls are managed using a call stack. When a function is called, it is pushed onto the stack. Once the function completes execution, it is popped off the stack, returning control to the previous function.
What’s the call stack?
Every time a function is called, it is added to the call stack. If multiple functions are called without returning, the call stack can grow too large and run out of memory, causing a stack overflow.
When using recursion, if there is no base case to stop the function, the recursion will continue indefinitely, filling up the call stack and eventually leading to a memory overflow.
Explain the quicksort algorithm
Quicksort is a sorting algorithm. It uses divide and conquer to sort a list.
First, choose a pivot, then iterate through the list. Place value less than the pivot to the left and greater to the right.
Then use recursion to repeat the process until the whole array is sorted.
- Best/Average Case: O(nlogn) (when partitions are roughly equal)O(nlogn)O(n \log n)
- Worst Case: O(n2) (if the pivot is always the smallest or largest element)O(n2)O(n^2)
What’s a hash function?
- A hash function takes an input (string) and returns a number.
- It should map different words to different numbers.
- The same word should always map to the same number.
How a Hash Function Works?
- There is an array in the background.
- When a string is input, the hash function converts it into a number, which serves as the index where the value is stored.
- To retrieve a value, the hash function finds the corresponding index.
Example:
Given key-value pairs:
-
avocado: 1.23,peach: 2.12,tomatoes: 2.3
The hash function might convert:
avocado → 0tomatoes → 1peach → 2
Stored in an array as:
0: 1.23 — 1: 2.3 — 2: 2.12
To get the price of tomatoes, the function returns:
```python
array[1] = 2.3
~~~
