Car Race Puzzle (Google)

20^th, October, 2010

Given 49 cars and 7 tracks of equal length. No two have the same speed. How to find the 25^th fastest car? At least how many races are needed? The puzzle posted here.

I am providing my initial thought on the puzzle. We are given 49 cars and 7 tracks. We can arrange them into 7 groups. Conduct first race among these 7 groups, we will have seven ordered sets.

For easy reference, let us name them from group A through group G. Further, in group A, let us name the best car as A1 and last car as A7. Similarly other groups. Now conduct one more race among the winners of all groups. At this point we needed 8 races to figure out groups order along with order in each group. We can represent them in the following matrix form.

For simplicity, assume that the result of 8^th race is A1 through G1. We can arrange them as shown in the above diagram.

By careful observation, we can avoid those cars in red border, since they can’t fall in the first 25 places. We can also avoid A1, since it occupies first place.

Now we have 24 cars, some preprocessed information and 7 tracks. How best can we group them with the preprocessed information in hand, and having 7 tracks. Obviously, we need to group them in 3 groups, leaving 3 remaining.

[ If we observe, we have a matrix in which all rows sorted and only the first column sorted. Can we think of sorting the 2D matrix both vertically and horizontally? Locating 25^th element in that matrix is our target. ]

From now I have fun, since I am not sure how to proceed.

Either A2 or B1 can occupy 2^nd place. If B1 wins second place, we will end up in more races. Best possible case will arrive when A2 wins for second place.

Yet to fill

Tree equations

19, Oct, 2010

Given an N-ary tree and number of internal nodes (I), find leaf nodes in the tree. Question posted here.

I thought many people get confused while working with tree/graph related mathematics. I am providing two fundamental equations that help in understanding these equations.

In a tree with I internal nodes and L leaf nodes, the total number of nodes is sum of internal nodes and external (leaf) nodes, i.e.

T = I + L -----à 1

Assume, we are given with 3 poles (nodes). We need minimum two ropes (edges/branches in graph terminology) to connect them. Similarly, a tree with T nodes on total will have (T – 1) branches.

An N-ary tree with I internal nodes will have (N x I) branches. It is because, each internal node can have utmost N branches. We have the following relation with total nodes T,

T – 1 = (N x I) ------à 2

From the above two equations, it is clear that leaf nodes can be given by the following relation,

L = (N - 1) x I + 1

In a binary tree, N = 2, hence in a binary tree external nodes are always one more than the internal nodes.

Scala-Lift-Twitter

Scala is a new generation programming language which supports both Function Programming and Object Oriented Programming. It forms an alternative domain specific language due to the provisions such as mixins, methods as opeartor, no macros, no meta programming, etc. The language can be extended with the help of these features without altering the syntax.

Lift is web framework designed in Scala. Twitter is one major application designed in Scala to date.

The programmer needs JVM and Scala compiler. Easy to learn and experiment. Try out your had.

Permuting the words of a string

10th October, 2010

Given a string, how can you permute all words of the string? The question was asked here.

Given below is the working code. Algorithmic steps can be understood from the comments.

// Prints all the words in the string array

void printTheArray(char *array[], int size)

{

    static int count;

    int index;

    printf("%d ", count);

    for(index = 0; index < size; index++)

    {

        printf("%s ", array[index]);

    }

    count++;

    printf("\n");

}

// swpping integers is easy, swapping strings nothing but swapping their base

inline

void swapStringPointers (char *stringsVector[], int i, int j)

{

    char *base;

    base = stringsVector[i];

    stringsVector[i] = stringsVector[j];

    stringsVector[j] = base;

}

// Actual permutation algorithm (recursive)

inline

void permuteWords (char *stringsVector[], int vectorSize, int processedIndex)

{

    int currentIndex;

    if (processedIndex == vectorSize)

    {

        // print the vector

        printTheArray(stringsVector, vectorSize);

    }

    else

    {

        for (currentIndex = processedIndex; currentIndex < vectorSize; currentIndex++)

        {

            // No need to swap the same element

            if(currentIndex != processedIndex)

                swapStringPointers (stringsVector, processedIndex, currentIndex);

            // Recursively permute the smaller instances

            permuteWords (stringsVector, vectorSize, processedIndex + 1);

            // No need to swap the same element

            if(currentIndex != processedIndex)

                swapStringPointers (stringsVector, processedIndex, currentIndex);

        }

    }

}

int main ()

{

    // Just add one more string if you want to test

    char *strings[] = {"SARI", "GAMA", "PADA", "NISA"};

    int size = sizeof(strings)/sizeof(strings[0]);

    // Prints original array

    printTheArray(strings, size);

    printf("\n");

    // Permutes all words in the string

    permuteWords (strings, size, 0);

    return 0;

}

SQLite

Are you using Android phone? Then you are using SQLite software, a light weight structured query language for database. An open source software and implemented in C language. Worth reading the wiki link and if interested explore the design.

Designed by D. Richard Hipp about 10 years ago. The SQLite DLL also embedded as a plugin into Qt framework.

Member alignment of structures

When we declare structures, usually their size will not match to the sum of individual elements size. The structures size will atleast be sum of all elements size or more. Why is it so?

I referred many books for information, but almost all are helpless. Some how, I could able to trace reasons using web search. Thanks to search engines, Art of Assembly Programming book and colleagues.

Processor architectures are advanced and optimized for optimum performance. In olden days memory was byte addressable. To maintain backward compatibility next versions of many architectures were also needed to support byte addressing.

Here is the question...

Byte is 8 bits. Present day processors have 32 bit or 64 bit processing word length. It means they can process 4 or 8 bytes at a time. Usually integer is most prominent processing type on any processor. It occupy the size of processing word length.

If the memory is to be byte addressable due to backward compatibility, processor need to issue 4 read cycle to read one integer which is time consuming. In lieu of, the hardware manufacture arranges memory in banks of one byte each. So, a 32 bit processor needs 4 banks of memory. (Assuming such kind of hardware support, few processors will not have hardware pins representing least two bits).

The fun comes here. How to read data types, like char (one or two bytes), double (8 bytes always), vector types (GCC), etc... To overcome this issue, the processors provides byte read instruction (e.g. LDRB on ARM). These byte read instructions can identity, in which bank the byte is stored and shifts the data to Least Significant Byte position automatically during data fetch mode. This impacts on performance.

To get better performance characteristics, few architectures won't allow misalignments. The processor issues a platform exception which is to be addressed by the system programmer. Otherwise the results will be error prone.

I have published much better article on GeeksforGeeks.