Dynamic Programming In Data Structures - Study Mode
[#206] What is the space complexity of the following dynamic programming implementation of the matrix chain problem? #include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n]
int i,k,row,col,len
for(i=1
i<n
i++)
arr[i][i] = 0
for(len = 2
len < n
len++)
{
for(row = 1
row <= n - len + 1
row++)
{
col = row + len - 1
arr[row][col] = INT_MAX
for(k = row
k <= col - 1
k++)
{
int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col]
if(tmp < arr[row][col])
arr[row][col] = tmp
}
}
}
return arr[1][n - 1]
}
int main()
{
int mat[6] = {20,5,30,10,40}
int ans = mat_chain_multiplication(mat,5)
printf("%d",ans)
return 0
}
Correct Answer
(C) O(n 2 )
[#207] What is the output of the following program? #include<stdio.h>
#include<limits.h>
int min_jumps(int *arr, int strt, int end)
{
int idx
if(strt == end)
return 0
if(arr[strt] == 0) // jump cannot be made
return INT_MAX
int min = INT_MAX
for(idx = 1
idx <= arr[strt] && strt + idx <= end
idx++)
{
int jumps = min_jumps(arr, strt + idx, end) + 1
if(jumps < min)
min = jumps
}
return min
}
int main()
{
int arr[] ={1, 2, 3, 4, 5, 4, 3, 2, 1},len = 9
int ans = min_jumps(arr, 0, len-1)
printf("%d
",ans)
return 0
}
Correct Answer
(A) 4
[#208] What is the output of the following implementation of 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 = max_num(sum,ans)
}
return ans
}
int main()
{
int arr[] = {2, 3, -3, -1, 2, 1, 5, -3}, len = 8
int ans = kadane_algo(arr,len)
printf("%d",ans)
return 0
}
Correct Answer
(D) 9
[#209] What is the time complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements? #include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9
int cur_max, tmp_max, strt_idx, sub_arr_idx
cur_max = arr[0]
for(strt_idx = 0
strt_idx < len
strt_idx++)
{
tmp_max=0
for(sub_arr_idx = strt_idx
sub_arr_idx < len
sub_arr_idx++)
{
tmp_max +=arr[sub_arr_idx]
if(tmp_max > cur_max)
_____________
}
}
printf("%d",cur_max)
return 0
}
Correct Answer
(A) O(n 2 )
[#210] What is the output of the following code? #include<stdio.h>
int get_min(int a, int b)
{
if(a<b)
return a
return b
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
int t1[n], t2[n], i
t1[0] = entry[0] + spent[0][0]
t2[0] = entry[1] + spent[1][0]
for(i = 1
i < n
i++)
{
t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i])
t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i])
}
return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1])
}
int main()
{
int time_to_reach[][3] = {{6, 1, 5},
{2, 4, 7}}
int time_spent[][4] = {{6, 5, 4, 7},
{5, 10, 2, 6}}
int entry_time[2] = {5, 6}
int exit_time[2] = {8, 9}
int num_of_stations = 4
int ans = minimum_time_required(time_to_reach, time_spent,
entry_time, exit_time, num_of_stations)
printf("%d",ans)
return 0
}
Correct Answer
(C) 34