Close

## How does Bubble sort works?

Bubble sort is a comparison based sorting algorithm. It works like following.  We perform series of iterations to ‘bubble up’ the elements one by one so that they form a sorted order. For example we have to sort an array [3,1,4,5,2] in ascending order, In the first iteration, the element 5 will be bubbled up…

## Program to find GCD of two numbers

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder – from WikipediaFor example, the GCD of 8 and 12…

## Finding the length of a linked list

In this post we will see an algorithm to find the length of the linked list. Here singly linked list is implemented in Object Oriented Programming (OOP) paradigm in C++. The algorithm is very simple. Just start at the beginning of the linked list, move to next until you reach the end of the list,…

## Member initialization list in C++

You all know that in C++, constructors are used to create an object. We normally initialize all the data members with some valid data in the constructor. We generally write code similar to the following and think that m_data variable is being initialized where as it is actually being assigned. class MyClass{ public: Myclass(int d)…

## Finding the missing element in an array:

An array of size (n-1) contains all the numbers in the range [1..n] except one number which is missing. Write a program to find the missing number in O(n) time and O(1) space. For example let N= 5 and the input array is [1,3,4,5], the output should be 2. Given O(n) space we can always…

## Couple elimination problem

Given a string of some symbols, write a program to transform a string by repeatedly eliminating two same symbols occurring together.For example if the input string is ‘RGGB’ it will be reduced to ‘RB’ because ‘GG’ can be eliminated. Here are some more examples of input – outputInput   | Output——————-GBRRBR  | GRBGRGRR  | BGRGGGBB    |…

## Replacing spaces in a character array with %20

Given a character array which contains some spaces. we have to replace all the spaces with the string ‘%20’. This algorithm is commonly used during HTML encoding of the URLs in the web browsers. Assume that the array has enough space at the end to accommodate the expanded string, how do we do this efficiently?…

## Common elements between two sorted arrays

Given two sorted arrays, how do you efficiently find the common elements between those two?Method#1: Simple and Brute-force approachIterate through one array, and try to find the element in another array using linear search. If it is found, then print it. This approach takes O(n^2) time as for each element in the first array we…

## Rotating an array

Rotating an array: In this post we will discuss two solutions for rotating an array by a given number of times. One is a simple solution and another uses the reversal operation (discusses in the previous post). Method#1: Simple and intuitive In this method, we will copy the last element into a variable, and shift…

## Reversing an array

In this post we will discuss a simple problem on Arrays. Given an array of numbers, how do we reverse it efficiently? Here is the simple and effective approach. We start with one index pointing to the start, and another index pointing to the end of the array. We swap the two elements at these…