Sort the Result Array

We have an integer array that is sorted in ascending order. We also have 3 ints A, B and C. We need to apply A*x*x + B*x + C for each element x in the array and return the corresponding sorted array.

Example: Input array = -1 0 1 2 3 4 and A = -1, B = 2, C = -1
Result of applying the formula to each element = -4 -1 0 -1 -4 -9
So expected result = -9 -4 -4 -1 -1 0 (sorted)

Time complexity :o(n), no extra space

Method: Parabolic Property
The equation given is parabolic. So the result of applying it to a sorted array will result in an array that will have a maximum/minimum with the sub-arrays to its left and right sorted.

In your case the maximum is 0 and the sub array to its left [-4 -1] is sorted in ascending order and the sub-array to its right [-1 -4 -9] is sorted in descending order.
All you need to do is merge these sorted arrays which is linear in time.

So the algorithm is:

Apply equation on each element
Find maximum/minimum
Merge subarrays

Useful Link:
http://stackoverflow.com/questions/4551599/sorting-result-array

Caterpillars and Uneaten Leaves

K caterpillars are eating their way through N leaves, each caterpillar falls from leaf to leaf in a unique sequence, all caterpillars start at a twig at position 0 and falls onto the leaves at position between 1 and N. Each caterpillar j has as associated jump number Aj. A caterpillar with jump number j eats leaves at positions that are multiple of j. It will proceed in the order j, 2j, 3j…. till it reaches the end of the leaves and it stops and build its cocoon.

Given a set A of K elements K<-15, N<=10^9, we need to determine the number of uneaten leaves.

Input:

N= No of uneaten leaves.

K= No. of caterpillars

A = Array of integer jump numbers

Output: The integer nu. Of uneaten leaves.

Sample Input:10, 3, 2, 4, 5

Output: 4

Explanation:

[2, 4, 5] is a j member jump numbers, all leaves which are multiple of 2, 4, and 5 are eaten, leaves 1,3,7,9 are left, and thus the no. 4

http://codereview.stackexchange.com/questions/95145/caterpillar-uneaten-leaves
http://stackoverflow.com/questions/27248327/caterpillars-and-leaves-can-we-do-better-than-onc
http://qa.geeksforgeeks.org/219/uneaten-leaves-problem

Active and Inactive cells after k Days

Given a binary array of size n where n > 3. A true (or 1) value in the array means active and false (or 0) means inactive. Given a number k, the task is to find count of active and inactive cells after k days. After every day, status of i’th cell becomes inactive if its left and right cells have same value, i.e., either both are 0 or both are 1.
Since there are no cells before leftmost and after rightmost cells, the value cells before leftmost and after rightmost cells is always considered as 0 (or inactive).

http://www.geeksforgeeks.org/active-inactive-cells-k-days/

Maximize value of (arr[i] – i) – (arr[j] – j) in an array

Given an array, arr[] find the maximum value of (arr[i] – i) – (arr[j] – j) where i is not equal to j. Where i and j vary from 0 to n-1 and n is size of input array arr[].

http://www.geeksforgeeks.org/maximize-value-of-arri-i-arrj-j-in-an-array/

Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space

Given an array arr[] of size n where every element is in range from 0 to n-1. Rearrange the given array so thatarr[i] becomes arr[arr[i]]. This should be done with O(1) extra space.

Examples:

Input: arr[]  = {3, 2, 0, 1}
Output: arr[] = {1, 0, 3, 2}

Input: arr[] = {4, 0, 2, 1, 3}
Output: arr[] = {3, 4, 2, 0, 1}

Input: arr[] = {0, 1, 2, 3}
Output: arr[] = {0, 1, 2, 3}

http://www.geeksforgeeks.org/rearrange-given-array-place/
http://www.geeksforgeeks.org/rearrange-array-arrj-becomes-arri-j/

Sort an array in wave form

