The array is one of the major data structures on which you will definitely find a minimum of one question in interviews as well as in coding contests. An array is a linear data structure that stores the elements in contiguous order and the size of the array is predefined where a little few complications are there to create a dynamic array. Problems in an array can occur in multiple topics and techniques of competitive programming like Recursion, Backtracking, Bit manipulation, sorting and searching but in this article, we will cover some of the basic array problems that are mostly asked in technical interviews by most MNCs, service-based companies and semi-product based companies.
Table of Contents
😏 Problem-1) Missing Number
One of the major asked problems in an interview where your task is to find the missing element in the sequence of a given array of integers from 1 to n and one number is missing means the size of an array must be n+1.
Example
How to find the missing number in a contiguous element array? (Approach)
From common maths, we know that we can find the n series (AP) using the formula n * (n+1) / 2. this will give the sum of n+1 numbers and subtract the sum of the remaining elements we will get the missing number. suppose the first sample input where the sum of elements is 49 which is 9 elements and the length after adding the missing element should be 10 so using 10 as n calculate n * (n+1)/2 so we get 55 and if we subtract 49 from 55 then the result is 6 which is required answer.
💻 Code ~ The code is very much simple and should take only 4 lines so try to implement it after knowing the approach.
def MissingNumber(arr):
n = len(arr)+1
sm1 = (n * (n+1)) // 2
sm2 = sum(arr)
return sm1-sm2
arr = [1, 2, 3, 4, 5, 7, 8, 9, 10]
print(MissingNumber(arr))
😏 Problem - 2) Maximum product of two integers
Given an array of N positive integers. Your task is to find a maximum product of two integers where all elements are positive.
Example
Approach
The first answer that you have to give in the interview is a naive approach which has maximum complexity. So the approach is basic to use two loops and check each and every combination and calculate their product and find the maximum product.
💻 Code ~
def MaximumProduct(arr):
max_prod = 0
n = len(arr)
for i in range(n):
for j in range(i+1, n):
#prod of each possible unique combination
curr_prod = arr[i] * arr[j]
if curr_prod > max_prod:
max_prod = curr_prod
return max_prod
arr = [3, 8, 5, 12, 6, 2, 7]
print(MaximumProduct(arr))
If the interviewer asks to optimize the code then first you should follow the sorting plus two sums approach. Two sum approach is also a very simple approach where we use two pointers and check for the best possible combination. We already have the article on the two pointer technique where we have solved the two sums problem.
😏 Problem - 3) Check whether the array is unique or duplicate
The problem statement is given an array of integers and your task is to check whether the array contains duplicate elements or the complete array is unique.
Example
Approach to Problem
The approach is again simple create one empty array and iterate in a given array and check for every element that is present in an empty list. If it is present that means it is occurring repetitive times else add the element to the list and last if everything seems fine then return true.
💻 Code ~
def isUnique(arr):
temp = []
for ele in arr:
if ele in temp:
print(f'{ele} is duplicate element')
return False
else:
temp.append(ele)
#if everything is right
return True
arr = [1, 3, 7, 5, 3, 7, 5, 9]
if isUnique(arr):
print("Unique")
else:
print("duplicate")
😏 Problem - 4) Find Middle Elements
The problem statement is simple where you are given an array of integers and you have to return an array without first and last elements.
Example
Solution
The approach is very simple like in python you can perform direct slicing or you can remove the first and last element and print the rest of the array. One more solution is to iterate the array from 1 to n-1 and print each element. Whatever best suits you can follow the approach.
💻 Code - The code hardly takes 2 lines
def MiddleElements(arr):
#method - 1(slicing)
return arr[1:-1]
#method - 2 (remove first and last element)
arr.pop() #last element
arr.pop(0) #first element
😏 Problem - 5) Find the best scores
Given an array of N integers and your task is to find the top 2 best scores. The problem statement is simple where you need to find the maximum and second maximum element from an array where the element may present duplicate or multiple times.
Example
How to find the maximum and second maximum from an array?
If you are thinking of a sorting approach and returning the last two elements then it will not work because the array contains duplicate elements. What we can do is we can find a set of arrays which contain all unique elements and find a maximum element from a set after that, you can remove the maximum element and again find the maximum that will output the second maximum from an array.
💻 Code ~
def firstSecond(arr):
lst = set(arr)
first = max(lst)
lst.remove(first)
second = max(lst)
return first, second
If you want to go with sorting order then we can sort the array in descending order and the first element will be a maximum element. To find the second maximum iterate in the array till we get a different element the maximum and as we get another element the maximum terminates the loop.
def firstSecond(given_list):
a = given_list #make a copy
a.sort(reverse=True)
print(a)
first = a[0]
second = None
for element in given_list:
if element != first:
second = element
return first, second
😏 Problem - 6) All Pairs equal the target sum
Given an array of integers and your task is to find all pairs whose sum is equal to a target sum.
Example
Approach
If you are in an interview then first you must speak out the naive approach where we iterate in array in O(N^2) complexity and check for each combination whether the sum is equal to the target sum or not.
💻 Code - Try once to implement the approach on your own.
def pairSum(myList, target):
result = []
for i in range(len(myList)):
for j in range(i+1,len(myList)):
if myList[i] + myList[j] == target:
result.append(str(myList[i]) +"+"+ str(myList[j]))
return result
Important Note 📌
The questions are not completed and the list will go on till pattern based programming where you will be given a simple pattern that you need to create using a program and write a code. So, we have created a complete list of the top 60 programs with solutions and explanations that you can access using this link (Github). You will find the name of the question and a solution link where a question is explained. The code of most of the problems is written in C++ but we ensure that you can easily convert it to python. The top problems for interviews in a list that you need to prepare are listed below.
- Factorial (Iterating and recursion solution)
- Fibonacci (Iteration and recursion solution)
- Find and check Prime Number
- Pattern based problems
- Square and square root problems
- Solving series problems (AP)
As you complete this basic question then we have already published two tutorials on arrays on our site where you will find popular array algorithms you need to know and problems based on array algorithms so it is a humble request to prepare array data structure very well you should once refer this two articles.
- Popular Array Algorithms to prepare for technical Interviews
- Top Array coding problems for Interviews
Conclusion
These are the top basic problems that are asked in interviews and we have given you a list of basic 60 coding problems with their solution and explanation. I hope that if you are serious about your placements and preparation then you will access the list uploaded on Github and prepare those questions. And if you are sitting in interviews of semi-product based companies or product-based companies then the referral 2 article will really help you in preparing array data structure very well.
👉 I hope that wherever is discussed in this article is clear to you. If you have any doubts then feel free to post them in the comment section below or you can send your query and suggestions through the contact form. This helps other readers to learn something new and amazing.
👉 Keep following crazy-techie for wonderful articles and if you want tutorials on other data structures and competitive programming topics then just explore our blog home page.
Thanks for your time! 😊