CareerCup

Algorithm:
1. store array1 in HashMap better to use LinkedHashMap and insert elements as in array1 example B, A, C
2. scan through array2 and increment the count for each B, A , C
3. and read HashMap/LinkedHashMap using array1 keys and print

it looks like we could use the count sort, the complexity should be linear

Instead of Array.IndexOf I should have used Hashtable to make the complexity O(n).
Otherwise this is sorting based on the first array and adding extra elements(whose order is unknown) to the end.
Any improvements?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace SortArrayUsingDiffRule
{
    class Program
    {
        static char[] arr = new char[] {'B','A','C'};
        static char[] Sort = new char[] {'D', 'A', 'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A' };        
        static int[] Count = new int[arr.Length];
        static List<char> Extras = new List<char>();
        static void Main(string[] args)
        {
            for (int i = 0; i < Sort.Length; i++)
            {
                int index = Array.IndexOf(arr, Sort[i]);
                if (index != -1)
                {
                    Count[index]++;
                }
                else
                {
                    Extras.Add(Sort[i]);
                }
            }

            int j = 0;
            int k = 0;
            while(j<Count.Length)
            {
                while (Count[j] > 0)
                {
                    Sort[k]=arr[j];
                    Count[j]-- ;
                    k++;
                }
                j++;
            }
            for (int i = 0; i < Extras.Count; i++)
            {
                Sort[k++] = Extras[i];
            }
        }
    }
}

Pseudocode

orderArray = {"C","A","B"}
inputArray={"A", "C", "B", "B", C, A, B, C, C, A, A, B, A B, C B B}

create a counterarray of size orderArray

for each element in inputArray
     counterarray[index of element in orderarray] ++ ; // assume no other inputs
end for

print orderArray[i] element countarray[i] times

Should be O(n) (unless the remainder array needs to be resorted (you can shift those to end and run quicksort)

The answer which interviewer will be looking for will be of O(size of a1)(sizeofa2)

If the sorting needs to be done based on only 3 character in a1, ideal solution is to go with 3 colored problem, wherein we sort the number based on 4 pointer. The algorithm says that any char that belongs to type 1 should go to initial part of array and type 3 should go towards end.

Code to explain this is as follow

private static char[] sortSecBasedOnFirst(char[] a1, String str) {
			int len = str.length();
			char[] output = new char[len];
			Map<Character, Integer> map = new HashMap<Character, Integer>();
			int index = 1;
			for(char c : a1){
				map.put(c, index++);
			}
			int indexForFirst = 0;
			int indexForMiddle = 0;
			int indexForLast = len - 1;
			int indexForDefault = len -1;
			for(int i = 0; i < len ; i++){
				char c = str.charAt(i);
				Integer ind = map.get(c);
				if(ind == null ){
					ind = -1;
				}
				switch (ind) {
				case 1:
					output[indexForMiddle++] = output[indexForFirst];
					output[indexForFirst++] = c;
					
					break;
				case 2:
					output[indexForMiddle++] = c;
					break;
				case 3:
					output[indexForLast--] = c;
					break;
					
				default:
					output[indexForLast-- ] = output[indexForDefault];
					output[indexForDefault--] = c;
					break;
				}
			}
		return output;
	}

public class CountingSortAlpha {

	public static char[] sort(char[] a, char[] b) {
		char[] c = new char[a.length];
		char[] ref = new char[b.length];
		
		for (char ch : a) {
			for(int i = 0; i < b.length; i++)
				if (ch == b[i]) {
					ref[i]++;
					break;
				}
		}
		
		for(int i = 1; i < ref.length; i++)
			ref[i] += ref[i - 1];
		
		for(int i = a.length - 1; i >= 0; i--) {
			c[ref[index(a[i], b)] - 1] = a[i];
			ref[index(a[i], b)]--;
		}
		
		return c;
	}
	
	private static int index(char ch, char[] b) {
		for (int i = 0; i < b.length; i++)
			if (b[i] == ch)
				return i;
		return 0;
	}
	
	public static void main(String args[]) {
		char[] a = {'A', 'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A'};
		char[] b = {'B', 'A', 'C'};
		for (char c : a)
			System.out.print(c + " ");
		System.out.println();
		char[] c = sort(a, b);
		for (char ch : c)
			System.out.print(ch + " ");
		System.out.println();
	}
}

Hi this solution could be easy adding to the solution :
public class Arry_Sort {
public static void main(String args[]){

char[] array1 = {'B', 'A', 'C'};
char[] array2 = {'A', 'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A'};

for(int i=0;i<array1.length;i++){
for(int j=0;j<array2.length;j++){

if(array1[i]==array2[j]){
System.out.print(array2[j]);
}
}

}

}

}

function sort_rule($rule,$subject) {
	$rule_length = count($rule);
	$subject_length = count($subject);
	$pos_to_insert = 0;
	$temp = '';

	for($i=0; $i<$rule_length; $i++) {
		for($j=$pos_to_insert; $j<$subject_length; $j++) {
			if($subject[$j]==$rule[$i]) {
				$temp = $subject[$pos_to_insert];
				$subject[$pos_to_insert] = $subject[$j];
				$subject[$j] = $temp;
				$pos_to_insert++;
			}
		}
	}
	
	print_r($subject);
}

sort_rule(['B','A','C'],['A','B','A','C','A','B','B','C','A']);

import java.lang.*;
public class ArraySort {
public static void main(String[] args) {
char[] ch1= {'A', 'B', 'A', 'C', 'A', 'B', 'B', 'C', 'A'};
char[] ch2= {'A', 'B', 'C'};
char[]ch3=new char[ch1.length];
int k=0;
for (int i=0;i<ch2.length;i++){
for(int j=0;j<ch1.length;j++){
if((Character.toUpperCase(ch2[i])==Character.toUpperCase(ch1[j]))){
ch3[k]=ch1[j];
k++;
}}}
System.out.println(ch3);}}

my @arr = (B,A,C);
my @array = (A,B,C,C,A,B,B,A,C);
my @sort;
my $i=0;
for($i=0;$i<scalar(@arr);$i++)
{
push @sort, grep { $_ eq $arr[$i] } @array;
}
print "Array: @sort \n";

import java.util.Arrays;
import java.util.Comparator;




public class CompareCharacter implements Comparator<Character> {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

Character[] c={'A','B','A','C','A','B','B','C','A','F','D','T'};
Arrays.sort(c, new CompareCharacter());
//System.out.println(c);
for (Character each : c)
{
System.out.println(each);
}




}

@Override
public int compare(Character o1, Character o2) {
if ((o1=='A' || o1== 'a') && (o2=='B' || o1== 'B')) return 1;
else if ((o1=='B' || o1== 'b') && (o2=='A' || o1== 'a')) return -1;
else {
return o1.compareTo(o2);
}

}

}

