Saturday, 15 September 2012

Arithmetic With Precision

                                Arithmetic With Precision

Have you ever used C/C++. Tried to perform simple arithmetic operations on real numbers of considerably longer length. If yes, then you must have known that none of these languages provide you the answers with perfect precision. Even the same may be the case with java. So, here is the task. Just take two numbers (of course real), try to perform any arithmetic operation (+,-,/,*) and then try to simply print it on the console, but with infinite precision.


    987432189374581923.123276453
+ 199283777167383992.383477628
____________________________________________

Take care, answer should look like one of operands, without any exponential notation.

Sunday, 9 September 2012

Stack with min operation in O(1)



Stack with push, pop and min,  all in O(1)

 

Problem

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element so far? Push, pop and min should all operate in O(1) time.

Trivia

This is a pretty standard question now. The question has been asked in many interviews in past and will be asked in many interviews in future.

Approach

There can be many ways to approach this problem:
1) One way is to introduce another variable min in data structure 'Node' which keep tracks of min element so far in the stack.

So the new data structure for stack would look something like:
struct Stack_Node {
   int val;
   int min;
   struct Node *next;
}  Node;

Now when you push the element into stack, its local min variable is calculated and updated.
new->min = Minimum(value, top->min);
And while doing the pop operation, the min is already up to date in stack so far. So one can simply delete the top node.

There is just one problem with this approach - if it is a large stack, we will waste a lot of space keeping track of min element. So if space isn't the issue, like it isn't now a days :), this method is perfectly fine. Otherwise we can do better too.

2) The other way to solve a problem is using additional stack which keep tracks of min so far.

So the new push and pop operations for stack would be like:
stack<int> s2;
push {
    if (value <= s2.top())  s2.push(value)
    s1.push(value)
}
pop {
    value = s1.pop()
    if(value=s2.top()) s2.pop()
}
min {
    if(!s2.isEmpty()) s2.top()
}


Time Complexity

Push - O(1)
Pop - O(1)
Min - O(1)


There is a similar question in which you have to design a stack which, in addition to push and pop, also has a function max which returns the maximum element so far.


Sunday, 2 September 2012

Tower Of Hanoi - Non-recursive Approach

Tower Of Hanoi

                                                             --  shaikzakir3149@gmail.com


Hello all, this is my first post. Hope you find it useful ...


Implement non-recursive Towers of Hanoi. Given the number n of disks as input, maintain appropriate pegs/rods to simulate the movement of the disks among the three pegs: Source, Auxilary & Destination.
Output the sequence of moves of the disks. Following is an example of the output expected by your program.

No. of disks: 3
Sequence of Moves
1. Source → Destination
2. Source → Auxilary
3. Destination → Auxilary
4. Source → Destination
5. Auxilary → Source
6. Auxilary → Destination
7. Source → Destination

Note: Remember that towers of hanoi can be solved in (2^n - 1) at the best for given n disks.



Algorithm:

While size of Destination is less not equal to n
do
{
If num of disks is even then

       Make legal move between Source and Auxilary
       Make the legal move between pegs Source and Destination

else

        Make the legal move between pegs Source and Destination  
        Make the legal move between pegs Source and Auxilary

endif

Make legal move between pegs Auxilary and Destination



}
end While


Note that a legal move is one which abides by the rules of the puzzle. Only a smaller disk can be moved onto a larger disk.

Running Time Complexity :

 The runtime complexity of this algorithm is O((2^n - 1)/3) which is equivalent to O(2^n). Clearly the stack operations (push, pop and peek) have a runtime equal to O(1).

The code is given in Java.


Source Code :


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
//package tower.of.hanoi;
import java.io.*;
import java.util.Stack;
import java.util.EmptyStackException;
/**
 *
 * @author Shaik
 */
