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.

Reply via email to