Google Interview Question
Country: United States
Why not just store an integer count of each letter? That would use less space and be more efficient time-wise as well.
I think it's equivalent. You would win a little during the second loop but then loose some during the third loop where you have to append the char for every count of your integer.
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;
}
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;
}
Here is the test code:
int main()
{
char pSrc[]="aadfadfiagaflagagafaggsdfsdfsdipoqpeidkdjhbcdefghijklmnopqrstuvwxyzAiafadfBDDGBADDSEFHCDEFGHIJKLMNOPQRSTUVWXYZ";
// char pSrc[]="abcABC";
char pDst[256];
char pDict[]="ZYXWVUTSRQPONMLKJIHGFEDCBAabcdefghijklmnopqrstuvwxyz";
// char pDict[]="cbaABDC";
dictsort(pSrc, pDst, pDict);
printf("src %s dict %s ==> dst %s\n", pSrc, pDict, pDst);
}
Test Results:
amb-sw2 a5m 107% ./a.out
finished the counting
finsihed the accumlating
finished sorting
src aadfadfiagaflagagafaggsdfsdfsdipoqpeidkdjhbcdefghijklmnopqrstuvwxyzAiafadfBDDGBADDSEFHCDEFGHIJKLMNOPQRSTUVWXYZ dict ZYXWVUTSRQPONMLKJIHGFEDCBAabcdefghijklmnopqrstuvwxyz ==> dst ZYXWVUTSSRQPONMLKJIHHGGFFEEDDDDDCBBAAaaaaaaaaaaabcdddddddddeefffffffffgggggghhiiiiijjkkllmnoopppqqrsssstuvwxyz
~
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 ??
We can. How would you build this custom comparator, though? That's an important part of the question.
@eugene
building the comparator depends on the api of the dictionary, what would be the api of the dictionary? is it also the problem to be solved by us
Using comparator in java:
import java.util.*;
public class CustomizedDictSorting {
public static void main(String[] args) {
Character[] dict = {'c', 'b', 'a'};
System.out.println(sortStringUsingCustomizedDict("abccc", dict));
}
public static String sortStringUsingCustomizedDict(String s, Character[] customizedDict) {
// two versions of char array
char[] charList = s.toCharArray();
Character[] characterList = new Character[s.length()];
// char -> Char
for (int i=0; i<s.length(); i++) {
characterList[i]=charList[i];
}
// convert dict to arry
final List<Character> customizedDictArray = Arrays.asList(customizedDict);
Arrays.sort(characterList, new Comparator<Character>() {
public int compare(Character a, Character b) {
return customizedDictArray.indexOf(a)-customizedDictArray.indexOf(b);
}
}
);
// Char -> char
for (int i=0; i<s.length(); i++) {
charList[i]=characterList[i];
}
// get return string
return new String(charList);
}
}
The comparator is easy to implement since all classes implementing List interface have the indexOf function; however my conversion between char[] and Character[] is really messy here... Anyone get a better idea?
Completely agree! Although Java has really awesome utilities to implement customized sorting, it is purely object-based, which adds unnecessary inconvenience to primitive variable sorting. As far as I known, some Java platforms like Apache have added utilities to convert between Object(wrapper) arrays and primitive arrays. ArrayUtils in Apache has methods: toObject(char[]) and toPrimitive(Character[])
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;
}
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;
}
Java:
=====================
- Zythum42 February 28, 2013