GATE questions

 DS Data Structures

Q1. Consider the following array of integers:

A = [2, 3, 7, 10, 12, 15, 18]
What is the time complexity of the best algorithm to determine whether there exists a pair of elements whose sum is 22?

A. O(n²)
B. O(n log n)
C. O(n)
D. O(log n)

✅ Answer: C
Use two-pointer technique since array is sorted → O(n)

✅ C++ Code:

#include <iostream>
using namespace std;

bool hasPairWithSum(int arr[], int n, int target) {
    int i = 0;         // Start pointer
    int j = n - 1;     // End pointer

    while (i < j) {
        int sum = arr[i] + arr[j];

        if (sum == target) {
            cout << "Pair found: " << arr[i] << " + " << arr[j] << " = " << target << endl;
            return true;
        } else if (sum < target) {
            i++;  // Move to higher value
        } else {
            j--;  // Move to lower value
        }
    }

    cout << "No pair found with sum " << target << endl;
    return false;
}

int main() {
    int A[] = {2, 3, 7, 10, 12, 15, 18};
    int n = sizeof(A) / sizeof(A[0]);
    int target = 22;

    hasPairWithSum(A, n, target);

    return 0;
}

---

🧪 Output:

Pair found: 7 + 15 = 22

---

🕒 Time Complexity:

• O(n) — each element is visited at most once.

• Space Complexity: O(1)

 

📚 2. Stacks

Q2. What is the output of the following postfix expression?

Postfix: 6 2 3 + - 3 8 2 / + *

A. 15
B. 24
C. 18
D. 36

✅ Answer: B
Expression: 6 - (2 + 3) = 1, and 3 + (8 / 2) = 7 → 1 * 7 = 7

Wait! Let's redo that properly:

Step-by-step:
6 2 3 + → 6 5 → 6 - 5 = 1  
3 8 2 / → 3 4 → 3 + 4 = 7  
1 * 7 = 7

Oops! There’s an error in the key.

✅ Correct Answer: 7

✅ Tree Traversal Dry Run – Sample

Given Tree:

     A
    / \
   B   C
  / \   \
 D   E   F

Traversals:

• Inorder: D B E A C F

• Preorder: A B D E C F

• Postorder: D E B F C A

• Level Order (BFS): A B C D E F