Unknown
BAN USER
Questions (1)
Comments (12)
Reputation 130
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 vote
If the linked list does not contain a cycle, then this partial function is injective (one-to-one), meaning that no two nodes map to the same successor. Injective functions can indeed be inverted, which is why you can reverse a regular linked list. However, if the list contains a cycle, then there are two nodes with the same successor, so the function is not injective and thus does not have an inverse. So no, you cannot reverse the linked list and expect to get another linked list, if the list has a cycle.
However, if you treat the linked list as a more general graph in which each node can have any number of incoming or outgoing edges, then the inverse does exist. It's just not a linked list anymore.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Eugene can you explain how will the deterministic time algorithm actually work?
- Unknown July 08, 2012