Track4

Question 1

Write a recursive function to find floor(log2(n))

Answer 1

fun(int n){
if(n==1)
return 0;
else
return 1 + fun(n/2);
}

Question 2

Write a recursive method to print binary equivalent of a number

Answer 2

fun(int n){
if(n==0)
return;

 fun(n/2);
 print(n%2); }

Question 3

What is a tail recursive method and why do we prefer it over non-tail recursive methods?

Answer 3

A recursive method having recursive call as the last statement is called tail-recursive method. That is, there are no statements after the recursive call.
Tail recursive methods are faster than non-recursive ones.

Question 4

Write a tail recursive method to compute factorial of ‘n’

Answer 4

int fact(int n, int k){
if(n==0)
return k;

  return fact(n-1, n*k) }

Question 5

Write a tail-recursive method to compute the sum of first ‘n’ natural numbers

Answer 5

int getSum(int n, int sum){
if(n==0)
return sum;

 return getSum(n-1, n+sum);

}

invocation : getSum(n, 0)

Question 6

Write a recursive code to check if a given string is palindrome or not

Answer 6

boolean isPalindrome(String str, int start, int end){
if(start>=end)
return True;
if(str.charAt(start)!=str.charAt(end))
return False;
return isPalindrome(str, start+1, end-1);
}

Question 7

Given a rope of length = n, that can be cut with pieces of length a, b and c. Then find the max number of pieces that this rope can be cut.

Answer 7

m(n, a, b, c) = 0 ; if n=0
= -1 ; if res=-1 or n<0
= 1 + res ; otherwise

where, res = max{ m(n-a,…) , m(n-b, …), m(n-c, …)}

Time = O(3^n), space = O(n)

Question 8

Given a string “abc”, print it’s subsets like {“”, a, b, c, ab, bc, ac, abc}

Answer 8

printSS(str, temp){
if(str==””){
print(temp)
return;
}
printSS(str[1], temp)
printSS(str[1], temp + str[0])
}

Question 9

Explain the tower of hanoi problem. And how to solve it

Answer 9

toh(n, A, C, B){
if(n==1){
mov(n, A, C)
return
}
toh(n-1, A, B, C)
mov(n, A, C)
toh(n-1, B, C, A)
}

Question 10

Josephus Problem :
n people are standing in a circle and one of them has a gun. The person with the gun kills the k’th person counting himself as 1st. The gun is handed over to the person standing after the person killed and the process is repeated until there is only one survivor.
Considering the person with the gun as 0th position, find the position of the survivor (0 to n-1).

Answer 10

Two ways to solve this :-
Method 1 :
—————————-
jos(n,k,start){
if(n==1)
return start
killed = (start + k-1)%n
survivor = jos(n-1, k, killed%(n-1) )
if(survivor>=killed)
survivor = survivor + 1
return survivor
}
Here, in an iteration say 3rd person is killed, then 4th person would be considered as 3rd person in the next iteration, 5th would become 4th and so on. Thus there is a correction of 1 for every position starting 3. So, if the survivor returned by the next iteration is 3 or larger than 3 we must add 1 as a correction to it.

Here, we dont pass start.
jos(n, k)
So, each iteration places the gun in the hands of 0th person. So the last iteration will return 0 always as survivor. We must add correction to it.

In an iteration say person with position 2 was killed. So, the gun would have to be with person positioned 3. But it would instead be placed with position 0 here.
So in this case starting with the gunner positions are : 3 4 0 1
But they are instead considered : 0 1 2 3
Thus, the correction is to perform (survivor + k)%n
Correction is performed in each iteration.

Question 11

Subset sum Problem:
Given a set like [10, 5, 2, 3, 6] and sum like say 8. Find the count of subsets that when summed give 8.

Answer 11

Logic => At each element in the set, we are faced with two choices :- include the element and exclude the element.

subsetsum(arr, sum, start) = subsetsum(arr, sum, start-1) +
subsetsum(arr, sum-arr[start], start-1)
= 1 if (start<0 and sum=0)
= 0 if(start<0 and sum!=0)

Time = O(2^n)

Question 11

Subset sum Problem:
Given a set like [10, 5, 2, 3, 6] and sum like say 8. Find the count of subsets that when summed give 8.

Answer 11

Logic => At each element in the set, we are faced with two choices :- include the element and exclude the element.

subsetsum(arr, sum, start) = subsetsum(arr, sum, start-1) + subsetsum(arr, sum-arr[start], start-1)

Question 12

Given a string say “ABC”, print all the possible permutations. Like in this case, {ABC, ACB, BCA, BAC, CAB, CBA}

Answer 12

printPerm(str, index) {
if(index==len(str)){
print(str)
return
}

      for(i=index to i=len(str)){
               swap :: str[index],  str[i])
               printPerm(str, index+1)
                swap back :: str[index], str[i]
       } }

Time :: O(n^n), I think its O(n!)