**Question:** How could you determine if a linked list contains a cycle in it, and, at what node the cycle starts?

**Answer:** There are a number of approaches. The approach I shared is in time N (where N is the number of nodes in your linked list). Assume that the node definition contains a boolean flag, `bVisited`

.

`struct Node` |

Then, to determine whether a node has a loop, you could first set this flag to `false`

for all of the nodes:

`// Detect cycle` |

Then, to determine whether or not a cycle existed, loop through each node. After visiting a node, set `bVisited`

to `true`

. When you first visit a node, check to see if the node has already been visited (i.e., test `bVisited == true`

). If it has, you've hit the start of the cycle!

`bool bCycle = false;` |

A *much better* approach was submitted by 4Guys visitor George R., a Microsoft interviewer/employee. He recommended using the following technique, which is in time O(N) and space O(1).

Use two pointers.

`//`

error checking and checking for NULL at end of list omitted

p1 = p2 = head;

do {

p1 = p1->next;

p2 = p2->next->next;

} while (p1 != p2);

`p2`

is moving through the list twice as fast as`p1`

. If the list is circular, (i.e. a cycle exists) it will eventually get around to that sluggard,`p1`

.

Thanks George!

**Question:** How would you reverse a doubly-linked list?

**Answer:** This problem isn't too hard. You just need to start at the head of the list, and iterate to the end. At each node, swap the values of `pNext`

and `pPrev`

. Finally, set `pHead`

to the last node in the list.

`Node * pCurrent = pHead, *pTemp;` |

**Question:** Assume you have an array that contains a number of strings (perhaps `char * a[100]`

). Each string is a word from the dictionary. Your task, described in high-level terms, is to devise a way to determine and display all of the anagrams within the array (two words are anagrams if they contain the same characters; for example, `tales`

and `slate`

are anagrams.)

**Answer:** Begin by sorting each element in the array in alphabetical order. So, if one element of your array was `slate`

, it would be rearranged to form `aelst`

(use some mechanism to know that the particular instance of `aelst`

maps to `slate`

). At this point, you `slate`

and `tales`

would be identical: `aelst`

.

Next, sort the entire array of these modified dictionary words. Now, all of the anagrams are grouped together. Finally, step through the array and display duplicate terms, mapping the sorted letters (`aelst`

) back to the word (`slate`

or `tales`

).

**Question:** Given the following prototype:

`int compact(int * p, int size); ` |

write a function that will take a sorted array, possibly with duplicates, and compact the array, returning the new length of the array. That is, if `p`

points to an array containing: `1, 3, 7, 7, 8, 9, 9, 9, 10`

, when the function returns, the contents of `p`

should be: `1, 3, 7, 8, 9, 10`

, with a length of 5 returned.

**Answer:** A single loop will accomplish this.

`int compact(int * p, int size)` |

## No comments:

## Post a Comment