Given an unsorted array of integers, sort the array into a wave like array. An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..

Examples:

 Input:  arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
 Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80} OR
                 {20, 5, 10, 2, 80, 6, 100, 3} OR
                 any other array that is in wave form

 Input:  arr[] = {20, 10, 8, 6, 4, 2}
 Output: arr[] = {20, 8, 10, 4, 6, 2} OR
                 {10, 8, 20, 2, 6, 4} OR
                 any other array that is in wave form

 Input:  arr[] = {2, 4, 6, 8, 10, 20}
 Output: arr[] = {4, 2, 8, 6, 20, 10} OR
                 any other array that is in wave form

 Input:  arr[] = {3, 6, 5, 10, 7, 20}
 Output: arr[] = {6, 3, 10, 5, 20, 7} OR
                 any other array that is in wave form
http://www.geeksforgeeks.org/sort-array-wave-form-2/

Find common elements in three sorted arrays

Given three arrays sorted in non-decreasing order, print all common elements in these arrays.

Examples:
ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20, 80

ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}
Output: 5, 5
http://www.geeksforgeeks.org/find-common-elements-three-sorted-arrays/

Find Maximum number possible by doing at-most K swaps

Given a positive integer, find maximum integer possible by doing at-most K swap operations on its digits.

http://www.geeksforgeeks.org/find-maximum-number-possible-by-doing-at-most-k-swaps/

Pending

Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges for consecutive numbers.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

http://www.programcreek.com/2014/07/leetcode-summary-ranges-java/

Array Resources for Interviews

I will update useful links in internet to study questions related to Arrays.

http://tech-queries.blogspot.in/search/label/Arrays%2FStrings
http://www.geeksforgeeks.org/archives/category/c-arrays
http://k2code.blogspot.in/search/label/arrays

Print all Jumping Numbers smaller than or equal to a given value

A number is called as a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1.
All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not.

Given a positive number x, print all Jumping Numbers smaller than or equal to x. The numbers can be printed in any order.

Example:

Input: x = 20
Output:  0 1 2 3 4 5 6 7 8 9 10 12

Input: x = 105
Output:  0 1 2 3 4 5 6 7 8 9 10 12
         21 23 32 34 43 45 54 56 65
         67 76 78 87 89 98 101

Note: Order of output doesn't matter, 
i,e., numbers can be printed in any order

http://www.geeksforgeeks.org/print-all-jumping-numbers-smaller-than-or-equal-to-a-given-value/

How to check if two given sets are disjoint?

Given two sets represented by two arrays, how to check if the given two sets are disjoint or not? It may be assumed that the given arrays have no duplicates.

Difficulty Level: Rookie

Input: set1[] = {12, 34, 11, 9, 3}
       set2[] = {2, 1, 3, 5}
Output: Not Disjoint
3 is common in two sets.

Input: set1[] = {12, 34, 11, 9, 3}
       set2[] = {7, 2, 1, 5}
Output: Yes, Disjoint
There is no common element in two sets.

http://www.geeksforgeeks.org/check-two-given-sets-disjoint/

Convert array into Zig-Zag fashion

Given an array of distinct elements, rearrange the elements of array in zig-zag fashion in O(n) time. The converted array should be in form a < b > c < d > e < f.

Example: 
Input:  arr[] = {4, 3, 7, 8, 6, 2, 1}
Output: arr[] = {3, 7, 4, 8, 2, 6, 1}

Input:  arr[] =  {1, 4, 3, 2}
Output: arr[] =  {1, 4, 2, 3}

http://www.geeksforgeeks.org/convert-array-into-zig-zag-fashion/

Arrange given numbers to form the biggest number

