## onpduo

BAN USERI think this is a normal problem. I once did some research in Machine Translation(MT). So if you want to translate meaningfully, it requires a lot of work, with statistical methods and machine learning techniques. So I think it is just a problem for word-word substitution. They want to see which data structure you will use. For me, I will use hash table.

- onpduo August 08, 2012100 numbers for 5 times sorting, each 20 numbers, thus we get 5 queues of sorted numbers. Then take 20 numbers first, each queue contains 4 numbers in memory, and dequeue the biggest, then enqueue the next. Over and over, every time dequeue the biggest number in 5 queues.

- onpduo August 08, 2012There 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

I think first we can generate/choose m from n items in nCm ways (using combinations).

Then find all the LCS(longest common subsequence), with length M-1.

Finally rearrange them, making neighbouring sets with LCS length M-1.

I think it is workable without considering the time complexity.

Anyone has better ideas?

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

vote for rkt.

- onpduo August 14, 2012