Google Interview Question
SDE1sCountry: India
this would only cater for the case of finding "direct" children/parents, the questions of the OP says "all the children nodes and all the parents"...
traverse the graph (N1->N2), (N1->N3), (N1->N4), (N2->N3), and (N3->N4) and extract nodes and add them to node_master table:
<node_master>
node_id, node_value
N1 1234
N2 34
N3 56
N4 90
Then for each node, extract the children, add them to node_family table:
<node_family>
node_parent, node_child
N1 N2
N1 N3
N1 N4
N2 N3
N3 N4
Then to find the parent/child: SQL query may be:
SELECT node_master.node_id, node_family.node_child
FROM node_master INNER JOIN node_family
ON node_master.node_id = node_family.node_id
WHERE <specify a filter>;
I'd keep the PATH infomation for each node.
Table Node
- Id
- Value (or Cost)
- Path
Assume that the graph is like below.
(i.e. a complete binary tree which is a special form of a graph)
. 1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Example Rows for the graph above:
Id Path
-------------------------
1.......... NULL
2.......... 1
3.......... 1
4.......... 1,2
5.......... 1,2
6.......... 1,3
7.......... 1,3
8.......... 1,2,4
9.......... 1,2,4
10..........1,2,5
11..........1,2,5
12..........1,3,6
13..........1,3,6
14..........1,3,7
15..........1,3,7
Selecting all parents of Node X:
. SELECT [Path] FROM [PathTable] WHERE [Id] = X;
Selecting all children of Node X:
. declare @path varchar(max);
set @path = (SELECT [Path] FROM [PathTable] WHERE [Id] = X);
set @path = @path + ',%';
SELECT [Id] FROM [PathTable] WHERE [Path] LIKE @path;
However, this is only an optimization for the given conditions. There are many disadvantages of this solution. For example insert and delete operations are too costly since you need to update all impacted paths in the table..
A self referential table would work.
1
/ \
2 3
/ \ \
4 5 6
Example Node Table
| ItemId | ParentId |
| 1 | NULL |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
To select parent of node 2:
SELECT ParentId FROM Node WHERE ItemId = 2;
To select children of node 2:
SELECT ItemId FROM Node Where ParentId = 2;
This is a pretty general solution:
- Anonymous April 15, 2013Table Nodes
(Node_ID INT, Node_Value X)
Table Adjacents
(Node_ID INT, Adj_Node_ID INT, PathCost INT)
Then to retrieve all children of a node:
Select Adj_Node_ID from Adjacents Where Node_ID=SomeNodeId
To retrieve the 'parents' of a node:
Select Node_ID from Adjacents Where Adj_Node_ID=SomeNodeId