Dynamic Programming In Data Structures - Study Mode
[#291] Consider the following code snippet: 1. int sum[len], idx
2. sum[0] = arr[0]
3. for(idx = 1
idx < len
idx++)
4. sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx])
5. int mx = sum[0]
6. for(idx = 0
idx < len
idx++)
7. if(sum[idx] > mx)
8. mx =sum[idx]
9. return mx
Which method is used by line 4 of the above code snippet?
Correct Answer
(D) Memoization
[#292] What is the value stored in arr[2][2] when the following code is executed? #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[] = "defg"
int ans = edit_distance(s1, s2)
printf("%d",ans)
return 0
}
Correct Answer
(B) 2
[#293] Consider the following naive method to find the maximum sub-array sum: #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
} Which line should be inserted to complete the above code?
Correct Answer
(D) cur_max = tmp_max
[#294] Consider the following code: #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] = _______________
}
}
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
} Which of the following lines should be inserted to complete the above code?
Correct Answer
(C) ans[i][j] || ans[i - arr[j - 1]][j - 1]
[#295] What is the output of the following code? #include<stdio.h>
int cat_number(int n)
{
int i,j,arr[n],k
arr[0] = 1
for(i = 1
i < n
i++)
{
arr[i] = 0
for(j = 0,k = i - 1
j < i
j++,k--)
arr[i] += arr[j] * arr[k]
}
return arr[n-1]
}
int main()
{
int ans, n = 8
ans = cat_number(n)
printf("%d
",ans)
return 0
}
Correct Answer
(C) 429