## Ebay Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

new code

``````public static void printAnagram(String [] collection,String target)
{
for(int i=0;i<collection.length;i++)
{
if(isAnagram(collection[i],target))
System.out.println(collection[i]);
}
}
public static boolean isAnagram(String m,String b)
{
if(m.length()!=b.length())
return false;
int [] counts1=counts(m);
int [] counts2=counts(b);
for(int i=0;i<counts1.length;i++)
{
if(counts1[i]!=counts2[i])
return false;
}
return true;
}
public static int[] counts(String m)
{
int[] count=new int[256];
for(int i=0;i<count.length;i++)
count[i]=0;
for(int i=0;i<m.length();i++)
{
count[m.charAt(i)]++;
}
return count;
}``````

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

That is correct. But instead of count[256] , you can take count[26] and map using (charAt(i)-'a') , assuming all are lowercase.

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

A String of size n has n! anagrams. O(n2) algorithm is impossible. O(n!) is the best you can do.

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

Lets say there's m different strings, and each string is on average n letters long

Make a copy of the original array, lets call this c-arr
Sort each string in c-arr alphabetically (ie. the words car, rac, and arc all become acr). should be m*n log n
Sort the string you want to find anagrams of alphabetically (big O of nlogn)
run through c-arr, and compare your sorted string with the elements in c-arr (big O of m * n at worst, you can easily make it better)
If you hit a match, then for that index in c-arr, print or do whatever operation you have to on the original array at the same position

total big O: m*n log n + nlogn + m * n = nlogn +m*n, which is n^2 or less

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

public class Anagrams {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] stringSet = new String[]{"car","arc","art","arct","rac"};
String target = "car";
int n= stringSet.length;
for(int i=0; i<n; i++) {
if(target.length()==stringSet[i].length()){
if(isAnagrams(target,stringSet[i])){
System.out.println(stringSet[i]);
}
}
}

}

public static String sort(String s){
char[] arr = s.toCharArray();
java.util.Arrays.sort(arr);
return new String(arr);
}

public static boolean isAnagrams(String target, String current){
if(sort(target).equals(sort(current)))
return true;
return false;
}

}

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

can you please explain runtime complexity of this algorithm ? why are you creating hashtable everytime for target ?

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

There are N strings in an array, and you need to find all the anagram of a given string in this array. Suppose all the strings are composed of 26 lowercase characters, then use 26 different prime numbers to represent the 26 characters(eg. 2, 3, 5, 7...), then for every string in this array, compute the product of all the character in this string, and compare with the product of the given string, if equal, it is the anagram of the given string. O(n^2) time complexity.
eg. abc = 2*3*5 = cab = 5*2*3

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

Working code: ideone.com/eiFQn

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

void sort(char str[5][10],int i)
{
int p=0,q=0;
char temp;
int length=strlen(str[i]);

for(p=0;p<length;p++)
{
for(q=p;q<length;q++)
{
if(str[i][p]> str[i][q])
{
temp=str[i][p];
str[i][p]=str[i][q];
str[i][q]=temp;
}
}
}

}

int main()
{
int i=0,count=0;
char test[]="ACR";

while(i<5)
{
sort(str,i);
i++;
}

i=0;
while(i<5)
{
if(!strcmp(str[i],test))
count++;
i++;
}

}

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

that is n^2*logn

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

HashMap<String, TreeSet<String>

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

public class Anagrams {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] stringSet = new String[]{"car","arc","art","arct","rac"};
String target = "car";
int n= stringSet.length;
for(int i=0; i<n; i++) {
if(target.length()==stringSet[i].length()){
if(isAnagrams(target,stringSet[i])){
System.out.println(stringSet[i]);
}
}
}

}

public static String sort(String s){
char[] arr = s.toCharArray();
java.util.Arrays.sort(arr);
return new String(arr);
}

public static boolean isAnagrams(String target, String current){
if(sort(target).equals(sort(current)))
return true;
return false;
}

}

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

public static void printAnagrams(String[] strArr, String target){
if(strArr == null){
System.out.println("Error");
}
for(int i = 0; i < strArr.length; i++){
if(isAnagram(strArr[i], target){
System.out.println( strArr[i] + "is Anagram of" + target)
}
}
}

private static boolean isAnagram(Sting str1, String tar){
if(str1.length() != tar.length() || str.equals(tar)){
return false;
}
int[] freq = new int[256];

for(int i = 0; i < str1.length(); i++){
int charInt = str.charAt(i);
freq[charInt]++;
}

for(int j = 0; j < tar.length(); j++){
int charInt2 = tar.charAt(j);
if(--freq[charInt2] < 0){
return false;
}
}
return true;
}

O(N^2) time O(N^2) space

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

``````public void findAnagram(String[] strings, String s) {
HashMap<String, List<String>> map = new HashMap<String, List<String>> ();
for (String element: strings) {
List<String> value;
if (map.containsKey(sort(element))) {value = map.get(sort(element)); }
map.put(sort(element), value);
}
printAnagrams(s, map);
}
public String sort(String s) {
char[] array = s.toCharArray();
Arrays.sort(array);
return new String(array);
}

public void printAnagrams(String s, HashMap<String, List<String>> map) {
if(map.containsKey(sort(s)) {
for (String anagram: map.get(sort(s)).toArray(new String[0])) {
System.out.println("anagram of s: "+ anagram);
}
}``````

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

This is correct and give the correct output to me

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

It fails for input String[] stringSet = new String[]{"car","arc","artc","arct","rac","cccc"};
String target = "arct";

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

#include <stdio.h>
#include <string.h>
int check_anagram(char [], char []);

int main(void)
{
char *a="suresh", *b="reshsu";

if (check_anagram(a, b)== 1)
printf("\"%s\" and \"%s\" are not anagrams.\n", a, b);
else
printf("\"%s\" and \"%s\" are anagrams.\n", a, b);

return 0;
}

int check_anagram(char a[], char b[])
{
int hash[26] = {0},c = 0;

while (a[c] != '\0')
{
hash[a[c]-'a']++;
hash[b[c]-'a']--;
c++;
}

for(c=0;c<26;c++){
if(hash[c] != 0)
return 1;
}
return 0;
}

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

public static ArrayList<String> get_anagrams_results(String[] test,String aim){
ArrayList<String> results=new ArrayList<String>();
for(int i=0;i!=test.length;i++){
if(isAnagrams(test[i],aim)){
}
}
return results;
}
public static boolean isAnagrams(String o1,String o2){
if(o1.length()!=o1.length()){
return false;
}

int[] holdChar=new int[256];
for(int i=0;i!=o1.length();i++){
holdChar[(int)o1.charAt(i)]++;
}
for(int i=0;i!=o2.length();i++ ){
if(--holdChar[(int)o2.charAt(i)]==-1){
return false;
}
}
return true;
}

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

also your code gives compile error on iterator<Character>

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

Sorry about that. I ll provide correct code later

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.

### 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.

### 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.