## Interview and Exam Questions and Answers

This set contains a list of commonly asked questions. They are short interview questions aimed at freshers interview, campus placement drives, and also for job interviews. You can use these to have a quick grasp and brush-up of your fundamentals. These questions can be viewed on a mobile phone also because this website is built on responsive web design.

## What is worst case space complexity of bubble sort algorithm?

O(1) auxiliary.

## What is worst case efficiency of linear search?

The best case efficiency of linear search is *O(n)*.

## Write code in java for selection sort algorithm

public void selectionSort(int[] arr) { int i, j, minIndex, tmp; int n = arr.length; for (i = 0; i < n - 1; i++) { minIndex = i; for (j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } if (minIndex != i) { tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } } } }

## What is the best case efficiency of binary search?

The best case efficiency of binary search is O(1).

## What is the complexity of the bubble sort algorithm?

The complexity is O(n^{2}). The time required to execute the bubble sort algorithm is proportional to (n^{2}), where n is the number of input items.

## What is the mathematical definition of selection sort?

We define selection sort mathematically:

Let L be a non-empty set and such that f(L) = L' where:- L' is a permutation of L,
- for all and
- s is the smallest element of L, and
- L
_{s}is the set of elements of L without one instance of the smallest element of L.

## Which are the two principle criteria for selecting a hash function?

Two principle criteria for selecting a hash function are:

- It should be easy and quick to compute.
- It should achieve a uniform distribution of keys in address space.

## How can a binary tree be represented as a *array*?

Consider the binary tree with the nodes labeled from 0 to 6,as shown in the following figure.

In the preceding binary tree, the node labeled x will be stored at index x in the array. Consider the array representation of preceding binary tree, as shown in the following figure.

For any node with index i, n-1>i>0,the following holds true:

- Parent of i is at index(i-1)/2
- Left child of i is at index 2i+1. If 2i+1>n-1 there is no left child.
- Right child of i is at index 2i+2. If 2i+2>n-1 there is no right child

## Do bubble sort and selection sort have quadratic order of growth?

Yes, bubble sort and selection sort have quadratic order of growth.

## List some techniques that are used to design a hash function?

There are various techniques that can be used to design the hash function:

- Truncation Method
- Modular Method
- Mid Square Method
- Folding Method

## My C/C++ Videos on Youtube

Here is the complete playlist for video lectures and tutorials for the absolute beginners. The language has been kept simple so that anybody can easily understand them. I have avoided complex jargon in these videos.