Data structures and algorithms for interviews — Problems with solutions Pt.1

Almost every interview for coding and software development roles is incomplete without a programming interview. There are thousands of questions in coding sites like LeetCode and it is impossible to cover all the topics within a short period.

In this series, I will provide solutions to frequently asked interview questions under major topics such as arrays, linked lists, trees, dynamic programming etc.

Photo by Headway on Unsplash

Find the duplicate in an array of N integers

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Conditions:
1. You must not modify the array (assume the array is read-only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Sample Input: [1,3,4,2,2]
Sample Output: 2
Solution:
def findDuplicate(self, nums: List[int]) -> int:
        n=len(nums) #size of array
        for i in range(0,n):
            nums[nums[i]%n -1]=nums[nums[i]%n -1]+n
        for i in range(0,n):
            if nums[i]>=n*2:
                return i+1

Explanation: Consider the sample input with array nums of 5 elements. The array nums is used as a bucket.

• For each element in the array, nums[nums[i]%n -1] is used to pick the bucket.
  In this example, for element 2 in an array of 5 elements, nums[2%5 -1] = nums[1].
• For every element in array, the value n is added to its bucket by nums[nums[i]%n -1] = nums[nums[i]%n -1]+n. In this example, for element 4 of value 2 , nums[2%5 -1]= nums[1] + 5 = 3+5 = 8.
• When an element occurs twice in the array, its bucket will contain a value greater than 2n, because n is added twice to its bucket. In this example, for element 5 of value 2, nums[2%5 -1]= nums[1] + 5 = 8 + 5 = 13.
• Thus by iterating through the array once again to find the element which is greater than 2n, we can find the duplicate element. Here, only nums[1] will have a value greater than 10.
• Time complexity: O(n) and space complexity: O(1) (since no extra space Is used)

Sort an array of 0s, 1s and 2s (Dutch flag national problem)

The dutch national flag

Given an array nums consisting 0s, 1s and 2s. The task is to write a function that sorts the given array. The functions should put all 0s first, then all 1s and all 2s in last. The array must be sorted in-place.

Sample Input: [2,0,2,1,1,0]
Sample Output: [0,0,1,1,2,2]
Solution:
def sortNumbers(self, nums: List[int]) -> None:
        arr=[0,0,0]     #counter array
        for n in nums:  #count the number of 0s,1s,2s
            arr[n]+=1
        i=0   #to iterate over arr[]
        k=0   #to iterate over nums[]                   
        while i<3:
            if arr[i]>0:
                nums[k]=i    #replace the element in nums
                arr[i]-=1    #count is decremented
                k+=1
        #if count becomes zero, we move to next element in arr.
            elif arr[i]==0:  
               i+=1
        print(nums)

Explanation:

• The arr[3] is used to count the number of 0s,1s and 2s.
• arr[0] contains 0s count, arr[1] contains 1s count and arr[2] contains 2s count.
• Then, the first arr[0] elements in the nums array are replaced with 0s, next arr[1] elements are replaced 1s and so on.

See also Dutch national flag problem.

Missing number

Given an array nums containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Sample Input: [9,6,4,2,3,5,7,0,1]
Sample Output: 8
Solution:
def missingNumber(self, nums: List[int]) -> int:
        l=len(nums)  #size of nums
        x1=0
        x2=nums[0]
        for i in range(1,l+1):
            x1=x1^i
        for j in range(1,l):
            x2=x2^nums[j]
        
        return x1^x2

Explanation:

We will solve this problem using the XOR property: A ^ A = 0

Any number XORed with itself will give 0.

• Since the array contains distinct numbers from 0 to n, we will XOR numbers from 0 to n and store in x1.
• The elements of the given array nums are XORed and stored in x2.
• When we perform x1^ x2, the common elements nullify each other thus the missing number alone remains.
• For example, let consider 4 distinct consecutive numbers 0,1,2,3.
  Let nums=[0,1,3]
  Then, x1= 0 ^ 1 ^ 2 ^ 3 and x2 = 0 ^ 1 ^ 3.
  x1 ^ x2 = (0^ 1 ^ 2 ^ 3)^( 0 ^ 1 ^ 3.) = 2, which is the missing element.

I hope my explanation was easy to understand. Please let me know in the comments if you have any doubts and what other topics you want me to cover!

References

• Leetcode
• GeeksforGeeks