# Tag Archives: algorithms

## Valid Dictionary Words Algorithm

The problem is like this : Given a string str and a dictionary of words determine if str can be segmented into a space-separated sequence of one or more dictionary words. Example Input: str = “InterviewGeek”, dict = [“Interview”, “Geek”,”hell”] , Output : true Algorithm : For each word in the string check if it’s… Read More »

## Find if 2 Rectangles overlap

Given two rectangles with their base parallel to each other . You have to find whether the rectangles overlap or not. Ex Rect1(2,3,5,6) Rect2(1,3,1,10) Where a rectangle is specified by coordinates of it’s TopLeft (x1,y1) and BottomMRight(x2,y2) coordinates in sequence for rect1 TopLeft(2,3) and BottomRight(5,6). The problem is very simple . Since the rectangle have… Read More »

## Merge Sort Code

Merge Sort belongs to category of divide and conquer algorithms. Which means it divides the problem into  small subproblems, solves them and then combine the solutions of these subproblems to generate solution  of the original problem.Merge Sort compares elements with each other for sorting the list. The steps followed to mergesort are are: Divide the unsorted list… Read More »

## Quick Sort Code

Quick Sort belongs to the category ofdivide and conquer algorithms. Quicksort  divides a large list into two smaller lists around a selected pivot . Quicksort can then recursively sort the sub-lists.It sorts the elements inplace. The steps followed are are: Select an element, called a pivot, from the list. Reorder the list so that all elements with values… Read More »

## Find the median of two sorted arrays

Given two sorted arrays A and B containing N elements each. Give an algorithm to ﬁnd the median of two sorted arrays in O(lgN) time. Ex A={1,2,3} B={1,4,5,6} median=3 . The naive algorithm will be to merge the arrays A and B and return the median .But the time complexity will be O(N) and this… Read More »

## Counting Sort

Counting Sort is not a comparison sort.Counting sort assumes that each of the input element is an integer in the range 0 to k, for some integer k. When k=O(n), the sort runs in O(n) time. The basic idea of counting sort is to determine, for each input element x, the number of elements less… Read More »

## Binary Search code

Binary Search finds the position of a specified value (key) in a sorted array.In each step it discards half of the elements to search , thus the worst case running time of binary search is O(log n).Believe it or not 80 out of 100 of the programmers fail to write the correct code for binary… Read More »

## Balanced Parentheses Algorithm

This is a classic example of how using an appropriate Datastructure can improve the quality of your algorithm. The Balanced Parentheses or Valid Parentheses is like this : Given a string containing ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid or not. [(a+b)+c] is Valid where as (a+b)+c] is… Read More »

## 3 sum problem or a+b+c=sum

The 3 Sum 🙂 problem is like this : Given an array of integers A, find 3 numbers a,b,c such that they add up to a specific target number s. a+b+c =s The problem is somewhat similar to the two sum problem . Ex Input : A={4,5,1,2,3} s=8 output :5,2,1 We can take different approaches… Read More »

## Two Sum (a+b =s) Problem

The Two Sum problem is like this : Given an array of integers A, find two numbers a,b such that they add up to a specific target number s. a+b =s Though this problem looks simple but this problem forms a kind of base for solving other bigger problems like 3sum problem and 4 sum… Read More »