Posts

Showing posts from December, 2016

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Image
Ever came across a problem which asks you to find a single number (or a number that occurs once) amongst a set of repeated numbers (which are repeated twice each) ? Well, it is a pretty common problem and is asked a lot of times.

There are many ways to solve the problem. The most obvious but inefficient approach to solve the problem would be to use a brute force approach where you can loop through the list multiple times to find the repeated numbers or you can have a count of all the numbers occurring and just return the number that has a count of 1. But an efficient way to solve the problem would be to use the bitwise operators.

The basic idea behind the solution is that XOR of two same numbers is 0.

Problem

Sample Input : 1 2 3 2 3

Sample Output : 1

We will simply loop through all the elements in the array and XOR each of them and save them in a variable.

So we will have 1 XOR 2 XOR 3 XOR 2 XOR 3. 2 XOR 2 and 3 XOR 3 would fetch 0, leaving us with 0 XOR 1. And this would obviously ret…

Finding the Longest Palindrome in a String

Image
Hey ! Finding the longest palindrome in a string is one of the most commonly asked interview questions if you're aspiring to be a software development engineer. In this post we will be dealing with an optimal solution for this problem. There are two ways to solve the problem. They are listed down as follows.
Brute Force 
Initialise result to an empty string.Loop through each character of the string.Find for a matching character.See if the string bounded by the two characters form a palindrome. If they do then check if the length of this string is greater than the string in result variable. If else assign the string to result. This is an obvious solution for the problem but this is a brute force approach and is the least efficient of all the approaches. The main pitfall being the repeated checking of palindromic strings. To overcome this we can go for a dynamic approach which is discussed below.
Dynamic Approach
This is based on the concept that if the string asasa has to be a palind…