InterviewSolution
Saved Bookmarks
InterviewSolution
This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
In the following C function, let n >= m.int gcd(n,m){if (n%m ==0) return m;n = n%m;return gcd(m, n);}How many recursive calls are made by this function?(A) (logn)(B) (n)(C) (loglogn)(D) (sqrt(n))(A) A(B) B(C) C(D) D |
| Answer» | |
| 2. |
Consider the following functions: f(n) = 2^n g(n) = n! h(n) = n^logn Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?(A) f(n) = O(g(n)); g(n) = O(h(n))(B) f(n) = (g(n)); g(n) = O(h(n))(C) g(n) = O(f(n)); h(n) = O(f(n))(D) h(n) = O(f(n)); g(n) = (f(n))(A) A(B) B(C) C(D) D |
| Answer» None | |
| 3. |
What is the time complexity of Floyd–Warshall algorithm to calculate all pair shortest path in a graph with n vertices?(A) O(n^2logn)(B) Theta(n^2logn)(C) Theta(n^4)(D) Theta(n^3) |
| Answer» | |
| 4. |
What does it mean when we say that an algorithm X is asymptotically more efficient than Y?(A) X will be a better choice for all inputs(B) X will be a better choice for all inputs except possibly small inputs(C) X will be a better choice for all inputs except possibly large inputs(D) Y will be a better choice for small inputs |
| Answer» | |
| 5. |
In a competition, four different functions are observed. All the functions use a single for loop and within the for loop, same set of statements are executed. Consider the following for loops:A) for(i = 0; i < n; i++)B) for(i = 0; i < n; i += 2)C) for(i = 1; i < n; i *= 2)D) for(i = n; i > -1; i /= 2)If n is the size of input(positive), which function is most efficient(if the task to be performed is not an issue)?(A) A(B) B(C) C(D) D |
| Answer» | |
| 6. |
What is the time complexity of the below function?void fun(int n, int arr[]){int i = 0, j = 0;for(; i < n; ++i)while(j < n && arr[i] < arr[j])j++;}(A) O(n)(B) O(n^2)(C) O(nlogn)(D) O(n(logn)^2) |
| Answer» None | |
| 7. |
Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2…Dmint n, rev;rev = 0;while (n > 0){rev = rev*10 + n%10;n = n/10;}The loop invariant condition at the end of the ith iteration is: (GATE CS 2004)(A) n = D1D2….Dm-i and rev = DmDm-1…Dm-i+1(B) n = Dm-i+1…Dm-1Dm and rev = Dm-1….D2D1(C) n != rev(D) n = D1D2….Dm and rev = DmDm-1…D2D1 |
| Answer» | |
| 8. |
Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4? f1(n) = 2^n f2(n) = n^(3/2) f3(n) = nLogn f4(n) = n^(Logn)(A) f3, f2, f4, f1(B) f3, f2, f1, f4(C) f2, f3, f1, f4(D) f2, f3, f4, f1 |
| Answer» None | |
| 9. |
What is time complexity of fun()?int fun(int n){int count = 0;for (int i = n; i > 0; i /= 2)for (int j = 0; j < i; j++)count += 1;return count;}(A) O(n^2)(B) O(nLogn)(C) O(n)(D) O(nLognLogn) |
| Answer» | |
| 10. |
Which of the following is not O(n^2)?(A) (15^10) * n + 12099(B) n^1.98(C) n^3 / (sqrt(n))(D) (2^20) * n |
| Answer» | |
| 11. |
Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE? (GATE CS 2012)(A) (B) (C) (D) (A) A(B) B(C) C(D) D |
| Answer» | |
| 12. |
What is the time complexity of fun()?int fun(int n){int count = 0;for (int i = 0; i < n; i++)for (int j = i; j > 0; j--)count = count + 1;return count;}(A) Theta (n)(B) Theta (n^2)(C) Theta (n*Logn)(D) Theta (nLognLogn) |
| Answer» | |
| 13. |
The following statement is valid.log(n!) = (n log n).(A) True(B) False |
| Answer» | |
| 14. |
The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is. (GATE CS 2012)(A) T(n) = 2T(n – 2) + 2(B) T(n) = 2T(n – 1) + n(C) T(n) = 2T(n/2) + 1(D) T(n) = 2T(n – 1) + 1 |
| Answer» None | |
| 15. |
Consider the following two functions. What are time complexities of the functions?int fun1(int n){if (n <= 1) return n;return 2*fun1(n-1);}int fun2(int n){if (n <= 1) return n;return fun2(n-1) + fun2(n-1);}(A) O(2^n) for both fun1() and fun2()(B) O(n) for fun1() and O(2^n) for fun2()(C) O(2^n) for fun1() and O(n) for fun2()(D) O(n) for both fun1() and fun2() |
| Answer» | |
| 16. |
Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. which of the following statements is true? (GATE CS 2000)a) t (n) is 0 (1)b) n < t (n) < nc) n log 2 n < t (n) < d) t (n) = (A) a(B) b(C) c(D) d |
| Answer» | |
| 17. |
Consider the following function int unknown(int n) { int i, j, k = 0; for (i = n/2; i <= n; i++) for (j = 2; j <= n; j = j * 2) k = k + n/2; return k; }What is the return value of the function? (GATE CS 2013)(A) (B) (C) (D) (A) A(B) B(C) C(D) D |
| Answer» | |