Related InterviewSolutions

• 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
• 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
• 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)
• 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
• 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
• 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)
• 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
• 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
• 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)
• 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