int lps(char *seq, int i, int j) // i and j are first and last character
{
// If there is only 1 character
if (i == j)
return 1;
// If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;
// If the first and last characters match
if (seq[i] == seq[j])
return lps (seq, i+1, j-1) + 2;
// If the first and last characters do not match
return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}
Category Archives: Algorithms
Find the largest multiple of 3
1.Sort the array in increasing order.
2.Queue q0 stores the elements which on dividing by 3 gives remainder 0.
3.Queue q1 stores the elements which on dividing by 3 gives remainder 1.
4.Queue q2 stores the elements which on dividing by 3 gives remainder 2.
5.Find the sum of all the given digits.Let it be ‘s’.
6.If s is divisible by 3,goto step 9.
7.If s when divided by 3 gives remainder 1:
Remove one item from q1.
If q1 is empty,remove two items from q2.
If q2 contains less than two elements,number is not possible.
8.If s when divided by 3 gives remainder 2:
Remove one item from q2.
If q2 is empty,remove two items from q1.
If q1 contains less than two elements,number is not possible.
9.Empty all queues into an temporary array and sort it in decreasing order.
CODE
int findMaxMultupleOf3( int* arr, int size )
{
// Step 1: sort the array in non-decreasing order
qsort( arr, size, sizeof( int ), compareAsc );
// Create 3 queues to store numbers with remainder 0, 1 and 2 respectively
Queue* queue0 = createQueue( size );
Queue* queue1 = createQueue( size );
Queue* queue2 = createQueue( size );
// Step 2 and 3 get the sum of numbers and place them in corresponding queues
int i, sum;
for ( i = 0, sum = 0; i < size; ++i )
{
sum += arr[i];
if ( (arr[i] % 3) == 0 )
Enqueue( queue0, arr[i] );
else if ( (arr[i] % 3) == 1 )
Enqueue( queue1, arr[i] );
else
Enqueue( queue2, arr[i] );
}
// Step 4.2: The sum produces remainder 1
if ( (sum % 3) == 1 )
{
// either remove one item from queue1
if ( !isEmpty( queue1 ) )
Dequeue( queue1 );
// or remove two items from queue2
else
{
if ( !isEmpty( queue2 ) )
Dequeue( queue2 );
else
return 0;
if ( !isEmpty( queue2 ) )
Dequeue( queue2 );
else
return 0;
}
}
// Step 4.3: The sum produces remainder 2
else if ((sum % 3) == 2)
{
// either remove one item from queue2
if ( !isEmpty( queue2 ) )
Dequeue( queue2 );
// or remove two items from queue1
else
{
if ( !isEmpty( queue1 ) )
Dequeue( queue1 );
else
return 0;
if ( !isEmpty( queue1 ) )
Dequeue( queue1 );
else
return 0;
}
}
int aux[size], top = 0;
// Empty all the queues into an auxiliary array.
populateAux (aux, queue0, queue1, queue2, &top);
// sort the array in non-increasing order
qsort (aux, top, sizeof( int ), compareDesc);
// print the result
printArr (aux, top);
return 1;
}
Clone a linked list with next and random pointer
ALGO
The idea is to use Hashing. Below is algorithm.
1. Traverse the original linked list and make a copy in terms of data.
2. Make a hash map of key value pair with original linked list node and copied linked list node.
3. Traverse the original linked list again and using the hash map adjust the next and random reference of cloned linked list nodes.
CODE
public class Node {
private Node next;
private Node random;
private String data;
// getters and setters omitted for the sake of brevity
}
private Node deepCopy(Node original) {
Map<Node, Node> map = new HashMap<Node, Node>();
// We scan the original list and for each Node x we create a new
// Node y whose data is a copy of x's data, then we store the
// couple (x,y) in map using x as a key.
Node x = original;
while (x != null) {
Node y = new Node();
y.setData(new String(x.getData()));
y.setNext(null);
y.setRandom(null);
map.put(x, y);
x = x.getNext();
}
// We scan again the original list and
// we set the pointers buildings the new list
x = original;
while (x != null) {
// we get the node y corresponding to x from the map
Node y = map.get(x);
// let x' = x.next; y' = map.get(x') is the new node
// corresponding to x'; so we can set y.next = y'
y.setNext(map.get(x.getNext()));
// let x'' = x.random; y'' = map.get(x'') is the new
// node corresponding to x''; so we can set y.random = y''
y.setRandom(map.get(x.getRandom()));
x = x.getNext();
}
return map.get(original);
}
DFA based division
Example
Suppose we want to check whether a given number ‘num’ is divisible by 3 or not
- When we are at state 0 and read 0, we remain at state 0.
- When we are at state 0 and read 1, we move to state 1, The number so formed(1) in decimal gives remainder 1.
- When we are at state 1 and read 0, we move to state 2, The number so formed(10) in decimal gives remainder 2.
- When we are at state 1 and read 1, we move to state 0, The number so formed(11) in decimal gives remainder 0.
- When we are at state 2 and read 0, we move to state 1, The number so formed(100) in decimal gives remainder 1.
- When we are at state 2 and read 1, we remain at state 2, The number so formed(101) in decimal gives remainder 2.
The transition table looks like following:
state 0 1
_____________
0 0 1
1 2 0
2 1 2
Let us check whether 6 is divisible by 3?
Binary representation of 6 is 110
state = 0
1. state=0, we read 1, new state=1
2. state=1, we read 1, new state=0
3. state=0, we read 0, new state=0
Since the final state is 0, the number is divisible by 3.
Let us take another example number as 4
state=0
1. state=0, we read 1, new state=1
2. state=1, we read 0, new state=2
3. state=2, we read 0, new state=1
Since, the final state is not 0, the number is not divisible by 3. The remainder is 1.
Note that the final state gives the remainder.
Make a fair coin from a biased coin
Question
You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with 40% probability. Write a new function that returns 0 and 1 with 50% probability each. Your function should use only foo()
Answer
We call foo() two times. Both calls will return 0 with 60% probability. So the two pairs (0, 1) and (1, 0) will be generated with equal probability from two calls of foo().
(0, 1): The probability to get 0 followed by 1 from two calls of foo() = 0.6 * 0.4 = 0.24
(1, 0): The probability to get 1 followed by 0 from two calls of foo() = 0.4 * 0.6 = 0.24
So the two cases appear with equal probability. The idea is to return consider only the above two cases, return 0 in one case, return 1 in other case. For other cases [(0, 0) and (1, 1)], recur until you end up in any of the above two cases.
int my_fun()
{
int val1 = foo();
int val2 = foo();
if (val1 == 0 && val2 == 1)
return 0; // Will reach here with 0.24 probability
if (val1 == 1 && val2 == 0)
return 1; // // Will reach here with 0.24 probability
return my_fun(); // will reach here with (1 - 0.24 - 0.24) probability
}
Check divisibility by 7
A number of the form 10a + b is divisible by 7 if and only if a – 2b is divisible by 7
Example:
the number 371: 37 – (2×1) = 37 – 2 = 35; 3 – (2 × 5) = 3 – 10 = -7; thus, since -7 is divisible by 7, 371 is divisible by 7.
Solution
return isDivisibleBy7( num / 10 – 2 * ( num – num / 10 * 10 ) );
LOGIC
10.a + b after multiplying by 2, this becomes 20.a + 2.b and then 21.a - a + 2.b Eliminating the multiple of 21 gives - a + 2b and multiplying by -1 gives a - 2b
Equal Probability
Question
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.
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.
We can generate from 1 to 21 with equal probability using the following expression.
5*foo() + foo() -5
Let us see how above expression can be used.
1. For each value of first foo(), there can be 5 possible combinations for values of second foo(). So, there are total 25 combinations possible.
2. The range of values returned by the above equation is 1 to 25, each integer occurring exactly once.
3. If the value of the equation comes out to be less than 22, return modulo division by 7 followed by adding 1. Else, again call the method recursively. The probability of returning each integer thus becomes 1/7.
CODE
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();
}
count number of substrings that start and end with 1
For example, if the input string is “00100101”, then there are three substrings “1001”, “100101” and “101”.
Ans
a) Count the number of 1’s. Let the count of 1’s be m.
b) Return m(m-1)/2
How to check if an instance of 8 puzzle is solvable
It is not possible to solve an instance of 8 puzzle if number of inversions is odd in the input state.
What is inversion?
A pair of tiles form an inversion if the the values on tiles are in reverse order of their appearance in goal state. For example, the following instance of 8 puzzle has two inversions, (8, 6) and (8, 7).
1 2 3 4 _ 5 8 6 7
CODE
int getInvCount(int arr[])
{
int inv_count = 0;
for (int i = 0; i < 9 - 1; i++)
for (int j = i+1; j < 9; j++)
// Value 0 is used for empty space
if (arr[j] && arr[i] && arr[i] > arr[j])
inv_count++;
return inv_count;
}
bool isSolvable(int puzzle[3][3])
{
// Count inversions in given 8 puzzle
int invCount = getInvCount((int *)puzzle);
// return true if inversion count is even.
return (invCount%2 == 0);
}
minimal sum of two integers that are made of the digits contained in the array
Given the array of digits (0 is also allowed), what is the minimal sum of two integers that are made of the digits contained in the array.
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207
ANSWER
Sort the array. The largest numbers should be in the least significant positions, so build up your two integers by alternating from the two arrays.
E.g. 1 3 5 7 8 9 => 1 and 3, then 15 and 37, then 158 and 379. 0 is a special case, if not allowed to use that as a leading digit then have to use it as the second digit.
Try adding two numbers, you would find all that matters is the order of magnitude of a digit and not which of the two numbers that a digit belongs. (e.g. 178+29 = 128+79 = 179+28 = 129+78)
Learn By Coding 