Find The Longest Sequence Of Prefix Shared By All The Words In A String

Objective: Write an algorithm to find The Longest Sequence Of Prefix Shared By All The Words In A String. This interesting problem was asked in the Google interview for software engineer. This problem is bit tricky, it looks difficult but actually it is simple problem.

Input: A String

Output: The longest sequence of prefix common in all the words in a string

Example:

“Bedroom BedClock BedTable BedWall” => “Bed”

Approach:

Read more

Quick Sort Implementation

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

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

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

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

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