Given a stream of integers (flow read from disk or some other resource, like a sensor counting some events). How can we find the median of elements read so far?
It is an interesting online algorithm. Online, we mean the algorithm that can output result after any instance of input processing. For example, after reading i-elements we should be able to tell the median of i-elements read till now.
I read the question on Gulli blog, and came up with some solution. I have posted the algorithm on Geeksforgeeks.
http://www.geeksforgeeks.org/archives/14873
Again, it is just for my reference of link. Any comments, please post on Geeksforgeeks.
Showing posts with label Algorithms. Show all posts
Showing posts with label Algorithms. Show all posts
Saturday, October 29, 2011
Saturday, July 30, 2011
Decision Trees - Fake Coin
30-July-2011
I have pending post from few months. It is on application of decision trees to analyze algorithms.
I have pending post from few months. It is on application of decision trees to analyze algorithms.
The puzzle is given below,
"We are provided a two pan fair balance and N identically looking coins, out of which only one coin may be defective. How can we trace which coin, if any, is odd one, and also determine whether it is lighter or heavier in minimum number of trials in the worst case?"
Try to solve the puzzle on your own, and then read my systematic solution on the following link
"We are provided a two pan fair balance and N identically looking coins, out of which only one coin may be defective. How can we trace which coin, if any, is odd one, and also determine whether it is lighter or heavier in minimum number of trials in the worst case?"
Try to solve the puzzle on your own, and then read my systematic solution on the following link
There are other applications of decision trees, like analyzing comparison based sorting routines. We may think that comparison is cheap operation, however, in reality we deal with large objects than simple integers, where comparison is costly operation. We need decision trees to analyze lower bounds of comparison sorting.
There are other advantages of trees like solving game of Nim, probability problems, etc...
Again the link is for my reference. Any comments post on Geeksforgeeks.org site.
Saturday, May 7, 2011
Connecting Capacitances - Project Euler Problem#155
8 - May - 2011
Fun to code. The same applies to Inductors and Resistors. The series appears as 1, 3, 7, 15, 31, 63, 127, 255, ... which is one less than powers of 2. Ofcourse generating this series is quite easy. The emphasis is on the recursion tree, and dynamic programming.
I came across an interesting problem. Given N capacitors (or inductors, resistors) of same value say C (unit is Farad). How many difference capacitances can be derived from these N capacitors connected in series, parallel and series-parallel combination.
For example if N = 1, only one way it can be connected. If N = 2, they can be connected in two different ways of series and parallel. If N = 3, they can be connected in 7 different ways. That means we can derive 7 different capacitance values from given 3 capacitors of same value. These 7 combinations can be found pictorially on the Project Euler page.
Can we generalize it? Yes. Say the total possible capacitances are represented as S(n). If we observe, only the difference between S(n-1) and S(n-2) will participate using next capacitor. For example to calculate S(n) we need the difference DELTA = S(n-1) - S(n-2), and all combinations upto S(n-1). The new capacitor C(n) can be connected in series and parallel with every combination of DELTA..
With an example it will be clear. We know S(1) = 1, S(2) = 3 and S(3) = 7. To calculate S(4) we need DELTA = S(3) - S(2) = 4. We can connect the 4-th capacitor in series and parallel with these 4 combinations, overall it adds 4 * 2 = 8 more combination to the existing 7 combination upto S(3). So, clearly S(4) = 2 x DELTA + S(3) = 15. There is a recursive formula. It is evident from the recursion tree given below for S(5).
Solution can be generalized as
S(n) = 2 x (S(n-1) - S(n-2)) + S(n-1)
= 3 x S(n-1) - 2 x S(n-2)
Base case S(1) = 1, S(2) = 3 and S(3) = 7.
We can code above formula using recursion easily.
int totalPossibleCapacitances(int n)
{
static int S[] = {1, 3, 7};
if(n > 3)
// Non trival case
return 3*totalPossibleCapacitances(n-1) - 2*totalPossibleCapacitances(n-2)
else
// Trivial case
return S[n - 1];
}
Complexity: What will be the complexity? If we observe the recursion tree, the problems are overlapped. Similar to the Fibonacci series. The characteristic equation of generalized solution can be written as
x ^ 2 - 3*x + 2 = 0 whose roots are x1 = 1 and x2 = 2. The solution is in the form
S(n) = A(x1)^n + B(x2)^n where A and B are constants that depends on initial conditions. After substitution of S(2) and S(3) we get,
S(n) = 1.2 * (2)^n - 3 which is exponential.
So, the above function runs with exponential complexity. Can we do better? Yes, the well known technique "Dynamic Programming".
If we observe from S(4), every number is depending on past two numbers only. S(n) = 3*S(n-1) - 2*S(n-2), i.e. we need to store only the past two values to find next number. A three element array will be sufficient. Given below pseudo code,
int totalPossibleCapacitances(int n)
{
// For efficiency purpose
// static
int S[] = {1, 3, 7};
if(n > 3)
{
// Non trivial
int activeIndex = 0;
for(int i = 4; i <= n; i++)
{
S[activeIndex] = 3*S[ (activeIndex + 2) % 3 ] - 2*S[ (activeIndex + 1) % 3 ];
activeIndex++;
activeIndex %= 3;
}
if(activeIndex)
activeIndex--;
return S[activeIndex];
}
else
{
// Trivial
return (n > 0 ? S[n - 1] : -1);
}
}
Fun to code. The same applies to Inductors and Resistors. The series appears as 1, 3, 7, 15, 31, 63, 127, 255, ... which is one less than powers of 2. Ofcourse generating this series is quite easy. The emphasis is on the recursion tree, and dynamic programming.
Friday, April 8, 2011
An Interview Experience
8 April, 2011
I don't like to present in interview panels unless really required. Today I had to be in an interview panel. Good puzzle I recapped after long time.
Two players A and B playing a game (similar to game of Nim). Given a pile of N coins, the players need to pick coins from the pile. In each move a player can pick atleast 1 and utmost m coins. The player who makes the last move is the winner.
For example if A starts the game, he can pick 1, 2, 3, ... m coins from the pile. Then B can pick 1, 2, 3, .... m coins from the remaining pile. Next A, followed by B, so on...
In the process, the player who makes last move (picks all remaining coins <= m from the pile) is the winner.
Now, given N = 15, m = 3, and A starts the game with some 1 <= x <= m coins. How many different ways are there that A can win the game?
Hint: Use state space analysis method (i.e. trees).Saturday, October 9, 2010
Permuting the words of a string
10th October, 2010
Given a string, how can you permute all words of the string? The question was asked here.
Given below is the working code. Algorithmic steps can be understood from the comments.
// Prints all the words in the string array
void printTheArray(char *array[], int size)
{
static int count;
int index;
printf("%d ", count);
for(index = 0; index < size; index++)
{
printf("%s ", array[index]);
}
count++;
printf("\n");
}
// swpping integers is easy, swapping strings nothing but swapping their base
inline
void swapStringPointers (char *stringsVector[], int i, int j)
{
char *base;
base = stringsVector[i];
stringsVector[i] = stringsVector[j];
stringsVector[j] = base;
}
// Actual permutation algorithm (recursive)
inline
void permuteWords (char *stringsVector[], int vectorSize, int processedIndex)
{
int currentIndex;
if (processedIndex == vectorSize)
{
// print the vector
printTheArray(stringsVector, vectorSize);
}
else
{
for (currentIndex = processedIndex; currentIndex < vectorSize; currentIndex++)
{
// No need to swap the same element
if(currentIndex != processedIndex)
swapStringPointers (stringsVector, processedIndex, currentIndex);
// Recursively permute the smaller instances
permuteWords (stringsVector, vectorSize, processedIndex + 1);
// No need to swap the same element
if(currentIndex != processedIndex)
swapStringPointers (stringsVector, processedIndex, currentIndex);
}
}
}
int main ()
{
// Just add one more string if you want to test
char *strings[] = {"SARI", "GAMA", "PADA", "NISA"};
int size = sizeof(strings)/sizeof(strings[0]);
// Prints original array
printTheArray(strings, size);
printf("\n");
// Permutes all words in the string
permuteWords (strings, size, 0);
return 0;
}
Friday, September 17, 2010
Hexadecimal string to Decimal integer conversion
17, Sep, 2010.
Question:
Given a string that contains hexadecimal number, write a function htoi() that returns the equivalent integer.
Examples:
getValue("1011", 2); // Binary string to integer
getValue("12345", 10); // Decimal string to integer
getValue("ABCDE", 16); // Hexadecimal string to integer
Error handling is omitted.
Question:
Given a string that contains hexadecimal number, write a function htoi() that returns the equivalent integer.
// Here is one function
int getValue(char const* hexString, int const radix)
{
int loopIndex; // Loop iterator
int signFlag = 1; // Keeps track of sign
signed int retValue = 0; // Final value
int currentDigit; // Current digit under process
int len = strlen(hexString); // Lenght of string
// Check for sign
if(hexString[0] == '-')
{
// Advance the base
hexString++;
// Remove '-' from count
len--;
// Sing is -ve
signFlag = -1;
}
// Iterate from left to right
// Accumulate the weight of each digit upon occurance of next digit
for(loopIndex = 0; loopIndex < len; loopIndex++)
{
currentDigit = toupper(hexString[loopIndex]) - ASCII_ZERO;
// Is the digit between A through F?
if(currentDigit > 9)
{
// Adjust numerical value
currentDigit -= (ASCII_A - '9');
}
// Based on Horner's principle
retValue = retValue * radix + currentDigit;
}
// Flip the sign, if required
retValue *= signFlag;
// This is the final value
return retValue;
}Examples:
getValue("1011", 2); // Binary string to integer
getValue("12345", 10); // Decimal string to integer
getValue("ABCDE", 16); // Hexadecimal string to integer
Error handling is omitted.
1. Overflow and underflow (if string contains more than 10 characters on 32 bit machines, i.e. length = [32*log(2) + 1] digits in general, which is the characteristic).
2. Invalid String (containing unexpected characters).
3. String not terminated with NUL character.
4. String is NULL.
5. What if a kernel space buffer is passed as hex string?
6. Is it reentrant?
7. Who will be the consumers of the function, and possible ways of misusing it?
8. What changes are required if wide character buffer (Unicode) is passed (portability issue).
9. Any optimizations without compromising on the functionality.
Saturday, September 11, 2010
Find right-most set bit in an integer
September 11, 2010
I recently posted one the following solution. Question is, given an integer (other than 0) find right most set bit in that integer.
You can see the post in the following link
The solution is given below,
// Position of rightmost set bit
An order of log(X) algorithm. We can conclude from 2's complement form that "a number can be converted to 2’s complement form by complementing each bit from right most set bit". For example, -7 can be obtained in the following way (assuming 8 bit size)
7 = 00000111
-7 = 11111001
8 = 00001000
-8 = 11111000
5 = 00000101
-5 = 11111011
If we perform ANDing between x and -x we left with right most set bit. All this takes O(1) time. Now use binary search [ O(log(x)) ] to figure out which bit is set. Given below is code.
int getPosition(unsigned x)
{
// ASSUMPTION: x will not be zero
// left, right and mid position
int l = 0, r = 33, mid = 0;
// temp value
unsigned temp;
// Iterate till we find the bit position
while(l < r)
{
// ((r - l) >> 1) + l - Is more effective??
mid = (l + r) >> 1;
// Set the most possible significant bit
temp = (1 << (mid - 1));
if(temp == x)
{
break;
}
else if(temp < x)
{
// Bit is in the higher half
l = mid;
}
else
{
// Bit is in the lower half
r = mid;
}
}
// Return mid itself if bits
// are positioned from 1 to 32
return (mid-1);
}
int getRightMostSetBit(unsigned x)
{
// Return 0 if x is zero
int position = 0;
// Avoid multiple return statements
if(x != 0)
{
// Make the integer passes as least power of 2
// Call the position locator
position = getPosition(x & -(signed)x);
}
return position;
}
If you find any errors, please let me know.
Counting bits in an integer
September 11th, 2010
I have simple approach as it was mentioned in the bit reversal algorithm. We can add the adjacent bits in each one bit position, two bit positions, four bit positions, etc… until we reach the number of bits in integer. I am providing pseudo code,
1. Add bits in positions (0, 1), (2, 3) so on (30, 31)
2. Add bits in positions (01, 23), (45, 67) so on (28 29, 30 31)
3. Add bits in positions (0123, 4567).....
4. Add bits in positions (01234567, 8 9 10 11 12 13 14 15)
5. Add the bits in first half and second half of the integer.
The algorithm takes log(N) steps to count the bits in integer.
An example will clarify it more clearly
Let us take 0x12345678, the corresponding binary representation can be written easily (it has 13 set bits)
00010010001101000101011001111000
00 01 00 10 00 11 01 00 01 01 01 10 01 11 10 00
After step 1 we get
00 01 00 01 00 10 01 00 01 01 01 01 01 10 01 00
After step 2 we get
00 01 00 01 00 10 01 00 01 01 01 01 01 10 01 00
0001 0001 0010 0001 0010 0010 0011 0001
After step 3 we get
0001 0001 0010 0001 0010 0010 0011 0001
00000010 00000011 00000100 00000100
After step 4 we get
00000010 00000011 00000100 00000100
0000000000000101 0000000000001000
After step 5 we get
0000000000000101 0000000000001000
00000000000000000000000000001101 – (13) Which is required result
The algorithm can be implemented using shifts and addition operation. There are multiple algorithms out there to compute number of set bits in an integer. For few of such algorithms see the following link
Depending on context we can choose right algorithm.
Subscribe to:
Posts (Atom)