Call a function F in a loop. F returns a string of 140 chars. Write to the output 1 when F returns a string with the same letters (basically a permutation) of a string previously returned. (the question was not this well formed)

Question

Anonymous · Accepted Answer

Build an hashmap where for every letter you count how many times it appears in the string, and put it in a set.
For every string check if the set contains the built hash.
OR sort the string, and put it in a set

Ali · Answer

I think sorting the word would work much better and is easier to understand

Anagram · Answer

This is called Anagram

Anonymous · Answer

"and put it in a set." to put it in a set you need to implement a way to compare hashs
What you would need is 
1 - build your hash for given word(O(n))
2 - check if the word is present in every other hash with same quantity, since you will need to compare with all previous words everytime the complexity is O(nk) where k is the number of distinct words

so overal complexity O(nk)

Anonymous · Answer

You can either create a custom hash function which is very complex or compress the phrase like:
a4b6f.... ordered alphabetically. If the 2 compressed phrases mach, they are anagrams. The complexity would be O(140) to compress each phrase * n phrases which leads to O(n) complexity.

Anonymous · Answer

Short python answer:

def findPermutationsSort():
    res = f([])
    
    perm_dict = {}
    for s in res:
        key = ''.join(sorted(s))
        if key in perm_dict:
            print 1
        else:
            perm_dict[key] = 1

Booking.com

Booking.com Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches