Linear Search algorithm using python

Why You Should Learn Data Structures and Algorithms

Whether you’re pursuing a career in software development or data science, it’s almost certain that you’ll be asked to solve programming problems like reversing a linked list or balancing a binary tree in a technical interview or coding assessment.

It’s well known, however, that you will almost never face these problems in your job as a software developer. So it’s reasonable to wonder why such problems are asked in interviews and coding assessments. Solving programming problems demonstrates the following traits:

  1. You can think about a problem systematically and solve it systematically step-by-step.
  2. You can envision different inputs, outputs, and edge cases for programs you write.
  3. You can communicate your ideas clearly to co-workers and incorporate their suggestions.
  4. Most importantly, you can convert your thoughts and ideas into working code that’s also readable.

Hackerrank solutions :- Click Here

It’s not your knowledge of specific data structures or algorithms that’s tested in an interview, but your approach towards the problem. You may fail to solve the problem and still clear the interview or vice versa. In this course, you will learn the skills to both solve problems and clear interviews successfully.

We will use problem solving approach to understand the concept

QUESTION 1: Alice has some cards with numbers written on them. She arranges the cards in decreasing order, and lays them out face down in a sequence on a table. She challenges Bob to pick out the card containing a given number by turning over as few cards as possible. Write a function to help Bob locate the card.

Cards

There are few method/approach to solve the question.

The Method

Upon reading the problem, you may get some ideas on how to solve it and your first instinct might be to start writing code. This is not the optimal strategy and you may end up spending a longer time trying to solve the problem due to coding errors, or may not be able to solve it at all.

Here’s a systematic strategy we’ll apply for solving problems:

  1. State the problem clearly. Identify the input & output formats.
  2. Come up with some example inputs & outputs. Try to cover all edge cases.
  3. Come up with a correct solution for the problem. State it in plain English.
  4. Implement the solution and test it using example inputs. Fix bugs, if any.
  5. Analyze the algorithm’s complexity and identify inefficiencies, if any.
  6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

“Applying the right technique” is where the knowledge of common data structures and algorithms comes in handy.

Problem

We need to write a program to find the position of a given number in a list of numbers arranged in decreasing order. We also need to minimize the number of times we access elements from the list.

Input
  1. cards: A list of numbers sorted in decreasing order. E.g. [13, 11, 10, 7, 4, 3, 1, 0]
  2. query: A number, whose position in the array is to be determined. E.g. 7
Output
  1. position: The position of query in the list cards. E.g. 3 in the above case (counting from 0)

First we will use brute-force algorithm to solve the question, i.e we will iterate through each and every item in the list and then check whether the selected number is equal to the query or not. Now, because we are iterating through every item in the list(hit and trial method) therefore, it is called as brute-force algorithm.

def locate_card(cards, query):
    position = 0
    while position < len(cards):
        if cards[position] == query:
            return position
        position += 1
    return -1

Here, we have created a function locate_card with two arguments, cards and query and position is the index of the item on the list which starts with 0. Use a while loop until the position is less than the length of cards to prevent the edge case of list to be empty. Then, we compare the item at the position index with the query and if they are equal we return the position otherwise, we will increment the position by 1 and reiterate through the list of cards. If nothing is found while looping we simply returns the -1.

This approach is called brute-force algorithm, since we are iterating through every single item in the list.

Now, in the next article we will learn how we can create a more efficient algorithm so that we can improve the execution time.

Thanks for reading

Cheers!!!

Happy Coding and stay safe

Leave a Reply