This problem is close to copying a graph. For that as you said, just
do DFS or BFS and maintain a map from original nodes to copies. Use
the copy to set pointers whenever it exists. When it doesn't exist,
make a new node and add it to the map.
You can implement the map in various ways. A hash table works fine.
If you can add a pointer to each original vertex node, you can store
the mapping right there. If nodes are numbered consecutively, you can
use these as indices into a table. Etc. Etc. Lots of schemes are
possible. No matter how you do it, the algorithm is the same:
Node copy(Node x)
{
if (x == null) return null;
if (Map(x) != null) return Map(x);
xCopy = new Node();
Set Map(x) = xCopy;
xCopy.next = copy(x.next);
xCopy.other = copy(x.other);
return xCopy;
}
But general graph copy is overkill here. The searching requires O(L)
space for a list of length L. So for this special problem, just
traverse the list once to find and copy all the nodes and then a
second time to set the "other" pointers:
Node Copy(Node x)
{
// Using a dummy head node makes copying simple.
Node dummyHead = new Node();
Node q = dummyHead;
// Make the copied list and fill in the Map.
for (Node p = x; p != null; p = p.next, q = q.next) {
Node pCopy = new Node();
q.next = pCopy;
Set Map(p) = pCopy;
}
// Set all the other pointers.
for (Node p = x; p != null; p = p.next)
Map(p).other = Map(p.other);
return dummyHead.next;
}
The final question is whether you can implement the Map in a tricky
way. After the list is constructed, you have the L "other" pointers
doing nothing, so how can they be exploited?
I'll let you think about that...
On Mar 13, 2:01 am, Umer Farooq <the.um...@gmail.com> wrote:
> Yes that is exactly what they wanted. I proposed BFS for this solution.
> Anyway, there was another problem that I was able to solve; but the
> interviewer brought up a much more efficient approach.
>
> The problem was:
>
> - Given a linked a linked list with one pointer pointing to next,
> another pointer pointing to any random pointer in the list. The random
> pointer can be before or after the current pointer or it can even be at the
> same node. Write a piece of code that can produce an exact copy of the
> linked list.
>
>
>
>
>
>
>
>
>
> On Tue, Mar 13, 2012 at 10:57 AM, Umer Farooq <the.um...@gmail.com> wrote:
> > Yes that is exactly what they wanted. I proposed BFS for this solution.
> > Anyway, there was another problem that I was able to solve; but the
> > interviewer brought up a much more efficient approach.
>
> > The problem was:
>
> > Given a linked l
>
> > On Mon, Mar 12, 2012 at 11:31 PM, Gene <gene.ress...@gmail.com> wrote:
>
> >> Since there is no mention of weights, you are looking for any spanning
> >> tree. Primm and Kruskal are for _minimum_ spanning tree. They are
> >> overkill for this problem.
>
> >> You can construct a spanning tree in any graph with DFS. Just record
> >> every edge you find that reaches a vertex that has never been visited
> >> before. This has to find every vertex, and since you are recording
> >> only the first edge used to arrive at each vertex, these edges must
> >> form a tree. This works even if there are cycles. The algorithm is O(|
> >> E|).
>
> >> Note that in general a graph doesn't have a single root. So you'd
> >> search from all roots. Another way to think about this: introduce
> >> your own dummy root and edges to each vertex where there are no
> >> incident "in" edges. Of course you don't report the dummy edges.
>
> >> On Mar 12, 1:09 pm, atul anand <atul.87fri...@gmail.com> wrote:
> >> > i guess they were talking abt spanning tree , so you can use prism or
> >> > kruskal algo to do the same.
>
> >> > On Mon, Mar 12, 2012 at 3:05 PM, Umer Farooq <the.um...@gmail.com>
> >> wrote:
> >> > > Hello friends,
>
> >> > > I recently had an onsite MS interview. One of the questions that they
> >> > > asked was:
>
> >> > > - Given a directed graph, write a program that takes root of the
> >> graph
> >> > > and returns root of a tree which comprises of all the nodes of the
> >> graph in
> >> > > the same way as they appeared in the graph (the graph contains no
> >> cycles).
>
> >> > > --
> >> > > Umer
>
> >> > > --
> >> > > You received this message because you are subscribed to the Google
> >> Groups
> >> > > "Algorithm Geeks" group.
> >> > > To post to this group, send email to algogeeks@googlegroups.com.
> >> > > To unsubscribe from this group, send email to
> >> > > algogeeks+unsubscr...@googlegroups.com.
> >> > > For more options, visit this group at
> >> > >http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Umer
>
> --
> Umer
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
