Ebay Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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
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;
}
}
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
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()
{
char str[5][10]={"CAR","ARC","ATUL","RADHA","RAC"};
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++;
}
}
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;
}
}
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
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)); }
else {value = new LinkedList<String>();}
value.add(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);
}
}
#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;
}
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)){
results.add(test[i]);
}
}
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;
}
new code
- Vincent August 09, 2012