public class TowerOfHanoi {

    
    public static int legalMove(Stack A, Stack B)
    {
        int a,b;
        try {
        a = Integer.parseInt(A.peek().toString());
        }
        catch(EmptyStackException e){
        a = 0;    
        }
        try {
            b = Integer.parseInt(B.peek().toString());
        }
        catch(EmptyStackException e){
        b = 0;    
        }
        if(a==b) return 0;
        if(a == 0)             // If peg A is empty, then pop from B and push the disk onto A
    {
        A.push(B.pop());
            return 2;           // Return 2 as move occurred from B to A
    }
        else if(b == 0)        // If peg B is empty, then pop from A and push the disk onto B
        {
        B.push(A.pop());
        return 1;           // Return 1 since move occurred from A to B
    }
        
        if(a<b)
        {
        B.push(A.pop());
        return 1;               // Return 1 since move occurred from A to B
        }
        else if(a > b)            // value of top disk of peg A is greater than the value of topmost disk of peg B
        {
        A.push(B.pop());
        return 2;               // Return 2 since move occurred from B to A
        }
        return -1;
    }
        
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int stepNumber = 0;
        int status = 0;
        try {
        Stack Source = new Stack();
        Stack Auxilary = new Stack();
        Stack Destination = new Stack();
        
        System.out.println("Enter the number of disks : ");
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine());
        if(n<=0)
        {
            System.out.println("Sorry wrong input, negative numbers not allowed.");
            System.exit(1);
        }
        for(int i=n; i>0; i--)
            Source.push(i);
        int m = n%2;
        do {
            if(m==1)
            {
                if((status = legalMove(Source,Destination)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Destination");
                else if (status == 2)
                    System.out.println((++stepNumber) + ". Destination --> Source");
                
                if((status = legalMove(Source,Auxilary)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Auxilary");
                else if(status == 2)
                    System.out.println((++stepNumber) + ". Auxilary --> Source");
                else 
                    break;
            }
            
            else
            {
                if((status = legalMove(Source,Auxilary)) == 1)  
                    System.out.println((++stepNumber) + ". Source --> Auxilary");
                else if (status == 2)
                    System.out.println((++stepNumber) + ". Auxilary --> Source");
                
                if((status = legalMove(Source,Destination)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Destination");
                else if(status == 2)
                    System.out.println((++stepNumber) + ". Destination --> Source");
                
            }
            
            if((status = legalMove(Auxilary,Destination)) == 1) 
                System.out.println((++stepNumber) + ". Auxilary --> Destination");
            else if(status == 2)
                System.out.println((++stepNumber) + ". Destination --> Auxilary");
        }while(Destination.size()!=n);
        System.out.println("X-----------------------X");
        }         

        catch (Exception e){
        }
        }
    }


Ibibo Interview Questions (Tradus.in, goIbibo.com, payU.in)


Interview Questions for Software Engineer Profile

Ibibo Web Pvt Ltd - May 2012



round1

1. Linked list contain alphabets.find if it is palindrome or not
2. Array of unsorted no. is given, find triplets which satisfy a2 + b2 = c2.
3. Duplicate a linked list.


round2

1. Sorted array cyclically right-shifted unknown no of times. find an element in it.
2. Stack which does push, pop and findMin in O(1).


round3

1. Given 2 arrays unsorted, insert common elements in third array in O(n).
2. Given 2 arrays unsorted, insert unique elements in third array in O(n).
3. Fill n*n matrix clockwise starting from center. Write efficient code.
ex.   7   8  9
        6   1  2
        5   4  3
4. Print 2D matrix in spiral order.


round4

1. Lots of technical questions from Resume.
2. Given three arrays A,B,C containing unsorted numbers.  Find three numbers a, b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum.



Saturday, 30 June 2012

Interviewstreet Meeting Schedules - Amazon India Coding Challenge : Solution C++


Interviewstreet Amazon India Coding Challenge 

Meeting Schedules Problem



Problem

Given M busy-time slots of N people, You need to print all the available time slots when all the N people can schedule a meeting for a duration of K minutes.
Event time will be of form HH MM ( where 0 <= HH <= 23 and 0 <= MM <= 59 ), K will be in the form minutes
An event time slot is of form [Start Time, End Time ) . Which means it inclusive at start time but doesn’t include the end time.

Sample Input:                                                       Sample Output:
5 120                                                                    00 00 09 00
16 00 17 00                                                          17 00 20 45
10 30 15 30
20 45 22 15
10 00 13 25
09 00 11 00


Algorithm

1) Create a bit array busy[ ] of size equal to total no of minutes per day which is 24*60=1440.
             busy[i] = 1 mean minute is busy because of some meeting going on.
             busy[i] = 0 mean minute is free and another meeting can be organized.
             i represent that minute from the day, ex: For 10:30, i would be 10*60+30 = 630
2) For each input interval, fill busy[i] array on that interval.
3) After each input interval is processed, start scanning busy[ ] array from 0 to 1440 for k continuous
    free minutes.And whenever you find the interval print the interval. There may be more than 1 such
    interval.

Have a better approach in mind, please share it for our readers in comments section.


Solution


//All test cases passed
#include<iostream>
using namespace std;

void print(int i) {
  if(i==0 || i==1440) cout << "00 00";
  else {
     int j = i/60;
     int k = i%60;
     if(j<10) cout << "0" << j << " ";
     else cout << j << " ";
     if(k<10) cout << "0" << k ;
     else cout << k ;
  }
}

int main()
{

int m,k;
cin>>m>>k;
int busy[1440];
int a1,a2,b1,b2;
int i;
for(i=0;i<1440;i++)
    busy[i]=0;
   
while(m--) {
   
    cin>>a1>>a2>>b1>>b2;
    int start = a1*60+a2;
    int end = b1*60+b2;
    for(i=start;i<end;i++)
        busy[i]=1;

}
int j;
i=0;
while(i<1440) {
    j=i;
    if(busy[j] == 1) {
        i++;
        continue;
    }
    while(j < 1440 && busy[++j]!=1);
    if((j-i)>=k) {
       //cout << i << " " << j << endl;
       print(i);
       cout << " ";
       print(j);
       cout << endl;
    }
    i=j;
}

//cin >> i;
   
}


Time Complexity

Busy array is scanned twice, so O(n)





Friday, 29 June 2012

InterviewStreet Find Strings Solution C++


InterviewStreet Find Strings Solution C++


Problem

https://www.interviewstreet.com/challenges/dashboard/#problem/4efa210eb70ac

Algorithm

Declare a set<string> which will contain strings lexicographically ordered.
For each input string
     generate all its substrings one by one and add them  to set
For each query
     move pointer to require index in set and return the string
     if query no is greater than size of set, print Invalid.

 

