Zynga Interview Question
Country: United States
Fried-to-friend can actually be viewed as an un-directed graph/forest with many disconnected components. These disconnected components are set of people who are friend to someone in that component but none of them are friends to people in other component.
Now lets try to apply graph data structure in this case.We represent graphs as either--> a) adjacency list or b) Adjacency matrix or c)incident list or d) incident matrix.
Considering option a - Adjacency list
Each 'person' entry in table will point to list of other 'person' IDs which in turn will point to IDs of their friends.
As the no of friends is very dynamic as well as big, The table friends will have two columns - person ID and friendsList. Column friendList will store BLOB file storing comma separated list of friend person IDs.
I think we store all the friends of a person into a xml file in the relational database, for example
A(a) has B(b),C(c),D(d),E(e), where small letter represents a unique key for a person
we store as follow
<a, A, <sex info>, <age>, <some other info>,"b,c,d,e(we make this as xml file as attach it with every person)">
Now when i have to find out weather A' is friend of B' , i just have to find out A' in list and then i look at it's xml file for B' it it present then yes, otherwise no, obviously if A's xml file contain B then B's xml also contain A
similarly update, friend deletion ,addition, etx. can be done very efficiently, because these xml files can be searched parallelly also
How about storing a unique user tuple as a record in a table (say user table). Store every unqiue friend combination as a tuple in the sorted order of the friends name in a db. This is purely in terms of RDBMS perspective. - equivalent of storing an edge in a friend network.
On adding a node and set of edges to the network = adding rows to friend tuple table.
Removing nodes and edges = removing rows from friend tuple table.
Cons: is table scalable containing all tuples of friends ?
Can we do it by this..
Just make generic table that contains two column "name of person" "table name"
where the table name is the name of table which contains the each persons frinds list .With the help of this ,it is easy to track records.
why we can not do this one, simple basic appreach:
- kamoliddin January 23, 2013table: USER_FRIENDS
columns: user_id friend_user_id
user_id, friend_user_id columns together will be unique and they both will be FK for USERS table.
is it much compilicated, or will be slow?