Quick revision

Articles in this category are good for quick revision before an interview.

Job Sequencing algorithm – Java

by

Objective: You are given n jobs along with the deadline and profit for each job. Your task is to write an algorithm to choose the jobs wisely which can maximize the profit. Also compute the maximum profit. Below are the details Each job duration is 1 unit. Name – Name of the job. Deadline – … Read more

Implement/Design the version control map system

by

Problem: Implement the version control map system which takes the snapshot of the versions of data. Implement the following functions: put(key, value) – puts the value again the key in the latest version of the map get(key) – get the value of the key for the latest version of the data snapshot() – take a … Read more

Find if any two intervals overlap in given intervals

by

Objective: Interval is defined as [start, end]- the start of an interval to the end of the interval. Given a list of Intervals. Your task is to check if any two intervals overlap. Example: Given Interval: [[1,5], [6,10], [12,15], [3,7]] Two intervals are present which intersect Given Interval: [[1,5], [6,10], [12,15]] No intervals overlasx Approach:  … Read more

Print all steps to convert one string to another string

by

Objective: Given two strings, source string and target string, which are permutation or anagram of each other. You are allowed two swap only consecutive characters. Write an algorithm to print all the steps ( all the swaps) which will lead the conversion of the source string to the target string. NOTE: There could be multiple … Read more

Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

by

Objective: Count all the paths from left top corner to right bottom corner in two dimensional array.

Input: Two Dimensional array

Output: No of paths.

Approach :

1. Recursive

Recursive solution to this problem is similar to Print All Paths from Top left to bottom right in Two Dimensional Array

But the Time complexity will be exponential because there will be many sub problems which will be solved again and again to get the final solution. read this : “Dynamic programming vs Recursion

2. Dynamic Programming (Better Solution)

Create two dimensional resultCount array to store the number of paths from top left corner.

Read more

Merge or Combine Two Sorted Linked Lists

by

Objective: Given two sorted linked lists, objective is to merge both the lists in sorted order.

Input: Two sorted linked list List a, List b.

Example: 

List a : ->2->6->18

Listb: ->1->3->17->19

Merged List: ->1->2->3->6->17->18->19

Approach:

Read more

Quick Sort Implementation

by

Objective: Write an algorithm to sort an array in increasing or decreasing order using Quick Sort.

Input:  An Array arrA[]

Output: A sorted array.

Approach:

  • Choose any element from the array and call it as pivot element, Example here we have selected middle element as pivot
  • Place all the elements smaller than pivot in the left side of pivot.
  • Place all the elements greater than pivot in the right side of pivot.
  • Sort left side and right side recursively.

Example:

Read more

Valid or Well Formed Parentheses | Part – 1

by

Objective: You have been asked to Write an algorithm to find Whether Given the Sequence of parentheses are well formed. This question was asked in the Amazon Interview.

Input: A String contains a sequence of parentheses

Output: true or false on whether parentheses are well formed or not

Approach:

  • Idea is to have two counters, one for open parentheses ‘{‘ and one for close ‘}’
  • Read one character at a time and increment one of the counters
  • If any given point of time count of close parentheses is greater than the open one, return false
  • If at the end both counters are equal, return true

Example: { { } { } } – Well formed

{ { } { = Not well formed

Read more

Find an Element in 2 dimensional sorted array

by

Objective : Write an algorithm to find an Element in 2 dimensional array where rows and columns are sorted respectively.

Input: A two dimensional sorted array, arrA[][].

Sorted 2D array

 

Output : True or false based on whether element exists and its location

Approach:

Read more

Find a peak element in a Given Array

by

Objective : In this article we will discuss an algorithm to Find a peak element in a Given Array. We will see the recursion techniques to solve this problem.

Peak Element: peak element is the element which is greater than or equal to both of its neighbors.

Input:  Array, arrA[] .

Output: A peak element and its index

Approach:

A simple approach is to do a linear scan to a array and using few variables we can find a peak element. But the Time Complexity will be O(n) but real question is, Can we do better?

The Answer is yes, by using Binary Search techniques.

Read more

Find a Missing Number From a Sequence of Consecutive Numbers

by

Objective : You have been asked to Write an algorithm Find a Missing Number From a Sequence of Consecutive Numbers

Input:  Array, arrA[] with a missing number and Range

Output : missing number

Approach:

  • Approach is very simple, Add all the given numbers say S
  • Calculate sum of N numbers by formula n(n+1)/2 , say N
  • Find missing number m = N-S

Read more