Dynamic Programming In Data Structures - Study Mode
[#236] 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[] = "somestring", s2[] = "anotherthing"
int ans = edit_distance(s1, s2)
printf("%d",ans)
return 0
}
Correct Answer
(A) 6
[#237] What will be the output when the following code is executed? #include<stdio.h>
int fibo(int n)
{
if(n==0)
return 0
int i
int prevFib=0,curFib=1
for(i=1
i<=n-1
i++)
{
int nextFib = prevFib + curFib
prevFib = curFib
curFib = nextFib
}
return curFib
}
int main()
{
int r = fibo(10)
printf("%d",r)
return 0
}
Correct Answer
(B) 55
[#238] Consider the following dynamic programming implementation: #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 _____________
}
int main()
{
char s[] = "abcda"
int ans = min_ins(s)
printf("%d",ans)
return 0
} Which of the following lines should be added to complete the code?
Correct Answer
(D) len - arr[len][len]
[#239] What will be the value stored in arr[5] when the following code is executed? #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 = 10
ans = cat_number(n)
printf("%d
",ans)
return 0
}
Correct Answer
(B) 42
[#240] The recursive formula for Catalan number is given by Cn = ∑Ci*C(n-i). Consider the following dynamic programming implementation for Catalan numbers: #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--)
______________________
}
return arr[n-1]
}
int main()
{
int ans, n = 8
ans = cat_number(n)
printf("%d
",ans)
return 0
} Which of the following lines completes the above code?
Correct Answer
(C) arr[i] += arr[j] * arr[k].