Google Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
1
of 3 vote

it can be considered as same client-server problem.
where 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.

- guruji January 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The 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.

- Atri January 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

trie or suffix tree should also have constant time access.

- nn January 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about map reduce emit phase for client words and reduce for server words

- Anonymous January 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you elaborate more on this?

- cancer16789 May 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

TRIE takes O(n) worst case. bham, lawyered!

- Anshul January 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

bamboozled

- dude January 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

:)

- Anonymous June 09, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More