CareerCup

1. Have a array [0-26]. This will initially have 0's
2. Traverse through Array A. And increment counters of the array we have, when we encounter respective values.
3. Similarly traverse Array B.
4. Now traverse the array and print the construct the new Array or print the output.

It will take O(n) time and O(n) space.

count sort

//
//  main.cpp
//  MergeCharArrays
//
//  Created by Srikant Aggarwal on 09/01/12.
//  Copyright 2012 NSIT. All rights reserved.
//

#include <iostream>

using namespace std;

int main (int argc, const char * argv[])
{

    int n, m;
    int i = 0;
    
    cin >> n >> m;
    
    char *A = new char[n];
    char *B = new char[m];
    
    char temp[26] = {0};
    
    while(i < n)
    {
        cin >> A[i];
        temp[A[i] - 'a']++;
        i++;
        
    }
    
    i = 0;
    while(i < m)
    {
        cin >> B[i];
        temp[B[i] - 'a']++;
        i++;
    }
    
    char *C = new char[n+m];
    i = 0;
    int index = 0;
    
    while(i < 26)
    {
        int j = temp[i];
        
        while(j > 0)
        {
            C[index] = i+'a';
            index++;
            j--;
        }
        
        i++;
    }
    
    i = 0;
    while(i < (n+m))
    {
        cout << C[i] << " ";
        i++;
    }
    
    return 0;
}

the merge step of merge sort can be used.

Unless the two arrays are sorted, how can this be done in O(n)?

If one of the arrays have space equal to 2N (size of first array + size of second array), then we can use the following algorithm:

1. Place a pointer at the end of both the arrays. Here 'end' refers to the last element in each array that has a character (remember that one of the arrays will have empty space since its 2N).

2. Place another pointer at the end of 2N (this will be the write pointer).

3. Then simply pick the character from the larger of the two characters from the array (using the pointer in step 1).

4. Whichever array you picked the character from, decrement the pointer in that array and also decrement the write pointer (from Step 2).

You are done in O(2N) = O(N) time.

If both the arrays are of size O(N) - that is no empty space, then simply use count sort, while scanning both arrays. You will need a temporary 'aux' array, so if the question demands O(1) space, then we will need some smart strategy.

void mergeAndSortTwoArrays(vector<char> &str1,
vector<char> &str2, vector<char> & str3)
{
int flag[26];
for (int i=0;i<26;i++)
{
flag[i] =0;
}
for (int i=0;i<str1.size();i++)
{
++flag[str1[i]-'a'];
}
for (int i=0;i<str2.size();i++)
{
++flag[str2[i]-'a'];
}
for (int i=0;i<26;i++)
{
for (int j=0;j<flag[i];j++)
{
str3.push_back('a'+i);
}
}
}

#include<iostream.h>
#include<stdlib.h>
int main()
{
char a[]={'a','v','s','w','a','v','n'};
char b[]={'q','r','y','i','s','f'};
int ar[26]={0};

for(int i=0;i<7;i++)
{

ar[a[i]-'a']++;


}

for(int i=0;i<6;i++)
{

ar[b[i]-'a']++;


}




cout<<"\n\n";
int k=0;
char c[6+7];
for(int i=0;i<26;i++)
{
if(ar[i]>0)
{
for(int j=0;j<ar[i];j++)
{
//char l=i;
c[k]=i+'a';
cout<<" [ "<<c[k]<<" ] ";
k++;
} }}
char c1;
cin>>c1;
}


a better solution