This question appeared in an undergrad data structures final. The details are sound.
I need help to design a data structure for a directed graph with the following properties:
- Initialization should be done in O(1) time.
- AddVertex(id1,id2,...idK) - Add a new vertex to the graph. The new vertex is added with id=N+1 where N is the number of existing vertices. id1...idK are the neighbors of the new vertex, such that there is an outgoing edge from the new added vertex to each of the vertices id1 .. idK. This should be done in O(K) time.
- GetNumberOfNeighbors(id) - Return the number of outgoing edges for a vertex with a given id (id is in 1..N). This should be done in O(1) time.
All O(1) times are for worse case.
I know that the idea is to allocate a new array of K*constant length during the AddVertex method, and to copy K vertices to it in O(K) total, but I don't know how to do this exactly.
Thanks a lot