Frequently Asked Questions - Part 1

1. Differentiate between Union and Structure

2. Differentiate between Primitive and Non-Primitive Data Structure

3. Differentiate between Linear and Non Linear Data Structure

4. Differentiate between getchar(); and putchar()

5. How to analyze time complexity of any program. Read about Recursive methods, back-successive methods and master theorem.

Time complexity is an abstract way to represent the running time of an algorithm in terms of the rate of growth and Big-O notations only. It is an approximate estimation of how much time an algorithm will take for a large value of input size. To analyze the time complexity of a program, we need to follow the following steps:

1. Identify the basic operations: Determine the operations that contribute most to the program's running time, such as comparisons, assignments, and arithmetic operations.
2. Determine the input size: Identify the input size (n) that affects the program's running time. It could be the number of elements in an array, the length of a string, or the size of a matrix.
3. Count the frequency of basic operations: Analyze the algorithm and count how many times each basic operation is performed in terms of the input size (n).
4. Express the total count as a function of the input size (T(n)): Combine the counts of each basic operation and express them as a function of the input size (n).
5. Find the highest order term: Identify the highest order term in T(n), as this term will dominate the growth of the function for large values of n.
6. Remove the constant factors: Simplify the highest order term by removing any constant factors, as they become less significant as n grows.
7. Express the time complexity using Big O notation: Represent the simplified highest order term using Big O notation (e.g., O(n), O(n^2), O(log n), etc.) to provide an upper bound on the program's running time.

6. Analyze the complexity of the following program:

a() {
  int i, j, k, n;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= i^2; j++) {
      for (k = 1; k <= n/2; k++) {
        printf("Hello");
      }
    }
  }
}

The answer is O(n^4). Lets us check how.

The input size affecting the program’s running time is n. The outer loop i runs n times. The middle loop j tuns i^2 times for each outer loop iteration. The inner loop k runs n/2 times for each iteration of the middle loop. By expressing the total count as a function of an input size (T(n)), we get T(n) = Σ [i^2 * (n/2)] for i = 1 to n. We the find the highest order term: T(n) = (n/2) * Σ [i^2] for i = 1 to n The sum of squares of the first n integers is given by the formula: Σ [i^2] = n * (n + 1) * (2n + 1) / 6 or it can be written as: T(n) = (n/2) * n * (n + 1) * (2n + 1) / 6 Removing the constant figures we get: T(n) = n^2 * (n + 1) * (2n + 1) / 12. Thus, as n grows large, the terms n^2, n, and 2n+1 dominate the growth of the function. And so, we get the time complexity of the given program is O(n^4), as the highest order term is n^2 * n * 2n, which is n^4.

Let's analyze the time complexity of the given code snippet:

1. The outer loop runs n times.
2. The middle loop runs i^2 times, where i is the current iteration of the outer loop. Since it is nested inside the outer loop, the number of iterations will be the sum of squares of all integers from 1 to n, which can be expressed as (n * (n + 1) * (2n + 1)) / 6.
3. The innermost loop runs n/2 times, and it is nested inside both the outer and middle loops.

To calculate the total time complexity, we multiply the number of iterations of each loop:

• Outer loop: n
• Middle loop: (n * (n + 1) * (2n + 1)) / 6
• Innermost loop: n/2

Total time complexity: n * (n * (n + 1) * (2n + 1)) / 6 * n/2

Now we simplify the expression and keep the highest order term:

• The highest degree term in the expression is n^4, as it is the term that dominates the growth of the function for large values of n.

Therefore, the time complexity of the given code snippet is O(n^4).

7. How to find the address of an element present in an array

Array is a collection of homogeneous data. To find the address of an element present in an array, you can use the following formula:
Address of element = Base address + (Index of element * Size of data type)
Here, the base address is the memory location of the first element in the array, the index of the element is its position in the array (starting from 0), and the size of the data type is the memory required for a single element in the array (in bytes).

8. Design an algorithm to find the greatest / largest number within the elements of the array.

For finding the largest number within the elements of the array, we can use the following algorithm:

1. Initialize a variable max and set its value to the first element of the array.
2. Iterate through the array from the second element to the last element.
3. For each element, compare it with the max value.
4. If the current element is greater than max, update the value of max to the current element.
5. After iterating through the array, the value of max will be the largest number in the array.

We can implement the above steps in the following manner:

#include <iostream>
using namespace std;

int main() {
int n, max;

cout << "Enter the number of elements in the array: " ; cin>> n;
  int arr[n];

  cout << "Enter the array elements: " ; 
  for(int i=0; i < n; i++) { 
    cin>> arr[i];
  }

  max = arr[0];
  for(int i = 1; i < n; i++) { 
    if(arr[i]> max) {
      max = arr[i];
    }
  }

  cout << "Largest number in the array: " << max << endl;
  return 0;
}

9. Using the continue statement WAP in C to read 15 integers from the user and print the sum of only the positive integer.

In C, we can write the program which follows the above requirements in the following manner:

#include <stdio.h>

int main() {
    int i, num, sum = 0;
    for (i = 0; i < 15; i++) {
        scanf("%d", &num);
        if (num < 0) {
            continue;
        }
        sum += num;
    }
    printf("Sum of positive integers: %d\n", sum);
    return 0;
}

And in C++ we can write the program which fulfills the above requirements in the following way:

#include <iostream>
using namespace std;

int main() {
    int num, sum = 0;
    for (int i = 0; i < 15; i++) {
        cin >> num;
        if (num < 0) {
            continue;
        }
        sum += num;
    }
    cout << "Sum of positive integers: " << sum << endl;
    return 0;
}

10. Differentiate between an AVL tree and explain the balance factor in an AVL tree.

The balance factor of a node in an AVL tree is the difference between the height of its left subtree and the height of its right subtree. Mathematically, it can be defined as:
Balance Factor = Height(Left Subtree) - Height(Right Subtree)
A node is considered balanced if its balance factor is -1, 0, or 1. If the balance factor of any node becomes less than -1 or greater than 1, the tree is considered unbalanced and needs to be rebalanced through rotations. These rotations can be single (left or right) or double (left-right or right-left) depending on the imbalance scenario.