 Solution

If you know better solution please post it in comments section.
//4 out of 7 test cases passed
#include<iostream>
#include<set>
#include<string>
typedef unsigned long long int big;
using namespace std;

int main() {

int n,i;
cin >> n;

set<string> s;
set<string>::iterator it;

string s1,temp;
for(i=0;i<n;i++) {   
    cin >> s1;
    int len = s1.length();
    int j,k;
    for(j=0;j<len;j++)
        for(k=len-j;k>0;k--) {
            temp = s1.substr(j,k);
            s.insert(temp);
        }                      
}

it=s.begin();
int curr = 1;
int q;
cin >> q;
big k, len;
len = s.size();
cout << len;
for(i=0;i<q;i++) {
    cin >> k;
    if(k>len) {
       cout << "INVALID\n";
       continue;
    }
    if(curr+(len/2) < k) {
      it = s.end();
      it--;
      curr = len;
    }
    if(curr-(len/2) > k) {
       it = s.begin();
       curr = 1;
    }
    if(k>curr) {
        int j= k-curr;
        while(j) { it++; j--; }
        cout << *it << endl;
        curr = k;
    }
    else if(k<curr) {
        int j=curr-k;
        while(j) { it--; j--;}
        cout << *it << endl;
        curr = k;
    }
    else cout << *it << endl;
}

cin >> i;
}




Saturday, 23 June 2012

Print boundary of a binary tree. Microsoft Interview.


Print boundary (edge nodes or outside frame) of a binary tree

Microsoft Interview (May 2012) 



Problem Statement

Print outside frame of a binary tree anti-clockwise.
1) Print all left most nodes.
2) Print all leaf nodes.
3) Print all right most nodes.

