CareerCup

Dictionary<int, int> counts = new Dictionary<int, int>();
            int[] input = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };            
                        
            foreach( int i in input)
            {
                int count;

                if (counts.TryGetValue(i, out count))
                {
                    counts[i] = i ^ count;
                }
                else
                {
                    counts[i] = i;
                }                
            }

            foreach( var pair in counts)
            {
                if ( pair.Value == 0 )
                {
                    Console.WriteLine(pair.Key);
                }
            }

Dictionary<int, int> counts = new Dictionary<int, int>();
            int[] input = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };            
                        
            foreach( int i in input)
            {
                int count;

                if (counts.TryGetValue(i, out count))
                {
                    counts[i] = i ^ count;
                }
                else
                {
                    counts[i] = i;
                }                
            }

            foreach( var pair in counts)
            {
                if ( pair.Value == 0 )
                {
                    Console.WriteLine(pair.Key);
                }
            }

yep, good catch.

easily fixed by additionally storing which thread (1 or 2) the # was encountered in
(if not queued yet; and seen by the other thread...
queue it for writing)

assuming the cpu has multiple processors
three threads, 1 hashtable (or trie), 1 queue --

thread #1:
read from file #1 (treat the long ints as strings )
insert the long int into a hashtable, key is the #, value is a bool.
if the # is already in the table, check the bool to see if it's been queue'd for writing.
if it hasn't, add the # to a queue, set the bool to true

thread #2
same as thread #1, except it reads from file #2

thread #3
deque a # from the queue, write it to file
when thread #1 is finished and thread #2 is finished and the queue is empty...
done.

access to the hashtable and queue need to be sync'd across threads.

assuming the file is on disk; most of the time is going to spent in reading/writing files,
so breaking that work up across multiple threads is ideal (assuming the files are large).

The memory usage might be too high with a hashtable;
this could be reduced by using a trie/radix tree

void AnagramSort( string[] input )
{
    int index = 0;

    for ( int i=0; i < input.Length; i++ )
    {
        if ( IsAnagram(input[i]) )
        {
            Swap( input, index, i );
            index++;
        }
    }
    // Array is now partitioned with all anagrams on the left, all non-anagrams on right.
    // If nicer formatting is desired, QuickSort each block of the subArray
    // e.g. Array.Sort( input, 0, index - 1 ) and Array.Sort( input, index, input.Length )
}

So what's the logN solution?

Read the file.
Store the data in an interval tree.
The interval is stored in seconds and represents the time spent in the room
( so need a function for converting HH:MM:SS to just S )

To compute the # of people in the room at time HH:MM:S

Convert the time to check to S
Get a list of all intervals that overlap the requested time.
the number of people in the room is equal to the size of this list.

IntervalTree provides a good balance between space and time here.

Can also be solved with a hashTable
Key is the time in seconds
Value is the number of people in the room at that time.
Time to populate the table is more expensive as is the memory usage --
but the lookup would be faster.

Yep. Can't do a simple flip.
Need to do a 1/N flip as you posted.

when n=100

chance to pick the nth element = 50%
chance to pick a previous element in the sequence = 50%

Yep, 5 is correct.
I misread the meaning of '*'.
I thought it matched any character, rather than the previous.

This problem is just a regular expression call.

Actually, you don't need to maintain a count of n.
Just track one number.

When you get a new number; generate a coin-flip (50%/50%).
if heads keep the old number
if tails, overwrite the old number with the new number.

when the sentinel comes up; just return the number.

need to handle the case where the sentinel is first number in the stream.