Eliminate the pairs (two same chars adjacent to each other) in string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem:
You are given a string. You have to eliminate the pairs (two same chars adjacent to each other).
eg. input string RGBBGBGR –> RGGBGR–> RBGR (output)
Solution:
We should check if we have character pair then cancel it. and then check for next character and previous character. Keep canceling the character until we either reach start of the array or end of the array or not find a pair.
[Read More]Move the Spaces to Front of the String
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem: Given a string that has set of words and spaces, write a program to move the spaces to front of string, you need to traverse the array only once and need to adjust the string in place.
string = “move these spaces to beginning”
output =” movethesepacestobeginning”
Solution:
Maintain two indices i and j. Traverse from end to beginning.
If the current index contains char, swap chars in index i with index j.
[Read More]Replace all spaces in a string with “%20″ in c-style string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem Write a C program that will replace all spaces with ‘%20′
Example
Input: “Mr John Smith "
Output: “Mr%20John%20Smith
Solution The algorithm is as follows:
Count the number of spaces during the first scan of the string. Parse the string again from the end and for each character:
If a space is encountered, store “%20”.
Else, store the character as it is in the newly shifted location.
[Read More]How many possible ways the child can run up the ladder
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A child is running up a ladder with n steps, and can hop either 1 step or 2 steps at a time. Calculate how many possible ways the child can run up the ladder.
This problem is similar to Fibonacci Problem. Each step n can be reached from either two steps below (n-2) or one step below (n-1), thus the number of possibilities to reach that step is the sum of the possibilities to reach those other two steps.
[Read More]Find row with maximum number of 1s in sorted matrix
Posted on January 17, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: You are given a MxN matrix with each row sorted. Matrix is having only 0′s and 1′s. You have to find row wotth maximum number of 1′s.
eg. matrix given:
000111
001111
011111
000011
111111 // row with max number of 1′s
Method 1: Brute force approach
Traverse the matrix row wise and count number of 1′s. If the number of 1′s is greater than max count than store index of row.
[Read More]Company specific interviews
Posted on January 17, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Find Position of the only Set Bit
Posted on January 17, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem: You are given a number having only one “1″ its binary representation,. You have to find position of it?
Solution:
First of all we will check if number is power of two, Beacuse then only its binary represenattion will contain only one “1″.
After that, start from rightmost bit and one by one check value of every bit. Following are steps:
Initialize two variables; i = 1 (for looping) and pos = 1 (to find position of set bit) Inside loop, do bitwise AND of i and number ‘N’.
[Read More]Checking if a bit is on or off without affecting other bits
Posted on January 17, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Let’s say that we have a bit string of 1101 and we want to know if the 2nd bit is on or off. Here is a way to do it:
int isAvailable (int bitString, int targetNum) { return bit\_string & (1 << targetNum); } bit_string: the bit string whose bits we are interested in. For example, 1101 and we are interested in the 2nd bit which is the bit in bold.
[Read More]Toggle a specified bit in a bit string without effecting other bits
Posted on January 17, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
For example, we have a bit string 0111 and you have to turn the left most bit on 0 -> 1. How can we do that? We’ll use XOR (^), left shift operation («) and the 0001 (1) bit string.
Shift the 1 bit of 0001 to the position of the bit you want to change. In our example, we need to toggle the 3th bit (first bit is at position 0, that’s why our target is at 3rd position not 4th).
[Read More]Divide a number by a power of two using bit right shift
Posted on January 17, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
In opposite to left shift, when we right shift a number we divide it by a power of two. For example, 4 » 2 = 0100 » 2 = 0001 = 1 = 4 / 2^2. Here is the general formula: