Ebay Interview Question for Software Engineer / Developers


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.

- raja roy January 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- raja roy January 08, 2012 | Flag
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;
        }

- Anonymous January 07, 2012 | Flag Reply
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)
				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;
	}

- rajarshi129 October 10, 2012 | Flag Reply
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[] 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++;
}
}
}
}

- Zeyuan February 06, 2013 | Flag Reply
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("Adam");
strArray.push_back("Martha");
strArray.push_back("Terry");
sortString();
return 0;
}

- bo hou January 10, 2012 | Flag Reply
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>();
				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++;
			}
		}
	}

- Greatbear October 24, 2012 | Flag Reply
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;
            }
        }
        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);
        }
    }

}

- xietao.mailbox@gmail.com December 24, 2012 | Flag Reply
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)
{
hash.Add(str[0], str);
}

foreach (char c in characters)
{
 result.Add(hash[c].ToString());
}

- Spandy February 06, 2013 | Flag Reply
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;
				}
			}
		}

- bling! March 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bling! March 22, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More