Free practice from Big-O to interview questions!
Stay informed through our newsletter to further your career!
Learn about different recruitment and networking strategies!
No Spam. Limited Emails.
Unsubscribe if you don't like it.
Practice company specific questions from Google, Facebook, and more that interviewers frequently ask.
Always have access to our content so you can come back whenever you're recruiting again.
Learn the fundamental thought process with detailed walkthroughs to quickly solve unfamiliar problems.
We're constantly adding more challenging problems and tips to keep up with the interview process.
As a woman in tech I felt intimidated by the Software Engineering interview process and felt that I didn't have a strong enough technical background and experience. 1TakeInterview breaks down the problem in a way that teaches the fundamentals on how to approach difficult problems. It has given me a boost of confidence during the recruitment process.
1TakeInterview taught me the essential problem solving skills for the interview process and provided me with problems that accurately represented the difficulty I saw at most companies. This is a great website and will definitely help you lock down the internship or job!
I had an interview for my dream company and wanted to be as prepared as possible. 1Takeinterview's approach and explanations gave me the insight I needed to perform well and get the job. During the interview I was able to break it down exactly as these problems do. I'd really recommend 1TakeInterview to anyone who is trying to prepare for Software Engineering interviews so they can beat the competition!
I was surprised how many techniques and tricks I was able to learn through 1TakeInterview. I built a fundamental understanding on how to solve unfamiliar questions ranging from LinkedLists to Trees and have been able to re-use the techniques over and over again. 1TakeInterview provides valuable insight to the different coding paradigms that can be directly used in interviews.
The list of interview topics felt like I was reading a foreign language. The 1TakeInterview course made the process managable and made a huge difference during my interview process. Each question either showed up or was a variation of what I was asked. I'm so thankful for your service and help.
1TakeInterview provides insightful step-by-step explanations that LeetCode or HackerRank could not offer, and those are crucial in really cracking all the coding questions instead of memorizing typical solutions. I would recommend it for everyone who finds it challenging to solve coding questions independently since 1TakeInterview really teaches you how to approach each problem!
As I was preparing for my first ever coding interview, I spent hours trudging through problems on HackerRank and LeetCode, attempting to follow vague explanations from random users when I got stuck. 1takeinterview provided me with the fundamental skills needed to solve any coding problem with clear, step-by-step instructions, saving me days in preparation time. I learned important algorithms faster through 1takeinterview than I did in school.
Write a function to return the Nth number of the fibonacci sequence.
Remember the fibonacci sequence is as follows:
with the 4th number being 2 and the 8th number being 13.
Our recursive easy solution isn’t very effective or efficient. You can’t calculate large fibonacci values nor will it be fast. This method duplicates work.
If the fibonacci is only built off of the two previous numbers is there an easy way to keep track of that instead of all numbers.
We can do this in O(n) time
This can also be done in O(1) space
What do we know about the fibonacci sequence?
Every number is equal to the sum of the two previous numbers in the sequence (except for the first two numbers.) So the 8th number is created by adding the 6th (5) and 7th(8) numbers together.
How can we represent this algorithm of adding the Nth-2 and Nth-1 numbers together?
Our Function would look something like this:
def fibonacci(n): return fibonacci(n-2) + fibonacci(n-1)
Using recursion, we could backtrack until we find the first numbers in the sequence to build up to find the (n-2) and (n-1) numbers.
Recursion usually needs a base case though, what is that in our case?
Well, when n = 1 or n = 2 then the value in the sequence is always 1. We could add that to our function so that the function always terminates and builds up.
def fibonacci(n): if (n == 0 or n ==1) : return 1 else: return fibonacci(n-2) + fibonacci(n-1)
What’s the runtime of this?
Well every number greater than 2 will make two calls to the function fibonacci. So if we call the function fibonacci(6) we have the following:
Every single call with n > 2 , makes two calls. So as the tree builds up we have 2n. This is because we have 2 calls for a depth of n.
How can we make this faster?
Right now, we’re building up our answer backwards. For the 5th fibonacci number, we calculate the 4th and 3rd. For the 4th number we calculate the 3rd and second and so on. As you can see, we calculate the 3rd fibonacci twice due to the way we build up backwards.
We can use a dynamic programming approach and build up the Nth fibonacci number forwards the same way if you were doing this by hand.
Have an idea on how we can approach this?
Starting off the sequence by hand, we’d start with 0,1,1,2,3. How do we calculate the next number? Well, we take the current number (which is 3) and add it to the previous number (which is 2) and we get 5. So we get 0,1,1,2,3,5. Well now, the current number is 5 and previous number is 3.
Do you see the pattern?
def fibonacci(n): if(n==0 or n==1): return 1 # Otherwise we want to run a loop to build up the numbers prev = 0 current = 1 for x in range(2,n): current = prev + current prev = current - prev return current
So we have our base case :
if(n==0 or n==1): return 1
Because we know these are the smallest values of fib that are calculated and we don’t want to calculate anything less than these cases.
So we start with our prev = 0 and current = 1 so that we have the first two numbers of the sequence and continue to build from there.
The for loop, goes through to calculate fib(2) through fib(n) but the trick is, it only calculates each 2…n one time each!
In each iteration, we update the current fibonacci number using the rule as we are doing by hand! (Current plus the previous number gives us a new current number!) Then we can iteratively figure out what the new prev variable should be and update that.
Finally, when we reached the nth number iteration, we can return the current value which would be the nth fibonacci number.
Since we’re running through solving the fibonacci numbers only once for each number, the loop (2,n) tells us we start at 2 and go until n, this gives us insight that we’re doing a linear loop, with constant work in each interation so this is an O(n) algorithm compared to O(2n) recursive algorithm which will also take up a large amount of space on the call stack. Our iterative version however only takes up O(1) space.
Even though the recursive function is very simple, easy to write and intuitive, we are making a lot of sacrifices in time and space (not to mention practicality).
In situations like this, really try to avoid a recursive solution because you’re taking up extra space on the call stack that you can forgo when you take an iterative approach.
Rephrasing our approach to understanding that we only really needed to add two previous values helped us bridge the gap between knowing we want to get an O(n) approach to actually solve the iterative solution.
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
# For example, given the array : [-2,1,-3,4,-1,2,1,-5,4] # The continguous subarray with the largest sum is : [4,-1,2,1] with a sum = 6.
Remember, you only have to output the largest sum, not the actually subarray.
You can solve this is linear time O(n) as the most efficient solution. Don’t try to look at every possible subarray.
This actually doesn’t need any additional space. The most efficient solution has O(1) space.
Ensure that the original array passed in was not modified or mutated.
To start, try to write out a couple examples of the Maximum Continuous Subarray problem and find the “maximum sum” by hand. What’s the process you take to figure that out?
We need to find a subarray of at least length 1 and a good start would be to find all subarrays in our given input which would be a brute force approach to solving this problem. How can we find all subarrays?
Well starting at the first index we can move through the entire array calculating the sum, similarly for the second index we would move through the rest of the array - ignoring the first index since we’ve already looked at all of the subarrays using the first index.
def maxSubarraySum(self, nums): max = 0 for i in range(len(nums)): sum = 0 for j in range(i,len(nums)): sum += nums[j] if (sum > max): max = sum return max
What’s the runtime of this brute-force algorithm? On the first iteration we’re doing N calls, and on the second iterations N-1 calls and on the third iteration N-2 calls. That pattern continues and we have N + (N-1) + (N-2) + (N-3) + ….. + 1 = O(N2).
O(N2) is a good start but we can be more efficient. Do you have an idea of where to start?
To do better than O(N2) we’d have to go for O(N log N) or even better, O(N). O(N log N) typically is seen when we are doing some sorting or searching functionality where we are recursively breaking up the input by half. That’s not obvious nor applicable in this problem since we can’t sort the input, and searching doesn’t do anything for us. As such, we should see if we can do this in an O(N). This requires us to loop through the entire array only once, and looking at every element only once.
Technically we can loop two, three, five, ten times and look at each element once during each loop, and that would be O(2n), O(3n), O(5n), which gets reduced to O(n). It is important to note that we are looping a known and finite number of times.
Typically when we are going for an O(N) approach and can only look at elements once, we’re going to be taking a greedy approach.
With a greedy approach we usually need some variables to keep track of some things as we move through the array.
In this example, we’re looking for a maximum sum subarray so we definitely would want to have a MaximumSumSoFar - this will be initialized to the first element in the array since the maximum sum subarray has to include at least one element.
At each iteration MaximumSumSoFar is either going to be:
How do we know we have the second case? How would you know what other elements to include with the “current element”
When looking at the “current element” we either want to add this value to the subarray sum we’ve been keeping track of so far, or to start a new subarray sum with this as the first element. What information do we need to keep track of now?
At every iteration we want to keep track of :
Here's a solution of what that may look like:
def maxSubarraySum(self, nums): # Here's what it would look like at step to decide # How we keep track of our max sums for num in num: curSum = max(num, curSum + num) maxSum = max(maxSum, curSum)
Are we done?
Have you thought through any of the edge cases? Defining the edge cases or constraints to your problems and your assumptions are critical during an interview. In our situation, we’ve assumed that our input will always have at least one element in it, and that elements can have be positive and negative. Here are some more situations to consider:
The first situation should be fine because we’re either considering the value in that iteration step to be added to the previous max sum or to start the new max sum. Therefore, when looking at only negative values we won’t be adding (-2) to (-1), but instead just set (-2) as the current sum. And the MaximumSumSoFar would be set to (-1) in the first iteration and then won’t change.
The second situation is a really simple catch, we can just add a check to see if our input has a length > 0, otherwise we would return or throw and error.
As we process each value in our array we are going to try to use that value. This value could potentially be the start of a new subarray, which would mean being the first value of the subarray, or we could include it by adding it to the current sum subarray. We also decide to update the maxSum after each value because at any point if the currentSum > maxSum then we want to update the maxSum value.
Finally at the end we simply return maxSum.
def maxSubarraySum(self, nums): # Base case to check if we have a non-empty array if not nums: return 0 # Set the max sum and current sum to be the first element in the array # This helps un handle the situation when we have decreasing only # Values in our input curSum = A maxSum = A # Iterate over all numbers except the first since we know the value for num in nums[1:]: # The current sum will need to start fresh with this number # Or we will add it to the curSum. curSum = max(num, curSum + num) # The running max sum which we return at the end maxSum = max(maxSum, curSum) return maxSum
As we move through the input we only look at each number in the input array only once, if we have n numbers in our input array this will bring us to an O(n) run time time since all other operations can be done in O(1) time such as calculating the current and maximum sums variables.
Our space complexity is also down to O(1) since we aren’t using any data structures, only two variables to keep track of our sums.
Here we’re able to see how powerful and useful a greedy algorithm is, but we may be wondering how do I even know when to use a greedy algorithm?
Usually we want to try to solve the problem in a single pass through the solution but then we need to figure out what to do. Typically at this point you should ask yourself how would I be keeping track of the best values as I move through this input? What variables and information do I need at each value to determine how to update my best values?
If we interpret this for our situation that was keeping track of the current and max sum since at each step we had to decide if we were starting a new current sum with the value in the array, or were we going to continue the current sum by simply adding the value onto it.
For the maximum sum, we simply just had to check if the current sum at each iteration was bigger than the current max sum and update it if needed.
Try to break down future problems like this and asking yourself, “What information do I need at each iteration in order to try to keep track of the best values so far”.
Given a singly linked list, determine if it is a palindrome.
(Palindrome : a word, phrase, or sequence that reads the same backward as forward)
It’s a singly linked list so you only have a next pointer. NO previous pointer.
Consider these example:
5 -> 4 -> 3 -> 3 -> 4 -> 5 5 -> 4 -> 3 -> 4 -> 5
Does your code work to return yes on both of these situations? When the length is both even and odd?
You may choose to modify the original input.
We can actually do this in O(N) with O(1) extra space.
Try by working out these examples by hand and think about the process in which you solve them.
1 -> 2 -> 3 -> 2 -> 1 1 -> 2 -> 2 -> 1
Do you see how you could translate the process into code? Do any data structures or common algorithms come across your mind?
If we had an Array instead of a linked list, how would you approach this problem?
You’d probably start by comparing the first and last elements and work your way in until the indices equaled each other, or crossed each other.
Can we represent our Linked List in a similar way to get started with solving the question?
We could start by copying over the Linked List into an array and operating it as we discussed above.
def palindromeLL(self, head): tempArray =  while head: # Add the value for each node to the array tempArray.append(head.value) head = head.next # Finished copying over values into the array, now we can check # If its a palindrome start = 0 end = len(tempArray) -1 while start < end: # The palindrome isn't possible if(tempArray[start] != tempArray[end]): return False start += 1 end -= 1 return True
By copying over the linked list into an array we are using an additional O(n) and using O(n) time to iterate through the linked list, as well as O(n) time to work through the array to check if it is a palindrome. Overall this solution is O(n) space and O(n) time.
Since we are going to have to look at every element in the linked list, we definitely can’t get faster than O(n) time. However, can we do better on the space and work with the linked list that we’re given?
The main problem is that this is a singly linked list and nodes do not have a previous pointer. What if we had a previous pointer to the node before? How would this change your approach?
With a previous pointer, that would allow us to walk backwards in the linked list, as this would allow us to either start in the middle and work out, or start outside and walk towards the middle.
Instead of creating a previous pointer, what if we reversed half of the linked list so that the next pointer functioned as if it was a previous pointer. Where does this bring us?
We begin by using a fast and slow pointer so we can find the middle of the linked list - this is variable based on an odd or even length list.
After finding the middle, we reverse the second half of the list, the first half can be reversed as well - the implementation would be very similar.
With our two pointers we can walk down their respective halves and compare values until one or both of them reaches null.
def palindromeLL(self, head): # Creating our fast and slow pointers fast = head slow = head # Need to find the middle of the linked list so we can # Then reverse one side while fast and fast.next: fast = fast.next.next slow = slow.next # We choose to reverse the second half of the linked list # Reversing the first half is just as fine node = None while slow: nxt = slow.next slow.next = node node = slow slow = nxt # We've finished reversing one half of the array # But we need to now actually compare values and # Walk down step by step the forward and reversed list while node: # while node and head: if node.val != head.val: return False node = node.next head = head.next return True
Since we’re making one pass with the fast and slow pointers, and then a second to walk through each half, we’re doing a total of O(n) + O(n) = O(n) work as each pass is O(n). The space however is brought down to O(1).
Since we are not using any additional space other than the data structure that is given to us the in problem, we have creatively modified the input to behave as we could have approached with an array.
Trying to think about moving forward and backwards on a singly linked list isn’t the easiest thing to visualize and approach. Start off by abstracting the data structure into something easier to handle, such as an array made it easier to think about the concept behind validating a palindrome.
A lot of linked list problems usually have the two pointer approach with a fast and slow pointer to accomplish various tasks. The reason this is so powerful is because it allows you to perform mathematical operations and indexing pretty much onto a linked list.
Those underlying concepts aren’t readily available like they are in an array.
Purchase our entire catalogue of 40+ real CS interview questions with detailed question walkthroughs and key problem strategies! Sign up now for an exclusive early bird price for lifetime access! We focus on teaching you how to think about and breakdown interview questions instead of throwing a solution at you or just explaning a soluton. Each problem focuses on a different fundamental paradigm to help you quickly solve challenging problems. Don't wait! Get Access now along with a 100% money-back guarantee.