Remove duplicates from infinite integers

You are given an infinite stream of integers. The stream of integers is unsorted and are provided by iterator so that you don't have the access to all the elements at once. You have to return another iterator from the input iterator so that there are no duplicates and the input order is maintained.

http://www.dsalgo.com/2013/03/remove-duplicate-infinite-integer.html

Guess Number higher or lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6.

Return 6.
http://www.programcreek.com/2014/07/leetcode-guess-number-higher-or-lower-java/

The Stock Span Problem

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate span of stock’s price for all n days.
The span Si of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.
For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}
http://www.geeksforgeeks.org/the-stock-span-problem/

Find maximum of minimum for every window size in a given array

Given an integer array of size n, find the maximum of the minimum’s of every window size in the array. Note that window size varies from 1 to n.

Example:

Input:  arr[] = {10, 20, 30, 50, 10, 70, 30}
Output:         70, 30, 20, 10, 10, 10, 10

First element in output indicates maximum of minimums of all
windows of size 1.
Minimums of windows of size 1 are {10}, {20}, {30}, {50}, {10},
{70} and {30}.  Maximum of these minimums is 70

http://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/

Find Square and cubic root of a number

Given a number n, find the cube root of n.
Examples:

Input:  n = 3
Output: Cubic Root is 1.442250

Input: n = 8
Output: Cubic Root is 2.000000
http://www.geeksforgeeks.org/find-cubic-root-of-a-number/

Square root of an integer:
http://www.geeksforgeeks.org/square-root-of-an-integer/

Rearrange positive and negative numbers

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.

For example, if the input array is [-1, 2, -3, 4, 5, 6, -7, 8, 9], then the output should be [9, -7, 8, -3, 5, -1, 2, 4, 6]

Strategy: Partition in Quick Sort
http://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers-publish/

Variation 2:
Given an array of positive and negative numbers, arrange them such that all negative integers appear before all the positive integers in the array without using any additional data structure like hash table, arrays, etc. The order of appearance should be maintained.

Examples:

Input:  [12 11 -13 -5 6 -7 5 -3 -6]
Output: [-13 -5 -7 -3 -6 12 11 6 5]
http://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers/

Efficient Data Stricure for findMin(), findMax(), deleteMin(), deleteMax(), insert, delete

Design a Data Structure for the following operations. The data structure should be efficient enough to accommodate the operations according to their frequency.

1) findMin() : Returns the minimum item.
   Frequency: Most frequent

2) findMax() : Returns the maximum item.
    Frequency: Most frequent

3) deleteMin() : Delete the minimum item.
    Frequency: Moderate frequent 

4) deleteMax() : Delete the maximum item.
    Frequency: Moderate frequent 

5) Insert() : Inserts an item.
    Frequency: Least frequent

6) Delete() : Deletes an item.
    Frequency: Least frequent

http://www.geeksforgeeks.org/a-data-structure-question/

Sort numbers stored on different machines

Given N machines. Each machine contains some numbers in sorted form. But the amount of numbers, each machine has is not fixed. Output the numbers from all the machine in sorted non-decreasing form.

Example:
       Machine M1 contains 3 numbers: {30, 40, 50}
       Machine M2 contains 2 numbers: {35, 45} 
       Machine M3 contains 5 numbers: {10, 60, 70, 80, 100}
       
       Output: {10, 30, 35, 40, 45, 50, 60, 70, 80, 100}

Representation of stream of numbers on each machine is considered as linked list. A Min Heap can be used to print all numbers in sorted order.

http://www.geeksforgeeks.org/sort-numbers-stored-on-different-machines/

10 maximum integers from 1 million integers

You Have File of Containing 1 Million Integers You need To Find 10
Maximum Integer Out of Them.How You Will Do That. What is Time &
space Complexity of Algorithm that you will use then optimize the
solution..

Constraints- U can't Store Whole File in memory at one time.

Strategy:

Using Min Heap:

Use a min-heap of 10 elements.Initialize the heap with first 10 elements in O(10) [constant] time.For each of the next element,check whether it is greater than root of min heap,if it is,replace that element by the next element and heapify the heap again in O(log10) [constant] time.At last extract all the 10 elements one by one in O(log10) constant time each.so space complexity O(1) time complexity O(N).

Using Max Heap:

A solution for this problem may be to divide the data in some sets of 1000 elements (let’s say 1000), make a heap of them, and take 10 elements from each heap one by one. Finally heap sort all the sets of 10 elements and take top 10 among those. But the problem in this approach is where to store 10 elements from each heap. That may require a large amount of memory as we have billions of numbers.

Reuse top 20 elements from earlier heap in subsequent elements can solve this problem. I meant to take first block of 1000 elements and subsequent blocks of 990 elements each. Initially heapsort first set of 1000 numbers, took max 10 elements and mix them with 990 elements of 2^ndset. Again heapsort these 1000 numbers (10 from first set and 990 from 2^nd set), take 10 max element and mix those with 980 elements of 3^rd set. Repeat the same exercise till last set of 990 (or less) elements and take max 20 elements from final heap. Those 10 elements will be your answer.

Complexity: O(n) = n/1000*(complexity of heapsort 1000 elements)

Since complexity of heap sorting 1000 elements will be a constant so the O(n) = N i.e. linear complexity 

Clone a Binary Tree with Random Pointers

Given a Binary Tree where every node has following structure.

struct node {  
    int key; 
    struct node *left,*right,*random;
} 

The random pointer points to any random node of the binary tree and can even point to NULL, clone the given binary tree.

http://www.geeksforgeeks.org/clone-binary-tree-random-pointers/

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/

Pending

Count Inversions in an array

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. 

Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j 

Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

http://www.geeksforgeeks.org/counting-inversions/
http://www.geeksforgeeks.org/count-inversions-in-an-array-set-2-using-self-balancing-bst/

http://quiz.geeksforgeeks.org/counting-inversions-using-set-in-c-stl/

Variation: Find Surpasser Count of each element in array
A surpasser of an element of an array is a greater element to its right, therefore x[j] is a surpasser of x[i] if i < j and x[i] < x[j]. The surpasser count of an element is the number of surpassers. Given an array of distinct integers, for each element of the array find its surpasser count i.e. count the number of elements to the right that are greater than that element.
Examples:
Input:  [2, 7, 5, 3, 0, 8, 1]

Output: [4, 1, 1, 1, 2, 0, 0]
http://www.geeksforgeeks.org/find-surpasser-count-of-each-element-in-array/

Self Crossing or not

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south,x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │

Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>

Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>

Return true (self crossing)

 There are only three situations when the path will not cross itself:

1. The number keeps increasing (which will form an growing spiral).
2. The number keeps decreasing (which will form an shrinking spiral).
3. The number increases first, then decreases, and never increases again.   

The harder part is to implement all three situations. Since our program should be one pass, we should check if the number keeps increasing (or decreasing), or if it changes its trend.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public boolean isSelfCrossing(int[] x) {         if (x == null || x.length < 4)             return false;         int length = x.length;         int t1 = 0, t2 = x[0], t3 = x[1], t4 = x[2], t5;         boolean isIncrease = (t4 > t2);         for (int i = 3; i < length; i++) {             t5 = x[i];             if (isIncrease && (t3 >= t5)) {                 if ((t1 + t5) < t3 || ((i < length - 1) && x[i + 1] + t2 < t4))                     isIncrease = false;                 else if (i < length - 1)                     return true;             } else if (!isIncrease && (t3 <= t5))                 return true;             t1 = t2;             t2 = t3;             t3 = t4;             t4 = t5;         }         return false;     }