Interview Questions on Arrays

Rotate matrix clockwise

Problem statement - Given an array of N rows and N columns (square matrix), rotate the matrix by 90° in clockwise direction. Solution - This is an implementation based problem, which means that when asked in an interview, the interviewer is mainly testing your skill to write a program which follows some set of rules. There are no tricky cases here but you might struggle in the interview if you don't have the right approach ...
Read More

Print matrix in spiral order

Problem statement - Given a 2D array (or matrix) of N rows and M columns, print it in a spiral order. Example, for the below matrix - int[] arr = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, }; The output is - 1 2 3 6 9 8 7 4 5 Solution - When an interviewer asks you this question, he/she is just testing your implementation skills. This question isn't tough because ...
Read More

Add one to digit array

Problem statement - Given a non-negative integer in the form of an array of digits, add one to digit array. The digits are stored such that the most significant digit is at the head of the list. Eg. - A = {1, 3, 5}, answer = {1, 3, 6} Solution - When an interviewer asks questions like these, he is testing your implementation skills and you ability to discover the corner cases. The solution is ...
Read More

First missing integer in an unsorted array

Problem statement - Given an unsorted integer array, find the first missing positive integer. Example, If A = [-1, 4, 2, 3, 5], missing integer = 1. If A = [1, 5, 2, 3, 4, 7], missing integer = 6. If A = [-1, -2, -3, -4], missing integer = 1. Clues - Your solution should be O(N) in time and O(1) in space. Can you make changes in the array such that you can ...
Read More

Maximum sum contiguous sub-array

Problem statement - Given an array, find a contiguous sub-array whose sum is maximum. More precisely, if we have an array A[0, 1, 2 ... N], we need to find a sub-array A[i, i + 1, i + 2, ... j] such that the sum of elements in the sub-array is maximum. Clues - Your solution should be O(N) in time and O(1) in space. Can you think of a solution which solves the problem ...
Read More

Find the majority element in an array

Problem statement - Given an unsorted array, find the majority element (element which occurs for more than N/2 times). Clues - Solution must be O(N) in time and O(1) in space. If the majority element exists, there will only be one such element. How can we find it? Solution - 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 ...
Read More

Find pivot element in a sorted and rotated array

Problem Statement - Suppose we have a sorted array, and now we rotate it N times, find the pivot element. The pivot element would be the largest element. Also, can you calculate N? Clues - Solution should be O(log N) in time and O(1) in space. Can you think of  a binary search based solution where you keep comparing the middle element with the last element? Solution - The pivot element is basically, the largest ...
Read More

Kth smallest element in an array

Problem Statement - Given an unsorted array of N elements, find the kth smallest element. kth smallest element is the element at index k if the array were sorted. Clues - Solution should be O(N) in time and O(1) in space. Can you think of a divide-and-conquer based solution? Can you apply Quicksort's partitioning logic here? Solution - This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm ...
Read More

Intersection of two sorted arrays

Problem statement - Given two sorted arrays, find the intersection (elements present in both arrays). Clues - Solution must be O(M + N) in time and O(min(M, N)) space. Can you apply merge sort's merging logic here? Solution - This is simple, we can do this in O(M + N) time, where M and N are the array lengths. What we will do here is similar to the “merging” step in merge sort. We will ...
Read More

Element in an array which appears once while other elements appear twice

Problem Statement - Given an array of numbers where all numbers appear twice except for one number which appears only once, find that number. Clues - Solution should be O(N) in time and O(1) in space. Use bit operations. Solution - XOR of two same numbers is zero. So, if we take the XOR of all numbers in the array, the numbers which appear twice will get cancelled and in the end the number which ...
Read More