Problem-1: You have an array consisting of 2n+2 elements, n elements in it are married, i.e they occur twice in the array, however there are two element which only appears once in the array. You need to find those numbers assuming that all are positive numbers in O(N) time and O(1) space complexity.
Assume -
Array elements (array): 1 2 3 4 5 6 7 8 0 10 11 12 13 0 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Now we are having 30 numbers. Each number is repeated exactly two times except a (9) and b( 14).
1. Get the XOR of each value in array res = array[0]
for i = 1 to N-1: res = res ^ array[i]
2. Take leftmost set bit of this "res" (call it Y)
3. Mask is Y, now XOR all elements which are greater or equal than mask. result would be missing number "b" (14).
4. Now XOR this "b" with your earlier "res". result would be missing number "a" (9).
Problem-2: Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr "C" routine?
(eg given s1 = ABCD and s2 = CDAB, return true)
(given s1 = ABCD, and s2 = ACBD , return false)
strstr(strcat(s1,s1), s2);
so if the string is ABCD, the concatenation will make it ABCDABCD and hence any rotation will fall within the concatenated string
Problem-3: Implement a reader writer lock. (multiple readers, one writer). Once done, also implement upgrade and downgrade of the locks.
void ReaderThread::run() {
...
semaphore++;
read_file();
semaphore--;
...
}
void WriterThread::run() {
...
mutex.lock();
for (int i = 0; i < MaxReaders; ++i)
semaphore++;
mutex.unlock();
write_file();
semaphore -= MaxReaders;
...
}
Problem-4: Sizeof operator
(unsigned long)(char *)((type *)0+1)-(unsigned long)(char *)(type *)0
Problem-5: Arrange the following pattern -
a0 a1 a2 a3 a4 a5 a6 bo b1 b2 b3 b4 b5 b6 as
a0 b0 a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 with minimum time and space complexity.
This problem can be solved using recursion. We will be traversing whole pattern from 0-(n-1) recursively in order to push all the data in program stack. and while stack unwinding we will arrange data in the desired pattern. Following is C++ implementation of the given problem -
const int size = 12;
int len = size;
string str[size] = {
"a0", "a1", "a2", "a3", "a4", "a5", "b0", "b1", "b2", "b3", "b4", "b5"
};
void move(string a, string b, int ip,int jp) {
if(jp >= len-1) {
str[--len] = b;
str[--len] = a;
return;
}
ip++;
jp++;
move(str[ip], str[jp], ip, jp);
if (len > 0) {
str[--len] = b;
str[--len] = a;
}
return;
}
int main () {
move("","",-1,(size/2)-1);
cout << "\n Output Array: ";
for (int index = 0; index < size; index++) {
cout << str[index] << " ";
}
return 0;
}
Problem-6: Give a sorting algorithm that sorts 3 (distinct) numbers using 3 comparisons in the worst case?
void max (int a, int b, int c) {
if (a < b)
if (b < c)
cout << "sorted from small to large:" << a <<" "<< b <<" "<< c;
else
if (a < c)
cout << "sorted from small to large:" << a <<" "<< c <<" "<< b;
else
cout << "sorted from small to large:" << c <<" "<< a <<" "<< b;
else
if( c < b)
cout << "sorted from small to large:" << c <<" "<< b <<" "<< a;
else
if (c < a)
cout << "sorted from small to large:" << b <<" "<< c <<" "<< a;
else
cout << "sorted from small to large:" << b <<" "<< a <<" "<< c;
}
Problem-7: Write atoi and itoa function with all test cases.
char* itoa(int x) {
int i = x < 0 ? 3 : 2;
int t = abs(x);
while (t = t / 10) ++i;
char* s = new char[i];
s[--i] = '\0';
t = abs(x);
while (i) s[--i] = '0' + (t % 10), t = t / 10;
if (x < 0) s[0] = '-';
return s;
}
int atoi(const string& v) {
int sign = 1;
int i = 0;
if(v[0] == '-')
sign = -1;
string::const_iterator it = v.begin();
while (it != v.end()) {
if(*it == '-') {
it++;
continue;
}
i = (i << 3) + (i << 1) + (*it-'0');
it++;
}
return i*sign;
}
Problem-8: fibonacci
int fibo(int nth,int num1, int num2) {
if(n==1) return num1;
if(n==2) return num2;
return fibo(nth-1,num2,num1+num2)
}
One more drawback with the recursive approach apart from the drawback of using the stack is that, here we do a lot of rework in calculating the values for calling the functions. For e.g: while calculating f(5), we calculate values for f(4) and f(3) and while calculating the value of f(4), we again calculate f(3). Thus we calculate the same value again which is nothing but waste of resources. This is actually a problem of dynamic programming.
int FindnthFibonacciNumber(int n) {
int f1 = 0; int f2 = 1; int sum = 0;
if (n == 1)
return 0;
else if (n == 2)
return 1;
else {
int k = 2;
while (k < n) {
sum = f1 + f2;
f1 = f2;
f2 = sum;
k++;
}
return sum;
}
}
Fn = ![\frac{1}{\sqrt{5} } *[\frac{1+\sqrt{5} }{2} ]^{n} - \frac{1}{\sqrt{5} } *[\frac{1-\sqrt{5} }{2} ]^{n}](https://lh6.googleusercontent.com/QWws_9cfa1Jiv-SvQ_7iLng_fvj2dZL-OPUvWynSxeDJkx0KaDIyuvTZVDU0ojDb8krFJDAK_URw_V5NSME2Iagwnu7URgFUblJs8mQwjShUBiJxEYEbnJ-zZ-LB-1G0Na43W_Y)
Problem-9: Find number of zeros in n! ?
num_zeros = floor(n/5) + floor(n/5^2) + floor(n/5^3) ...
The logic is straightforward. There will be as many zeros as there are no of 5s in the numbers, as 5 * 2 = 10 and num(5) < num (2). Note that these 5s also include the multiples of 10. So we don't need extra logic for them.
int zeros = n/5; // round down to nearest integer
while(zeros < 0) {
zeros += zeros/5;
}
Problem-10: Implement Division
Approach - 1
int getQuotient(int numerator, int denom) {
if (numerator < denom) {
return 0;
} else {
return 1 + getQuotient(numerator - denom, denom);
}
}
The algorithm is perfect but for the fact you need to call the function getQuotient instead of divide in the last line of code. I would say recursion would be a overkill for such small operation... Maybe we can just implement the iterative version of the code as it avoids recursion overhead and is also as intuitive as the recursive version
Approach - 2
public int getQuotient(int dividend,divisor) {
int count = 0;
if(dividend < divisor)
return 0;
else if(divisor==0)
return error;
else {
while(dividend >= divisor) {
dividend-=divisor;
count++;
}
}
return count;
}
Problem-11: Implement MemMove and MemCopy
memmove() offers guaranteed behavior if the source and destination arguments overlap. memcpy() makes no such guarantee, and may therefore be more efficient to implement. It's always safer to use memmove().
void *memmove(void *dest, const void *src, size_t count);
void * mymemmove(void *to, const void *from, size_t size) {
unsigned char *p1;
const unsigned char *p2;
p1 = (unsigned char *) to;
p2 = (const unsigned char *) from;
p2 = p2 + size;
// Check if there is an overlap or not.
while (p2 != from && --p2 != to);
if (p2 != from) {
// Overlap detected!
p2 = (const unsigned char *) from;
p2 = p2 + size;
p1 = p1 + size;
while (size-- != 0) *--p1 = *--p2;
} else {
// No overlap OR they overlap as CASE 2 above.
// memcopy() would have done this directly.
while (size-- != 0) *p1++ = *p2++;
}
return to;
}
Problem-12: Determine machine’s endianness.
"Little Endian" means that the low-order byte of the number is stored in memory at the lowest address, and the high-order byte at the highest address. (The little end comes first.)
Example: Byte3 Byte2 Byte1 Byte0
will be arranged in memory as follows:
Base Address+0 Byte0
Base Address+1 Byte1
Base Address+2 Byte2
Base Address+3 Byte3
Intel processors (those used in PC's) use "Little Endian" byte order.
"Big Endian" means that the high-order byte of the number is stored in memory at the lowest address, and the low-order byte at the highest address. (The big end comes first.) Our LongInt, would then be stored as:
Base Address+0 Byte3
Base Address+1 Byte2
Base Address+2 Byte1
Base Address+3 Byte0
Problem-13: Find square root of an integer.
Using Binary search method -
Sq_root(n) {
count=0;
for(int i=1;sum<=n;i+=2) {
sum+=i;
count++;
}
return (count);
}
Using Newton’s Method -
// Fn+1 = Fn - Fn/fn -> 1/2(fn+V/fn)
public static double sqrt(final double V, final double tolerance) {
if(V <= tolerance) return V;
double fn = V/2;
final Function<Double, Double> Fn = (Double fx) -> {return (fx + (V/fx))/2;};
double fn1 = 0;
do {
fn1 = Fn.apply(fn);
if(Math.abs(fn1-fn) <= tolerance) break;
fn = fn1;
} while(fn > tolerance);
return fn1;
}
// call
sqrt(25.0, Double.POSITIVE_INFINITY)
Problem-14: find angle between clock’s hands
A general approach to such problems is to consider the rate of change of the angle in degrees per minute. The hour hand of a normal 12-hour analogue clock turns 360 degrees in 12 hours. This is equivalent to 360 degrees in 720 minutes or 0.5 degrees per minute. The minute hand turns 360 degrees in 60 minutes or 6 degrees per minute.
Equation for the degrees on the hour hand -
(0.5 degrees per minute on the hour hand) * (the time on the hour hand * 60 minutes per hour) + (0.5 degrees per minute on the minute hand) * (the time on the minute hand)
Equation for the degrees on the minute hand -
(6 degrees per minute on the minute hand) * (the time on the minute hand)
The angle between the hands can also be found using the formula -
angle = cos-1(cos(5.5*x))
where x=the number of minutes past noon. This will always give an angle between 0 and 180 degrees.
Problem-15: Given three points of a triangle and one arbitrary point, determine whether that point lies inside, on or outside the triangle.
int isInside(Triangle, point);
/return 1 if inside, -1 if outside, 0 if on the triangle
If P is the point to be tested, and A,B,C are the vertices, find angles APC, APB and BPC. If the sum of angles is equal to 360, the point is inside. Else, not.
Problem-16: How do you compute the number of digit after dot (.) in floating point number.
e.g. if given 3.554 output=3
for 43.000 output=0
double no =3.44;
int count =0;
while (!(n-(int)n>-0.0000001 && n-(int)n<0.0000001)) {
{
count++;
no=no*10;
}
printf("%d",count);
There are some numbers that can not be indicated by float type. for example, there is no 73.487 in float type, the number indicated by float in c is "73.486999999999995" to approximate it.
In the IEEE 754 Specifications, a 32 bit float is divided as 24+7+1 bits. The 7 bits indicate the mantissa.
Lets say ur input number = 10.23456 once you are at 10234.56 and multiply with 10, the next number comes as 102345.5999999998 instead 102345.6 so the loop will go on, never completes and that is the behavior of double and float. Best way to do is convert to string and do it.
Problem-17: Returns gcd of x and y
Approach -1
int gcd (int x, int y) {
int g;
if (x < 0)
x = -x;
if (y < 0)
y = -y;
if (x + y == 0)
ERROR;
g = y;
while (x > 0) {
g = x;
x = y % x;
y = g;
}
return g;
}
Approach -2
int gcd (x, y) {/*Note : X > Y*/
if(y == 0) return x;
if(x < y) return 0;
gcd(y, x%y);
}
Problem-18: (x pow y) mod N
unsigned long qe2(unsigned long x, unsigned long y, unsigned long n){
unsigned long s,t,u;
int i;
s = 1; t = x; u = y;
while(u) {
if(u&1) s = (s* t)%n;
u>>=1;
t = (t* t)%n;
}
return s;
}
recursive algorithm:
unsigned long fast_exp(unsigned long x, unsigned long y, unsigned long N) {
unsigned long tmp;
if(y==1) return(x % N);
if ((y&1)==0) {
tmp = fast_exp(x,y/2,N);
return ((tmp* tmp)%N);
}
else {
tmp = fast_exp(x,(y-1)/2,N);
tmp = (tmp* tmp)%N;
tmp = (tmp* x)%N;
return (tmp);
}
}
Problem-19: Hash Table is recommended over Binary Search Tree
- When Data is in ascending/descending order
- Insertion/Deletion are not frequently required.
- Sorted sequence is not required.
- Searching is a prevalent operation.
- When data are comparatively less. When Data is more, Hashing might require more extra location to avoid Collision.
Problem-20: Sorting order
Sort
|
Avg
|
Best
|
Worst
|
Space
|
Remarks
|
Bubble sort
|
O(n2)
|
O(n2)
|
O(n2)
|
Constant
|
Always use a modified bubble sort
|
Modified Bubble sort
|
O(n2)
|
O(n)
|
O(n2)
|
Constant
|
Stops after reaching a sorted array
|
Selection Sort
|
O(n2)
|
O(n2)
|
O(n2)
|
Constant
|
Even a perfectly sorted input requires scanning the entire array
|
Insertion Sort
|
O(n2)
|
O(n)
|
O(n2)
|
Constant
|
In the best case (already sorted), every insert requires constant time
|
Heap Sort
|
O(n.log.n)
|
O(n.log.n)
|
O(n.log.n)
|
Constant
|
By using input array as storage for the heap, it is possible to achieve constant space
|
Merge Sort
|
O(n.log.n)
|
O(n.log.n)
|
O(n.log.n)
|
Depends
|
On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
|
Quick sort
|
O(n.log.n)
|
O(n2)
|
Constant
|
constant
|
Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.
|
Problem-21: Give an algorithm to find all valid permutation of parentheses for given n for eg for n=3
{}{}{} {{{}}} {{}}{} {}{{}}
void print ( string str , int open , int closed , int n )
{
if ( closed > open ) return ;
if ( closed > n || open > n ) return ;
if ( str.size() == 2*n ) print str ;
fun ( str + '(' , open+1 , closed , n ) ;
fun ( str + ')' , open , closed+1 , n ) ;
}
Problem-36: A common problem for compilers and text editors is determining whether the parentheses in a string are balanced and properly nested. For example, the string ((())())() contains properly nested pairs of parentheses, which the strings )()( and ()) do not. Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. For full credit, identify the position of the first offending parenthesis if the string is not properly nested and balanced.
bool parenthesis_validation(const string& seq) {
string::const_iterator it(seq.begin());
int valid = 0;
while (it != seq.end() && valid >= 0) {
if(*it == '(') {valid++;}
else if(*it == ')'){valid--;}
else {;}
it++;
}
return valid == 0;
}
Problem-22: Permutation of a string.
public static List<String> permutation(final String msg) {
List<String> permutations = new ArrayList<String>();
permutation("", msg, permutations);
return permutations;
}
private static void permutation(final String prefix, final String msg, final List<String> permutations) {
if(msg == null) return;
if(msg.length() == 1) permutations.add(prefix+msg);
for(int index=0; index < msg.length(); ++index) {
permutation(prefix+msg.charAt(index), msg.substring(0, index)+msg.substring(index+1), permutations);
}
}
Problem-23: Find Lexicographical rank of a string
Assume it has all distinct characters.
Total number of permutations = n! (n is length of string)
Start from first character and traverse till end. find how many characters are ranked before this, suppose this is x, now we know there are x * (n-1)! permutations are ranked above this. Repeat the procedure for every character in string.
int n = strlen(str);
int rank = 0;
for (i = 0; i < n-1; i++) {
int x=0;
for (j = i+1; j<n ; j++) {
if (str[i] > str[j]) x++;
}
rank = rank + x*((n-i-1)!)
}
return rank;
Problem-24: Find next lexicographically sorted next Permutation of a string.
Example : next_permutaion(1234) => 1243
consider the seq sorted and try to find out next big
public static String next_permutation(String message) {
if(message == null || message.length() <= 1) return message;
int i = message.length()-1;
while(true) {
int j = i--;
if(message.charAt(i) < message.charAt(j)) {
int k = message.length()-1;
while(message.charAt(i) >= message.charAt(k)) --k;
// Swap(i, k)
// reverse(j, end)
final StringBuilder permutation = new StringBuilder(message);
char tmp = permutation.charAt(i);
permutation.setCharAt(i, permutation.charAt(k));
permutation.setCharAt(k, tmp);
return permutation.substring(0, j+1)+
new StringBuilder(permutation.substring(j, message.length())).reverse().toString();
}
if(i <= 0) return new StringBuilder(message).reverse().toString();
}
}
Problem-25: There exists 2D char array.. we need to find out whether a given string("microsoft") exists in the given matrix. the string can be vertical or horizontal..but NOT diagonal. it can also be in this form..(like the snake in the cell games )
m . . o t . .
. i r . f . .
. c . . . . .
bool find (string [n] = 'microsoft', maze[P * Q] = array, int pStr, int i, int j) {
if (pStr > n)
return FOUND
if (i*j > P*Q )
return NOT_FOUND
while (I*J < P*Q) {
if(maze[i, j] == string [pStr]) {
pStr++;
find (string, maze, pStr, i+1 , j);
find (string, maze, pStr, i , j + 1);
} else {
if(i == P && j < Q) {
i = 0;
j++
} else if( i < P && j < Q) {
i++;
}
}
}
Problem-26: Convert a string to uppercase
void ToUpper(char * S) {
while (*S!=0) {
*S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S;
S++;
}
}
Problem-27: Remove duplicate elements in a string- microsoft in O(n) and without using extra memory.
1. Save occurrence of a particular character using 32 bits of an integer I
2. Now take two pointers for array say p1, p2
3. p1 = p2 = str[0]
4. Read string using pointer p1
check if (int)*p1 bit is set in I
a) if Yes
p1++
b) if No
set (int)*p1 bit in integer I using bitwise operator
p1++;
p2++
5. *(p2++) = '\0'
Problem-28: Find upper bound element of given element in the sorted sequence.
upper_bound : first element which compares greater than value
public static int upper_bound(int [] A, int val) {
int pos = 0;
int dist = A.length;
while(dist > 0) {
int step = dist/2;
int lo = pos + step;
if(A[lo] <= val) {
pos = ++lo;
dist -=(step+1);
} else {
dist = step;
}
}
return pos;
}
Problem-29: Find lower bound element of given element in the sorted sequence.
lower_bound : first element which does not compare less than value
public static int lower_bound(int [] A, int val) {
int pos = 0;
int dist = A.length;
while(dist > 0) {
int step = dist/2;
int lo = pos + step;
if(A[lo] < val) {
pos = ++lo;
dist -= (step+1);
} else {
dist = step;
}
}
return pos;
}
Problem-30: Find equal range of given element in the sorted sequence.
equal_range : returns pair of indices which holds values equivalent to Val
public static pair equal_range(int [] A, int val) {
return Pair.make_pair(lower_bound(A, val), upper_bound(A, val));
}
Problem-31 You are given an array containing both positive and negative integers and required to find the subarray with the largest sum.
int maxSum = 0;
int thisSum = 0;
int i=0;
int j=0;
int seqStart = 0, seqEnd = N-1;
while (j < N) {
thisSum =thisSum + a[j];
if( thisSum > maxSum ) {
maxSum = thisSum;
seqStart = i;
seqEnd = j;
} else if( thisSum < 0 ) {
i = j + 1;
thisSum = 0;
}
j=j+1;
}
printf ("%d->%d\n", seqStart, seqEnd);
Problem-32: Given a string and print the words which have the same exact letters. Space is the only separator.
Example- abc bbe bca derwe eeb => abc bca
abc bbe abcd derwe eeb => Nothing
Approach-1
1) Associate a Prime number with each letter.
2) Hash by product of the word letter.
3) Maintain a list of words for each key
4) Iterate and print all lists having more than one word
But this won’t work if word is very long since it will cause overflow.
Approach-2
Build trie for every word after sorting it lexicographically, while inserting just query if it is already in trie.
Problem-33: Find Longest common substring (LCS).
Using Dynamic Programming -
public static String longestCommonSubstringDP(final String first, final String second) {
if(first == null || second == null || first.isEmpty() || second.isEmpty()) return "";
final Integer [][] pos = new Integer [first.length()+1][second.length()+1];
for(final Integer [] row : pos) Arrays.fill(row, 0);
int max = 0;
String lcs = "";
for(int i=0; i < first.length();++i) {
for (int j = 0; j < second.length(); j++) {
if(first.charAt(i) == second.charAt(j)) {
if(i == 0 || j == 0) pos[i][j] = 1;
else pos[i][j] = 1+pos[i-1][j-1];
if( pos[i][j] > max) {
max = pos[i][j];
lcs = first.substring(i-max+1, i+1);
}}}
}
System.out.println("max len of lcs="+max);
return lcs;
}
Using Suffix Tree - This problem can be solved by using Suffix tree data structure. Build suffix tree for string first and second. The common substrings can be identified by any node in this tree that has first and second string children from the same position. Identify all such nodes and return the string having maximum length.
Problem-34: Find Longest palindrome in given string.
This is same problem as finding longest common substring, Identify longest common substring in given string and its reverse.
public static String longestPalindromDP(final String message) {
return longestCommonSubstringDP(message, new StringBuilder(message).reverse().toString());
}
Problem-35: Find smallest palindrome number bigger than given number.
Problem-36: Given a dictionary of unknown language and characters. Find out order between characters.
Example : Dictionary = ab, bcd, ce, de
Order = a, b, c, d, e
Use Map and linked list to maintain the alphabets order, make first character as node in list and match two consecutive words to decide the next alphabet order, do for all words in dict.
Problem-37: “Word break problem” . Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.
Example :
Dictionary : i, like, sam, sung, samsung, mobile, ice, cream, icecream, man, go, mango.
Input: ilikesamsung
Output : I like samsung
Build trie with each word in dictionary.
Iterate over prefixes of input string
if it is word in trie
store this word
recurse the whole for rest of suffix
else go for next prefix.
send all the stored words separated with space.
Problem-38: Find minimum snippet of words of given paragraph containing all given keywords.
scan all keywords from paragraph and record its positions -
k1 = {a, b, c, d} // sorted
k2 = {a2, b2, c2}
k3 = {a3, b3}
Let the 1st column to be min window, now move smallest index to right and check for window length , repeat and find minimum.
Problem-40: Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false.
Problem-41: Find pythagorean triplets in a given array.
Using Euclid Formula -
For All E A, such that E is even
Get prime factorization of E/2 => P and Q
Look for A and B in array, such that
A = P2+Q2
B = P2-Q2
Problem-42: In a matrix containing zeros and ones, find biggest submatrix containing only ones.
This problem is also called finding biggest island. This can be solved using flood fill algorithm, an eight way recursion algorithm.
public static int BiggestIsland(Integer [][] earth) {
if(earth.length == 0) return 0;
int maxsoFar = 0;
for(int r=0; r < earth.length;++r) {
for(int c=0; c < earth[earth.length-1].length;++c) {
if(earth[r][c] == 1) {
int max = BiggestIsland(earth, r, c , 0);
if(max > maxsoFar) maxsoFar = max;
}
}
}
return maxsoFar;
}
public static int BiggestIsland(Integer [][] earth, int r, int c, int area) {
if(earth[r][c] == 0) return area;
area += earth[r][c];
earth[r][c] = 0;
if(r > 0)
area = BiggestIsland(earth, r-1, c, area);
if(r < earth.length-1)
area = BiggestIsland(earth, r+1, c, area);
if(r > 0 && c > 0)
area = BiggestIsland(earth, r-1, c-1, area);
if(r < earth.length-1 && c < earth[earth.length-1].length-1)
area = BiggestIsland(earth, r+1, c+1, area);
if(r > 0 && c < earth[earth.length-1].length-1)
area = BiggestIsland(earth, r-1, c+1, area);
if(r < earth.length-1 && c > 0)
area = BiggestIsland(earth, r+1, c-1, area);
if(c > 0)
area = BiggestIsland(earth, r, c-1, area);
if(c < earth[earth.length-1].length-1)
area = BiggestIsland(earth, r, c+1, area);
return area;
}
Problem-43: Given a gold mine of n*m dimension. Each field in this mine contains an integer which is amount of gold in tons. Initially miner is in first column but could be at any row i. He can move only (right ->, right up /, right down \). Find out maximum amount of gold he can collect and path followed by him.
Driver program
public static String goldMiner(final Integer [][] mine) {
String path = "";
Integer [][] memo = new Integer [mine.length][mine[mine.length-1].length];
for(Integer[] row : memo) Arrays.fill(row, -1);
for(int k=0; k < mine.length; ++k)
memo[k][mine[mine.length-1].length-1] = mine[k][mine[mine.length-1].length-1];
for(int r = 0; r < mine.length; ++r) {
memo[r][0] = goldMiner(mine, r, 0, memo);
}
// construct path
for(int c = 0; c < mine[mine.length-1].length; ++c) {
int maxSofar = 0;
for(int r = 0; r < mine.length; ++r) {
if(maxSofar < memo[r][c]) maxSofar = memo[r][c];
}
path += maxSofar+" ";
}
return path;
}
Memoization (top down approach)
private static int goldMinerMem(final Integer[][] mine, int r, int c, Integer [][] memo) {
if(r >= mine.length || r < 0 || c < 0 || c>=mine[mine.length-1].length)return 0;
if(memo[r][c] != -1){
return memo[r][c];
}
memo[r][c] = mine[r][c]+Math.max(goldMine(mine, r, c+1, memo),
Math.max(goldMine(mine, r-1, c+1, memo),
goldMine(mine, r+1, c+1, memo)));
return memo[r][c];
}
Dynamic Programming (bottom up)
private static void goldMinerDP(Integer[][] mine, Integer[][] DP) {
for(int c = mine[mine.length-1].length-2; c >= 0; --c) {
for(int r = 0; r < mine.length; ++r) {
int rightUp = (r == 0 ? 0 : DP[r-1][c+1]);
int right = DP[r][c+1];
int rightDown = (r == mine.length-1 ? 0 : DP[r+1][c+1]);
DP[r][c] = mine[r][c]+Math.max(rightUp, Math.max(right,rightDown));
}
}
}
Problem-45: Find out longest increasing subsequence in a given array.
public static int longestIncreasingSubSeq(Integer [] seq) {
Integer [] lis = new Integer [seq.length];
Arrays.fill(lis, 1);
for(int i=1; i < seq.length; ++i) {
for(int j=0; j < i; ++j) {
if(seq[i] > seq[j] && lis[i] <= lis[j]) lis[i] = lis[j]+1;
}
}
return Collections.max(Arrays.asList(lis));
}
Problem-46: Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
Coin Denomination problem: This is classic dynamic problem also known as knapsack problem.
public static int coinDenomination(final int [] coins, int sum) {
Integer [] DP = new Integer [sum+1];
Arrays.fill(DP, Integer.MAX_VALUE);
DP[0] = 0;
for(int i=1; i <=sum; ++i) {
for(int j=0; j< coins.length; ++j) {
if(coins[j] <= i && 1+DP[i-coins[j]] < DP[i]) DP[i] = 1+DP[i-coins[j]];
}
}
return DP[sum];
}
Problem-47: Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.
Balanced Partitioning
public static boolean isSubsetSum(int [] A, int n, int sum) {
if(sum == 0) return true;
if(n <= 0 && sum != 0) return false;
if(A[n] > sum) isSubsetSum(A, n-1, sum)
//1 . including current element
// 2. excluding current element
return isSubsetSum(A, n-1, sum -A[n]) || isSubsetSum(A, n-1, sum)
}
Problem-48: Sort a given stack, using another stack.
private static Stack<Integer> sort(final Stack<Integer> stack) {
if(stack == null || stack.size() < 2) return stack;
Stack<Integer> another = new Stack<Integer>();
another.push(stack.pop());
final Integer marker = null;
while(!stack.isEmpty()) {
if(stack.peek() >= another.peek()) {
another.push(stack.pop());
} else {
int element = stack.pop();
stack.push(marker);
while(!another.isEmpty() && another.peek() > element)
stack.push(another.pop());
another.push(element);
while(stack.peek() != marker) another.push(stack.pop());
stack.pop(); // marker
}
}
return another;
}
public static Object [] sort(final Integer [] arr) {
Stack<Integer> stack = new Stack<Integer>();
for(int ele : arr) stack.push(ele);
return sort(stack).toArray();
}
Problem-49: There is continuous incoming stream of integer numbers. At any point of time find its median.
Running Median: Take MaxHeap and MinHeap. For the first two elements add smaller one to the MaxHeap on the left, and bigger one to the MinHeap on the right. Then process stream data one by one -
Step 1: Add next item to one of the heaps if next item is smaller than MaxHeap root add it to MaxHeap, else add it to MinHeap
Step 2: Balance the heaps (after this step heaps will be either balanced or one of them will contain 1 more item) if number of elements in one of the heaps is greater than the other by more than 1, remove the root element from the one containing more elements and add to the other one
Then at any given time we can calculate median like this:
If the heaps contain equal elements; median = (root of MaxHeap + root of MinHeap)/2 Else median = root of the heap with more elements