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

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.

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 c_i. 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)*c_i 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)

Interviewstreet Median Challenge Part 2 Solution C++

InterviewStreet Median Challenge 

Problem Statement

The median of M numbers is defined as the middle number after sorting them in order, if M is odd or the average number of the middle 2 numbers (again after sorting) if M is even. Given an empty number list at first. Then you can add or remove some number from the list. For each add or remove operation, output the median of numbers in the list.

Example : For a set of m = 7 numbers, { 9, 2, 8, 4, 1, 3, 10 } the median is the third number in sorted set { 1, 2, 3, 4, 8, 9, 10 } which is 4. Similarly for set of m = 4, { 4, 1, 10, 3 }, the median is the average of second and the third element in the sorted set { 1, 3, 4, 10 } which is (3+4)/2 = 3.5  

Input: The first line contains n, the number of operations. The next n lines is either "a x" or "r x" which indicates the operation is add or remove.

Output: For each operation: output the median after doing the operation. If the operation is remove and the number x is not in the list, output "Wrong!" in a single line. If the result is an integer DO NOT output decimal point. And if the result is a double number, DO NOT output trailing 0s.

Other conditions:   0 < n <= 100,000 and for each "a x" or "r x" , x will fit in 32-bit integer.

Input:

7

r 1

a 2

a 3

a 2

r 2

r 3

r 2

Output:

Wrong!

2

2.5

2

2.5

2

Wrong!

Note: As evident from the last line of the input, if after remove operation the list becomes empty you have to print "Wrong!" ( quotes are for clarity ).

Algorithm

1) Use two multisets - first one will keep small n/2 numbers, minset and other one will keep next n/2 numbers, maxset.
2) For insert operation:
     if the number is greater than max of minset, add it to maxset
     else add it to minset
3) For remove operation:
     if the number is in minset, remove it
     else if number is in maxset, remove it
     else do nothing
4) After every insert/remove operation, adjust size of both sets i.e. make it n/2
     if(size-of-maxset > size-of-minset) remove first element from maxset and insert it in minset
     if(size-of-minset > size-of-maxset + 1) remove last element from minset and insert it in maxset
5) Calculate Median as..
     if(size of both minset and maxset is zero) No median
     else if (size of minset > size of maxset) max of minset is median
     else if (size of minset = size of maxset) avg of max of minset and min of maxset is median

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

Solution

// All test cased passed.

#include<iostream>
#include<set>

using namespace std;

int main()
{
int n;
cin>>n;
multiset<int> s1,s2;
int b; char c;
int flag = 0;
long long int median=0;
multiset<int>::iterator it;
for(int i=0;i<n;i++) {
    flag = 0;
    cin >> c >> b;
    if(c=='a') {
       if(s1.size() == 0) s1.insert(b);
       else {
          it = s1.end(); it--;
          int max = *it;
          if(b > max) s2.insert(b);
          else s1.insert(b);
       }
    }
    else if (c == 'r') {
       it = s1.find(b);
       if(it!=s1.end() && *it == b) s1.erase(it);
       else {
          it = s2.find(b);
          if(it!=s2.end() && *it == b) s2.erase(it);
          else flag = 1;
       }
    }
 
    // adjust size(make it n/2) of both two sets
    if(s2.size() > s1.size()) {
       it = s2.begin();
       s1.insert(*it);
       s2.erase(it);  
    }
    if(s1.size() > s2.size()+1) {
       it = s1.end();it--;
       s2.insert(*it);
       s1.erase(it);
    }
  
    // finding median
    if(flag == 1 || (s1.size() == 0 && s2.size() == 0))
      cout << "Wrong!\n";
    else if(s1.size() != s2.size()) {
       if(s1.size() > 0) {
         it = s1.end(); it--;
         cout << *it << endl;
       }
       else if(s2.size() > 0) {
         // program might not enter here
         it = s2.begin();
         cout << *it << endl;
       }
    }
    else if(s1.size()== s2.size()){
       it = s1.end(); it--;
       median = *it;
       it = s2.begin();
       median += *it;
       if(median%2==0)
              printf("%.0lf\n", median/2.);
       else
              printf("%.1lf\n", median/2.);
    }
    else cout << "Wrong!\n";
}


} 

