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,

Thursday, March 22, 2012

[Amazon Interview] Compare the BSTs

Given two unsorted integer arrays, your task is to compare the BST formed by both the arrays.

e.g [3 2 1 4 5] & [3 4 2 5 1]
when the BST is formed by taking the elements from the left, both BST turn out to be same.

        /  \
      2     4
     /         \
    1           5

Expected time complexity O(n).

Wednesday, February 8, 2012

[Amazon Online Test] : Finding the inorder successor

Given a binary search tree with the following node structure

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
    struct tree *next;
The next pointer of each node is pointing to null.
Write a code to initialize the next pointer of each node to its inorder successor.


Traverse in the BST in reverse inorder manner(i.e. postorder) and initialize the inorder successor as the last element visted.

Below piece of code initializes the next element to the inorder successor.

void inorder_successor(struct node * root) {
     static struct node * current = NULL;
     if(root == NULL)
     root->next = current;
     current = root;

Thursday, February 2, 2012

Euler problem : Finding the minimum sum

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.


This can be solved by an easy application of the DP.
A nice variation of the  above problem is to find the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.


Tuesday, January 24, 2012

Euler Problem: Pandigital number

Multiplying 9 by 1, 2, 3, 4, and 5, gives the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n >1?

Its fun to solve the problem without the use of code :)

Saturday, January 21, 2012

[Amazon Online Test] Find the nodes at k distance.

Given a tree with the root and a particular node, find the nodes which are atmost at a distance of k from the particular node and print them in sorted order.


Lets say the given tree is

And the given node is of the value 50, and distance k = 3
Then the desired result is 5, 30, 50, 70, 90