Ebay Interview Question
Software Engineer / DevelopersCountry: United States
C#:
private static void SortArrayByOrder(string[] sortOrder, string[] arr)
{
Dictionary<string, int> reverseSortOrder = new Dictionary<string, int>();
int count = 0;
foreach (string s in sortOrder)
reverseSortOrder[s] = count++;
QuickSortByOrder(reverseSortOrder, arr, 0, arr.Length - 1);
}
private static void QuickSortByOrder(Dictionary<string, int> sortOrder, string[] arr, int lo, int hi)
{
if (hi < lo) return;
int d = SortByOrderPartition(sortOrder, arr, lo, hi);
QuickSortByOrder(sortOrder, arr, lo, d - 1);
QuickSortByOrder(sortOrder, arr, d + 1, hi);
}
private static int SortByOrderPartition(Dictionary<string, int> sortOrder, string[] arr, int lo, int hi)
{
int i = 0, j = hi + 1;
string v = arr[lo];
while (true)
{
while (StringCompare(sortOrder, arr[++i], v) < 0) if (i == hi) break;
while (StringCompare(sortOrder, arr[--j], v) > 0) if (j == lo) break;
if (i >= j) break;
StringExchange(arr, i, j);
}
StringExchange(arr, lo, j);
return j;
}
private static int StringCompare(Dictionary<string, int> sortOrder, string x, string y)
{
string fC = x[0].ToString();
string sC = y[0].ToString();
if (sortOrder[fC] < sortOrder[sC]) return -1;
else if (sortOrder[fC] > sortOrder[sC]) return 1;
else return 0;
}
private static void StringExchange(string[] arr, int i, int j)
{
string temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
Java:
// Sort on char array
public ArrayList<String> sortOnCharArray(char[] chars, String[] strings)
{
ArrayList<String> stringArrayList = new ArrayList<String>();
HashMap<Character, String[]> mapper = new HashMap<Character, String[]>();
mapper = ConstructMap(chars, strings);
for (int count=0; count<chars.length; count++)
{
String[] pullArray = mapper.get(chars[count]);
String[] sortedPullArray = SortStrings(pullArray);
for (String str : sortedPullArray)
stringArrayList.add(str);
}
return stringArrayList;
}
public HashMap<Character, String[]> ConstructMap(char[] chars, String[] strings)
{
HashMap<Character, String[]> mapper = new HashMap<Character, String[]>();
for (int count=0; count<strings.length; count++)
{
if (contains(chars, strings[count].charAt(0)))
{
String[] pushArray = new String[strings.length];
if (mapper.containsKey(strings[count].charAt(0)))
{
String[] push = new String[mapper.get(strings[count].charAt(0)).length+1];
push = mapper.get(strings[count].charAt(0));
push[push.length-1] = strings[count];
pushArray = push;
}
else
{
pushArray[0] = strings[count];
}
mapper.put(strings[count].charAt(0), pushArray);
}
}
return mapper;
}
public String[] SortStrings(String[] strings)
{
for (int count = 0; count<strings.length; count++)
{
if (strings[count]==null)
strings[count] = "";
}
Arrays.sort(strings);
return strings;
}
public boolean contains(char[] chars, char ch)
{
for (char c : chars)
{
if (c == ch)
return true;
}
return false;
}
public static void main (String args[]) {
char[] c = {'T', 'M', 'A'};
String[] strArray = {"Adam","Martha","Terry","Amir","Tony"};
String[] output = new String[strArray.length];
strOut(c,strArray,output);
for(int i=0;i<output.length;i++){
System.out.printf("%s\n",output[i]);
}
}
public static void strOut(char[] c, String[] strArray, String[] output){
int count = 0;
for(int i=0;i<c.length;i++){
for(int j=0;j<strArray.length;j++){
if(strArray[j].charAt(0) == c[i]){
output[count] = strArray[j];
count++;
}
}
}
}
#include "stdafx.h"
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<map>
#include<vector>
using namespace std;
vector<char> c;
map<char, int> c1;
vector<string> strArray;
int compare(int x, int y)
{
string & a =strArray[x];
string & b =strArray[y];
for (int i=0;i<a.length() && i<b.length();i++)
{
if (c1[a[i]] -c1[b[i]]!=0)
return c1[a[i]] -c1[b[i]];
}
if (a.length() == b.length())
return 0;
if (a.length() > b.length())
{
return 1;
}
return -1;
}
int partition(int rank[], int L, int R)
{
int tmp = rank[L];
while (L<R)
{
while (compare(tmp, rank[R])<=0 && L<R)
--R;
if (L>=R)
break;
rank[L] =rank[R];
while (compare(rank[L], tmp)<=0 && L<R)
++L;
if (L>=R)
break;
rank[R--] =rank[L];
}
rank[L] =tmp;
return L;
}
void QuickSort(int rank[], int L, int R)
{
if (L<R)
{
int pivot =partition(rank, L, R);
QuickSort(rank, L, pivot-1);
QuickSort(rank, pivot+1, R);
}
}
void sortString()
{
int *rank = new int[strArray.size()]();
for (int i=0;i<c.size();++i)
{
c1[c[i]] =i;
}
for (int i=0;i<strArray.size();i++)
rank[i] =i;
QuickSort(rank, 0, strArray.size()-1);
for (int i=0;i<strArray.size();i++)
{
printf("%s\n", strArray[rank[i]].c_str());
}
}
int main()
{
c.push_back('T');
c.push_back('M');
c.push_back('A');
strArray.push_back("Adam");
strArray.push_back("Martha");
strArray.push_back("Terry");
sortString();
return 0;
}
Java short version:
public static void sortStrings(String[] strArray,char[] c){
HashMap<Character,ArrayList<String>> hashmap = new HashMap<Character,ArrayList<String>>();
for(int i = 0; i < strArray.length; i++)
{
char firstChar = strArray[i].charAt(0);
if(!hashmap.containsKey(firstChar)){
ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add(strArray[i]);
hashmap.put(firstChar, arrayList);
}else
{
hashmap.get(firstChar).add(strArray[i]);
}
}
int i = 0;
for(char n: c)
{
if(hashmap.get(n) == null)
continue;
ArrayList<String> arr = hashmap.get(n);
for(String str: arr){
strArray[i] = str;
i++;
}
}
}
public class MyString {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
char [] c = {'T', 'M', 'A'};
final int chars [] = new int[26];
for(int i=0;i<c.length;i++){
chars[c[i] - 'A'] = i+1;
}
int size = c.length;
for(char i='A';i<'Z';i++){
if(chars[i-'A'] == 0){
size ++;
chars[i-'A'] = size;
}
}
String [] strs = {"Adam","Martha","Terry"};
List<String> list = Arrays.asList(strs);
Collections.sort(list, new Comparator<String>(){
public int compare(String s1, String s2){
int i = 0;
while(i< s1.length() && i < s2.length()){
if(s1.charAt(i) == s2.charAt(i)) continue;
else return chars[s1.charAt(i) - 'A'] - chars[s2.charAt(i) -'A'];
}
if(i == s1.length() && i < s2.length()){
return -1;
}
if(i < s1.length() && i == s2.length()){
return 1;
}
if(i==s1.length() && i==s2.length()){
return 0;
}
return 0;
};
});
for(String s : list){
System.out.println(s);
}
}
}
char[] characters = new char[] {'T', 'M', 'A' };
string[] strings = new string[] { "Adam", "Martha", "Tell" };
List<string> result = new List<string>();
Hashtable hash = new Hashtable();
foreach (string str in strings)
{
hash.Add(str[0], str);
}
foreach (char c in characters)
{
result.Add(hash[c].ToString());
}
create a trie based on the given sorted input array and maintain that order at each level. Then read the trie from left to right(inoder traversal) to get the array of sorted strings.
ex- given sorted array char c[]= { 'T', 'M', 'A'} and assuming the priority of others char to be lower and according to their ascii value...
given string array = {"atlas", "adam", "martha", "mta", "terry", "tammy"}
so now we will scan the strings one at a time and throw them into the trie with maintaining each level according to the given sorted char array ...the resulting trie would look something as follows:
so as you can see each child node maintains a sorted order based on the input array....now just do inoder traversal to get the sorted array of given strings.
- raja roy January 08, 2012