Given an array of numbers, arrange them in a way that yields the largest value. For example, if the given numbers are {54, 546, 548, 60}, the arrangement 6054854654 gives the largest value. And if the given numbers are {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value.

http://www.geeksforgeeks.org/given-an-array-of-numbers-arrange-the-numbers-to-form-the-biggest-number/

Absolute distinct count in a sorted array

Given a sorted array of integers, return the number of distinct absolute values among the elements of the array. The input can contain duplicates values.

Input: [-3, -2, 0, 3, 4, 5]
Output: 5
There are 5 distinct absolute values
among the elements of this array, i.e.
0, 2, 3, 4 and 5)

Input:  [-1, -1, -1, -1, 0, 1, 1, 1, 1]
Output: 2

Input:  [-1, -1, -1, -1, 0]
Output: 2

Input:  [0, 0, 0]
Output: 1 

http://www.geeksforgeeks.org/absolute-distinct-count-array-sorted-absolute-values/

Count the number of possible triangles

Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as three sides of triangles. For a triangle to be possible from 3 values, the sum of any two values (or sides) must be greater than the third value (or third side).

For example, if the input array is {4, 6, 3, 7}, the output should be 3. There are three triangles possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}. Note that {3, 4, 7} is not a possible triangle.
As another example, consider the array {10, 21, 22, 100, 101, 200, 300}. There can be 6 possible triangles: {10, 21, 22}, {21, 100, 101}, {22, 100, 101}, {10, 100, 101}, {100, 101, 200} and {101, 200, 300}

http://www.geeksforgeeks.org/find-number-of-triangles-possible/

Find Union and Intersection of two sorted arrays. Modify it the same for two unsorted arrays

Union and Intersection of two sorted arrays

Given two sorted arrays, find their union and intersection.

For example, if the input arrays are: 
arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}. 

http://www.geeksforgeeks.org/union-and-intersection-of-two-sorted-arrays-2/

Find Union and Intersection of two unsorted arrays

Given two unsorted arrays that represent two sets (elements in every array are distinct), find union and intersection of two arrays.

For example, if the input arrays are:
arr1[] = {7, 1, 5, 2, 3, 6}
arr2[] = {3, 8, 6, 20, 7}
Then your program should print Union as {1, 2, 3, 5, 6, 7, 8, 20} and Intersection as {3, 6}. Note that the elements of union and intersection can be printed in any order.

http://www.geeksforgeeks.org/find-union-and-intersection-of-two-unsorted-arrays/

pending

Find popular items

Find popular item in sorted array of natural numbers.
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.

This is actually a very interesting problem. Since the popular item is defined as the element is repeated more than 1 / 4 times, and since it is a sorted array, so it can only occurs on 0, n / 4, n /2 and 3n/4 index. And the rest is just do binary search and get the range.

?

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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

public class PopularNumber {  public static void popular(int[] n){   if(n == null || n.length == 0)    return;   int len = n.length;   int[] check = {0, len / 4, len / 2, 3 * len / 4};   for(int i = 0; i < 4; i++){    if(i > 0 && n[check[i]] == n[check[i - 1]])     continue;    int l = check[i];    int start = binarySearchStart(n, n[l]);    int end = binarySearchEnd(n, n[l]);    //need to be larger than the ceil in case len / 4.0 is not an integer    if(end - start + 1 >= Math.ceil(len / 4.0))     System.out.println(n[l]);   }  }  private static int binarySearchEnd(int[] n, int target){   int len = n.length;   int start = 0;   int end = len - 1;   while(start + 1 < end){    int mid = (start + end) / 2;    if(n[mid] <= target)     start = mid;    else     end = mid;   }   if(n[end] == target)    return end;   else return start;  }  private static int binarySearchStart(int[] n, int target){   int len = n.length;   int start = 0;   int end = len - 1;   while(start + 1 < end){    int mid = (start + end) / 2;    if(n[mid] >= target)     end = mid;    else     start = mid;   }   if(n[start] == target)    return start;   else    return end;  }    public static void main(String[] args) {   //int[] n = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8};   int[] n = {1, 1, 2, 3, 4};   popular(n);  } }