Find running median from a stream of integers

Problem:
Given that integers are read from a data stream. Find median of elements read so for in efficient way.

Solution:
We can use a max heap on left side to represent elements that are less than effective median, and a min heap on right side to represent elements that are greater than effective median.

After processing an incoming element, the number of elements in heaps differ at most by 1 element (because we re-balance the heaps if needed). When both heaps contain same number of elements, we pick average of heaps root data as effective median. When the heaps are not balanced, we select effective median from the root of heap containing more elements.


NOTE: Finding running median from a stream of data is a tough problem, and finding an exact solution with memory constraints efficiently is probably impossible for the general case. On the other hand, if the data has some characteristics we can exploit, we can develop efficient specialized solutions. For example, if we know that the data is an integral type, then we can use counting sort, which can give you a constant memory constant time algorithm. Heap based solution is a more general solution because it can be used for other data types (doubles) as well. And finally, if the exact median is not required and an approximation is enough, you can just try to estimate a probability density function for the data and estimate median using that.

Complexity:

time - O(1)
space - O(n) or O(1)

Links and credits:
http://stackoverflow.com/questions/10657503/find-running-median-from-a-stream-of-integers

Generate 1 and 0 with equal probability

Problem:
Given a function “f” in which 0 occurs with probability 0.4 and 1 occurs with probability 0.6. Using function “f” deduce a new function “f1” such that both 0 and 1 occurs with probability 0.5.

Solution:
Run the function f() two times. The possible outcomes are

00 with probability 0.4*0.4

11 with probability 0.6*0.6

01 with probability 0.4*0.6

10 with probability 0.6*0.4

Notice that the probabilities for 01 and 10 are the same. So create a new function f1() such that

f1():
   first = f()
   second = f()
   if (first == 0 and second == 0) or (first == 1 or second == 1):

      discard and run again
   else: 
      if first == 0 and second == 1: return 0
      else: return 1

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://www.geeksforgeeks.org/amazon-interview-set-64-campus-sde/

Find heavy ball

Problem:
9 identical balls. one ball is heavy. find the heavy ball with only 2 measurements ........ dead easy.

Solution:
this is super easy. split the ball into three groups with 3 balls each. pick two groups out to measure if they are equal weight. this way, you could find out which group contains the heavy ball. Then from this particular group, you could pick two to do one more measurement, this way, you find out the heavy ball

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=5204967652589568

Min number of slaves to find poison

Problem:
There is a king, who has got 1000 bottles of Rum with him, of which One bottle contains poison. And he has any number of slaves. He has got 1 hour to decide which bottle contains Poison, and any slave who even takes a sip of the poison, dies within an hour. How many least number of slaves does the king need to use, to make out which bottle contains poison.

Solution:
The answer is still 10. (2 power 10 = 1024) List numbers until 1000 in binary format vertically. Each 1 represents a slave and with the combination of slaves you can find the poisoned rum.
8 = 2 power 3. So three slaves

Eg:          1 2 3 4 5 6 7 8
Slave 1:     0 0 0 1 1 1 1 0
Slave 2:     0 1 1 0 0 1 1 0
Slave 3:     1 0 1 0 1 0 1 0

from the above combination you can find the rum bottle based on which slaves died

Complexity:

time - O(1)
space - O(log n)

Links and credits:
http://www.careercup.com/question?id=6345092675665920

Integer to Roman

Problem:
Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Solution:

public String intToRoman(int num) {
    int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    StringBuilder res = new StringBuilder();
    int i=0;
    while (num>0) {
        int times = num / nums[i];
        num -= nums[i]*times;
        for (; times>0; times--) {
            res.append(symbols[i]);
        }
        ++i;
    }
    return res.toString();
}

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/194/integer-to-roman

Palindrome Number

Problem:
Determine whether an integer is a palindrome. Do this without extra space.

Solution:
First, compare the first and last digit. If they are not the same, it must not be a palindrome. If they are the same, chop off one digit from both ends and continue until you have no digits left, which you conclude that it must be a palindrome.

Now, getting and chopping the last digit is easy. However, getting and chopping the first digit in a generic way requires some thought.

bool isPalindrome(int x) {
    if (x < 0) return false;
    int div = 1;
    while (x / div >= 10) {
        div *= 10;
    }
    while (x != 0) {
        int l = x / div;
        int r = x % 10;
        if (l != r) return false;
        x = (x % div) / 10;
        div /= 100;
    }
    return true;
}

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/181/palindrome-number

Generate integer from 1 to 7 with equal probability

Problem:
Given a function foo() that returns integers from 1 to 5 with equal probability, write a function that returns integers from 1 to 7 with equal probability using foo() only. Minimize the number of calls to foo() method. Also, use of any other library function is not allowed and no floating point arithmetic allowed.

Solution:
If we somehow generate integers from 1 to a-multiple-of-7 (like 7, 14, 21, …) with equal probability, we can use modulo division by 7 followed by adding 1 to get the numbers from 1 to 7 with equal probability.

Consider

5*foo() + foo() - 5

This expression generates numbers 1..25 with equal probability. Now, if we only accept numbers 1..21 and return i%7+1, then we get numbers 1..7 with equal probability. If the above expression returns a number >= 22, then ignore it and run the procedure once again until a proper number is returned.

int my_rand() // returns 1 to 7 with equal probability
{
    int i;
    i = 5*foo() + foo() - 5;
    if (i < 22)
        return i%7 + 1;
    return my_rand();
}

Complexity:

time - O(1), but really unpredictable, depends on the behavior of foo()
space - O(1)

Links and credits:
http://www.careercup.com/question?id=22457666
http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/
ARRAY: http://stackoverflow.com/questions/137783/expand-a-random-range-from-15-to-17

Count bits in an integer

Problem:
Count the no. of 1's in an integer.

Solution:

Solution #1: The most straightforward approach is to check each bit one by one. Here is the code,

int count1(int n)
{
    int count=0;

    while(n)
    {
        if(n&1)
            count++;

        n = n>>1;
    }

    return count;
}

Solution #2: The below code is an efficient version which improves the average time.
This code is faster because on each iteration it always clears the LSB of the number.

int count2(int n)
{
    int count=0;

    while(n)
    {
        count++;
        n = n&(n-1);
    }

    return count;
}

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://puddleofriddles.blogspot.ru/2012/03/count-bits-in-integer.html

Modify bits x...y in an integer

Problem:
given two integers and two bit positions. Set the first integer between the two bit positions to be that of the second integer.

Solution:
The trickiest part is to calculate the mask:

int replace_bits(int a, int b, int x, int y) 
{ 
    int mask = ((1 << (y - x + 1)) - 1) << x; 
    // Clear a and replace with that of b 
    return ((a & ~mask) | (b & mask)); 
}

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=13532675

Calculate ceiling (y / x) w/o using % (modulo)

Problem:
given y bytes and you can transfer only x bytes at once..give a mathematical expression having only + - / * which gives the number of iterations to copy y bytes. ( dont try giving modulo operator answers )

Solution:

ceiling(y / x) = (y + (x - 1)) / x

In order to prove correctness you need to check two case sets:
1. y % x == 0 => addition of x-1 doesn't affect the result, so it is y/x (which is ok)
2. y % x > 0 => addition of x-1 increments result with 1 (which is ok because we need another copy for the remaining y % x bytes).

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=14911702