Back To Back SWE
What Is Asymptotic Analysis? And Why Does It Matter? A Deeper Understanding of Asymptotic Notation.
updated
A useful tool for understanding recursive algorithms is the recurrence.
A recurrence allows us to succinctly say exactly what a recursive algorithm does in terms of work and analyze it.
π Free 5-Day Course - backtobackswe.com/five-day
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
A linked list is a linear data structure that consists of "nodes" that are connected by "links" to form a linked structure that is a conceptual list.
The "nodes" are often objects in memory and the "links" are pointers that point to the next node in memory.
Before knowing what types of linked list i.e. singly linked list, doubly linked lists, and circular linked list in different languages like c, python, java, etc. are, you need to understand what linked lists are.
π Free 5-Day Course - backtobackswe.com/five-day
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=APRIL40
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
β New Unseen Questions
Given a sorted array, create a binary search tree with minimal height.
Input:
[1, 2, 3, 4, 5, 6, 7]
Output:
[4, 2, 6, 1, 3, 5, 7]
Explanation:
4
/ \
2 6
/ \ / \
1 3 5 7
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
π Free 5-Day Course - backtobackswe.com/five-day
Levels In A Binary Tree
In general, a binary tree with n nodes will have at least 1 + floor(log_2(n)) levels
When we do something like a tree traversal or heap insertion or removal this is why we use a bound of O(h) which for a balanced binary tree really means O(log(n)).
We will traverse at most a log amount of levels in the asymptotic sense since that is our tail behavior. Our asymptotic behavior is logarithmic.
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
π Free 5-Day Course - backtobackswe.com/five-day
In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge.
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
π Free 5-day mini-course - backtobackswe.com
Quicksort is popular because it is not difficult to implement, works well for a variety of different kinds of input data, and is substantially faster than any other sorting method in typical applications. It is in place (uses only a small auxiliary stack), requires time proportional to N log N on average to sort N items, and has an extremely short inner loop.
Quicksort is a divide-and-conquer method for sorting. It works by partitioning an array into two parts, then sorting the parts independently.
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
π Free 5-Day Course - backtobackswe.com/five-day
First, we must ask what asymptotic means. Well, you have probably heard of the word "asymptote".
An asymptote is a "line that continually approaches a given curve but does not meet it at any finite distance".
Therefore, asymptotic analysis is the analysis of tail behaviors not reaching any finite point. It is a method of describing limiting behavior.
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
π Free 5-Day Course - backtobackswe.com/five-day
A priority queue is an ADT that behaves like the normal queue but each element has some priority, i.e., the element with the highest priority would come first. The priority of the elements in a priority queue determines the order in which elements are removed from the queue.
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Most programs contain loop constructs. When analyzing running time costs for programs with loops, we need to add up the costs for each time the loop is executed. This is an example of a summation. Summations are simply the sum of costs for some function applied to a range of parameter values.
π Free 5-Day Course - backtobackswe.com/five-day
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
An ADT is a data type is defined by its behavior from the point of view of a user of the data, we can implement it however we want as long as we give the user the interface they need to get what they expect from the ADT.
APIs let your product or service communicate with other products and services without having to know how theyβre implemented.
π Free 5-Day Course - backtobackswe.com/five-day
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Preorder Traversal: node left right
Inorder Traversal: left node right
Postorder Traversal: left right node
π Free 5-Day Course - backtobackswe.com/five-day
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
An overview of how to solve problems using backtracking. We make choices, constrain how our recursion advances, and converge toward a goal.
π Free 5-Day Course - backtobackswe.com/five-day
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Asymptotic Analysis: It is widely used in Computer Science to describe the limiting behavior of algorithm resource use.
We look at functions to see their behavior (often to track resource consumption) when an input gets arbitrarily large (big).
But first off, what is a function? What does y = 2x mean? Let's go way back.
It means this:
- Each variable is something we are tracking. Here we track y and x. They can be anything we want them to be
- y and x are intimately related by our function that we defined
- Each time we gain 1 unit of x, we gain 2 units of y
- x is input and y is output (Remember: we can have more than 1 input variable influencing y)
So what is y and what is x (or our series of inputs if we had more)? Whatever we want them to be.
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=YOUTUBE20
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
β New Unseen Questions
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Flow Networks: en.wikipedia.org/wiki/Flow_network
FordβFulkerson Algorithm: en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Max-Flow Min-Cut Theorem: en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Proofs: Reference "Algorithm Design" by Jon Kleinberg and Γva Tardos Chapters 7.1, 7.2 for excellent proofs on all of this.
Things I'd Improve On This Explanation (w/ More Time):
1.) I should have done a walk-through showing how the residual graph dictates how the original graph's edge flows (f(e)) are updated each iteration. (That would've made it more clear how the residual graph in the Ford-Fulkerson algorithm tells us how to update the flow on each edge (f(e)) in the original graph along the s-t path P, THEN we update the residual graph (also along P) to prepare for the next iteration.)
2.) Go into the actual augmentation once we find an s-t path P in the residual graph. We can only modulate the flow f(e) for each edge in the original graph on path P Β± the smallest value residual graph edge on path P. The smallest forward edge on path P in the residual graph is the "bottleneck" to how much we can increase flow along the path P in the original graph. (hard to visualize...the textbook may have to take it away with this one, but when you understand this you'll really get it after watching this video)
I also didn't talk about time complexity, but the amount of while loop iterations is bounded to the capacity coming out of start node 's'. We can't ever push more flow from 's' than the sum of capacities of those exiting edges. If each interaction increases the value of the flow v(f) by 1 (and v(f) starts at 0 in the beginning since no "water" is going through the "pipes"), we can do at most C augmentations of the flow network where C = sum(edge capacities leaving 's').
In each while loop:
- O(|V| + |E|) to find the augmenting path
- O(|E|) to update the flows in the original graph
- O(|E|) to update the residual graph
So total runtime can be bounded to O(C * (|V| + |E|)).
#backtobackswe #benyamephrem
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Subscribe To Live Tech Offers: offerfeed.io
Join Our Coaching Service: backtobackswe.com/coaching
In this video, we talk about the Interval Scheduling Maximization Problem. We look at the greedy solution as well as a proof via an exchange argument.
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Subscribe To Live Tech Offers: offerfeed.io
Join Our Coaching Service: backtobackswe.com/coaching
This is a video walking through & contrasting Dijkstra's Algorithm & Prim's Algorithm based on the greedy choices each algorithm is optimized to make.
Prim's algorithm optimizes for the min-cost edge that connects the subset of vertices not in the minimum spanning tree to the subset of vertices in the minimum spanning tree we are trying to expand. We ensure every iteration we are choosing the min-cost edge that crosses the cut (wikipedia: a 'cut' is a partition of the vertices of a graph into two disjoint subsets).
Dijkstra's algorithm optimizes for the shortest cost path to get from the start vertex to a given vertex. We ensure every iteration we are improving our tentative costs from a fully optimized vertex.
Big thank you to Professor Kruskal for taking the time to do this with me.
Kruskal's Algorithm: en.wikipedia.org/wiki/Kruskal%27s_algorithm
Clyde Kruskal: https://www.cs.umd.edu/~kruskal
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Subscribe To Live Tech Offers: offerfeed.io
Join Our Coaching Service: backtobackswe.com/coaching
For a long time I've wanted to create a class/community around technical interviews. This is something I will be dedicating a lot of time to in the coming months.
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Subscribe To Live Tech Offers: offerfeed.io
Join Our Coaching Service: backtobackswe.com/coaching
___________________________________________________________________
Endscreen Music by: http://www.davidcuttermusic.com / @dcuttermusic
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
I found this proof in my algorithms class notes. I think I explained this decently.
Some Notes On This Topic: https://www.cs.umd.edu/users/meesh/cmsc351/mount/lectures/lect16-lower-bnds-sorting.pdf
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Samrat Jha is a software engineer at Appian Corporation (at the recording of this interview).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given a root node for a binary tree, serialize the binary tree into a string representation. Deserialize that same string representation into a tree identical to the original tree given.
The key is to understand what our fundamental operation/job is in each call to the function.
Our fundamental job is to encode/materialize a single node/int value.
Compiler Design Phases: geeksforgeeks.org/compiler-design-phases-compiler
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
Elements of Programming Interviews problem 10.13
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Gaurav Sen teaches system design on YouTube and is a software engineer.
Gaurav's YouTube Channel: youtube.com/channel/UCRPMAqdtSgd0Ipeef7iFsKw
Gaurav on LinkedIn: linkedin.com/in/gaurav-sen-56b6a941?originalSubdomain=in
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given an array and k, find the k'th largest element as efficiently as possible. Return the actual value of the k'th largest item.
I got this question in my final round of Facebook internship interviews...this is before I knew how to solve recurrences and analyze algorithms, etc...I fucked it up but who cares...I talked for so long and thought the optimal solution was log(n)...but I was really wrong.
Approaches
Sort: O(n*log(n))
Use A Min-Heap: O(n*log(k))
Remember QuickSort...how does it work...what does it fundamentally do...partition
The kth largest element will be at index n - k
Ex:
arr = [ 3, 2, 1, 5, 6, 4 ]
k = 2
The first largest element should be at the last index ... index 5 ... (6) - (1) = 5
The 2nd largest element should be at index (6) - (2) = 4
The n'th largest element should be at the first index ... index 0 ... (6) - (6) = 0
So...
finalPivotPosition == n - k ... The pivot is the k'th largest element
finalPivotPosition greater than n - k ... k'th largest must be in the left partition
finalPivotPosition less than n - k ... k'th largest must be in the right partition
We an pick a pivot however we want but random is best since we have a equal likelihood to pick any element.
The worst case is O(nΒ²) but the likelihood this can happen goes down exponentially because it can only happen if the greatest or least item is chosen as a pivot repeatedly.
Complexities
Time: O(n)
On average we will be splitting the input in half leading to a recurrence of T(n) = T(n/2) + (n - 1)
If we solve for these exact amount of comparisons we see that we stay to the order of linear time.
Space: O(1)
Everything is done in-place.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is question 12.8 in the fantastic book "Elements of Programming Interviews".
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Implement counting sort. Analyze its best, average, and worst case time complexities.
This algorithm generalizes to anything that you can map to a positive integer value for sorting (like sorting an array of characters).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Write a program which takes as input a very long sequence of numbers and prints the numbers in sorted order. Each number is at most k away from its correctly sorted position. (Such an array is sometimes referred to as being k-sorted).
Pramp: pramp.com
Examples:
Input:
[ 3, -1, 2, 6, 4, 5 , 8 ]
k = 2
Each number is no more than 2 indices from its final sorted position.
Output:
[ -1, 2, 3, 4, 5, 6, 8 ]
It is often that data finds itself in an almost sorted state.
For example: A server needs to sort orders coming in internationally and due to differences in server loads and network routes some earlier orders come in after later orders.
How do we efficiently sort this almost sorted data?
Whenever I hear or think of sorting or searching, I think of my fast sorting algorithms, binary search, and min/max heaps.
Approach 1 (Brute Force)
Just run a quick sorting algorithm like mergesort or quicksort and have the array sorted in O( n * log(n) ) time.
This is an obvious answer.
The key insight we need to make is that most of the items are very close to their final positions and therefore we need to just βtouch upβ the order of the items.
How will we perform this βtouch upβ?
Approach 2 (Min Heap To The Rescue)
Example:
[ 3, -1, 2, 6, 4, 5, 8 ]
k = 2
How do I know who belongs at index 0?
Well, this leads me to ask you, what are the potentialities for each index? What items could be at index 0?
3 can, -1 can (if it moves 1 spot back), 2 can (if it moves 2 spots back), but 6 cannot (it would have to move 3 spots back but k = 2, this is not allowed).
Now our interest is in k + 1 items, 3, -1, and 2 each could go at index 0.
Our job is now reduced to finding the minimum of k + 1 elements at a time.
What data structure helps me with keeping track of minimums and maximums in a set of data very well?
A heap.
We will use a min heap because we want access to the smallest item across k + 1 items.
The Algorithm
Add the first k + 1 items to a min heap.
Iterate through every index in the array.
Place the min item and add the next item that has not been added yet to the heap.
When we cannot add un-added items to the heap near the end (at some point every item will have seen the heap but we will not be at the end of the iteration just yet) we can just continue ejecting and placing the min items.
Complexities
Time: O( n * log( k ) )
For all n items we will perform an insertion and removal from a min heap holding k + 1 items.
Space: O( k )
The heap will hold k + 1 numbers at maximum before an item is ejected.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is 11.3 in the book "Elements of Programming Interviews"
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given the root of a binary tree and 2 references of nodes that are in the binary tree, find the lowest common ancestor of the 2 nodes. The nodes do not have parent pointers.
The Approach
So there are many modulations of this problem where you can build a hashtable and make parent pointers, etc. We will focus on the recursive solution.
The Algorithm
The key is that we want to root ourselves at a node and then search left and then right for either of the 2 nodes given.
If we see either node, we will return it, if we do not find the node in a subtree search the value of null will be returned and bubbled up.
After we search both left and right we ask ourselves what our results mean.
If we found nothing to the left, we just bubble up what is on the right (whatever that search result may be). This node we sit at cannot be the LCA since the left and right did not yield the 2 nodes we want.
If we found nothing to the right, we just bubble up what is on the left (whatever that search result may be). This node we sit at cannot be the LCA since the left and right did not yield the 2 nodes we want.
If both the right and left result are not null, we have found our LCA.
Why?
We know it is an ancestor at the least but we definitely know it is the lowest common ancestor because we went bottom upwards, whatever we hit will be the LCA and it will bubble up.
Complexities
Time: O( n )
We will be touching the whole tree in the search, there are n nodes in the tree and we do O(1) work at each node. There are not exactly n calls though but I need to double check this...I need to solve the recurrence but oh well...we know it will stay linear in the asymptotic regard.
Space: O( h )
Stack usage at maximum will be the trees height. Worst case would be O(n) if our tree is skewed purely to the left or right and we need to find deep nodes. But n IS h in that case. But we say O( n ) in that case since it is more accurate to what is happening, the tree's size in nodes dominating the height.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Subscribe To Live Tech Offers: offerfeed.io
Join Our Coaching Service: backtobackswe.com/coaching
Question: Implement QuickSort. Explain how it works. Explain the best and worst cases.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: There are 2 versions.
Version 1: Every row is sorted left to right in non-decreasing order. The first integer of each row is greater or equal to the last integer of the previous row.
Version 2: Every row is sorted left to right in non-decreasing order. Every column is sorted top to bottom in non-decreasing order. There are no guarantees that the first item of any row or column relates to the last item in the previous row or column.
Sorted. Binary search is very likely. Investigate, how do we reduce our decision space?
Our first answer does not need to be logarithmic (it is so crucial you understand logarithms and what they mean....you need to know your complexities to refine answers and notice avenues to better solutions).
The key to search problems is that you notice the fundamental decision we can make to reduce the problem.
...more notes I wrote...
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Can we multiply 2 numbers using less than n^2 atomic multiplications? Yes, we can.
Update: There is O(n*log(n)) integer multiplication now: https://hal.archives-ouvertes.fr/hal-02070778/document
Karatsuba Multiplication On Wikipedia: en.wikipedia.org/wiki/Karatsuba_algorithm
You don't need this for the interview.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Free Mini DSA Course - backtobackswe.com
Try Our Full Platform: backtobackswe.com
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
An overview of how to solve problems using backtracking.
- We make choices, we constrain how our recursion advances and we converge toward a goal.
- It can be used in multiple problems:
N Queens
Graph coloring
Sum of Subset
0/1 Knapsack
- It is also an important concept for Artificial Intelligence.
N Queens Video: youtube.com/watch?v=wGbuCyNpxIg
0/1 Knapsack Video: youtube.com/watch?v=xCbYmUPvc2Q
++++++++++++++++++++++++++++++++++++++++++++++++++
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Great Resource: cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/analysis/notations.html
Big O Cheat Sheet: http://bigocheatsheet.com
Today we will initiate a discussion on something that I have lied to you about for a very long time. This will be as simple as possible.
We will not only consider the informal definition but rather also look at the mathematical understandings behind why we call these asymptotic βboundsβ.
Again, we care about this because the true colors of an algorithm can only be seen in the asymptotic nature of runtime and space.
So imagine this, we have these components:
A function T(n) which is the actual number of comparisons, swaps...just...resources an algorithm needs in terms of time or space. It is a function of n. When n changes, T(n) changes.
Our job is to classify behaviour.
A bound O( f(n) ) is the function that we choose to apply for the specific bounding.
The definitions, an example:
"T(n) is O(f(n))" iff for some constants c and n0, T(n) less than or equal to c * f(n) for all n greater than or equal to n0
In English...this means...we can say that f(n) is a fundamental function that can upper bound T(n)'s value for all n going on forever.
We have an infinite choice for what c is.
Our constant does not change behavior, it changes "steepness" of the graph.
We are saying that...if I declare f(n) as an upper bound, then I can find a constant c to multiply against f(n) to ALWAYS always always keep T(n) beneath my c * f(n)...T(n) will never beat c * f(n) for infinite n values...hence asymptotic bounding.
If we can't find this c then f(n) fails as an upper bound because it does not satisfy the asymptotic requirement.
So why are constants dropped?
Well...think about what we just did. The injection of the arbitrary c as a multiple onto a base function removes the need for a constant. It adds no meaning to a bound because it is conceptually already a part of the definition of what a bound is.
Big Bounds
Big O: Upper bound on an algorithm's runtime
Theta (Ξ): This is a "tight" or "exact" bound. It is a combination of Big
For example:
An algorithm taking Ξ©(n log n) takes at least n log n time, but has no upper limit.
An algorithm taking Ξ(n log n) is far preferential since it takes at least n log n (Ξ©(n log n)) and no more than n log n (O(n log n)).
Big Omega (Ξ©): Lower bound on an algorithm's runtime.
Little Bounds
Little o: Upper bound on an algorithm's runtime but the asymptotic runtime cannot equal the upper bound.
There is no little theta (ΞΈ).
Little Omega (Ο): Lower bound on an algorithm's runtime but the asymptotic runtime cannot equal the lower bound.
If you can't get an exact upper bound, try lower bounding (although it is less useful to be honest).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
#asymptoticnotations
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Analyze Heap Sort's comparisons exactly in the best, average, and worst case of input data. Give an asymptotic bound for each case.
Video On Implementing A Binary Heap: youtube.com/watch?v=g9YK6sftDi0
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given an array with a sequence that represents a RPN expression, evaluate the Reverse Polish Notation expression.
This is one of those textbook problems. It is a classic expression of when LIFO behaviour is favorable to us when solving certain problems.
To have an RPN expression we need 2 things by definition:
A single digit or series of digits.
It is in the form ["A", "B", "o"] where A and B are integers and o is an operator (either +, -, *, or / ).
Examples:
[ "3", "4", "+", "2", "*", "1", "+" ]
is the same things as ( ( 3 + 4 ) * 2 ) + 1
which is the same things as ( 3 + 4 ) * 2 + 1 because of order of opeartions.
Example 2:
[ "1", "1", "+", "2", "2", "*", "+" ]
Approach
This is a classic stack problem, let us just do this.
The 2 key operations:
When we see a digit we push it to the stack.
When we see an operation we perform 2 pops, apply the operation between the 2 values (first popped item goes on left of the sign, 2nd popped item goes on the right of the sign), and then push the result back onto the stack so we can work with it as we continue.
If it is a valid RPN expression then we should have no problems with mismatches and null pointers, clarify that it is a valid RPN string always with your interviewer.
Complexities
n is the length of the RPN expression
Time: O( n )
We will process all n operators/operands in the expression. Each will either entail an O(1) push/pop or an O(1) arithmetic calculation.
Arithmetic operations take O(1).
Push and pop take O(1).
Space: O( d )
Let d be the total operands (numbers).
Let b be the number of operators (+, -, *, /)
If we have d digits and b operators where d + b = n, we certainly will not use O( d + b ) space (operators are not pushed to the stack).
A worst case is that we have all numbers, followed by the operators. And we will have a stack height of d digits. So we can bound to that.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 9.2 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Add two integer values without using the "+" operator.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given a string S and a string T, find the minimum window in S which will contain all the characters in T (matching or exceeding in frequency) in complexity O(n).
Anytime we have time reduced to linear time and we know that much must be done, that is indicative of using some sort of auxiliary structure to keep track of information for us so time can stay low in complexity.
Complexities
s = length of search string
t = length of "pattern" or "character" string
Time: O( s + t )
At worst we will touch each element twice, once by the left pointer and once by the right pointer.
Ex:
s = "aaaaat"
t = "t"
We will spend t time to build the character requirements hashtable.
Space: O( s + t )
At worst the window hashtable will have a mapping for every character in s.
At worst t will have all unique characters.
s = "abcdef"
t = "abcdef"
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is 13.7 in the fantastic book Elements of Programming Interviews
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Analyze the total work that Merge Sort performs as an exact function of n, the length of the input list.
My Old MergeSort Video: youtube.com/watch?v=fHYVhCL4riM
The Infinite Series 1 + 2 + 4 + 8 + ... : en.wikipedia.org/wiki/1_%2B_2_%2B_4_%2B_8_%2B_%E2%8B%AF
Logarithm Rules: chilimath.com/lessons/advanced-algebra/logarithm-rules
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: You are given n eggs and specified a number of k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if the egg is dropped, it will break.
Note: There are more optimal solutions than this approach, but in a 45-minute interview they seem to me unreasonable to get. So I covered what one could reasonably deduce given they have never seen this question.
Complexities
Time: O( totalEggs * totalFloors^2 )
We will have totalEggs * totalFloors subproblems and spend O(totalFloors) time computing each subproblem.
Space: O( totalEggs * totalFloors )
We can upper bound to the number of subproblems which will be totalEggs * totalFloors subproblems (whether you include the base cases or not in the memoization table)
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: You are given 2 strings. Return the length of the longest subsequence that the 2 strings share.
Complexities
n = s1.length()
m = s2.length()
Time: O( nm )
We can upper bound time by the number of subproblems that we are going to solve.
Space: O( nm )
We upper bound space by the number of subproblems we will story answers to. Whether we do (n + 1)(m + 1) or (n)(m) doesn't matter asymptotically.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: You are given 3 things. The root of a binary tree, a single start node in the binary tree, and a number k. Return all nodes that are k "hops" away from the start node in the binary tree. Return a list of the values held at those nodes.
Complexities
n = total amount of nodes in the binary tree
m = total edges
Time: O( n + m )
This is standard to Breadth First Search. We upper bound the time by the number of nodes we can visit and edges we can traverse (at maximum).
Space: O( n )
We have a hashtable upper bounded by n mappings, a mapping to each node's parent.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Implement a queue (a FIFO structure...first-in-first-out) only using stacks internally as efficiently as possible.
This problem is classic and well known but as always, I want to walk you through the thought process and not just present the solution.
Complexities
n is the total items between the 2 stacks (in the overarching queue)
Time: O( 1 ) - amortized (for enqueue and dequeue operations)
Amortized time is the way to express the time complexity when an algorithm has the very bad time complexity only once in a while besides the time complexity that happens most of time (medium.com/@satorusasozaki/amortized-time-in-the-time-complexity-of-an-algorithm-6dd9a5d38045).
The motivation for amortized analysis is that looking at the worst-case run time per operation, rather than per algorithm, can be too pessimistic. (en.wikipedia.org/wiki/Amortized_analysis).
Space: O( n )
We upper bound space to the maximum amount of items that we will ever store.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 19.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: You are given the root node of a binary tree. Return a list consisting of each level of the tree (we will have a list of lists, a list for each level's items), where each level is traversed from left to right. A level order traversal.
What Do We Know?
We know our preorder, inorder, and postorder traversals...but this is a little different.
We want to go level by level here...what does this remind us of?
Every acyclic connected graph is a tree, and all trees are acyclic connected graphs.
This unlocks our ability to search a tree list we search a graph, using Breadth First Search and Depth First Search.
DFS will go deep, and BFS will go out level by level. We want BFS since it is a more natural approach to something like this.
We realize that this is just the breadth-first search of a tree structure.
We shift our knowledge from graph search to this problem.
Complexities
n is the total amount of nodes in the binary tree
Time: O( n )
Space:
With output: O( n ) because we will store n nodes in the list of levels structure.
Without output: O( n ) the queue at maximum at any point in time will hold some fractional component of the total nodes in the tree.
The fractional constant disappears and the asymptotic behavior is linear.
We can't bound the max space in the queue to the widest level because when we process the widest level...if there is a level below it we will have all the nodes from the widest level PLUS what we are adding into the queue as we process each node in the level (we remove 1 node and can add 2 children which will push us past the size of the widest level initially).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Give exact comparisons and moves that happen in the best, average, and worst case of insertion sort.
Gauss' Trick: http://mathcentral.uregina.ca/qq/database/qq.02.06/jo1.html
Bubble Sort Analysis: youtube.com/watch?v=euPlXW7dnlI
I'm so sorry that my camera was about to die. I had to cut the video short. The average case is the hardest part to understand so this video also would have been much longer.
I'm not sure if I will ever cover it in a video...so there's a really hard challenge. What's the amount of comparisons and moves for the average case? (the hard part is calculating the expected value for the total while loop comparisons)
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given a 2D matrix with integer values (and including at least 1 positive value) find the sub-rectangle with the largest sum.
I want to step you through all of the tough mental leaps to solve this problem.
Complexities
Let rows = the number of rows
Let cols = the number of columns
Naive Runtime: Ξ©(rows^2 * cols^2)
Explanation:
There are rows * cols possible start points and for each rows * cols possible start points we will do O(rows * cols) work, this causes us to have our time lower bounded by the amount of time it takes to explore all top left and bottom right combinations so that we can explore all 2D rectangles in the matrix.
This is not even including getting the sum for each 2D rectangle we set bounds for (we can do it in O(rows).
Similar to this problem leetcode.com/problems/range-sum-query-2d-immutable
Optimal Solution Runtime (2D Kadane's): O(cols^2 * rows)
We will try all combinations of left and right ending points for the possible 2D rectangle.
For that O(col^2) work we will do O(row) work to run Kadane's on the row sum cache (for each left-right combination of the possible final rectangle).
So the cumulative work will be O(cols^2 * rows).
Space will be O(rows) because of the vertical rows sum cache.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw


