Hello, people..! In this post, I will discuss some of the arrays interview questions (coding and conceptual), which you must solve before you attempt any technical interviews. The questions are given below. You may click on the question to see its solution. But, it is extremely recommended to think about how you would give your approach to solve a particular question before looking at its solution. And if you are reading this post, I assume that you have pretty good amount of experience with algorithms.. 😛
Coding Questions
int missingNumber(int arr[], int n) { int i, sum = 0; // Sum up all the numbers for (i = 0; i < n; ++i) { sum += arr[i]; } // Expected Sum - Actual Sum return (n * (n + 1)) / 2 - sum; }
int findNonDuplicate(int arr[], int n) { int xorVal = 0, i; // XOR all the elements for (i = 0; i < n; ++i) { xorVal ^= arr[i]; } return xorVal; }
- A[i] == B[j] – then add it to the intersection.
- A[i] > B[j] – then increment j.
- A[i] < B[j] – then increment i.
public static ArrayList<Integer> getIntersection(int[] A, int[] B) { // Add interesting elements to this collection ArrayList<Integer> intersection = new ArrayList<>(); int i = 0, j = 0; while (i != A.length && j != B.length) { if (A[i] == B[j]) { // If both are equal, add to intersection intersection.add(A[i]); ++i; ++j; } else if (A[i] > B[j]) { // Increment index to second array ++j; } else { // A[i] < B[j] // Increment index to first array ++i; } } return intersection; }
We can do this in O(N + K log K) time by using Quickselect Algorithm to find the kth largest element. Then we can partition the array in the Quicksort manner, where all elements greater than the kth greatest element are placed to one side, and apply an O(N log N) sorting algorithm on those K elements.
The Quickselect Algorithm is given under “Find the k^{th} smallest/largest element in an array” question. And then its just sorting 😉
This isn’t neccessarily a tough question, but it can get clumsy. You just have to observe how the indices are varying for in the 4 directions –
- Left-to-Right
- Top-to-Bottom
- Right-to-Left
- Bottom-to-Top
First try to do that for a square matrix, and then extend it to a rectangular matrix. Some sample test cases and outputs have been given to give you a better understanding of the problem.
Lastly, there’s a catch, for a rectangular matrix, you need a stopping condition. We have four loops (the four directions). If any of them had no iterations, then we stop the process. This is to ensure that we don’t print the same numbers which we already printed. Just try coding the spiral print for a rectangular matrix without any stopping condition, then you’ll see for yourself what I mean 🙂
6 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
Output –
1 2 3 4 5 6 12 18 24 30 36 35 34 33 32 31 25 19 13 7 8 9 10 11 17 23 29 28 27 26 20 14 15 16 22 21
3 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Output –
1 2 3 4 5 10 15 14 13 12 11 6 7 8 9
5 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Output –
1 2 3 6 9 12 15 14 13 10 7 4 5 8 11
public static void spiralPrint(int[][] arr) { // i denotes the depth for (int i = 0; i <= arr.length / 2; ++i) { boolean stop = true; // Left - Right for (int j = 0 + i; j < arr[0].length - i; ++j) { stop = false; System.out.println(arr[i][j]); } // If there we no iterations possible for the previous loop, it // means out spiral print is over, so we stop, otherwise, reset flag if (stop) { break; } else { stop = true; } // Up - Down for (int j = 1 + i; j < arr.length - i; ++j) { stop = false; System.out.println(arr[j][arr[0].length - 1 - i]); } if (stop) { break; } else { stop = true; } // Right - Left for (int j = arr[0].length - 2 - i; j >= 0 + i; --j) { stop = false; System.out.println(arr[arr.length - 1 - i][j]); } if (stop) { break; } else { stop = true; } // Down - Up for (int j = arr.length - 2 - i; j >= 1 + i; --j) { System.out.println(arr[j][i]); } if (stop) { break; } } }
- Instead of checking if the mid value is equal to the search value, we will only check if the lower limit is equal to the search value or not.
- If it is not equal, then we compare the mid value and the search value. If the mid value is lesser, we search in the second half of the limits.
- If the mid value is not greater (<=), then we search in the first half of the limits, inclusive of the mid.
The third modification is actually what does the trick and ensures that we get the first occurrence.
// A modified Binary Search procedure which returns the first // occurrence of 'searchValue' in a sorted array -> O(log N) int binarySearch(int arr[], int low, int high, int searchValue) { if (high - low >= 1) { // Must calculate 'mid' in this // fashion to avoid integer overflow int mid = low + (high - low) / 2; if (arr[low] == searchValue) { // If lower limit is 'searchValue' // return the lower limit return low; } else if (arr[mid] < searchValue) { // If array's mid value is lesser than 'searchValue' // search for it in the second half of the limits return binarySearch(arr, mid + 1, high, searchValue); } else { // If the array's mid value is greater // than OR EQUAL TO 'searchValue', search // for it in the first half of the limits return binarySearch(arr, low, mid, searchValue); } } else { if (arr[low] == searchValue) { return low; } } // 'searchValue' does not exist in the array return -1; }
- Instead of checking if the mid value is equal to the search value, we will only check if the upper limit is equal to the search value or not.
- If it is not equal, then we compare the mid value and the search value. If the mid value is lesser, we search in the first half of the limits.
- If the mid value is not lesser (>=), then we search in the second half of the limits, inclusive of the mid.
// A modified Binary Search procedure which returns the last // occurrence of 'searchValue' in a sorted array -> O(log N) int binarySearch(int arr[], int low, int high, int searchValue) { if (high - low >= 1) { // Must calculate 'mid' in this // fashion to avoid integer overflow int mid = low + (high - low) / 2; if (arr[high] == searchValue) { // If upper limit is 'searchValue' // return the upper limit return high; } else if (arr[mid] > searchValue) { // If array's mid value is greater than 'searchValue' // search for it in the first half of the limits return binarySearch(arr, low, mid - 1, searchValue); } else { // If the array's mid value is less // than OR EQUAL TO 'searchValue', search // for it in the second half of the limits return binarySearch(arr, mid, high - 1, searchValue); } } else { if (arr[high] == searchValue) { return high; } } // 'searchValue' does not exist in the array return -1; }
Peak Element – An element in an array is called a Peak Element, if it is not smaller (>=) than its neighbours. Where we imagine that elements out of array bounds to be at -∞.
The best solution to this is based on Divide-and-Conquer approach which gives an O(log N) solution. What we do here is –
- Divide the range into 2 halves.
- Check if the middle element is greater than its neighbours.
- If not –
- If the left-neighbour of mid element is greater than the mid element, it means that the values are falling, so, recursively continue the search in the 1^{st} half of the range.
- If the right-neighbour of mid element is greater than the mid element, it means that the values are rising, so, recursively continue the search in the 2^{nd} half of the range.
- Deal with base case conditions where there is only one element.
// A Divide-and-Conquer approach to find the peak element in an array // Returns the index of the peak element in the array -> O(log N) int peakElement(int arr[], int low, int high, int lowerBound, int upperBound) { int mid = low + (high - low) / 2; if (mid == lowerBound) { if (mid == upperBound) { // Only 1 element return mid; } else if (arr[mid] >= arr[mid + 1]) { // 1st element is greater than 2nd element return mid; } } else if (mid == upperBound) { if (arr[mid] >= arr[mid - 1]) { // Last element is greater than // the second last element return mid; } } else { if (arr[mid] >= arr[mid + 1] && arr[mid] >= arr[mid - 1]) { // Mid value is a peak return mid; } else if (arr[mid] < arr[mid + 1]) { // The value is rising, so go to the 2nd half return peakElement(arr, mid + 1, high, lowerBound, upperBound); } else if (arr[mid] < arr[mid - 1]) { // The value is falling, so go to the 1st half return peakElement(arr, low, mid - 1, lowerBound, upperBound); } } return 0; }
- arr[mid] > arr[high] – If the mid element is greater than the last element, then the pivot should be in the second half of the array. Why is this so? This is actually because it is a sorted and rotated array. You may not understand this at first, but think of the values of the elements in the array as a histogram. Try to understand the picture below, I’m sure you can figure out why this happens –
- arr[mid] < arr[high] – If the mid element is less than the last element, then the pivot should be in the first half of the range.
- If mid element is a peak – If the mid element satisfies the property of the peak element (not lesser than its neighbours), then, it is the pivot.
// A Divide-and-Conquer approach to find the pivot (highest) element in // a sorted rotated array - returns the index of the pivot -> O(log N) int peakElement(int arr[], int low, int high, int lowerBound, int upperBound) { int mid = low + (high - low) / 2; if (mid == lowerBound) { if (mid == upperBound) { // Only 1 element return mid; } else if (arr[mid] >= arr[mid + 1]) { // Pivot is the greater element return mid; } } else if (mid == upperBound) { if (arr[mid] >= arr[mid - 1]) { // Pivot is the greater element return mid; } } else { if (arr[mid] >= arr[mid + 1] && arr[mid] >= arr[mid - 1]) { // Mid value is the pivot return mid; } else if (arr[mid] > arr[high]) { // The Pivot is in the second half return peakElement(arr, mid + 1, high, lowerBound, upperBound); } else if (arr[mid] < arr[high]) { // The Pivot is in the first half return peakElement(arr, low, mid - 1, lowerBound, upperBound); } } return -1; }
We can do this in O(N) time if we have readymade data structures. In Java, we could use a HashSet
For this question, the elements of the array are distinct and we must print only the distinct pairs.
import java.util.HashSet; import java.util.Scanner; public class TwoElementSum { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int[] arr = new int[n]; HashSet<Integer> hashTable = new HashSet<>(); for (int i = 0; i < arr.length; ++i) { arr[i] = s.nextInt(); hashTable.add(arr[i]); // O(1) insertion } int k = s.nextInt(); // The sum to be compared for (int i = 0; i < arr.length && arr[i] < k - arr[i]; ++i) { if (hashTable.contains(k - arr[i]) && hashTable.contains(arr[i])) { // Counterpart is present // Print in increasing order System.out.println(arr[i] + " " + (k - arr[i])); } } } }
import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; public class ThreeElementSum { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int[] arr = new int[n]; HashSet<Integer> hashTable = new HashSet<>(); for (int i = 0; i < arr.length; ++i) { arr[i] = s.nextInt(); hashTable.add(arr[i]); // O(1) insertion } // The sum to be compared int k = s.nextInt(); Arrays.sort(arr); // O(N log N) // O(N^2) for (int i = 0; i < arr.length; ++i) { for (int j = i + 1; j < arr.length; ++j) { int val = k - arr[i] - arr[j]; if (val != arr[i] && val != arr[j] && hashTable.contains(val)) { // Counterpart is present if (val > arr[i] && val > arr[j]) { System.out.println(arr[i] + " " + arr[j] + " " + val); } } } } } }
- Take three loops to iterate over the array. (N^{3})
- Compute the fourth element mathematically and check if it is present in the array in O(1) time by using a Hash Table.
But this can be solved in O(N^{2}) time and with O(N^{2}) extra space –
- Store all the pairs and the indices of the elements which make up the pairs – O(N^{2})
- Now we have, our problem reduces to finding pairs whose sum is K, which can be done in linear time, which here, will cost us O(N^{2}) time.
But this takes too much memory. This solution will be posted soon.
import java.util.HashSet; import java.util.Scanner; public class FourElementSum { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int[] arr = new int[n]; HashSet<Integer> hashTable = new HashSet<>(); for (int i = 0; i < arr.length; ++i) { arr[i] = s.nextInt(); hashTable.add(arr[i]); // O(1) insertion } int sum = s.nextInt(); // The sum to be compared for (int i = 0; i < arr.length; ++i) { for (int j = 0; j < arr.length; ++j) { if (i == j || arr[i] > arr[j]) { // Ensuring increasing order of solution continue; } for (int k = 0; k < arr.length; ++k) { if (j == k || arr[j] > arr[k]) { // Ensuring increasing order of solution continue; } int val = sum - arr[i] - arr[j] - arr[k]; if (val > arr[k] && hashTable.contains(val)) { // All parts present - print in increasing order System.out.println(arr[i] + " " + arr[j] + " " + arr[k] + " " + val); } } } } } }
- Calcualte the middle element for the given range.
- Place all the elements greater than the mid element to its right.
- Place all the elements lesser than the mid element to its left.
- If ‘k’ is less than the index of the middle element, then recursively call quickselect on the left half of the range.
- If ‘k’ is greater than the index of the middle element, then recursively call quickselect on the right half of the range.
// Quick Select procedure to search for // the kth smallest element in O(N) time. void quickSelect(int arr[], int low, int high, int k) { if (high - low < k) { // A single element is // considered to be sorted return; } int mid = low + ((high - low) / 2); // Put the pivot at the last int temp = arr[mid]; arr[mid] = arr[high]; arr[high] = temp; int pivot = arr[high]; int i = low; int j = high - 1; // The partition while (j >= i) { if (arr[j] < pivot && arr[i] > pivot) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; ++i; --j; } else if (arr[j] < pivot && arr[i] <= pivot) { ++i; } else if (arr[j] >= pivot && arr[i] > pivot) { --j; } else if (arr[j] >= pivot && arr[i] <= pivot) { ++i; --j; } } // Bring the pivot back to its // appropriate place temp = arr[i]; arr[i] = arr[high]; arr[high] = temp; if (k >= i) { quickSelect(arr, i + 1, high, k); } else { quickSelect(arr, low, i, k); } }
We can do this in O(N) time by the Boyer–Moore majority voting algorithm. It is a simple 3-step algorithm –
- Initialization – We will take 2 variables, ‘candidate’ and ‘votes’ and set them to 0.
- Voting – Traverse through the array once. If votes is 0, then we set candidate to the current element. We will also check, if the current element (arr[i]) is equal to the candidate, if yes, increment votes, else decrement.
- Checking the winning candidate – After Step 2, we will compute the frequency of the value in candidate. If this is more than N/2, then the candidate is the majority element, otherwise, the majority element does not exist.
// Moore's Majority Voting Algorithm procedure // Computes the majority element in O(N) time // Returns the majority element // If no majority element, returns INT_MIN int majorityElement(int arr[], int length) { int votes = 0, candidate = -1, i; // Voting for (i = 0; i < length; ++i) { if (votes == 0) { candidate = arr[i]; } if (candidate == arr[i]) { ++votes; } else { --votes; } } votes = 0; // Get freq. of candidate for (i = 0; i < length; ++i) { if (arr[i] == candidate) { ++votes; } } // Verify if the candidate // is the majority element if (votes > length / 2) { return candidate; } else { return INT_MIN; } }
- Initialization – We will take 2 variables ‘currentSum’ and ‘maxSum’. currentSum is to store the sum of various contiguous subarrays during computation, and ‘maxSum’ is to store the maximum of all the values encountered by currentSum
- We will iterate through the array. As we look at each element, we will add it to currentSum, and, we will check if that element contributes to a positive currentSum. If yes, we add it to currentSum. This means that the element is a part of the contiguous subarray whose sum is stored by currentSum.
- If no, if it makes the currentSum negative, it means that it is the end of that subarray. In this case, we will reset our currentSum.
// Kadane's Algorithm procedure to compute // Maximum Contiguous Sum in an array - O(N) int maximumContigSum(int arr[], int length) { int currentSum = 0, maxSum = 0, i; for (i = 0; i < length; ++i) { // If element contributes // to a positive sum if (currentSum + arr[i] > 0) { currentSum += arr[i]; // Is this the maximum? if (currentSum > maxSum) { maxSum = currentSum; } } else { // Reset sums currentSum = 0; } } return maxSum; }
This post is a little dynamic. More questions will be added as soon as the solutions are made, some of the questions which will come in the near future are –
- Median of two sorted arrays.
- Find the smallest positive integer that cannot be represented as the sum of any subset of the array.
- Find the number of duplicates in an array using O(1) space.
- Given an array with +ve and -ve numbers. Rearrange such that +ve and -ve numbers appear alternatively, maintaining the relative order, using O(1) space.
Conceptual Questions
Array | Linked List |
---|---|
Memory allocated for an array is contiguous. | Memory allocated in a linked list need not be contiguous (mostly won’t be). |
Accessing an element takes O(1) time, as the elements can be randomly accessed using their index. | Accessing an element in a linked list takes O(N) time, as one would have to traverse the whole linked list to find the element. No random access. |
Arrays are of fixed size. | A linked list can grow or shrink in size, dynamically. |
Memory allocated for an array is contiguous. | Memory allocated in a linked list need not be contiguous (mostly won’t be). |
Inserting a new element, takes O(N) time. You must do this by creating a new array and copying everything including the new element into it. | Inserting a new element, takes O(1) time, provided you already know where to insert. |
Deleting an element, takes O(N) time. All though you won’t actually delete the allocated memory, the element is erased and the elements right to it are shifted left by one position, and our ‘size’ variable would be decremented. | Deleting a new element, takes O(1) time, provided you already know where to delete. |
The memory for the arrays we locally use, such as, int arr[] = {1, 2, 3};, is allocated on the stack (heap in java). Although, we can create them dynamically, where the memory is allocated on the heap. | Memory is always allocated on the heap. |
There is no wastage of space. | A node in a linked list must store the address of the adjacent nodes, so the amount of actual data stored is more, causes and O(N) wastage of space. |
As it is a matter of simple constant time arithmetic calculations, accessing an element in an array takes constant time.
int[] arr;
which is considered to be the clean way. But, things can change if you are declaring this with other variables. Such as –
int[] x, y, z;
Here, x, y, z, are all integer arrays, now consider –
int x[], y, z;
Here, x is an integer array, whereas others are normal local variables.
- Tight Strategy – We increase the array size by a constant ‘C’.
- Growth Strategy – We double the size of array when required.
- fun(int arr[][n]) – We can pass the 2D array directly in this manner if the length of the second dimension is available as a global constant or a macro.
- fun(int ** arr) – A 2D array is an array of arrays, so we can pass it as a 1D array of “integer array pointers” or pointer to pointers. This method can be very confusing to people who are not comfortable with pointers. It is easy to visualize the array as the sketch below –
I hope these questions help you. These are pretty base level interview questions. Nothing too great. But if you can solve these it will give you a great confidence boost and, what’s more, is that you can use these techniques to solve bigger problems based on arrays. Do leave a comment if you liked my post or if you have any queries… 🙂 … Keep practising… Happy Coding.. 😀
Hey can you mention your source?
My seniors! They just gave me a must-do-questions list 😛
O(N) O(1)?????
Ummm… I’m not getting you… What exactly is your question?!
That was just great! You could add more topics to the interview corner 🙂
Will do that soon 🙂
Working on it 🙂