How to detect a loop in a singly linked list?
Hint: Imagine 2 people running at different speed in a circle and what will happen?
Suppose you have a chunk of 128kb memory to manage. It is devided into an array of 128 units of 1kb. Design two functions: __malloc() to return an index of ONE free unit in the array and __free(i) to free the unit indexed by i. Most people say they need an index array of 128 elements to denote if the corresponding unit is taken or not and scan this index array to find the free unit. But can you find a way to always know what the next free unit is at?
Hint: Link list?
A null-terminiated ASCII string has M characters. It may or may not contain character 'P'. But if there is a 'P', change the first 'P' to 'Q'. Most people are to write a while-loop and at each character, check to see if it is '\0' and if it is 'P', which costs 2*M comparisons. (If you write a for-loop, it's still 2*M comparisons because loop needs to check if i < M for M times). The question is to write one that does only M comparisons.
Hint: The tricky part is that you don't know if there is 'P' or not... Can you somehow know?
I have more to add here...
Please email hot90000@yahoo.com to suggest an addition.