Parallelism

Threads and processes:
A computer will often appear to be doing many things simultaneously, such as checking for new e‐mail messages, saving a Word document, and loading a website. Each program is a separate “process”. Each process has one or more “threads”. If a process has several threads, they appear to run simultaneously. For example, an email client may have one thread that checks for new e‐mail messages and one thread for the GUI so that it can show a button being pressed. In fact, only one thread is being run at any given time. The processor switches between threads so quickly that they appear to be running simultaneously. Multiple threads in a single process have access to the same memory. By contrast, multiple processes have separate regions of memory and can only communicate by special mechanisms. The processor loads and saves a separate set of registers for each thread. Remember, each process has one or more threads, and the processor switches between threads.

Titanic Ship Crew Job

Got this code on codechef:
The captain of the ship TITANIC is a little .... off the track. He needs to select the crew for the ship. But everyone seems to be eligible. So to test their intelligence, he plays a game.
The contestants have to stand in a line. They are given the numbers in the order in which they stand, starting from 1. The captain then removes all the contestants that are standing at an odd position.
Initially, standing people have numbers - 1,2,3,4,5...
After first pass, people left are - 2,4,...
After second pass - 4,....
And so on.
You want to board the ship as a crew member. Given the total number of applicants for a position, find the best place to stand in the line so that you are selected.

Duplicate character in a given string..

The first solution that comes to mind is to use use nested loops..But then we realize that it's a O(n^2) solution.
So we need to refine this solution. A better option than arrives to have an additional array that stores count of each character. This solution is better off than the previous one as it's running time has reduces to O(n). But this one consumes O(n) extra memory.
Can we do it in linear time with constant memory?
If yes, then how?

Hats On A Death Row

You are one of 20 prisoners on death row with the execution date set for tomorrow. Your king is a ruthless man who likes to toy with his people's miseries. He comes to your cell today and tells you:
“I’m gonna give you prisoners a chance to go free tomorrow. You will all stand in a row (queue) before the executioner and we will put a hat on your head, either a red or a black one. Of course you will not be able to see the color of your own hat; you will only be able to see the prisoners in front of you with their hats on; you will not be allowed to look back or communicate together in any way (talking, touching.....).

The prisoner in the back will be able to see the 19 prisoners in front of him. The one in front of him will be able to see 18…

Starting with the last person in the row, the one who can see everybody in front of him, he will be asked a simple question: WHAT IS THE COLOR OF YOUR HAT?

He will be only allowed to answer “BLACK” or “RED”. If he says anything else you will ALL be executed immediately.

If he guesses the right color of the hat on his head he is set free, otherwise he is put to death. And we move on to the one in front of him and ask him the same question and so on…

Well, good luck tomorrow, HA HA HA HA HA HA!”

Now since you all can communicate freely during the night, can you find a way to guarantee the freedom of some prisoners tomorrow? How many?