CareerCup

Java:
=====================

public String sortByD(String s, List<Char> dict){
	String output = "";
	HashMap<Char, String> map = new HashMap<Char, String>();
	for (Char c : dict)
		m.put(c,"");
	for (int i = 0; i < s.length(); ++i)
		m.put(s.charAt(i),m.get(s.charAt(i))+s.charAt(i));
	for (Char c : dict)
		output += m.get(c);
	return output;
}

string sort_by_dict(const string & str, const string & dict)
{
int map[256] = {0};
for(int i = 0; i < str.length(); i++)
map[str[i]]++;
string result = str;
int index = 0;
for(int i = 0; i < dict.length(); i++)
{
char c = dict[i];
while(map[c] > 0)
{
result[index++] = c;
map[c] --;
}
}
return result;
}

A very elegant way of doing this is to substitute 'a' for the letter that comes first as per the dictionary, 'b' for the letter that comes second, and so on. Then sort normally by lexicographical order (possibly using an existing library). Then, reverse the letter substitution.

int array [26];
//assuming we are only using characters...this can be easily extended to any character
for(int i=0;i<str.length;i++){
int shiftValue = str.charAt(i) - 'a';
array[shiftValue] +=1;
}
//assuming dictonary is also an String and is sorted according to the rule
for(int i=0;i<dict.length;i++){
int findValue = dict.charAt(i) - 'a'
if (array[findValue] > 0){
syso ( (char) (array[findValue] + 'a');
}
}

Better approach would be to create a two dimensional ordering table from dictionary, and use that table for comparing two characters when sorting.

For example
a b
-----------
a | 0 1
b | 0 0
when compare(a,b) is required, we will return the corresponding value (1 in this case) to the sorting fuction.

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


int main()
{
//sort 26 chats from A-Z using "counting sort"
//time complexity O(n)

string input("SHEEP");
string ruler("PSEH");
vector<int> C(256,0), C_prime(256,0);//use ASCII code as index for counting array
string result=input;

//create counting auxilliary array called "C", it counts frequencies for each char
for(string::const_iterator p=input.begin();p!=input.end();p++){
C[int(*p)]++;
}

//convert C to C_prime (Auxilliary array)
int count=0;
for(string::const_iterator p=ruler.begin();p!=ruler.end();p++ ){
count += C[int(*p)];
C_prime[int(*p)]=count;
}

// input --> C_prime --> result mapping
for(string::const_iterator p = input.end()-1;p>=input.begin();p--){
result[C_prime[int(*p)]-1] = *p;
C_prime[int(*p)]--;
}

// output the sorted array : "PSEEH"
cout<<result<<endl;

return 0;
}

My idea is that we just use modified count sorting algorithm: Just change the accumulating processing according to the order of dictionary, not by the alphabet order. The following code would assume the string is 'a'-'z' and 'A'-'Z', and the Dict should contains all the alphabet char existing in the input strings.
Here is the code:

#include <stdio.h>
static  int getCharIndex(char c)
{
      if(c>='a'&&c<='z')
      {
        return c-'a';
      }else if(c>='A' && c<='Z')
      {
        return 'z'-'a'+1+c-'A';
      }else
      {
        /*error Here*/
        return -1;
      }
}
void  dictsort(char*pStr, char*pDst, char*pDict)
{
    int       charCnt[52];
    int       temp, temp2, len;
    if(NULL==pStr||0==*pStr||NULL==pDict||0==*pDict||NULL==pDst)
      return;
    memset((void*)charCnt, 0, sizeof(charCnt));
    /*Counting the number */
    for(len=0;*pStr;pStr++, len++)
    {
      temp2=getCharIndex(*pStr);
      if(0>temp2)
        return;
      charCnt[temp2]++;
    }
    printf("finished the counting\n");

    /*Accumulating now*/
    for(temp=-1;*pDict;pDict++)
    {
      temp2=getCharIndex(*pDict);
      if(0>temp2)
        return;
      charCnt[temp2]+=temp;
      temp=charCnt[temp2];
    }
    printf("finsihed the accumlating\n");
    /*Now we are going to sorting*/
    pDst[len]=0;
    for(; len; len--)
    {
      --pStr;
      temp2=getCharIndex(*pStr);
      if(0>temp2)
        return;
      pDst[charCnt[temp2]]=*pStr;
      charCnt[temp2]--;
    }
    printf("finished sorting\n");
    return;
}

inputString = 'SHEEP'
sortDict = 'PSHE'

for sortChar in sortDict:
	for char in inputString:
		if char == sortChar:
			print char

why cant we just reuse normal sorting and overload the comparator to compare according to the new dictionary ??

In C#

public void SortWithDict(string input, List<char> dict)
        {
            Console.WriteLine("Input = {0}", input);
            Console.Write("Output = ");
            foreach (char c in dict)
            {
                for (int i = input.Length - 1; i >= 0; i--)
                {
                    if (c == input[i])
                    {
                        Console.Write(c); // or store it into a list
                        input.Remove(i, 1);
                    }
                }

                if (input.Length == 0)
                    break;
            }

            Console.WriteLine();
        }

#include <stdio.h>
#include <stdlib.h>
#define SIZEOF(a) sizeof(a) / sizeof((a)[0])

char order[26];

void generateOrder(char dict[])
{
    int i=0;
    for(i=0;i<26;i++)
    {
        order[ dict[i] - 'a' ] = i;
    }
}
int position(char x)
{
    return order[x-'a'];
}
int compare(void *a,void *b)
{
    return position( *(char *)a) -  position (*(char *)b );
}
int main(void) {
    
	char dict[26] = {      'p','a','b','d','e',
                           'f','g','h','i','j',
                           'k','l','m','n','o',
                           'c','q','r','s','t',
                           'u','v','w','x','y',
                           'z'};
	
    
    generateOrder(dict);
    
    char str[6] = "sheep";
    qsort(str,SIZEOF(str),sizeof(char),compare);
    printf("%s",str);
	return 0;
}

void sortString(string &word, const string &dictionary) {

	map<char, int> m;
	for (int i=0; i<word.size(); i++) {
	map<char, int>::iterator it = map.find(word[i]);
	if (it == map.end()) word.insert(pair<char, int>(word[i], 1));
	else it->second += 1;
}
int k = 0;
for (int i=0;i<dictionary.size()) {
	map<char, int>::iterator it = map.find(dictionary[i]);
	if (it != map.end()) {
		word.replace(word.begin()+k, it->second, dictionary[i]);
		k += it->second;
}
}
return;
}

inputString = 'SHEEP'
sortDict = 'PSHE'

from collections import Counter

count_str = Counter(inputString)
b=''
for c in sortDict:
	b = count_str[c] * c

return b

public class Test {

public static void main(String[] args){

String input = "sheep";

char[] arr = input.toCharArray();

char temp;

for(int i=0;i<arr.length;i++){

for(int j=i+1;j<arr.length;j++){

if(arr[i] > arr[j]){

temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

}
}
}
for(int i=0;i<arr.length;i++)
System.out.println(arr[i]);
}
}

What do you guys think about this:
public String sortByString(String input, String sortBy) {
if (input == null)
return "";//Maybe throw exception here?
if (sortBy == null)
return "";//Maybe throw exception
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
String stringToReturn = "";
for (int i = 0; i < input.length(); i++) {
if (hashMap.get(input[i]))//already in so increment the value
hashMap.put(input[i], hashMap.get(input[i]) + 1);
else
hashMap.put(input[i], 1);
}
for (int i = 0; i < sortBy.length(); i++) {
if (hashSet.get(sortBy[i]))
for (int j = 0; j < hashSet.get(sortBy[i]); j++)
stringToReturn += sortBy[i];
}
return stringToReturn;
}

public String sortByString(String input, String sortBy) {
	if (input == null)
		return "";//Maybe throw exception here?
	if (sortBy == null)
		return "";//Maybe throw exception
	HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
	String stringToReturn = "";
	for (int i = 0; i < input.length(); i++) {
		if (hashMap.get(input[i]))//already in so increment the value
			hashMap.put(input[i], hashMap.get(input[i]) + 1);
		else
			hashMap.put(input[i], 1);
	}
	for (int i = 0; i < sortBy.length(); i++) {
		if (hashSet.get(sortBy[i]))
			for (int j = 0; j < hashSet.get(sortBy[i]); j++)
				stringToReturn += sortBy[i];
	}
	return stringToReturn;
}

What will be the output of:
char c[]={‘a’,’e’,’i’,’o’,’u’};
for(int i=0;i<2;i++)
System.out.println((char) (c[i]+1));

What will be the output of:
char c[]={‘a’,’e’,’i’,’o’,’u’};
for(int i=0;i<2;i++)
System.out.println((char) (c[i]+1));