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)

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".

Sorted array rotated unknown times, find an element Interview Question

Sorted array has been rotated unknown times, find an element in it

Amazon Interview (April 2012)

Problem Statement

A sorted array has been rotated for unknown no of times, find an element in it in O(logn). Write production ready and bug free code.
Ex if {2,4,6,8,10} is rotated 2 times it becomes{6,8,10,11,2,4}

Solution 

#include<stdio.h>

int find(int a[], int l, int r, int x);

int main()
{

int arr[6] = {6,8,10,11,2,4};
printf("%d",  find(arr,0,5,2));
scanf("%d", arr[0]);

}

int find(int a[], int l, int r, int x) {

while(l <= r) {

    int m = (l+r)/2;
   
    if(a[m] == x) return 1;
   
    if(a[l] <= a[m]) {
       if(x > a[m])
          l = m+1;
       else if(x >= a[l])
          r = m-1;
       else l = m+1;
    }
   
    else {
   
        if (x < a[m])
          r = m-1;
        else if (x <= a[r])
          l = m+1;
        else r = m-1;       
    }
}

return 0;
}


//If you have a different approach in mind, please share it in comments section for our readers.

Time Complexity

O(logn) for  array size is reduced by half every time one enters loop.

find all anagrams of a word in a file, Java Code : Amazon Interview

Find all anagrams of a word in a file 

Amazon Interview (Dec 2011)

Problem Statement

Find all anagrams of a word in a file. Input -  only file name and word. Output - all set of word in file that are anagrams of word. Write production quality code.

Algorithm

1) Use a hashmap with string as key and list<string> as value where list of strings contain all anagrams of a key string.
2) For each word in the file, find beta string which is its sorted version ex abd is sorted version of bad, adb and dba. Put this word to that list whose key is this beta string. If it does not exist then create a new list with the beta string as key in map.
3) Finally print all strings from the list whose key is the input word(sorted/beta string).

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

Solution

import java.util.*;
import java.io.*;

public class Anagram {
    public static void main(String[] args) {
    String beta = args[1];

        try {

            Map<String, List<String>> m = 

                   new HashMap<String, List<String>>();

            Scanner s = new Scanner(new File(args[0]));
            while (s.hasNext()) {
                String word = s.next();
                String alpha = sorting(word);
                List<String> l = m.get(alpha);
                if (l == null)
                    m.put(alpha, l=new ArrayList<String>());
                l.add(word);
            }

         List<String> l = m.get(sorting(beta));
       Object[] arr = l.toArray();
           for (int i=0; i < arr.length; i++)
                System.out.println(arr[i]);

        }
    catch (Exception e) {
            System.out.println(e);
            System.exit(1);
        }

    }

    private static String sorting(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a);
        return new String(a);
    }
}

Time Complexity

O(n) for visiting each word in file once. You can't do it actually in O(n) if you consider the time complexity involved in sorting each word.
If you consider that time complexity involve with sorting also, then you should know that java uses quicksort algorithm to sort char array for which time complexity is O(mlogm) and I have applied sorting function in my code to each word of file .Therefore the time complexity would be O(n*mlogm), where longest word has length m.

Replace all spaces in a string by %20. Amazon Interview

Replace all spaces in a string by %20.

Amazon Interview (Jan 2012)

Problem Statement

Replace all spaces in a string by %20. Write production quality code in first attempt  

Algorithm

1) Move along the string and count no of spaces.

2) New string length would be old string length + 2*no of spaces.

3) Start transferring characters from old string to new string and where ever there is space replace it with %20 as asked in question else transfer character as it is to new string. 

4) Finally put a '\0' character in end  of the new string.

Solution

// Replace all spaces in a string by %20.
// Write production quality code in first attempt.

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

int main()
{

char str[100];
//syntax to scan string till new line in C
scanf("%[^\n]", str);

int len = strlen(str);
int i,count=0,k=0;
for(i=0;i<len;i++)
    if(str[i]==' ') count++;
   
char newstr[len+2*count];
for(i=0;i<len;i++)
{
    if(str[i]==' ') {
        newstr[k++] = '%';
        newstr[k++] = '2';
        newstr[k++] = '0';
    }
    else
        newstr[k++] = str[i];
}
newstr[k] = '\0';
printf("%s\n", newstr);

}

Time Complexity