import java.util.ArrayList;
import java.util.List;


public class OddIntegerArray{
	public static void main(String[] args){
		int[] a={1,2,2,4,1,3,6,6,6,7,7,7,7,7};
		List aList1=new ArrayList();
		List aList2=new ArrayList();
		int j=0,k=0;
		for(int i=0; i<a.length; i++) {
			if(aList1.contains(a[i])){
				k=aList1.indexOf(a[i]);
				j=(Integer) aList2.get(k);
				aList2.remove(k);
				aList2.add(k, j+1);
			}
			else{
				j=aList1.size();
				aList1.add(j, a[i]);
				aList2.add(j, 1);
			}
		}
		
		for(int i=0;i<aList2.size();i++){
			int a1=(Integer) aList2.get(i);
			if((a1%2)!=0){
				System.out.println(aList1.get(i));
				
			}
			
		}

	}

}

public static void main(String[] args) {
// TODO Auto-generated method stub

int[]a=new int[]{1,2,2,4,1,3,6,6,6,7,7,7,7,7};
int b[]=new int[]{1,2,4,3,6,7};
int[]res=new int[a.length];
int i,j,k=0;
for(i=0;i<b.length;i++)
{
for(j=0;j<a.length;j++)
{

if(b[i]==a[j])
{
res[k]=a[j];
k++;
}
}

}
for( k=0;k<res.length;k++)
System.out.println(res[k]);
}

cannot understand what you want in output

1. hash in the range of 1 to length of array1
B => 3
A => 2
C => 1

2. Quick sort array2 with comparison based on hashed value of character.

complexity : O(n) + O(nlogn)

STL sort algorithm can be used with third parameter providing a "less" function which does:

bool less(char &a, char &b)
{
    return if index of a in the "ordering" vector is less then index of b in the "ordering" vector
}