An algorithm is little more than a series of steps required to perform some task. If we treat each step as a basic unit of computation, then an algorithm’s execution time can be expressed as the number of steps required to solve the problem.

This abstraction is exactly what we need: it characterizes an algorithm’s efficiency … Read More →

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top.

Consider the example shown in diagram. The value of n is 3. There are 3 ways to … Read More →

Subset sum problem is to find subset of elements that are selected from a given set whose sum adds up to a given number K. We are considering the set contains non-negative values. It is assumed that the input set is unique (no duplicates are presented).

Exhaustive Search Algorithm for Subset Sum

One way to find subsets that sum … Read More →

Recursion is a tool not often used by imperative language developers, because it is thought to be slow and to waste space, but as the author demonstrates, there are several techniques that can be used to minimize or eliminate these problems. He introduces the concept of recursion and tackle recursive programming patterns, examining how they … Read More →

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is … Read More →

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for 4 Queen problem.

The expected output is a binary matrix which has 1s for the blocks where queens are placed. For example following is the output … Read More →

In statistics, the mode of a set of numbers is the number that appears most often in the set. A data set does not necessarily have to have only one mode - if two or more values are "tied" for being the most common, the set can be said to be bimodal or multimodal, respectively … Read More →

It's a common requirement in programming challenges - such as Project Euler - to determine if a number is a prime number. Recently I was tasked with finding a nice method of finding the nth prime number.

Skip to my proposed solution, or the PHP implementation.

The obvious solution here is to iterate through the whole number … Read More →

Introduction

Each natural number that is divisible only by 1 and itself is prime.

Prime numbers appear to be more interesting to humans than other numbers.

Why is that and why prime numbers are more important than the numbers that are divisible by 2, for instance ?

Perhaps the answer is that prime numbers are largely used in … Read More →

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Examples:

set[] = {3, 34, 4, 12, 5, 2},

sum = 9

Output: True

//There is a subset (4, 5) with sum 9.

Let isSubSetSum(int set[], int n, int sum) … Read More →

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

1) Always pick first element as pivot.

2) Always pick last element as pivot (implemented below)

3) Pick a random element as pivot.

4) … Read More →

You are not allowed to use loop constructs like while, for..etc, and you can only use the following ADT functions on Stack S:

isEmpty(S)

push(S)

pop()

Solution

The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the … Read More →

Introduction

In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.

The B-tree is a generalization of a binary search tree in that a node can have more than two children. Unlike self-balancing binary search trees, the B-tree is … Read More →

Problem

Implement a function that checks whether a positive number is a palindrome or not. For example, 121 is a palindrome, but 123 is not.

Sollution

It is easy to check whether a string is a palindrome or not - we can check whether the first character and the last one are identical, and then compare the second … Read More →

Problem

If you have a 2 GB file with one string per line, which sorting algorithm would you use

to sort the file and why?

Solution

When an interviewer gives a size limit of 2GB, it should tell you something - in this case, it

suggests that they don¡¯t want you to bring all the data into memory

So what do … Read More →

Tris volumineux

Les algorithmes de tri doivent aussi être adaptés en fonction des configurations informatiques sur lesquels ils sont utilisés.On suppose que toutes les données sont présentes en mémoire centrale (ou accessibles en mémoire virtuelle). La situation se complexifie si l'on veut trier des volumes de données supérieurs à la mémoire centrale disponible (ou … Read More →

#include "stdlib.h"

#include "stdio.h"

#include "stdbool.h"

// Fonction d'affichage

void affichage (int grille[9][9])

{

for (int i=0; i

Given an array of integers which is initially increasing and then decreasing, find the maximum value in the array.

Input: arr[] = {8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1}

Output: 500

Input: arr[] = {1, 3, 50, 10, 9, 7, 6}

Output: 50

Corner case (No decreasing part)

Input: arr[] = {10, 20, 30, 40, 50}

Output: 50

Corner … Read More →

Dynamic Programming – Cutting Rods

This problems is presented in Introduction to Algorithms as an intro to Dynamic Programming.

Given a rod of length n inches and a table of prices pi for rod lengths: i = 1, 2, ... n, determine the maximum revenue rn obtainable by cutting up the rod to pieces and selling them.

The … Read More →

PROBLEM

write a code to reverse a C-Style String - ( C-String means that “abcd” is represented as five characters, including the null character )

EXCLUSIVE DISJUNCTION or EXCLUSIVE OR is a logical operation that outputs TRUE whenever both inputs differ (one is true, the other is false)

The XOR swap is an algorithm that uses the XOR … Read More →

Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals. Let the intervals be represented as pairs of integers for simplicity.

For example, let the given set of intervals be {{1,3}, {2,4}, {5,7}, {6,8} }. The intervals {1,3} and {2,4} … Read More →