Covert a string to upper case

void ToUpper(char * S)

{

while (*S!=0)

{

*S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S;

S++;

}

} 

Reverse a string

void ReverseString (char *String)

{

char *Begin = String;

char *End = String + strlen(String) - 1;

char TempChar = '\0';

while (Begin < End)

{

TempChar = *Begin;

*Begin = *End;

*End = TempChar;

Begin++;

End--;

}

}

Linked List Puzzle

How does one find a loop in a singly linked list in O(n) time using constant memory? You cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.).

Solution


I first figured this out when I was asked the question in a interview, so there’s verification that one question in the book was from a real interview. The best part of this problem is that I actually needed to write the code out for it a little while ago to detect a bug.
One way to detect a loop is to iterate over the list with 2 pointers at the same time where one is iterating at double speed. If the 2 pointers are ever equal after they iterate once and before they both reach an end, there’s a loop.
Now for another puzzle.. I think the next question I had to answer was something along the lines of “OK, How do you remove a loop in a linked list with the same constraints?” The latter question definitely seems harder, but in the sequence of questions I’d already answered for the interviewer, the solution was pretty obvious. I’ll leave that solution to someone else today.

Algorithm Speed in Practice

It's unlikely that you'll spend much time during your career writing sort routines. The ones in the libraries available to you will probably outperform anything you may write without substantial effort. However, the basic kinds of algorithms we've described earlier pop up time and time again. Whenever you find yourself writing a simple loop, you know that you have an O(n) algorithm. If that loop contains an inner loop, then you're looking at O(m × n). You should be asking yourself how large these values can get. If the numbers are bounded, then you'll know how long the code will take to run. If the numbers depend on external factors (such as the number of records in an overnight batch run, or the number of names in a list of people), then you might want to stop and consider the effect that large values may have on your running time or memory consumption.

The O() Notation

The O() notation is a mathematical way of dealing with approximations. When we write that a particular sort routine sorts n records in O(n²) time, we are simply saying that the worst-case time taken will vary as the square of n. Double the number of records, and the time will increase roughly fourfold. Think of the O as meaning on the order of. The O() notation puts an upper bound on the value of the thing we're measuring (time, memory, and so on). If we say a function takes O(n²) time, then we know that the upper bound of the time it takes will not grow faster than n². Sometimes we come up with fairly complex O() functions, but because the highest-order term will dominate the value as n increases, the convention is to remove all low-order terms, and not to bother showing any constant multiplying factors. O(n²/2+ 3n) is the same as O(n²/2), which is equivalent to O(n²). This is actually

What Do We Mean by Estimating Algorithms?

Most nontrivial algorithms handle some kind of variable input—sorting n strings, inverting an m × n matrix, or decrypting a message with an n-bit key. Normally, the size of this input will affect the algorithm: the larger the input, the longer the running time or the more memory used.
If the relationship were always linear (so that the time increased in direct proportion to the value of n), this section wouldn't be important. However, most significant algorithms are not linear. The good news is that many are sublinear. A binary search, for example, doesn't need to look at every candidate when finding a match. The bad news is that other algorithms are considerably worse than linear; runtimes or memory requirements increase far faster than n. An algorithm that takes a minute to process ten items may take a lifetime to process 100.
We find that whenever we write anything containing loops or recursive calls, we subconsciously check the runtime and memory requirements. This is rarely a formal process, but rather a quick confirmation that what we're doing is sensible in the circumstances. However, we sometimes do find ourselves performing a more detailed analysis. That's when the O() notation comes in useful.