PRAMP: Get Different Numbers Algorithm
As I continue my battle in learning how to solve algorithms for future technical interviews, I was recommended by a friend to schedule mock interviews on a site called Pramp!
Once you have signed up for Pramp, you receive 6 interview credits for you to you any time! You will also have the option to pick your language that you feel comfortable coding in along with what you would like to interview for. There is a nice variety of choices like Data structures and algorithms, Frontend, Data Science, and more.
Once you schedule your interview, you receive a confirmation email, which has a code challenge that you will be giving to your peer after they have given you yours. This was unexpected to me because I didn't realize the site is a back and forth interview formate! Nevertheless, I tried my best to understand the problem the best That I could in order to solve it. Unfortunately, it was out f my scope of knowledge because I had not understood Binary Search Trees that well. Thankfully, I took it more as a learning experience and took notes on the answer so that I could be able to help my peer when they were trying to solve this code challenge.
But anyway, when the day finally came to meet my peer. interviewer, I received the code problem Getting A Different Number, which is what I will be focusing this blog on.
Let's get into it, shall we? :)
Question:
Given an array arr of unique nonnegative integers, implement a function getDifferentNumber that finds the smallest nonnegative integer that is NOT in the array.
Even if your programming language of choice doesn’t have that restriction (like Python), assume that the maximum value an integer can have is MAX_INT = 2^31-1. So, for instance, the operation MAX_INT + 1 would be undefined in our case.
Your algorithm should be efficient, both from a time and a space complexity perspective.
Solve first for the case when you’re NOT allowed to modify the input arr. If successful and still have time, see if you can come up with an algorithm with an improved space complexity when modifying arr is allowed. Do so without trading off the time complexity.
Analyze the time and space complexities of your algorithm.
Example:
Input: arr = [0, 1, 2, 3] Output: 4
Constraints:
- [time limit] 5000ms
- [input] array.integer
arr - 1 ≤ arr.length ≤ MAX_INT
- 0 ≤ arr[i] ≤ MAX_INT for every i, 0 ≤ i < MAX_INT
- [output] integer
The Code:
Let’s start off with a Brute Force way of handling this challenge.
Brute Force Algorithms are exactly what they sound like — straightforward methods of solving a problem that rely on sheer computing power and trying every possibility rather than advanced techniques to improve efficiency. — FreeCodeCamp
The Breakdown:
- Here I create a case where, if the array happens to be empty then just return 0.
- I then duplicated our original array, sorted it, and assigned it to a random variable.
- I then iterated through the duplicated array. this is because I needed to start making a comparison to find my missing element.
- How I did my comparison is that I asked, “if the element at index [i] does not compare with our I in the loop, we must return that i”
- otherwise, we must return the length of the original array
What does that even look like?
n = [0, 1, 2, 3]if(n[i] != i) return i//=>
n[i] = 0 also equals i = 0 yes! increment i and move to next element
n[i] = 1 also equals i = 1 yes!
n[i] = 2 also equals i = 2 yes!
n[i] = 3 also equals i = 3 yes!since these are all true, the next best thing to do is return the length of our original array //=>
arr = [0, 1, 2, 3]
arr.length = 4which would be the next missing number!
Although this code passed, my peer suggested I work on understanding how to use hash maps or objects when it comes to tackling challenges that you can do comparisons when finding a different number.
That is when he mentioned using an object variable to start key and value pairs which are great for reducing the time complexity.
The Code:
The Breakdown:
- First, create an empty object variable
- Then say “ for every element in our array, make our element a key in the object variable and assign to true”.
- iterate through our array, if our object does NOT have a property at the index of i, return that element at i.
- otherwise, if there are no missing elements then return the length of the array itself.
Conclusion
Overall, my experience at Pramp was great. My peer interviewer was knowledgeable, understanding, and helpful in teaching me how to go from a brute force code to a more optimized code solution. If you are also someone that struggles with coding algorithms, I highly recommend signing up for Pramp!
References:
A cool cheat sheet I try to refer to when figuring out Big O Notation:
