My software development journey
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,…
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)…
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…
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 |…
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?…
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: 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…
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…
Stack is one of the most widely used data structure. In this post we will learn how to use the stack container (data structure) provided by C++ STL with an example. Let us consider the following problem. We have a string which contains only ‘(‘ and ‘)’ characters. We have to write a program to…
Map is one of the most useful data structure in solving many programming problems. Today we will see how to use C++ STL map with a simple example. Counting the frequency of letters in a given string. The map data structure stores <key,value> pairs. In this example key will be the character, and the value…