Time Complexity:

Insertion : O(logn)
Deletion : O(logn)
Median : O(1)



View another algorithm for Median problem here:
justprogrammng.blogspot.in/2012/06/interviewstreet-median-challenge.html

Interviewstreet String Reduction Solution C++

Interviewstreet Challenge String Reduction

Problem Statement

You are given a string consisting of a, b, and c's and following operation is allowed: Take any two adjacent character and they can be replaced with third character. For ex: a and b with c, b and c with a. Find length of smallest string, the operation can be applied repeatedly.
Ex: for input bcab, bcab -> aab -> ac -> b the output will be 1

Input: T test cases and next T lines contain strings to start with.
Output: T lines containing length of smallest possible resultant strings after applying operations repeatedly and optimally.

Algorithm

Use brute force approach, For each string
1) If length of string is 1 return 1
2) if len is 2 and both character are same return 2
3) else try to find smallest possible string from all possible ways i.e for every two adjacent character replace it with third character and invoke reduce again on this new smaller string until smallest possible string is reached.
4) If the string achieved is smaller then previous possible smaller string store and update minimum length.

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

Solution

// all 10 test cases passed

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

int minimum=1;
int value=1;


private boolean reduce(String s1) {
char[] array=s1.toCharArray();
int len=array.length;
minimum =array.length;
boolean flag;
String cat;
if(len==1)
{
value=1;
return true;
}
else if(array[0]==array[1] && len == 2)
{
value=2;
return true;
}

for(int i=0;i<len-1;i++)
{
if(array[i+1]!=array[i])
{

String new_string

=Character.toString(array[i]).concat(Character.toString(array[i+1]));
char reduce =other(new_string);
String sub1="";
String sub2=Character.toString(reduce);
String sub3="";
if(i==1)
{
sub1=Character.toString(array[0]);
}else if(i>1)
{
sub1=s1.substring(0, i);
}
if(i+2<len-1)
{
sub3=s1.substring(i+2,len);
}else if(i+2==len-1)
{
sub3=Character.toString(array[i+2]);
}
cat=sub1+sub2+sub3;
flag=reduce(cat);
if(flag)
{
minimum=Math.min(minimum, value);
return flag;
}
}
}
return false;
}

private char other(String s1) {
char ret_value='b';
if (s1.equalsIgnoreCase("bc")|| s1.equalsIgnoreCase("cb")) {
ret_value='a';
}
else if (s1.equalsIgnoreCase("ab")|| s1.equalsIgnoreCase("ba")) {
ret_value='c';
}
return ret_value;
}
   
   
public static void main(String[] args) {
Scanner scan;
Solution obj = new Solution();
scan = new Scanner(System.in);
int T = scan.nextInt();
for (int i = 0; i < T; i++) {
String s1 = scan.next();
obj.reduce(s1);
System.out.println(obj.minimum);
}
}
       
}

Time Complexity

In a string of length n, there are n-1 2 character pairs, At max each of these pair would contain different character so for n-1 pairs we replace it with third character and call reduce again on new string of length n-1 which has n-2 pairs and so on....(n-1)*(n-2)*(n-3)..1 = (n-1)! times.
Surely it can be done in better way. If you find a better solution, update me.

Interviewstreet Median Challenge Solution C++

Interviewstreet Median Challenge

Problem Statement

The median of M numbers is defined as the middle number after sorting them in order, if M is odd or the average number of the middle 2 numbers (again after sorting) if M is even. Given an empty number list at first. Then you can add or remove some number from the list. For each add or remove operation, output the median of numbers in the list.

Example : For a set of m = 7 numbers, { 9, 2, 8, 4, 1, 3, 10 } the median is the third number in sorted set { 1, 2, 3, 4, 8, 9, 10 } which is 4. Similarly for set of m = 4, { 4, 1, 10, 3 }, the median is the average of second and the third element in the sorted set { 1, 3, 4, 10 } which is (3+4)/2 = 3.5  

