Dynamic Programming In Data Structures - Study Mode
[#196] What is the value stored in arr[2][3] when the following code is executed? #include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a
return b
}
int lcs(char *str1, char *str2)
{
int i,j,len1,len2
len1 = strlen(str1)
len2 = strlen(str2)
int arr[len1 + 1][len2 + 1]
for(i = 0
i <= len1
i++)
arr[i][0] = 0
for(i = 0
i <= len2
i++)
arr[0][i] = 0
for(i = 1
i <= len1
i++)
{
for(j = 1
j <= len2
j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1]
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1])
}
}
return arr[len1][len2]
}
int main()
{
char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq"
int ans = lcs(str1,str2)
printf("%d",ans)
return 0
}
Correct Answer
(A) 1
[#197] What is the space complexity of the following dynamic programming implementation of the balanced partition problem? #include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j
for(i = 0
i < len
i++)
sm += arr[i]
if(sm % 2 != 0)
return 0
int ans[sm/2 + 1][len + 1]
for(i = 0
i <= len
i++)
ans[0][i] = 1
for(i = 1
i <= sm/2
i++)
ans[i][0] = 0
for(i = 1
i <= sm/2
i++)
{
for(j = 1
j <= len
j++)
{
ans[i][j] = ans[i][j-1]
if(i >= arr[j - 1])
ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1]
}
}
return ans[sm/2][len]
}
int main()
{
int arr[] = {3, 4, 5, 6, 7, 1}, len = 6
int ans = balanced_partition(arr,len)
if(ans == 0)
printf("false")
else
printf("true")
return 0
}
Correct Answer
(C) O(sum * n)
[#198] What is the output of the following program? #include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1]
int i,j,tmp_price,tmp_idx
max_val[0] = 0
for(i = 1
i <= len
i++)
{
int tmp_max = INT_MIN
// minimum value an integer can hold
for(j = 1
j <= i
j++)
{
tmp_idx = i - j
//subtract 1 because index of prices starts from 0
tmp_price = prices[j-1] + max_val[tmp_idx]
if(tmp_price > tmp_max)
tmp_max = tmp_price
}
max_val[i] = tmp_max
}
return max_val[len]
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5
int ans = rod_cut(prices, len_of_rod)
printf("%d",ans)
return 0
}
Correct Answer
(D) 12
[#199] What is the output of the following program? #include<stdio.h>
int fibo(int n)
{
if(n<=1)
return n
return fibo(n-1) + fibo(n-2)
}
int main()
{
int r = fibo(50000)
printf("%d",r)
return 0
}
Correct Answer
(D) Runtime error
[#200] Fill in the blank to complete the code. #include<stdio.h>
int main()
{
int coins[10]={1,3,4},lookup[100000]
int i,j,tmp,num_coins = 3,sum=100
lookup[0]=0
for(i = 1
i <= sum
i++)
{
int min_coins = i
for(j = 0
j < num_coins
j++)
{
tmp = i - coins[j]
if(tmp < 0)
continue
if(lookup[tmp] < min_coins)
______________
}
lookup[i] = min_coins + 1
}
printf("%d",lookup[sum])
return 0
}
Correct Answer
(B) min_coins = lookup[tmp]