What is an algorithm?

  • Sequence of steps that transform input into output.

What is time complexity of an algorithm?

  • Indicates total time needed by program to run to completion.
  • Expressed by using Big O notation.

What are the types of notation used for time complexity?

  1. Big Oh: Fewer than or same as iterations.
  2. Big Omega: More than or same as iterations.
  3. Big Theta: Same as iterations.

Explain the difference between the best case and worst case scenario of an algorithm?

  • Best Case: Arrangement of data for which the algorithm performs the best.
  • Worst Case: Worst set of input for a given algorithm.

What is a recursive algorithm?

  • Method of solving complicated problem by breaking down the problem into smaller and smaller sub-problems.
  • Involves the function calling itself.

What are the three laws of recursive algorithm?

  1. Base case (stopping point)
  2. Must call itself
  3. Change its state and move towards the base case.

Explain bubble sort

  • Compares pair of adjacent items. If they are in the wrong order, swap them.

Explain quick sort

  • Based on principle of partition exchange or divide and conquer.
  • Three main parts:
    1. Elements less than the pivot
    2. Pivot
    3. Elements greater than the pivot

When does the worst case of quick sort occur?

  • When one part after partition contains all elements and other part is empty. For example, sorted array and first or last element is chosen as the pivot.

How does binary search work?

  • Compare key with the item in the middle position of array. If key is less than the item searched, it should be in the lower half of array. If key is greater than the item searched, it should be in the upper half of the array.
  • O(log n)

Is it possible to use binary search for a linked list?

  • No, since random access is not allowed in a linked-list, we cannot reach the middle element in constant time.

A sorted array is rotated some unknown point, what is a way to efficiently search an element in it?

  • Use binary search.

How to count inversions in an array?

  • Two elements arr[i] and arr[j] in an array arr[] form an inversion if arr[i] > arr[j] AND i < j

What is Breadth First Search (BFS)?

  • Explores all nodes at present depth before moving on to the nodes at the next depth level.

What are the steps of BFS?

  1. Pick a node and enqueue all its adjacent nodes.
  2. Dequeue a node from the queue, mark it as visited and enqueue all its adjacent nodes.
  3. Repeat this process until queue is empty or goal is met.

What is the time complexity of BFS?

  • Tree: O(V) where V is the number of nodes.
  • Graph: O(V + E) where V is the number of vertices and E is the number of edges.

What is Depth First Search (DFS)?

  • Explores all the nodes by going forward if possible or uses backtracking.

What are the steps of DFS?

  1. Pick a node and push all its adjacent nodes into a stack.
  2. Pop a node from the stack and push all its adjacent nodes into a stack.
  3. Repeat this process until the stack is empty or you meet goal.

What is the time complexity of DFS?

  • Tree: O(V) where V is the number of nodes.
  • Graph: O(V + E) where V is the number of vertices and E is the number of edges.

When to use BFS or DFS?

  • Known solution is not far from root, use BFS.
  • Tree is very deep and solutions are rare, use BFS.
  • If tree is very wide, BFS might need too much memory, use DFS.

What is Dijkstra’s algorithm?

  • Finds the shortest path between a given node and all other nodes in a graph.
  • Uses weights of the edges to find the path that minimizes the total distance between source and all other nodes.
  • Commonly used for GPS.

What are the steps of Dijkstra’s algorithm?

  1. Start at source node to find the shortest distance between that node and all other nodes in the graph.
  2. Keeps track of the currently known shortest distance from each node to the source node and updates these values if a shorter path is found.
  3. Once shortest path between source node and another node is found, that node is marked as visited and added to path.
  4. Continues until all the nodes in the graph have been added to the path.

What is the time complexity of Dijkstra’s algorithm?

  • O(V^2) but drops to O(V+ElogV) using a min-priority queue.

What are divide and conquer algorithms?

  • Divide: Break problem into smaller sub-problems
  • Conquer: Solve each sub-problem
  • Combine: Put together solutions of sub-problems to get final solution.

What are examples of divide and conquer algorithms?

  1. Merge Sort
  2. Quick Sort
  3. Binary Search

What are greedy algorithms?

  • Always takes the best immediate solution while finding the goal.

What are examples of greedy examples?

  • Traveling salesman problem
  • Map coloring
  • Knapsack problem