Uploaded December 2018 | Updated November 2026, 3 hours ago
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 a raw IP address string without period separators between the digits. Return all valid IP addresses that can be created from the raw IP string where it is your job to place the periods.
This is sort of a knowledge question but if you get this in an interview you'd probably get the constraints, otherwise, it is the interviewer's fault for being a bad interviewer since general SWE questions should primarily be about problem solving skills and not domain specific knowledge/facts.
Whenever we hear "compute" or "generate" we know that we will have to do some sort of repeated looping or recursion in a backtracking approach. For this problem, we can do either.
Approach 1 (iteration)
A triple nested set of for loops where in each section we create a part of the IP string, validate that section we just snipped out and then continue on to generate the rest of the IP string
Approach 2 (backtracking)
The 3 Keys To Backtracking:
Our Choice:
- We will take snippets of substrings 1-3 characters long
Our Constraints:
- We cannot have a value greater than 255 or less than 0 in any subsection.
- We cannot have a leading 0 in any subsection
Our Goal:
- Get 4 valid subsections out of the raw string that we started with that will comprise the fully valid IP recomposition
We can make progress through the string, slowly decoding it in all ways possible by taking a snippet, validating it, and then continuing on in the generation path.
Since we will be using recursion, each recursive call will express all possible ways to arrange a certain subsection of the string that is...
Until we reach the base case which is when we have all 4 segments filled out (and by default, our index pointer has progressed to the string's length).
Complexities
Time: O(1)
- Off the bat, we know that we will have a constant time complexity because there are a limited amount of IP addresses (2^32 to be exact) so our time complexity will fall as O(1) ("constant")
Space: O(1)
- By the same line of reasoning, our space complexity is O(1)
++++++++++++++++++++++++++++++++++++++++++++++++++
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 is problem 7.10 in the book Elements of Programming Interviews by Adnan Aziz
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 a raw IP address string without period separators between the digits. Return all valid IP addresses that can be created from the raw IP string where it is your job to place the periods.
This is sort of a knowledge question but if you get this in an interview you'd probably get the constraints, otherwise, it is the interviewer's fault for being a bad interviewer since general SWE questions should primarily be about problem solving skills and not domain specific knowledge/facts.
Whenever we hear "compute" or "generate" we know that we will have to do some sort of repeated looping or recursion in a backtracking approach. For this problem, we can do either.
Approach 1 (iteration)
A triple nested set of for loops where in each section we create a part of the IP string, validate that section we just snipped out and then continue on to generate the rest of the IP string
Approach 2 (backtracking)
The 3 Keys To Backtracking:
Our Choice:
- We will take snippets of substrings 1-3 characters long
Our Constraints:
- We cannot have a value greater than 255 or less than 0 in any subsection.
- We cannot have a leading 0 in any subsection
Our Goal:
- Get 4 valid subsections out of the raw string that we started with that will comprise the fully valid IP recomposition
We can make progress through the string, slowly decoding it in all ways possible by taking a snippet, validating it, and then continuing on in the generation path.
Since we will be using recursion, each recursive call will express all possible ways to arrange a certain subsection of the string that is...
Until we reach the base case which is when we have all 4 segments filled out (and by default, our index pointer has progressed to the string's length).
Complexities
Time: O(1)
- Off the bat, we know that we will have a constant time complexity because there are a limited amount of IP addresses (2^32 to be exact) so our time complexity will fall as O(1) ("constant")
Space: O(1)
- By the same line of reasoning, our space complexity is O(1)
++++++++++++++++++++++++++++++++++++++++++++++++++
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 is problem 7.10 in the book Elements of Programming Interviews by Adnan Aziz




![The Recursive Staircase - Top Down & Bottom Up Dynamic Programming (Climbing Stairs on LeetCode)
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: You are climbing a staircase. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? (n is always a positive integer).
This is a classic problem. Let us tackle it thoroughly, there are many ways to do this that form the basis for how we do other problems bottom up with a DP table or top down with memoization.
The key with a problem like this is to instantly recognize that this turns into a series of subproblems, it is very similar to the Fibonacci sequence calculations.
Approach 1 (Top Down Recursion w/o Memoization)
Example:
n = 4
Let f(n) be the number of ways to climb n steps if we can take 1 or 2 steps.
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
Base case: f(0) = 1 and f(any negative number) = 0
Notice that we are resolving subproblems that we already have an answer to and hence we are wasting time.
Complexities
Time: O( 2 ^ n )
Each recursive call can spawn 2 more calls, depth of the recursion tree is n. This is a loose bound, a tighter one is around O( 1.62 ^ n )
Space: O( n )
Call stack max depth. Max depth of the recursion tree goes n calls deep.
Approach 2 (Use Memoization On Top Down)
Memoization: An optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Dynamic programming is all about storing the answers to previous sub-problems to speed up our runtimes by avoiding repeating work that has already been done.
Complexities
Time: O( n )
We cancel out many of the repeated calls that we might have made leading to us to have a linear time complexity.
Space: O( n )
Call stack max depth. And we will still have the dp table.
Approach 3 (Dynamic Programming Array)
DP is all about caching the answers to previous work and using it in current work.
dp[n] denotes the number of ways to climb n steps if we can take 1 or 2 steps.
dp[n] = dp[n - 2] + dp[n - 1]
The answer to n is the sum of the answer between two things:
our last step to n is 2 long
our last step to n is 1 long
Base Cases: dp[1] = 1 and dp[2] = 2
Complexities
Time: O( n )
A for loop making n - 2 iterations
Space: O( n )
We will be holding n + 1 entries in a dp array
Approach 4 (Fibonacci Number)
We notice that this is just the Fibonacci series. We can just use local variables to keep track of the items 1 and 2 behind where we stand.
Complexities
Time: O( n )
Still solve up to n subproblems.
Space: O( 1 )
No more dp array, we just use constant local variables
All other approaches are esoteric and are not practical in an interview, these include:
- Using Binets Method & matrix multiplication
- Using the mathematical, non-recursive, version of the Fibonacci Formula
++++++++++++++++++++++++++++++++++++++++++++++++++
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 The Recursive Staircase - Top Down & Bottom Up Dynamic Programming (Climbing Stairs on LeetCode)](https://i.ytimg.com/vi/NFJ3m9a1oJQ/mqdefault.jpg)
![Find The Second Largest Item - Heap & Tracking Approach (Beginner Big N Interview Question)
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 that may or may not be sorted, find the second largest item.
Approach 1 (Single Pass)
We keep track of a variable for the maximum number and keep track of a variable for the minimum number.
We do a linear traversal.
We keep track of a firstMax and a secondMax.
If the element is greater than firstMax:
firstMax becomes secondMax.
the element becomes firstMax.
Otherwise, if the first element is larger than secondMax and it is not the firstMax:
the element becomes secondMax.
The key thing here is to realize the case where the element might not dominate firstMax but it might still dominate the secondMax but it cannot dominate the secondMax if it is firstMax or else we will lose our actual secondMax.
At the end if secondMax is still not defined then we do not have an answer, otherwise, secondMax is our answer.
Complexities
Time: O( n )
n is the length of the array
Space: O( 1 )
we do not create anything past local variables that are primitives
Approach 2 (Min Heap)
We can use a min heap to hold at maximum 2 items. A min-heap will always have the smallest item available to us so we can get rid of it to only keep the k largest items.
it is almost like we need to think in opposites:
to extract the k max elements we use a min heap.
to extract the k min elements we use a max heap.
This is because the heap type desired corresponds to the item that we care the least about. To find maxes we dont care about mins. To find mins we dont care about maxes.
Every time we add a 3rd item we eject the smallest item from the min heap.
By the end of the traversal, we can just eject what our min heap held and that will be the 2nd largest item in the array.
Complexities
Time: O( n * log(2) ) = O( n )
insertion and removal from the heap will always take log(2) which is O( 1 ) time (constant) assuming that it is a balanced binary heap.
We traverse an array of length n.
Space: O( 2 ) = O ( 1 )
The space used for the min heap will always be constant.
Critical that you keep in mind:
empty cases [ ]
cases where there is only 1 item [ 2 ]
cases where there are repeated items [ 3, 3, 3, 3, 3, 3 ], etc.
++++++++++++++++++++++++++++++++++++++++++++++++++
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 Find The Second Largest Item - Heap & Tracking Approach (Beginner Big N Interview Question)](https://i.ytimg.com/vi/NheWPxGpoxQ/mqdefault.jpg)


![Total Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)
Try Our Full Platform: https://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 (doesnt 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: 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
++++++++++++++++++++++++++++++++++++++++++++++++++ Total Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)](https://i.ytimg.com/vi/RlXtTF34nnE/mqdefault.jpg)

