Category Archives: Arrays

View algorithms on Arrays

Next Greater Element in an array. [NGE]

Question: There is an array A[N] of N numbers. You have to compose an array Output[N] such that each element in Output[i] will tell the next greater element to the right in the original array. If there is no greater number to the right, then the output array should contain -1 in that position. Array 1: {4, 6,… Read More »

Kth largest element in an array (Method 1)

Question: Given an unsorted array of integers and a number ‘k’. Return the kth largest element in the array. Input: arr = {3,2,1,5,6,4}, k = 2 Output: 5 Given an unsorted array of integers, you need to determine the kth largest element. By taking a first glance at the problem we can be sure of one thing. If… Read More »

Convert a number into a string of words

Question: Given an integer N, convert it into a string of words. Input: N = 345 Output: three hundred forty five This is one of the most common problems that we come across in out daily lives. We need to input a number from the user and print it in words. First, we perform a number of checks… Read More »

Given a function that generates random number from 1-7, write a function that generates random numbers from 1-10.

Question: You are given a function rand7() – that generates random numbers from 1-7. Write a function rand10() – that uses rand7() to generate random numbers from 1-10. This appear to be one of those probabilistic analysis questions. You should be familiar with the concept of expected value, as it could be extremely helpful in probabilistic analysis. Hint:… Read More »

An array puzzle

Question: There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. Solve it without division operator and in O(n). For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and… Read More »

Find the intersection points of 2 sorted arrays.

Question: Given 2 sorted arrays, find the intersection elements between them. Array 1: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26 Array 2: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 Output: 6, 12, 18, 24 Let’s called Array1 as “A” and Array2 as “B”, each with size m and… Read More »

The Stock Market Problem

Question: Let us suppose we have an array whose ith element gives the price of a share on the day i. If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell. When we talk about the best… Read More »

Separate 0’s and 1’s in an array.

Question: Given an array arr[], that contains only 0’s and 1’s. Write a function that separate 0’s and 1’s in the array. Input: 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 Output: 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 The objective of the… Read More »

Separate odd and even numbers in an array.

Question: Given an array arr[], write a function that separates even and odd numbers. The function should print first all the even numbers and then the odd numbers. Input: 4, 8, 15, 16, 23, 42 Output: 4, 8, 16, 42, 23, 15 The objective of this problem is mainly to segregate the array in two halves. One half… Read More »

Find the majority element in an array. (Method 3)

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element =… Read More »