My software development journey
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…
In Competitive programming, learning to use the standard library than coding from scratch saves a lot of time. In this post we will use C++ STL(Standard Template Library) binary search algorithm with an example.Given a sorted array of numbers, How to find the frequency of a given number? Here is an efficient algorithm to do…