Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Though why not this be a trick maintain a counter type variable when a particular system gets a visitor he reads the count incr the count and then when the new user enters other system , inc the counter,when he gets new user , i guess before a traffic is split they come to a central point where we can keep this counter variable , when counter reaches 1000,i am done , dont know if its correct
I believe it is the same problem as to get the kth element from multilple array list, except arrays are far from each other. each array list is sorted by time. right?
I think your answer is partly correct. your solution assumes that the processing of the data will be one offline. say we have server1 with array1, server2 with array2,..., servern with arrayn so we can save in those arrays the user + time of entrence to google.com and then to sort those arrays offline by date and find the 1000th visitor by this order.
the other possibility is to found the 1000th user online. in this case i think each time a user visits google.com from one of the servers a request sould be sent to a "counting server" (server which purpose is to arrange the users by they time of entrence) with the user details + time of entrence to google.com. I suggest to use counter + ordered data structure like balanced binary serach tree that in counting serve enables to insert a new entry user in O(logn) operations. each request processed is of course increamenting the counter by one.
note that we can not assume the order in which the request are processed in the counting server due to communication isues. this means that for instance user1 can access google.com in server1 before user2 access it from server2 but the counting server might get the request to register user2 before user1. the only assumption i must make is that there is maximal time for any request to arrive to the counting server. lets say it is n sec then if the server counter reaches 1000 then we have to process the requests coming in the next n sec one of those requests contains the 1000th user.
I think each server can maintain their own record of userid and timestamp (considering their clocks are synchronized) and then send a copy of it to a central server. At the central server, you just need to do an external merge, because all the lists from servers would be sorted. Is it the right approach ?
O noo i dont know how answered for this question((
i try my answer
Answer
1. module User
2. next, api User
3. next getUser by id method
4. getUser(1000)
5. in model after database find user by id
or just view in database user id
How me correctly answered for this question??
SORRYY IS NOT 1000 USER is just visitor hmmm i think..
IF VISITOR THEN:
1. count visites
2. if COUNT vistes == 1000 then look ip user
Right??
In a distributed system, generally a global clock is maintained for the purpose of sychronization. In absence of global clock, the distributed systems send a copy of their local clock (refer Chandy-Lamport algorithm or Vector clocks). A similar way of transmitting the count of the user access should be designed.
- Learner September 15, 2012Note: The above text is not a solution for this question. It is just a thought process that I have shared.