Copying a full graph requires a BFS or DFS. But here we have a big
advantage. We know the nodes are linked in a single chain. So we
don't need to search to find all nodes. We can just use .next
pointers.
No matter how we do things, we will need Map(A) that returns the copy
of node A if it already exists.
If you use a separate map like a hash table, then things are very
simple. Traverse the list one time to make copies of all the nodes,
chain them in a list, and create the Map. Then traverse the original
list a second time to set the "other" pointers: for each node A, set
Map(A).other = Map(A.other).
The Map requires O(L) space for a list of length L.
But it turns out we can store the map in a very tricky way that
requires zero additional space _if_ we are allowed to change the
original list while making the copy. If A' is the copy of A, and we
start with list [ A,B,C,... ], then we transform this in one pass to
[A, A', B, B', C, C', ... ]. In this list, A.next is A'. So we have
created the map without losing any information.
Here's untested code that ought to be at least very close:
class Node {
int val;
Node next, other;
Node() {}
Node(int val, Node next, Node other) {
this.val = val;
this.next = next;
this.other = other;
}
Node(Node org) {
this(org.val, org.next, org.other);
}
/**
* @return a copy of the list including "other" pointers
*/
Node copy() {
// Make the copies and the map.
for (Node p = this; p != null; p = p.next.next)
p.next = new Node(p);
// Use the map to fix up the other pointers in the
copies.
for (Node p = this.next; p.next != null; p =
p.next.next)
p.other = p.other.next;
// Split into original list and list of copies.
Node dummyHead = new Node();
for (Node p = this, q = dummyHead; p != null; p =
p.next, q =
q.next) {
q.next = p.next;
p.next = p.next.next;
}
return dummyHead.next;
}
}
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.
