The landscape of coding interviews has evolved dramatically, becoming more challenging as we now have access to a plethora of coding problems. This increased competition means that merely understanding basic data structures and solving a handful of problems is no longer sufficient. This repository serves as a comprehensive guide to tackling these complexities. It is designed to help you master the intricacies of data structures and algorithms through a structured and pattern-based approach. Here, we break down the most common and challenging coding interview questions into understandable patterns, providing you with the tools to recognize and solve similar problems.
- By large, Computer Science concepts are seen as standalone. However, you might need to use it to build upon other elements.
For instance, in Machine Learning, there is a need for Linear Algebra, Calculus, and Statistics.
- Reasons for using DSA in ML:
- Finding the correct DS for various situations
- Be thoughtful for time/space complexity in:
- Model Training
- Model deployment on a larger scale
- Be thoughtful for time/space complexity in:
- Finding the correct DS for various situations
Source: Data Structures, Algorithms, and Machine Learning Optimization
The rate of increase of an algorithm is also referred to as the order of the algorithm
For example, instead of saying "this relationship has a linear rate of increase", we could instead say, "The order of this relationship is linear".
O Notation, and you'll see that the "O" in the name refers to the order of the rate of increase.
- Manually shipping a dataset stored in a hard drive to a data center has constant time (e.g. 24 hours). But uploading it to a server is not (route problems, encryption)
- For many problems, it's advisable to find the worst, best, and average Big O runtime complexity
We keep the m. Given that it might be large. 
- Common data structures:
- Big O notion
Linked lists are not indexed. Only nodes are linked together. 
- Stacks are implemented as lists in Python. s.append, s.pop
- Queue: beginning and end are available. You can also take a peek at the first one.
- Deques (Double ended- queue):
The summary of Data Structures and Algorithms plus Interview steps.
Take a look at a simple question like below: Question 1: Write an algorithm/program that returns the difference of two dates.
Step 1: Ask yourself the following questions
Q: For inputs (dates), what are the valid inputs? Q: How input are encoded? (yyyy,mm,dd) Q: Possible output returns? (an integer)
Step 2: Write simple code that works partially for the problem
- Chances are, you need to consider all possible conditions. Often, this results in getting stuck in finding the perfect solutions. Hence, it's advisable that you find the simplest solution that works. E,g, solve with a single simple case.
Tips: Break into simple parts so that we can see our progress. Write simple small codes that work No need to figure out all the details.
Now we look into the main topics that are being covered in most interviews/coding challenges. We also look into the patterns that appear in solutions that can be used in new problems. The goal is to understand the fundamentals and try to use them to solve problems.
What are time complexity of the following problems?
Finding the smallest of n numbers?
• Answer: O(n-1) ~ O(n)
Finding the biggest of n numbers?
• Answer: O(n-1) ~ O(n)
Finding the smallest and the biggest of n numbers?
• Answer: O(2n-3) ~ O(n)
Q: How to find number 25 in this a sorted array? A:
1. Linear search: O(n)
2. Binary Search: O(log(n)+1) ( Why it is called binary search? find a postion of binary)
Bubble sort:
Simple but not efficient
T:
Merge Sort:
Divide and Conquer: First, we divide 2 by 2
Second, we compare the elements and join the elements
Efficiency:
O (n log (n))
Q: Why we are seeing log (n) in our efficiency? Hint: same as the binary search problem
Efficiency:
O(n2) if it’s already sorted. Why? Wasting time
(Programming == tables)
The factorial problem in Python:
DP = Recursion + Memo-ization
Knapsack problem: Max value for weight limit
Knapsack. If you have to carry a weight (50kg) in your bag, how can you gather the most valuable items (e.g., 3 as the weight,500 as the value) with you?
How do you optimize which items with their weights to carry with you?
- Brute force: Check all the solutions and pick the best one: O (2^n) possible combinations. “exponential time”
Can we have a polynomial time algorithm? O(n^2)
- Smarter approach: Initiate with smallest item (2, 6) then (5, 9). Note that (4, 6) will not be placed since for index 4 value 6 is larger than 5.
Next look at index 6. By combining smallest value (2, 6) + (4, 5) we get higher value (11).
Figure: For each weight the maximum value we can hold.
Runtime is O(nW).
- Dynamic programming: {can you break into sub problems}
Sub-problem: Max value for some smaller weight
We start by using Base case ( so trivial to compute)
Base case: Smallest computation (compute values for one object)
+
Lookup table to store the trivial cases.
Longest common subsequent
The best option at each step might not lead to the best results.
Graph is a data structure that is mostly used to shows relations.
Directed (non-directed), Acyclic
The notion of connectivity: As seen below, the right graph is stronger. In contrast, the left group can be dissolved if one of the connections drops.
Sources to learn more:
- Udacity nano degree: Data Structures and Algorithms
- Data Structures and Algorithmic Thinking With Python
- Data Structures, Algorithms, and Machine Learning Optimization [If you are interested in ML]
- Bari's YouTube playlist [If you are a beginner]
DSA problems:
Machine Learning:
The following sources can be used for academia and research:
Complexity Theory##
Class P: n, n^2,… (any problem that can be solved in polytime)
Class NP (Nondeterministic):
Class Co-NP: _No_ polytime
Quick Sort: The idea is to use pivots to sort the array.
On each step we are performing two moving around.
(Pivot = Last element)
- Select the rightmost element as the pivot
- Shift Pivot to left by one element
- Swap start and left
- Compare Start with pivot. If (Start > Pivot repeat step 2)
- Else move to second start
Why it can be chosen as the most efficient algorithm?
Because on average it will outperform merge sort.
Great no need to move the original pivot anymore (2 is at the right place)
Check 2 with lefts
New pivot on right. Compare
Moving phase
Everything less than 8 and 10 sweep results in:
Everything less than 8 is already below 8