## Rotate matrix clockwise

Posted on

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. […]

## Print matrix in spiral order

Posted on

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 – The output is – Solution – When an interviewer asks you this question, he/she is just testing your implementation skills. This question isn’t tough because it doesn’t have […]

## Add one to digit array

Posted on

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 […]

## First missing integer in an unsorted array

Posted on

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 […]

## Maximum sum contiguous sub-array

Posted on

Find a contiguous sub-array whose sum is maximum. Using the dynamic programming based Kadane’s Algorithm, we can solve this in O(N) time.

## Find the majority element in an array

Posted on

Given an unsorted array, find the majority element. Majority element is defined as that element which occurs for more than N/2 times. If the majority element exists, there will only be one such element. We can do this in O(N) time by the Boyer–Moore majority voting algorithm.

## Find pivot element in a sorted and rotated array

Posted on

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 […]

## Kth smallest element in an array

Posted on

Given an unsorted array of N elements, find the kth smallest element. This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm is a divide-and-conquer based algorithm which rearranges the array such that the kth element is the kth smallest element in the array.

## Intersection of two sorted arrays

Posted on

Given two sorted arrays, find the intersection (elements present in both arrays). We can do this in O(M + N) time, where M and N are lengths of arrays. What we will do here is similar to the “merging” step in merge sort.

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

Posted on

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 […]