O(2n) <==> O(n) since we move pointer along string twice.

Merge two special arrays O(n) Code

Merge two special arrays with given conditions. 

Amazon Interview (May 2012).

 

 Problem Statement

Given two arrays having some elements in common, write a program to merge them such that all the elements occurring before common elements in both arrays also lie before common elements in merged array also and common element occurs only once in merged array.
Array can contain both alphabets and integers.
The elements lying before common element of both arrays can appear in any order in merged array.
Write a O(n) time complexity code.
Ex. A = [z,a,b,c,d,e,f]
       B = [k,g,a,h,b,f]
   Ans = [z,k,g,a,h,b,c,d,e,f]

Algorithm

1) Put elements of one array in hash-table.
2) Start incrementing pointer in 2nd array from 1 to n, if the element lie in hash-table put all elements before it in 1st array into the merged array else put this element into merged array.
3) Put any remaining elements into the merged array

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

Solution

import java.util.Map;
import java.util.HashMap;

class Solution
{

public static void main(String arg[])
{
char a[] = arg[0].toCharArray();
char b[] = arg[1].toCharArray();
char c[] = new char[a.length+b.length];
merge(a,b,c);
String s = new String(c);
System.out.println(s);
}

private static void merge(char a[], char b[], char c[]) {

Map<Character, Integer> m1 = new HashMap<Character, Integer>();

int i,j,k,l;

for(i=0;i<a.length;i++)
    m1.put(a[i],i);
       
l=0;i=0;j=0;
while(j<b.length) {
   
    if(m1.containsKey(b[j])) {
   
        k = m1.get(b[j]);
        while(i<=k)
            c[l++] = a[i++];
        j++;
    }
    else c[l++] = b[j++];
}
while(i<a.length)
    c[l++] = a[i++];
   
}
}   

Time Complexity: 

O(2n+m) where n is size of first array and m is size of second array. We travel first array twice once while putting its elements into merged array and second time while merging, therefore 2n for first array.



If you find this blog somewhat helpful, please give a +1.

Tree Longest Path: O(n) C code

Longest path between any two nodes of a Binary Tree

Amazon Interview (May 2012)

Problem Statement

Find the length of longest path between any two leaf nodes of a binary tree. Actually leaf nodes are at maximum distance so its okay to say nodes as well as leaf nodes.

Solution 1: 

// O(n*n) code

int longestPath(node *root)
{

   if(root==NULL)
     return 0;

   int left_height=0, right_height=0;
   int left_max=0, right_max=0;
  
   left_height = height(root->left);
   right_height = height(root->right);

   left_max = diameter(root->left);
   right_max = diameter(root->right);

   int temp = max(left_max,right_max);
  
   return max(temp, left_height+right_height);
}

int height(node* root)
{
   if(root == NULL)
       return 0;
   return 1 + max(height(root->left), height(root->right));
}

Solution 2:

 // O(n) code

// In this code we take adv of pointer and calculate the height in same recursion rather than 

// calling height separately as in Solution 1.

int longestPath(node *root, int *h) {

    int left_height=0, right_height=0;
    int left_max=0, right_max=0;
   
    if(root==NULL) {
      *h=0;
      return 0;
    }
   
    left_max=longestPath(root->left,&left_height);
    right_max=longestPath(root->right,&right_height);
   
    *h=max(left_height,right_height)+1;
   
    int temp = max(left_max,right_max);
   
    return max(temp, left_height+right_height);
   
}


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

Time Complexity:

1. O(n*n) - For each node (total n nodes) we calculate height which takes further O(n) time.
   So total time complexity O(n*n).
2. O(n) - We visit each node only once. So time complexity O(n).

If you find this blog somewhat helpful, please give a +1.

Compress a string aaabbbcc into a3b3c2 : O(n) C code

Amazon Interview: String Compression

Problem Statement

Given a string "aaabbbcc", compress it, = "a3b3c2" . Given that output string's length is always smaller than input string, you have do it inplace. No extra space like array should be used.

Solution

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

void compress(char *str,int len, int act);
char str[100];
int length;

int main()
{
scanf("%s",str);
length=strlen(str);
//compression
//we need a recursive sol so that
//cases like abbbccc or abcccc are also taken care of
compress(str,0,0);
printf("%s",str);
scanf("%d",&length);

}

