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: Given a sorted array, find the total count of occurrences of a given value K as efficiently as possible. (Hint: The best answer runs in O(log(n)) time)
This was a question that I got in my 1st round Facebook interview. Error: At 3:27 the "Answer" should have said 1. Sorry.
Approach 1:
Linear scan and count
Time: O(N)
Space: O(1)
Remember: whenever an array is sorted it automatically unlocks binary search which is very fast. Binary search should be first on your mind and you should tell your interviewer so immediately.
Binary search operates off what is called an invariant. Our invariant is that no matter how often we split the search space, the space will stay sorted and hence again binary search can be used on it (doesn't have to be perfectly sorted though as we will see in other problems)
Approach 2:
Binary search for the first element and then linear scan to count the elements from that first element to its last occurrence.
Average Case
Time: O(log(n))
Space: O(1)
Worst Case
Time: O(N)
Space: O(1) [O(log(n) if the binary search is recursive]
This is the approach that I was stuck on, but my interviewer then said, "Can we keep it log(n) in every case?"
Then I knew that we would only be dealing with binary searches, any linear scans would be unnecessary
I knew I needed to get the count somehow so it occurred to me...if it is sorted, the lastOccurrence will give us the count if we just subtract the first occurrence from it and add 1. That is the total elements between the first and last occurrence and they all must be that number itself since the array is sorted
Approach 3:
Binary search for the first occurrence. If not found then return 0 occurrences total. If found, binary search for the 2nd element.
The answer is: lastOccurrence - firstOccurrence + 1
Time: O(log(n)) + O(log(n)) = O(log(n))
Space: O(1) [O(log(n)) if the binary search is recursive]
Takeaways:
-) If an array is sorted, immediately think binary search even if the problem is not a search problem (in this case it is)
-) Be vocal, your interviewer will guide you. Say approaches that may even be suboptimal, they may be close to the optimal result
+++++++++++++++++++++++++++++++++++++++++++++++++++
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: nas.io/backtobackswe
πΉ Intuitive Video Explanations
βNew Unseen Questions
π Get All Solutions
Question: Given a sorted array, find the total count of occurrences of a given value K as efficiently as possible. (Hint: The best answer runs in O(log(n)) time)
This was a question that I got in my 1st round Facebook interview. Error: At 3:27 the "Answer" should have said 1. Sorry.
Approach 1:
Linear scan and count
Time: O(N)
Space: O(1)
Remember: whenever an array is sorted it automatically unlocks binary search which is very fast. Binary search should be first on your mind and you should tell your interviewer so immediately.
Binary search operates off what is called an invariant. Our invariant is that no matter how often we split the search space, the space will stay sorted and hence again binary search can be used on it (doesn't have to be perfectly sorted though as we will see in other problems)
Approach 2:
Binary search for the first element and then linear scan to count the elements from that first element to its last occurrence.
Average Case
Time: O(log(n))
Space: O(1)
Worst Case
Time: O(N)
Space: O(1) [O(log(n) if the binary search is recursive]
This is the approach that I was stuck on, but my interviewer then said, "Can we keep it log(n) in every case?"
Then I knew that we would only be dealing with binary searches, any linear scans would be unnecessary
I knew I needed to get the count somehow so it occurred to me...if it is sorted, the lastOccurrence will give us the count if we just subtract the first occurrence from it and add 1. That is the total elements between the first and last occurrence and they all must be that number itself since the array is sorted
Approach 3:
Binary search for the first occurrence. If not found then return 0 occurrences total. If found, binary search for the 2nd element.
The answer is: lastOccurrence - firstOccurrence + 1
Time: O(log(n)) + O(log(n)) = O(log(n))
Space: O(1) [O(log(n)) if the binary search is recursive]
Takeaways:
-) If an array is sorted, immediately think binary search even if the problem is not a search problem (in this case it is)
-) Be vocal, your interviewer will guide you. Say approaches that may even be suboptimal, they may be close to the optimal result
+++++++++++++++++++++++++++++++++++++++++++++++++++
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
++++++++++++++++++++++++++++++++++++++++++++++++++










![Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem)
Try Our Full Platform: https://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: 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 7.7 in Elements of Programming Interviews. Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem)](https://i.ytimg.com/vi/a-sMgZ7HGW0/mqdefault.jpg)