Dynamic Programming In Data Structures - Study Mode
[#201] What is the output of the following code? #include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1]
int dice, face, sm
for(dice = 0
dice <= num_of_dice
dice++)
for(sm = 0
sm <= S
sm++)
arr[dice][sm] = 0
for(sm = 1
sm <= S
sm++)
arr[1][sm] = 1
for(dice = 2
dice <= num_of_dice
dice++)
{
for(sm = 1
sm <= S
sm++)
{
for(face = 1
face <= num_of_faces && face < sm
face++)
arr[dice][sm] += arr[dice - 1][sm - face]
}
}
return arr[num_of_dice][S]
}
int main()
{
int num_of_dice = 4, num_of_faces = 6, sum = 3
int ans = get_ways(num_of_dice, num_of_faces, sum)
printf("%d",ans)
return 0
}
Correct Answer
(A) 0
[#202] Complete the following code for Kadane's algorithm: #include<stdio.h>
int max_num(int a, int b)
{
if(a > b)
return a
return b
}
int kadane_algo(int *arr, int len)
{
int ans, sum, idx
ans =0
sum =0
for(idx =0
idx < len
idx++)
{
sum = max_num(0,sum + arr[idx])
ans = ___________
}
return ans
}
int main()
{
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3},len=7
int ans = kadane_algo(arr,len)
printf("%d",ans)
return 0
}
Correct Answer
(D) max_num(sum,ans)
[#203] What is the output of the following program? #include<stdio.h>
#include<limits.h>
int min_jump(int *arr, int len)
{
int j, idx, jumps[len]
jumps[len - 1] = 0
for(idx = len - 2
idx >= 0
idx--)
{
int tmp_min = INT_MAX
for(j = 1
j <= arr[idx] && idx + j < len
j++)
{
if(jumps[idx + j] + 1 < tmp_min)
tmp_min = jumps[idx + j] + 1
}
jumps[idx] = tmp_min
}
return jumps[0]
}
int main()
{
int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9
int ans = min_jump(arr,len)
printf("%d
",ans)
return 0
}
Correct Answer
(B) 8
[#204] What is the value stored in LIS[5] after the following program is executed? #include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
int i, j, tmp_max
int LIS[len]
// array to store the lengths of the longest increasing subsequence
LIS[0]=1
for(i = 1
i < len
i++)
{
tmp_max = 0
for(j = 0
j < i
j++)
{
if(arr[j] < arr[i])
{
if(LIS[j] > tmp_max)
tmp_max = LIS[j]
}
}
LIS[i] = tmp_max + 1
}
int max = LIS[0]
for(i = 0
i < len
i++)
if(LIS[i] > max)
max = LIS[i]
return max
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9
int ans = longest_inc_sub(arr, len)
printf("%d",ans)
return 0
}
Correct Answer
(C) 4
[#205] What is the output of the following code? #include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1]
int dice, face, sm
for(dice = 0
dice <= num_of_dice
dice++)
for(sm = 0
sm <= S
sm++)
arr[dice][sm] = 0
for(sm = 1
sm <= S
sm++)
arr[1][sm] = 1
for(dice = 2
dice <= num_of_dice
dice++)
{
for(sm = 1
sm <= S
sm++)
{
for(face = 1
face <= num_of_faces && face < sm
face++)
arr[dice][sm] += arr[dice - 1][sm - face]
}
}
return arr[num_of_dice][S]
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6
int ans = get_ways(num_of_dice, num_of_faces, sum)
printf("%d",ans)
return 0
}
Correct Answer
(A) 10