//recursive code - prefered
void compress(char *str,int len, int act) {

if(len<length) {
    int k=len;
    int count=0;
    int c, n;
    while(str[k]==str[len]){
        len++; count++;
    }
    n = 0;
    c=count;
    do {
        c /= 10;
        n++;
    } while (c != 0);
   
    compress(str,len,act+n+1);
   
    str[act]=str[k];
    if(k+count==length)
       str[act+n+1]='\0';
    for(c=0;c<n;c++) {
        str[act+n-c]=(count%10)+48;
        count=count/10;
    }

}
return;
}


Time Complexity:  O(n)


If you found this blog somewhat helpful, please share it and Keep Visiting.....:)

Longest path between two nodes in a graph Amazon Problem : C code

Finding longest path between two nodes in a graph

Problem Statement 

Write algorithm/code to find longest path between any two cities. 4X4 matrix was given. If there is no connectivity between two cities then the distance between them was given as -1. Its cyclic graph.

Solution

Finding longest path between two nodes in a graph is an NP Hard problem. So, we should not try to find a polynomial solution to this problem. As you can see the given problem is of very small size. So even brute force is acceptable.

#include<stdio.h>

int longestPath(int node);

int matrix[4][4] = {{0,1,2,3},{1,0,1,1},{2,1,0,5},{3,4,3,0}};

int main()
{
printf("%d",longestPath(0));
}

int longestPath(int node) {

int dist=0,max=0,i;
for(i=node+1;i<4;i++) {
    dist=0;
    if(matrix[node][i]>0) {
        dist+=matrix[node][i];
        dist+=longestPath(node+1);
    }
    if(max<dist)
        max=dist;
}
printf("%d\t",max);
return max;
}

 

Time Complexity 

Let there be n cities. Given starting city as S and destination city as D. We are left with n-2 cities.
There are approximately 2^(n-2) * (n-2)! ways for reaching D from S.
Find length of all these ways and choose the smallest one.



The other problem of finding longest path is "Find longest path between any two nodes of a tree". Click any where on this line to see the problem.

 

 

 If you find this blog somewhat helpful, please share & Keep Visiting...:)

Find Longest Palindrome in a string : O(n*n) C code

  Given a string S, find the longest palindromic substring in S.

For example,
S = “caba".

The longest palindromic substring is “aba”.

Algorithm:

1. Palindrome mirrors around center and there are 2N-1 such centers in string. The reason is center of palindrome can be in between two letters(for even length string) or the letter itself (for odd length string).
2. Expand a palindrome around its center in both direction and look for maximum possible palindrome (O(n) time).
3. If the length of string is odd, the center would be letter, therefore repeat the step 2 for each letter and update maximum palindrome on the way.
   
4. If the length of string is even, the center would be between two letters, therefore repeat the step 2 for each such center and update the maximum palindrome on the way.
5. Since there are O(N) such centers, time complexity would be O(n²).

// O(n*n) time complexity and O(1) space algorithm
#include<stdio.h>
#include<string.h>

void longestpalindrome(char *str);

int main()
{
char *str = "abacba";
int i;
longestpalindrome(str);
scanf("%d", &i);
}

void longestpalindrome(char *str) {

int length = strlen(str);
printf("%d\n", length);
int i,j,k;
int start,end,max=0,curr;

if(length == 0) {printf("string null"); return;}

if(length%2!=0) { //if string is of odd length
    for(i=0;i<length-1;i++) {
        j=k=i;
        while(j>0 && k<length-1 && str[--j]==str[++k]); 
        curr = k-j+1;
        if(curr > max) {
           max = curr;
           start = j;
           end = k;
        }
    }
    for(i=start;i<=end;i++) printf("%c", str[i]);
    printf("\n");
}
else { //if string is of even length
    for(i=0;i<length-1;i++) {
        if(str[i]==str[i+1]) {
            j=i;
            k=i+1;
            while(j>=0 && k<=length-1 && str[j--]==str[k++]);
                    curr = k-j-1;
                    if(max < curr) {
                       max = curr;
                       start = j+1;
                       end = k-1;
                    }
        }
        for(i=start;i<=end;i++) printf("%c", str[i]);
        printf("\n");
    }
}
}
  
                         
           

// Time Complexity: O(n²)

// Space Complexity: O(1)