## Ebay Interview Question for Software Engineer / Developers

• 0

Country: United States

Comment hidden because of low score. Click to expand.
3
of 3 vote

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:

``````.
.
......................................
.               .                    .
.               .                    .
T.............        M..........        a.........
.             .        .          .          .        .
.             .        .          .          .        .
.             .        .          .          .        .
ammy   erry   ta       artha    tlas   dam``````

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.

Comment hidden because of low score. Click to expand.
0

``````the trie
.
.
......................................
.               .                    .
.               .                    .
T.......        M..........          a.........
.      .        .         .          .        .
.      .        .         .          .        .
.      .        .         .          .        .
ammy   erry     ta        artha      tlas     dam``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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)
}
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;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

public static void main (String args[]) {
char[] c = {'T', 'M', 'A'};
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++;
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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("Martha");
strArray.push_back("Terry");
sortString();
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();
hashmap.put(firstChar, arrayList);
}else
{
}
}

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++;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}
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);
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)
{
}

foreach (char c in characters)
{
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static void bar(char[] a, String[] b)
{
for (int i=0;i<a.length;i++)
{
for(int j=0;j<b.length;j++)
{
if (a[i]==b[j].charAt(0))
{
String temp=b[i];
b[i]=b[j];
b[j]=temp;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

``````static void bar(char[] a, String[] b)
{
for (int i=0;i<a.length;i++)
{
for(int j=0;j<b.length;j++)
{
if (a[i]==b[j].charAt(0))
{
String temp=b[i];
b[i]=b[j];
b[j]=temp;
break;
}
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.