Please note:
  • If a node is a left-most node, then its left child must be a left-most node as well.
  • If its left child does not exist, then its right child will be a left-most node.

 Example:
                                    1000
            500                                                1500
    240                510                    1300
120        300                600                   1320

Output:1000 500 240 120 300 600 1320 1300 1500


Algorithm

1) Print root node if it exist.
2) Print left most edges from top to bottom. If a node is a left-most node, then its left child must be a left-most node but if its left child does not exist, then its right child will be a left-most node.
3) Print leaf nodes - a node whose left and right child both are null it is a leaf node.
4) Print right most edges from bottom to top.
    
If you have a different approach in mind, please share it in the comments section.

 Solution

#include<stdio.h>
#include<stdlib.h>

struct node {
    struct node *left;
    struct node *right;
    int data;
};

struct node *newnode(int data)
{
        struct node *node=(struct node *)malloc(sizeof(struct node));
        node->data=data;
        node->left=NULL;
        node->right=NULL;
        return node;
}

void printLeftBoundary(node *root) {

    if(root==NULL) return;
    if(root->left) {
       printf("%d ",root->data);
       printLeftBoundary(root->left);
    }
    else if(root->right) {
       printf("%d ",root->data);
       printLeftBoundary(root->right);
    }
}

void printLeafBoundary(node *root) {

    if(root) {
  
       printLeafBoundary(root->left);
     
       if(root->left==NULL && root->right==NULL)
          printf("%d ",root->data);
        
       printLeafBoundary(root->right);
    }
}

void printRightBoundary(node *root)
{
    if(root==NULL) return;
    if(root->right) {
       printRightBoundary(root->right);
       printf("%d ",root->data);
    }
    else if(root->left) {
       printRightBoundary(root->left);
       printf("%d ",root->data);
    }
}

void printBoundary(node *root)
{
if(root)
    {
        printf("%d ", root->data);
      
        printLeftBoundary(root->left);
      
        printLeafBoundary(root);
      
        printRightBoundary(root->right);
    }
}

int main()
{
    struct node *root=newnode(1000);
    root->left=newnode(500);
    root->right=newnode(1500);
    root->left->right=newnode(510);
    root->left->right->right=newnode(600);  
    root->left->left=newnode(240);
    root->left->left->left=newnode(120);
    root->left->left->right=newnode(300);  
    root->right->left=newnode(1300);
    root->right->left->right=newnode(1320);  
  
    printBoundary(root);
  

    return 0;
}



Time Complexity

PrintLeftBoundary - O(h), where h is height of tree, log(n) nodes on left are visited once
PrintLeafBoundary - O(n), as each node is visited once
PrintRightBoundary - O(h), where h is height of tree, log(n) nodes on right are visited once.

O(n+2h) total time complexity
 


Interviewstreet Fibonacci Factor - Amazon India Coding Challenge : Solution C++


Interviewstreet Amazon India Coding Challenge 

Fibonacci Factor Problem


Problem Statement

Given a number k, find the smallest Fibonacci number f that shares a common factor d( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them. 
Input: T test cases where each contains integer k in [2,1000000]
Output: two separate numbers, f and d, where f is the smallest fibonacci number and d is the smallest number other than 1 which divides both k and f.
 

Algorithm

1) For each fibonacci number f in [2,k] , find smallest common factor, findSCF(k,f) = d
2) if d > 1 print f and d
3) else continue until you get your f and d.
4) If fibonacci no not found in [2,k], keep looking for f in [k,infinity) until f%k == 0.

If you have a different approach in mind, please share it in the comments section.

Solution

/*All test cases have passed.*/

#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long int big;

big findSCF(big a, big b) {
  if(a%2==0 && b%2==0) return 2;
  for(big i = 3; i <= b; i+=2)
      if(a%i==0 && b%i==0) return i;
  return 1;
}

