Algorithm Technical Interview Questions

What is an Algorithm? What is its Purpose?

An algorithm is a set of rules or a process that must be followed. Algorithms are commonly used in a variety of fields, from information technology, to mathematics and statistics, etc. In terms of computers or software, the algorithm is a structured procedure that allows a computer to solve a problem.

The algorithm works are a set of guidelines or steps that the computer must solve in chronological order in order to arrive at the solution. The purpose of the algorithm is to provide the computer, or rather the software, a set of instructions to follow, which must be complete till the end, and in the order provided. For example:

  • Create variable.
  • Title it 0
  • Add +1 for next variable
  • Continue 205 times
  • Give output

This is a simple but very vague example of an algorithm.

What is time complexity of Binary Search?

Binary search is also commonly known as half-interval search or logarithmic search. It is a type of search algorithm that can be used to find the position of a target value within a sorted array. The way binary search works is that it compares the target value to the middle element of the array. If the values are unequal, then the half in which the target value cannot exist is eliminated and is not searched. Binary Search then continues to search he remaining half in the same way until the target value is found.

Binary search runs in at worst logarithmic time, making O(log n) comparisons. It can also be said that O(log n) is the time complexity of Binary Search.

At a glance the complexity table is like this -

  • Worst case performance : O(log2 n)
  • Best case performance : O(1)
  • Average case performance: O(log2 n)
  • Worst case space complexity: O(1)

Can Binary Search be used for linked lists?

Binary search is a type of search that can be used to find a target value within a sorted array. In a linked list, random access is typically not allows, which makes it difficult to reach the middle element in O(1) time. As Binary Search searches in O(1) time, it cannot be used for linked lists. However, there are other ways to search a linked list, such as linear search.

How to find if two given rectangles overlap?

There are times when one may find themselves faced with two rectangles and be left wondering whether or not they are overlapping. In order to find out whether or not the two given rectangles overlap, the first step is to identify the rectangles. To do so, is to identify the coordinates of the rectangles. For this purpose, let’s consider them to be:

  • l1: Top Left coordinate of first rectangle
  • r1: Bottom Right coordinate of first rectangle
  • l2: Top Left coordinate of second rectangle
  • r2: Bottom Right coordinate of second rectangle

Then, lets write a function that would return true if the two given rectangles overlap: bool doOverlap(l1, r1, l2, r2)

The function should return true of one of the following conditions are met:

  • When left edge of R1 is on the right of R2's right edge. (That is, R1 is completely on the right of R2).
  • When right edge of R1 is on the left of R2's left edge. (That is, R1 is completely on the left of R2).
  • When top edge of R1 is on bottom of R2's bottom edge (That is, R1 is completely under R2).
  • When bottom edge of R1 is on top of R2's top edge (That is, R1 is completely over R2).

The function should return false for one of the following conditions:

  • One rectangle is above top edge of other rectangle.
  • One rectangle is on left side of left edge of other rectangle.
How to find angle between hour and minute hands at a given time?

One of the common problems one might face is to find the angle between the hour and minute hands at a given time. The easiest way to do this is this:

  • Take 12:00 (h = 12, m = 0) as a reference point.
  • Then find the angle that the hour hand makes with respect to 12:00 in h hours and m minutes.
  • Then find the angle that the minute hand makes with respect to 12:00 in h hours and m minutes.
  • Then subtract the two angles to find the angle between hour and minute hands.
When does the worst case of QuickSort occur?

QuickSort is a type of Divide and Conquer algorithm. It works by picking an element as pivot. It then partitions the given array around the picked pivot. There are many different versions of quicksort. Then differ in the way they pick pivot. QuickSort will pivot if four different ways:

  • Always pick first element as pivot
  • Always pick last element as pivot
  • Pick a random element as pivot
  • Pick median as pivot

Regardless of what it pick, the key element in QuickSort is partition(). The target of partitions is to put x at its correct position in a sorted array and put all the elements smaller than x before x, and put all elements greater than x after x, after it has been given an array and an element x of array as pivot.

Now there are times, when QuickSort might fail. Some of the worst cases of Quicksort might occur in following cases:

  • When one part after partition contains all elements and other part is empty
  • Array is already sorted in same order.
  • Array is already sorted in reverse order.
  • All elements are same

Add new comment

Plain text

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.