CareerCup

We could create a hash table on names, then each element of the hash table can be another hash table on last names. This would be O(1) ideally. Of course we should have another data structure that hashes on last names and then on first names.

I guess a solution better than O(N) must be obtained using TRIES (prefix trees).
We can arrange all the names and surnames in 2 different tries.
But here also we will require a connection between two tries. Can anybody suggest a solution?

one Trie with two entry of same name; first name+last name & last+first;

If we have all names in sorting order (priority given to first name and then last name), then we can use binary search tree to find the given name. then it is less than O(N).

Person is an object which has to be searched and accessed using his name / surname / name+surname.

So an O(logN) solution is possible by creating three sorted arrays one for name, another one for surname and another one for full name. And each will have the pointer to the person object. A binary search will be sufficient for that.

An O(1) solution is possible if we take hashtable or map for all of the three.

Trie will have worst case time complexity as O(n). So We should use 3 balanced binary search tree like AVL tree or red black tree where building the tree will take n*log(n) time and searching will take log(n) time and space complexity would be O(n).

I think trie would be a better approach along with @Gaurav's approach

Trie might be better than hash tables. Hash tables aren't good with phone book type entries.

Create a kd tree on (first name, last name). If the kd tree is balanced then search would be O(log n)

Two hashtables. One with key for First Name and other with key for Last Name with both values pointing to same Person object.
For each bucket store items in BST, sorted by the "other" name.
So when searching for complete name, we can do O(1) for First Name and then O(lg n) to find Second Name (or vice versa).

suffix tries can be used. Use <FirstName> : <LastName> and now you can even search on substrings, suffixes etc.

This simply is impossible unless the names are unique. If they are, a simple hash table would work.