Table of contents
1.
Introduction
2.
Questions
3.
Frequently asked questions
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Miscellaneous Gate PYQs

Author Shreya Deep
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Time complexity and bit-wise operations are the two main concepts one needs to learn when programming. Time complexity is the measure of the time taken by the processor to run a piece of code, and bit-wise operations are the operations done on the bits of a number. 

Questions

1. What is the output of the following code snippet for arr[] = {9, 12, 2, 11, 2, 2, 10, 9, 12, 10, 9, 11, 2}?
int fun(int arr[], int n)
{
   int x = arr[0];
   for (int i = 1; i < n; i++)
       x = x ^ arr[I];
   return x;

}

A. 10
B. 8
C. 7
D. 9

Solution: (D). The above code is taking the XOR of all the elements of the array arr. Thus, the answer will be 9.
 

2. What is the following expression doing? 
    x = (x<<1) + x + (x>>1)
A. Multiplying an integer with 5
B. Multiplying an integer with 2
C. Multiplying an integer with 3.5
D. Multiplying an integer with 0.5

Solution: (C). If the integer is 4, it becomes 15. If it’s 5, it gives 17. Thus, you can check for any integer, you’ll know that the expression multiplies it by 3.5

 

3. What is the following expression doing?
x = x & (x-1)
A. Turns off the rightmost set bit
B. Turns off the leftmost set bit
C. Turns all bits equal to 0
D. Turns all bits equal to 1

Solution: (A). After checking for any integer, we can conclude this.

 

4. The time complexity of Bellman-Ford single-source shortest path algorithm for a complete graph of n vertices is?
A. O(n^2)
B. O((n^2)*logn)
C. O(n^3)
D. O((n^3)*logn)

Solution: (C). 
 

5. The number of comparisons made in the worst case to search an element in a linked list is?
A. n/2
B. logn
C. n
D. logn - 1

Solution: (C). In the worst case, we might need to check all the elements one by one. Thus, the complexity can be O(n).

 

6. If we need to concatenate two linked lists in O(1) time, which of the following lists should be used?
A. Singly linked list
B. Doubly Linked List
C. Circular doubly linked list
D. Array implementation of list

Solution: (C). Circular doubly linked list will not require any traversal for concatenation.

 

7. Place the following time complexities in increasing order of value.
F1 = n^2, F2 = n^(3/2), F3 = n*(log2n), F4 = n^(log2n)
A. F3, F2, F1, F4
B. F3, F2, F4, F1
C. F2, F3, F1, F4
D. F2, F3, F4, F1

Solution: (B). is the correct order because F3<F2<F4<F1
 

8. What is the time complexity of the euclidean GCD method?
A. O(n)
B. O(nlog2n)
C. O(log2n)
D. O(n^2)

Solution: (C). The euclidean GCD method makes log2n comparisons. Thus, the time complexity is O(log2n).

 

9. What is the time complexity of the following code:
int f(n){
  if(n==1){
     return 1;
   }
return f(n-1)+f(n-1);
}
A. O(n)
B. O(logn)
C. O(n^2)
D. O(2^n)

Solution: (D). There will be 2^n calls made. Thus, the time complexity is O(2^n).

 

10. ∑O(n) where, k is varying from 1<=k<=n, where O(n) stands for order n is:
A. O(n)
B. O(n^2)
C. O(k^3)
D. O(3*(n^2))

Solution: (B). n time order n will be O(n*n) = O(n^2). 

Read More - Time Complexity of Sorting Algorithms

Frequently asked questions

  1. What is a Time Complexity?
    Time complexity is a computer science concept that quantifies the amount of time it takes a set of code or algorithms to process or run in relation to the amount of input. To put it another way, the time complexity measures how long it takes a program to process a given input.
     
  2. What does it imply to say that an algorithm X is asymptotically more efficient than another method Y? 
    We consider the algorithm's growth in terms of input size in asymptotic analysis. When an algorithm X takes less time than Y for all input sizes n greater than a number n0 where n0 > 0, it is said to be asymptotically better than Y. 
     
  3. The worst-case running times of algorithms A and B are O(n) and O(log n), respectively, then. Is it true that algorithm B always outruns algorithm A?
    The Big-O notation allows for an asymptotic comparison of algorithm execution times. Algorithm A may, for example, be faster than algorithm B for n < n0.
     
  4. How to find the binary representation of a number?
    A number can be converted into its binary form by continuously dividing it by 2 and adding the remainder to the answer until it equals 0.
     
  5. Can we use the left shift and right shift for negative numbers?
    Negative numbers should not be handled using the left and right shift operators. In C and C++, if the second operand is a negative number, the result is undefined behavior.
     
  6. How can we quickly check if a number is even or odd using bitwise operators?
    We can use the & operator to quickly check if a number is odd or even. For a number n, if (n & 1) yields 0, the number is even; else number is odd.

Conclusion

We discussed some of the GATE previous years asked problems on time complexity and bit operations here in this article.

Problems related to graphs are asked during various coding contests as well as placements tests.

Check out this problem - XOR Queries On Tree

To practice and learn more about such topics, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and an overview of interview experiences of various product-based companies.

Happy Coding!

Live masterclass