Google Interview Question
Software Engineer / DevelopersThe fact that multiple clients are present gets me to think that we will need locking mechanisms for access to the Memory.So,we can have a queue in which locking(with mutexes or semaphores etc.) is present.Clients add their words in the queue.The words for filtering are stored in hash table by hashing the word to be stored(something like Rabin karp algorithm requires,or maybe multiple hash functions for speeding up the matching).adding the words to the hash table by the server is convenient since only server is trying write access to the hash table.words are taken from queue and hashed through the function or functions for hashing and matched in the hash table.
Time complexity: O(1) for hashing and searching and matching the input words.O(1) for adding the words to the hash table.O(1)+time waiting for lock for adding a word to queue.
Please comment.
it can be considered as same client-server problem.
- guruji January 09, 2011where the same server is accessed by many clients at the same time.
for this we can adopt the terminology to complete each client request on separate thread. and all the preprossing before adding that words (to check the validity,if the word is already present or not etc ) should be on this thread, and this thread respond to client asynchronously whether word is saved or not.
ofcourse we should use proper locking method when accessing the common datastrucures from various threads.
as far as datastructure is concerned for we can use hastables & tries.
depending upon the requirement.
hashtables has very fast has constant time access but require the very good hash function in advance. which can be difficult to estimate in advance.
but tries has lgn access in all the cases.