int main()
{

int k,t;
cin >> t;
while(t--)
{
cin >> k;
big f = 2, prev = 1, temp, d=1;
while(f<=k) {
  d=findSCF(k,f);
  if(d>1) break;
  temp=prev;
  prev=f;
  f+=temp;
}
if(d > 1)
cout << f << " " << d << endl;
else {
while(f%k!=0) {
   temp=prev;
   prev=f;
   f+=temp;
}
cout << f << " " << k << endl;
}
}
}

/* 
Since k can be 10^6, f can be as large as 10^18, so i have used unsigned long long int as variable type of 'f' 
*/



The next in the series is "Meeting Schedules - Amazon India Coding Challenge".


Wednesday, 20 June 2012

Interviewstreet String Similarity Solution C++


Interviewstreet String Similarity Challenge



Problem Statement

String similarity of two strings is defined as length of longest prefix common to both strings. For example string similarity for abcd and abb is 2, length of ab. Calculate sum of similarities of a string with each of its suffixes.
Input: First line contains T, no of test cases and next T lines contain strings
Output: T lines contain answer.
Sample Input:                                                  Sample Output:
1                                                                       3
aa

Algorithm

1) calculate similarity value of string with each of its suffix, i.e if character at index i matches with 1st character calculate the similarity value for this suffix.
2) For calculating similarity value, start counter with 0 and keep counting until prefix of the given suffix matches with original string. if doesn't match break and return count.
3) Keep calculating sum by adding every count value returned.

If you have a different approach in mind, please share it in comments section.

Solution

#include<stdio.h>
#include<string.h>

int getSimilarity(char str[],int sub_ind,int st);

int main()
{
    int T,len=0,sum=0,i=0;
    char s[100001];
    scanf("%d",&T);
    while(T--)
    {
        sum=0;
        scanf("%s",s);
        int y=strlen(s);
        for(i=0;i<y;i++)
            if(s[i]==s[0])
            {
               
                sum=sum+getSimilarity(s,i,y);
            }
        printf("%d\n",sum);
    }
}

int getSimilarity(char str[],int sub_ind,int st)
{
    int g=sub_ind;
    int j, i=0;
    int count=0;
    for(i=g,j=0;i<st;i++)
        if(str[i]==str[j++])
        {
            count++;
        }
        else
            break;
    return count;  
}

Time Complexity
O(n*n), bcoz if first character of suffix matches with first character of original string then we calculate string similarity for this suffix with original string which takes O(n) time and there can be n such suffix matches.



Friday, 15 June 2012

InterviewStreet Flowers Challenge Solution : C++


InterviewStreet Flowers Challenge


Problem Statement


There are k friends who want to buy N flowers. Each flower has some cost ci. But there is condition that the price of flowers changes for customer who had bought flowers before. More precisely if a customer has already bought x flowers, he should pay (x+1)*ci dollars to buy flower number i. What is the minimum amount you have to pay to buy all N flowers?

Ex Input :                                       Output :
      3 3                                              13
      2 5 6


So first line contains n and k and next line contain ci, cost of ith flower.



Algorithm

1) Arrange all the cost in an increasing sequence...d1,d2..dn
2) Allot from end nth flower to friend 1, n-1 flower to friend 2 and so on..until k after which cost factor would be 2 and hence flower n-k would cost 2*d(n-k) to friend 1 and n-k-1 flower will cost 2*d(n-k-1) to friend 2 and so on until all flowers are bought by somebody.

If you have a different approach in mind, please share it in comments section.


Solution

#include<iostream>
#include<set>
using namespace std;


int main()
{
int n,k;
cin >> n >> k;
if(k > n) k=n;
int i,x;
multiset<int> s;
multiset<int>::iterator it;
for(i=0;i<n;i++) {
    cin >> x;
    s.insert(x);
}

//start calculating cost
int factor = 0;
unsigned long long int cost=0;
int count = 0;
it = s.end(); it--;
while(count!=n)
{
    if(count%k==0) factor+=1;
    cost+=(*it * factor);
    it--;
    count++;
}
cout << cost << endl;
cin >> cost;
}


Time Complexity

O(nlogn) to sort n cost numbers and O(n) to calculate the cost.
O(n+nlogn) => O(nlogn)
Hence time complexity will be O(nlogn)