Input: The first line contains n, the number of operations. The next n lines is either "a x" or "r x" which indicates the operation is add or remove.

Output: For each operation: output the median after doing the operation. If the operation is remove and the number x is not in the list, output "Wrong!" in a single line. If the result is an integer DO NOT output decimal point. And if the result is a double number, DO NOT output trailing 0s.

Other conditions:   0 < n <= 100,000 and for each "a x" or "r x" , x will fit in 32-bit integer.

Input:

7

r 1

a 2

a 3

a 2

r 2

r 3

r 2

Output:

Wrong!

2

2.5

2

2.5

2

Wrong!

Note: As evident from the last line of the input, if after remove operation the list becomes empty you have to print "Wrong!" ( quotes are only for clarity and not to be printed).

 

Algorithm

Idea is to use previous median value and pointer to find new median value instead of recalculating at every add or remove operation.

1) Use multiset which always keep elements in order and allow duplicates. In other words maintain sorted list somehow.

2) Let 'prev' pointer point to previous median value for odd size-of-set or 2nd element used to calculate average in case of even size-of-set and Let b be the element that will be inserted/deleted 

from the set.

2) If the operation is add

    2.1) Insert this element into set and then calculate the median

    2.2) if the size of set is 1 then first element will be the median

    2.3) else if b >= *prev and size-of-set is even now, increment prev to point to 2nd element for 

            this median

    2.4) else if b < *prev and size-of-set is odd now, decrement prev to point to new median.

3) If the operation is remove

    3.1) First calculate the new median then remove the element.

    3.2) If the size of set is 0 can't remove.

    3.3) else if the element doesn't exist in set then also can not remove.

    3.4) else if b = *prev and size of set is odd  increment the pointer to point to 2nd element
            for new median else if size is even and previous to prev and prev are both same element
            then do nothing else decrement the pointer to point to new median.

    3.5) else if b>=*prev && s.size()%2 == 0 decrement the prev pointer.

    3.6) else if b<=*prev && s.size()%2 != 0 increment the prev pointer.

    3.6) Now you can remove the element.

Solution

This solution is correct now. All test cases passed.

You can also have a look at another blog in which I have posted another good approach to solve this problem using two multisets unlike using one multiset as in this solution. Have a look here  http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge-part-2.html.


// All test cases passed
#include<iostream>
#include<set>

using namespace std;

int main()
{
int n;
cin>>n;
multiset<int> s;
int b; char c;
long long median=0;
static multiset<int>::iterator it, prev,temp;
for(int i=0;i<n;i++) {

    cin >> c >> b;
    
    if(c=='a') {
        s.insert(b);
        if(s.size()==1) prev = s.begin();
        else if(b >= *prev && s.size()%2 == 0) prev++;
        else if(b < *prev && s.size()%2 != 0) prev--;
    }         
    else if(c=='r' && s.size() > 0) {
        it = s.find(b);
        if(it == s.end() || *it != b) { cout << "Wrong!\n"; continue;}
        else if(*prev == b) {
           if(s.size()%2 != 0) prev++;
           else {
              temp = prev; temp--;
              if(*temp != b) prev--;
           }   
        }
        else if(b>=*prev && s.size()%2 == 0) prev--;
        else if(b<=*prev && s.size()%2 != 0) prev++;
        s.erase(it);                      
    }
    
    // to print median
    if(s.size()==0) cout << "Wrong!\n";
    else if(s.size()%2!=0) cout << *prev << endl;
    else {
          median = *prev;
          prev--;
          median = (median+*prev);
          if(median%2==0)
              printf("%.0lf\n", median/2.);
          else
              printf("%.1lf\n", median/2.);
          prev++;
    }
}


}   

Time Complexity

Insertion - O(logn)
Deletion - O(logn)
Median - O(1)

n number of inputs each either add or remove x, in multiset(c++) for insertion/remove  O(logn) and O(1) to calculate new median. So total time complexity O(n*logn) where n is no of inputs plus max possible element in set also.



Another better way to do the same problem using 2 multisets....which will also work for all test cases..... http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge-part-2.html.

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.