Uploaded December 2018 | Updated November 2026, 3 hours ago
Try Our Full Platform: nas.io/backtobackswe
πΉ Intuitive Video Explanations
βNew Unseen Questions
π Get All Solutions
Question: Each digit, apart from 0 and 1, in a phone keypad corresponds to one of three or four letters of the alphabet. Write a program which takes asinput a phone number (specified as a string of digits) and returns all possible character sequences that correspond to the phone number.
3 Keys To Backtracking:
Our choice: At each number we can choose certain letters
Our constraints: none really
Our goal: Get a string as ling as the original number given
Time:
O(4^n) * O(1) * O(n) = O(n(4^n)) [weak upper bound]
Since there are no more than 4 possible characters for each digit, there will be O(4^n) function calls at max.
Each call of the function will make at max 4 more calls. 4 * 4 * 4 * 4 * 4... = 4^n, n being the amount of digits provided as input.
O(1) work in each function call for the most part
O(n) time to copy the string over to the answer list in each base case since that is done character by character.
Space:
O(n) + O(4^n) = O(4^n)
Our recursion tree will go at max n calls deep.
We will have at max 4 choices at each digits so total we have roughly 3^n or 4^n total mneumonics that pan out and get stored in the result array.
One could get more mathematically rigorous but that approximation is enough for an interview situation.
++++++++++++++++++++++++++++++++++++++++++++++++++
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 7.7 in Elements of Programming Interviews.
Try Our Full Platform: nas.io/backtobackswe
πΉ Intuitive Video Explanations
βNew Unseen Questions
π Get All Solutions
Question: Each digit, apart from 0 and 1, in a phone keypad corresponds to one of three or four letters of the alphabet. Write a program which takes asinput a phone number (specified as a string of digits) and returns all possible character sequences that correspond to the phone number.
3 Keys To Backtracking:
Our choice: At each number we can choose certain letters
Our constraints: none really
Our goal: Get a string as ling as the original number given
Time:
O(4^n) * O(1) * O(n) = O(n(4^n)) [weak upper bound]
Since there are no more than 4 possible characters for each digit, there will be O(4^n) function calls at max.
Each call of the function will make at max 4 more calls. 4 * 4 * 4 * 4 * 4... = 4^n, n being the amount of digits provided as input.
O(1) work in each function call for the most part
O(n) time to copy the string over to the answer list in each base case since that is done character by character.
Space:
O(n) + O(4^n) = O(4^n)
Our recursion tree will go at max n calls deep.
We will have at max 4 choices at each digits so total we have roughly 3^n or 4^n total mneumonics that pan out and get stored in the result array.
One could get more mathematically rigorous but that approximation is enough for an interview situation.
++++++++++++++++++++++++++++++++++++++++++++++++++
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 7.7 in Elements of Programming Interviews.




![Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given an array of all integers that may or may not be sorted, determine the length of the longest subsequence that is strictly non-decreasing.
What Is A Subsequence?
A subsequence of an array is a subset of the array that maintains temporal order.
It does not have to be contiguous but it might turn out to be contiguous by chance.
Problem Name / Variants
This problem also comes in the form of asking for the longest strictly decreasing subsequence.
This is longest non-decreasing subsequence meaning that we will have a non-strictly increasing subsequence (aka we can have deltas of 0 between contiguous elements in the subsequence).
Approach 1 (Brute Force)
We can enumerate all 2^n subsets of the original array and then test them for the non-decreasing property.
The answer will be the longest subset that has the property.
This is too expensive.
Approach 2 (Dynamic Programming)
Do you see the potential for a subproblem here?
If you do, then we have the opportunity to use dynamic programming.
Example
[ -1, 3, 4, 5, 2, 8 ]
At the index 0 I always know that I can have a subsequence of length 1.
In fact, at all positions the longest non-decreasing subsequence can be at least length 1.
We then look at index 1, I need to ask myself if the item at index 1 can lengthen the longest subseqence found at index 0.
We check if 3 is greater than or equal to 1...it is. Great. index 1 can be tacked on but...should I?
The LNDS (longest non-decreasing subsequence) at index 1 is 0.
The LNDS at index 0 is 1.
Yeah...it makes sense because if I tack 3 onto the LNDS I found for the subproblem of just [ -1 ] then at index 1 I will also have a LDNS.
So what we basically do is build a table and ask ourselves these questions all along the way.
EACH CELL REPRESENTS THE ANSWER TO THE SUBPROBLEM ASKED AGAINST the subsequence from index 0 to index i (including the element at index i).
Complexities:
Time: O( n^2 )
n is the length of the array.
For each of the n elements we will solve the LNDS problem which takes O(n) time, therefore we yield a O( n^2 ) runtime complexity.
Space: O( n )
We will store our answers for each of the n LNDS subproblems.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 17.12 in Elements of Programming Interviews by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals](https://i.ytimg.com/vi/fV-TF4OvZpk/mqdefault.jpg)



![Find the kth Largest or Smallest Element of an Array: From Sorting To Heaps To Partitioning
Code & Problem Statement @ https://backtobackswe.com/platform/content/find-the-kth-largest-or-smallest-element/video?utm_source=youtube&utm_medium=video
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://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 kth largest element as efficiently as possible. Return the actual value of the kth 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 nth largest element should be at the first index ... index 0 ... (6) - (6) = 0
So...
finalPivotPosition n - k ... The pivot is the kth largest element
finalPivotPosition greater than n - k ... kth largest must be in the left partition
finalPivotPosition less than n - k ... kth 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: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is question 12.8 in the fantastic book Elements of Programming Interviews. Find the kth Largest or Smallest Element of an Array: From Sorting To Heaps To Partitioning](https://i.ytimg.com/vi/hGK_5n81drs/mqdefault.jpg)

