Subjective Interview Questions on Linear Search Set 1

Interview questions for beginners on linear search. Use them for preparing for a job interview. The questions have been answered to the point, and briefly. This is subjective type short answers question and answer set no. 1 in this series.

Last Reviewed and Updated on February 7, 2020
Posted by Parveen(Hoven),
Aptitude Trainer and Software Developer

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.

Why use sequential search?

  1. If your collection size is relatively small and you would be performing this search relatively a few times, then this might an option.
  2. Another case is when you need to have constant insertion performance (like using a linked list) and the search frequency is less.
  3. In addition, linear search places very few restrictions on the complex data types. All that is needed is a match function of sorts.

Write pseudo code to search the array in the reverse order, returning 0 when the element is not found.

  1. Set i to n.
  2. Repeat this loop
    1. If i <= 0,="" then="" exit="" the="">
    2. If A[i] = x, then exit the loop.
    3. Set i to i - 1.
  3. Return i

What do mean by Linear search optimization?

If the elements you would be searching in a list are NOT uniformly distributed, then you could do certain optimizations that can help you improve the efficiency of your search algorithms. For such improvements to be effective, you do need to know the characteristics of the data being searched, the frequency and also the fact that the underlying collection needs to be modifiable.
  1. Most Recently Used pattern: If the likelihood of the current element being searched again is high, then move if from it's current location (say position i) to the front of the collection (say position 0). This does require moving elements from A[0, i-1] to A[1, i] to accommodate the new element at A[0].
  2. The disadvantage of the above pattern is that it requires a lot of movement. One quick strategy is to move an element up on success by simply swapping the target element from position x with the first element at position 0. This eventually results in a similar pattern as the frequently searched elements bubble up to the top of the list.
  3. On the other end of the spectrum, if an element is unlikely to be search again, then moving it to the end on find improves the chances of the other elements being searched.

Suppose an array A with elements indexed 1 to n is to be searched for a value x. Write pseudo code that performs a forward search, returning n + 1 if the value is not found.

  1. Set i to 1.
  2. Repeat this loop:
    1. If i > n, then exit the loop.
    2. If A[i] = x, then exit the loop.
    3. Set i to i + 1.
  3. Return i.

What is best case efficiency of linear search?

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

Write an algorithm to search for an employee ID in an array(Hint: use linear search)

  1. Read the employee ID to be searched
  2. Set i=0
  3. Repeat step d until i>n or arr[i]=employee ID
  4. Increment i by 1
  5. If i>n : Display "Not found"
    Else Display "Found"

What is best case efficiency of linear search?

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

Linear search is special case of which search.

Linear search is special case of brute-force search.

Write a program in c for linear search.

#include<stdio.h>

int main()
{

    int array[100], search, c, number;

    printf("Enter the number of elements in array\n");

    scanf("%d",&number);

    printf("Enter %d numbers\n", number);

    for ( c = 0 ; c < number ; c++ )
    {

        scanf("%d",&array[c]);

    }

    printf("Enter the number to search\n");

    scanf("%d",&search);

    for ( c = 0 ; c < number ; c++ )
    {

        /* if required element found */
        if ( array[c] == search )
        {

            printf("%d is present at location %d.\n", search, c+1);

            break;

        }

    }

    if ( c == number )
    {

        printf("%d is not present in array.\n", search);

    }

    return 0;

}


What are the various applications of linear search?

Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an unordered list. When many values have to be searched in the same list, it often pays to pre-process the latter in order to use a faster 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.