## 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.

## In binary search algorithm, after every search operation, the search gets reduced by ______?

In binary search algorithm, after every search operation, the search gets reduced by 1/4.

## Write an algorithm for inserting node at the beginning of the doubly-linked list, when list is not empty.

- Allocate memory for the new node.
- Assign a value to the data field of the new node.
- Make the next field of the new point to the first node in the list.
- Make the prev field of START point to the new node.
- Make the prev field of the new node point to NULL.
- Make START point to the new node.

## Write an algorithm for in order traversing of binary tree.

Algorithm:Inorder(root)

- If(root=NULL): Exit
- Inorder(left child of root)
- Visit(root)
- Inorder(right child of root)

## Write an algorithm to insert a node at the end of the list, when the list is not empty.

The algorithm for inserting a node at the end of the list as follows:

- Allocate memory for the new node.
- Assign value to the data field of the new node
- Make the next field of the new node point to successor of LAST.
- Make the next field of LAST point to new node.
- Make LAST point to the new node.

## Write an algorithm to convert a binary tree into heap.

The following algorithm to convert a binary tree into heap:

- Set i=(n-1)/2
- Set j=2i+1
- Let heap=False
- Compare the value at index j with the value of its sibling at index j+1:
- If A[j+1]>A[j]:
- j=j+1

- If A[j]>A[(j-1)/2]:
- If((n>j) or(heap=False)),repeat step 4,5, and 6
- Decrement i by 1
- If(i>=),repeat steps 2 through 8

Swap A[j] with A[(j-1)/2

j=2j+1

Else

heap=True

## What is average case performance of binary search?

The average case performance of binary search is O(log n).

## What do you mean by **linked list**?

Linked lists are flexible data structure that provide a convenient way to store data. In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

## Sort an Array with C++

{ 30, 50, 20, 10, 40 }THIS IS A SCHEMATIC SOLUTION

const int nSize = 5; int anArray[nSize] = { 30, 50, 20, 10, 40 }; void main() { // Step through each element of the array for (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++) { // nSmallestIndex is the index of the smallest element // we've encountered so far. int nSmallestIndex = nStartIndex; // Search through every element starting at nStartIndex+1 for ( int nCurrentIndex = nStartIndex + 1; nCurrentIndex < nSize; nCurrentIndex++ ) { // If the current element is smaller // than our previously found smallest if (anArray[nCurrentIndex] < anArray[nSmallestIndex]) // Store the index in nSmallestIndex { nSmallestIndex = nCurrentIndex; } } // Swap our start element with our smallest element swap(anArray[nStartIndex], anArray[nSmallestIndex]); } }

### Another Variation of the above question: Rewrite the selection sort code above to sort in descending order (largest numbers first).

Simply change:If (anArray[nCurrentIndex] < anArray[nSmallestIndex])to

if (anArray[nCurrentIndex] > anArray[nSmallestIndex])nSmallestIndex should probably be renamed nLargestIndex as well.

const int nSize = 5; int anArray[nSize] = { 30, 50, 20, 10, 40 }; void main() { // Step through each element of the array for (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++) { // nLargestIndex is the index of the smallest element // we've encountered so far. int nLargestIndex = nStartIndex; // Search through every element starting at nStartIndex+1 for ( int nCurrentIndex = nStartIndex + 1; nCurrentIndex < nSize; nCurrentIndex++ ) { // If the current element is smaller // than our previously found smallest if (anArray[nCurrentIndex] < anArray[nLargestIndex]) { // Store the index in nLargestIndex nLargestIndex = nCurrentIndex; } } // Swap our start element with our smallest element swap(anArray[nStartIndex], anArray[nLargestIndex]); } }

## Write an algorithm for selection sort.

- Repeat step 2 and 3 varying j from 0 to n-2 //Repeat for n-1 passes
- Find the index of the minimum value in arr[j] to arr[n-1]
- Set min_index=j
- Repeat step c varying i from j+1 to n-1
- If arr[i]<arr[min_index]: min_index = i

- swap arr[j] with arr[min_index]

## Write algorithm for binary search for a desired element.

The following algorithm is used for binary search:

- Accept the element to be searched
- Set lowerbound=0
- Set upperbound=n-1
- Set mid=(lowerbound+upperbound)/2
- If arr[mid]=desired element:
- Display "Found"
- Go to step 10

- If desired element<arr[mid]:
- Set upperbound=mid-1

- If desired element>arr[mid]:
- Set lowerbound=mid+1

- If lowerbound ≤upperbound:
- Go to step 4

- Display "Not Found"
- Exit

## 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.