Dynamic Programming In Data Structures - Study Mode
[#286] What is the time complexity of the following dynamic programming algorithm used to find the maximum sub-array sum? #include<stdio.h>
int max_num(int a,int b)
{
if(a> b)
return a
return b
}
int maximum_subarray_sum(int *arr, int len)
{
int sum[len], idx
sum[0] = arr[0]
for(idx = 1
idx < len
idx++)
sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx])
int mx = sum[0]
for(idx = 0
idx < len
idx++)
if(sum[idx] > mx)
mx =sum[idx]
return mx
}
int main()
{
int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9
int ans = maximum_subarray_sum(arr, len)
printf("%d",ans)
return 0
}
Correct Answer
(A) O(n)
[#287] What is the output of the following code? #include<stdio.h>
#include<string.h>
int max(int a, int b)
{
if(a > b)
return a
return b
}
int min_ins(char *s)
{
int len = strlen(s), i, j
int arr[len + 1][len + 1]
char rev[len + 1]
strcpy(rev, s)
strrev(rev)
for(i = 0
i <= len
i++)
arr[i][0] = 0
for(i = 0
i <= len
i++)
arr[0][i] = 0
for(i = 1
i <= len
i++)
{
for(j = 1
j <= len
j++)
{
if(s[i - 1] == rev[j - 1])
arr[i][j] = arr[i - 1][j - 1] + 1
else
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1])
}
}
return len - arr[len][len]
}
int main()
{
char s[] = "efgfe"
int ans = min_ins(s)
printf("%d",ans)
return 0
}
Correct Answer
(A) 0
[#288] What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps? #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) O(n)
[#289] What is the output of the following code? #include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a
return b
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min
len1 = strlen(s1)
len2 = strlen(s2)
int arr[len1 + 1][len2 + 1]
for(i = 0
i <= len1
i++)
arr[i][0] = i
for(i = 0
i <= len2
i++)
arr[0][i] = i
for(i = 1
i <= len1
i++)
{
for(j = 1
j <= len2
j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1]
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1
}
arr[i][j] = min
}
}
return arr[len1][len2]
}
int main()
{
char s1[] = "abcd", s2[] = "dcba"
int ans = edit_distance(s1, s2)
printf("%d",ans)
return 0
}
Correct Answer
(D) 4
[#290] Which of the following lines should be added to complete the "if(op[k] == '&')" part of the following code? int count_bool_parenthesization(char *sym, char *op)
{
int str_len = strlen(sym)
int True[str_len][str_len],False[str_len][str_len]
int row,col,length,l
for(row = 0, col = 0
row < str_len
row++,col++)
{
if(sym[row] == 'T')
{
True[row][col] = 1
False[row][col] = 0
}
else
{
True[row][col] = 0
False[row][col] = 1
}
}
for(length = 1
length < str_len
length++)
{
for(row = 0, col = length
col < str_len
col++, row++)
{
True[row][col] = 0
False[row][col] = 0
for(l = 0
l < length
l++)
{
int pos = row + l
int t_row_pos = True[row][pos] + False[row][pos]
int t_pos_col = True[pos+1][col] + False[pos+1][col]
if(op[pos] == '|')
{
_______________
}
if(op[pos] == '&')
{
_______________
}
if(op[pos] == '^')
{
_______________
}
}
}
}
return True[0][str_len-1]
}
Correct Answer
(B) True[row][col] += True[row][pos] * True[pos+1][col]
False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col]