CareerCup

The best way to tackle these customized sorts is to provide a Comparator function (solution below is in Java. I guess in C++ also you can do this)

So Comparator would be :

Comparator<String> reverseComparator = new Comparator<String>() {
public int compare(String s1, String s2) {
String rev1 = //reverse the first String s1 here;
String rev2 = //reverse the first String s2 here;

return rev1.compareTo(rev2);

}

};

List<String> originalStringList = Arrays.asList("xxxB", "yyyC", "zzzA");

Collections.sort(originalStringList, reverseComparator);

Use qsort and define the compare function such that it compares the strings in reverse order starting with the last character.

#include<iostream>
#include<string>
using namespace std;
char *arr[] = {"xxxB","yyyC","zzzA"};
void sort()
{
for(int i = 0; i < 3 ; i++)
{
for(int j = i+1; j < 3 ; j++)
{
if(strcmp(arr[i],arr[j])> 0)
{
char *temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
void reverse(char *p,int len)
{
char arrev[strlen(p)];
int i = strlen(p)- 1;
int y = 0;
int j = len;
int count = strlen(p);
p = p + strlen(p)- 1;

while(i >=0)
{
arrev[y] = *p;
*p--;
i-- ;
y++;
}
arrev[count]= '\0';
strcpy(arr[j],arrev);
}

int main()
{

for (int i = 0; i < 3 ; i++)
{
reverse(arr[i],i);
}
sort();
for (int i = 0; i < 3 ; i++)
{
reverse(arr[i],i);
}
for (int i = 0; i < 3 ; i++)
{
cout<<"arr=="<<arr[i]<<endl;
}
return 0;

}

I cant find any solution better than reversing, sorting and reversing again :(

can we use java ?

How about:
1) Create an array of reversed strings with pointers to original strings.
2) Sort the newly created array.
3) Use the pointers to iterate through the original array.
4) This will save the cost of reversing the strings every time we do comparisons.

public static String reverse(String str){
StringBuilder sb = new StringBuilder();
for(int i=str.length()-1; i>=0; i--)
sb.append(str.charAt(i));
return sb.toString();
}

public static void main(String[] args) {
String[] arr = {"zzzC", "yyyB", "xxxA"};
HashMap<String, String> hm = new HashMap<String, String>();
for(int i=0; i< arr.length; i++){
hm.put(reverse(arr[i]),arr[i]);
}
ArrayList<String> tmp = new ArrayList<String>(hm.keySet());
Collections.sort(tmp);

ArrayList<String> result = new ArrayList<String>();
for(String str: tmp){
result.add(hm.get(str));
}

Object[] resultArr = result.toArray();
for (int i = 0; i < resultArr.length; i++)
System.out.println((String) resultArr[i]);

}

public static String reverse(String str){
StringBuilder sb = new StringBuilder();
for(int i=str.length()-1; i>=0; i--)
sb.append(str.charAt(i));
return sb.toString();
}

public static void main(String[] args) {
String[] arr = {"zzzC", "yyyB", "xxxA"};
HashMap<String, String> hm = new HashMap<String, String>();
for(int i=0; i< arr.length; i++){
hm.put(reverse(arr[i]),arr[i]);
}
ArrayList<String> tmp = new ArrayList<String>(hm.keySet());
Collections.sort(tmp);

ArrayList<String> result = new ArrayList<String>();
for(String str: tmp){
result.add(hm.get(str));
}

Object[] resultArr = result.toArray();
for (int i = 0; i < resultArr.length; i++)
System.out.println((String) resultArr[i]);

}

What about Radix Sort ? sort it with starting from the left most character . . . .

Why to reverse each string?
We can compare 2 strings character by character from end to start.

This can be done using trie data structure.Insert the reverse of words in trie and printing the word in reverse order.