Sliding Window Algorithm (Track the maximum of each subarray of size k)
Objective: Given an array and integer k, write an algorithm to find the maximum element in each subarray of size k. Example: int [] nums = { 1, 2, 3, 2, 4, 1, 5,...
Category: Arrays
Deque Implementation – Java
Java Deque Interface – It’s a linear collection. The Deque interface is a subtype of the util.Queue interface. Deque is acronym of “Double Ended Queue” means it supports insertion and removal of data from both...
Print all sub sequences of a given array
Objective: Given an array write an algorithm to print all the possible sub subsequences. Example: int [] a = {1, 2, 3}; Output: Possible sub sequences – {Empty}, {1}, {2}, {3}, {1, 2} ,{1,3}, {2,...
Sum of all sub arrays in O(n) Time
Objective: Given an array write an algorithm to find the sum of all the possible sub-arrays. Example: int [] a = {1, 2, 3}; Output: Possible subarrays – {1}, {2}, {3}, {1, 2} , {2,...
Print all subarrays of a given array
Problem: Given an array write an algorithm to print all the possible sub-arrays. Example: int [] a = {1, 2, 3}; Output: Possible subarrays – {1}, {2}, {3}, {1, 2} , {2, 3}, {1,...
Nuts & Bolts Problem (Lock & Key problem)
Objective: Given ‘n’ Nuts and ‘n’ Bolts of different sizes. There is one-to-one mapping between nuts and bolts. Write an algorithm to find all matches between nuts and bolts Note: This problem can also be...
Divide and Conquer – Rearrange array elements in special order
Objective: Given an array of integers of size 2n, write an algorithm to arrange them such that first n elements and last n elements are set up in alternative manner. Say n = 3 and...
Find median of two sorted arrays of same size
Objective: Given two sorted arrays of size n. Write an algorithm to find the median of combined array (merger of both the given arrays, size = 2n). What is Median? The median is the value separating the...
Find two non-repeating numbers in an array in O(n) time and O(1) space
Objective: Given an array of integers which has all the repeating numbers (twice) but two numbers which are non-repeating. Write an algorithm to find out those two numbers. Example int [] arrA = {4,5,4,5,3,2,9,3,9,8}; Output:...
Separate even and odd integers in a given array
Objective: Given an array which contains even and odd integers. Write an algorithm to separate even and odd numbers. Example int [] arrA = {1,2,3,4,6,8,7,12}; Output: [12, 2, 8, 4, 6, 3, 7, 1] Approach:...
Find three elements in an array that sum to a zero.
Objective: Given an array of integers write an algorithm to find 3 elements that sum to a zero. In short a+b+c = 0. Example int [] = { 3,-1,-7,-4,-5,9,10}; Elements are -4 9 -5 Approach:...
All elements appears thrice and one element appears once. Find that element in O(n) time and O(1) space
Objective: Given an array of integers in which all the elements are appear thrice but one which appears only one. Write an algorithm to find that element. Example int [] arrA = {6,5,3,2,4,2,5,6,3,3,6,5,2}; Output: 4...
Separate 0’s and 1’s in a given array
Objective: Given an array which contains only 0’s and 1’s. write an algorithm to separate 0’s and 1’s. Example int [] arrA = {1,0,1,0,1,1,0,0,0,0,1}; Output: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1,...
Find local minimum or local maximum in O(1).
Objective: Given an array such that every next element differs from the previous by +/- 1. (i.e. a[i+1] = a[i] +/-1 ) Find the local max OR min in O(1) time. The interviewer mentioned one...
Find three elements in an array that sum to a given value
Objective: Given an array of integer write an algorithm to find 3 elements that sum to a given number k. In short a+b+c = k. Example: int a [] = { 3,1,7,4,5,9,10} , k =...