Sunday, September 23, 2012

[Amazon Online test] Number of swaps required

Given an array containing 0 & 1 only, You have only 1 operation i.e. you can swap theadjacent elements in the array. Find the minimum number of operationsrequired to sort the given input array.

A = (0,0,1,0,1,0,1,1) 
Min Operations: 3.

 Let's start with some of the trivial test cases.
(1,0) -- Number of swaps = 1
(1,1,0) -- Number of swaps = 2
(1,1,0,0) -- Number of swaps = 4
So an important observation comes that given an array of the type
(1, 1, 1, ... n times, 0, 0, 0, .. m times)
Number of swaps = n*m (This is based on the fact that each 0 has to be pushed(swapped) back m number of time)

[DirectI Online test] Number of substrings containing atmost 2 different characters

Given an input string, find the number of substrings which contains atmost two different characters.
E.g - aabc Ans: 8 


Lets start with a simple approach,

The most naive solution would be to iterate over all the possible substrings of the array 
(~ n ^ 2) and then validate if the substrings have atmost two unique characters.
The complexity will go over to O(n^3), proof is left to the reader.

Can we do it better, indeed yes,