Complicated declarations in C and C++

8^th, August, 2010

Complicated declarations in C and C++

I have seen few questions related to complicated declarations in C and C++. For example see the following,

1. Declare a function with argument of int* which returns pointer to an array of integer pointers, http://geeksforgeeks.org/forum/topic/tcs-interview-question-about-cpuzzles-1
2. What does int (*fun2())[4] and int (*fun3)[3][4] mean? Posted on Geeksforgeeks site http://geeksforgeeks.org/forum/topic/pointer-doubt

Answer for case 1, int *(*foo(int *arg))[4];

‘foo’ is function taking integer argument and returning pointer to array of integer pointers.

An example code,

#include

// Symbolic size

#define SIZE_OF_ARRAY (4)

// pointer to array of (SIZE_OF_ARRAY) integers

typedef int *(*p_array_t)[SIZE_OF_ARRAY];

// Declaration : compiler should throw error

// if not matched with definition

int *(*foo(int *arg))[4];

// Definition  : foo returning pointer to an

// array of integer pointers

p_array_t foo(int *arg)

{

    // array of integer pointers

    static int *arr[SIZE_OF_ARRAY] = {NULL};

   

    // return this

    p_array_t pRet = &arr;

   

    return pRet;

}

void main()

{}

Let us see the other two declarations.

CASE 1: int (*fun2())[4];

int (*fun2())[4];

fun2() - A function taking no arguments, returning a pointer to array of 4 integers.

Let us see how I came to this conclusion.

In C and C++, every declaration will contain one declarator and one or more declaration specifiers. In the current declaration 'fun2' is declarator (an identifier in program context) and 'int', '4' are declaration specifiers. Dropping the declarator leaves the type information. So, the following is type

int(*())[4];

The parenthesis binds to the declarator due to their precedence. Further, the type information can be reduced to,

int(*)[4];

It is now clear that the above declaration is pointer to array of 4 integers.

Finally, the identifier 'fun2' is "a function with no arguments and returning pointer to array of 4 integers".

CASE 2: int(*fun3)[3][4];

It is pretty simple from the above description.

int(*fun3)[3][4];

After dropping the declarator we left with,

int(*)[3][4];

which is pointer to array of array of integers (dimensions are obvious).

So, the identifier 'fun3' is "a pointer to array of array of integers".

For more information, read the documentation related to C and C++ programming language references on MSDN.

Add two integers

22^nd, July 2010

Adding two integers without arithmetic operator

I heard this question multiple times, it is to judge our ability to link our understanding of digital circuits. I know, we can have some out-of-the box solutions. Given below, how I got the solution.

From digital circuits, recap that half adder can add two bits and full adder can add two bits along with carry bit, i.e. three bits. Can we augment the same logic here in software? The bitwise AND generates carry and XOR generates sum. C/C++ provides low level features to access bit level information.

Having understood the adder circuit logic, our algorithm can be depicted in the following steps,

1.     Inputs operands M and N

2.     Set sum = M XOR N

3.     Repeat the following steps until no carry

a.   Shift left the previously generated carry

b.   Save intermediate sum

c.   Update sum = sum XOR carry

4.     Stop

I have provided working code in the following links, http://ideone.com/gNi77 Try with negative numbers.

Question asked here http://geeksforgeeks.org/?p=8198#comment-1722

Find number of permutations using Stack

21^st, July, 2010

Find number of permutations

Assume we are receiving a stream of integers (1, 2, 3, 4, 5, … N). Using stack data structure (FIFO), find how many different permutations of the ordered stream is possible?

Solution: Interestingly, the answer is Catalan number.

A stack is a First In First Out data structure. The integers shall be pushed and popped in the order of their appearance in the input stream. Say, P(N) as possible permutations of the input stream. Let k representing an integer in the stream, hence the stack should contain k-1 elements and N-k-1 elements are in pipeline from the stream.

Fixing k position, the k-1 elements can be pushed and popped in (k-1)! ways. Similarly, the upcoming N-k-1 elements. In other words, there are P(k) permutations possible with the elements in the stack and P(N-k-1) permutations are possible with the upcoming integers. But, k can range from 1 to N, using multiplication and addition principle we get,

P(N) = ∑ P(k-1)P(N-k-1), k ranging from 1 to N, and P(1) = 1.

The expression P(N) is recursive. After expanding, we get Segner’s expression which can be represented in Catalan number.

P(N) = (2NcN)/(N+1) – Catalan Number C(N)

The above expression resembles the Catalan number. The Catalan numbers are ubiquitous.

Note that there are N! possible permutations using N integers, however, P(N) < N!. It is due to the definition of stack data structure.

Probability and Lagrange Identity

20^th July, 2010

Find the probability of meeting A and B.

Given a Cartesian plane as shown in the figure. Consider person A, initially at the origin and person B initially at the point (n, n) wants to meet. At each point (x, y), each one flips a coin and decides the next move; A moves up side on ‘Head’ and right side on ‘Tail’ to the next point, whereas B moves downward on ‘Head’ and left side on ‘Tail’ to the next point. Find the probability that they will meet within the square lattice.
Solution:

Say each point is one unit length. If A and B met, they must travel n points on total by both and meet on the diagonal at some point P. Let us assume, A traveled k units then B must travel (n – k) units. Hence they meet at point P(i, n − i), where 0 ≤ k ≤ n.

A has nCk possible ways from the origin where as B has nC(n – k) possible ways from point (n, n). Per multiplication principle, the total possible ways are (nCk) x ( nC(n – k) ). However, k can range from 0 to n. Summation of the product over possible values of k will give us the number of ways A and B can meet.

i.e. No of ways to meet = Sigma [(nCk) x ( nC(n – k) )], where 0 ≤ k ≤ n.

Simplified using Pascal identity, = Sigma [(nCk) x (nCk)], where 0 ≤ k ≤ n. Since, nCk = nC(n-k)

= Sigma [(nCk)]² , where 0 ≤ k ≤ n.

= 2nCn, Lagrange Identity

We are half done. What would be the total sample place? For each person A and B, it is possible to take 2ⁿ ways (sum of binomial coefficients). It means total sample space is 2²ⁿ. So, it is easy to find the probability.

Find the name ‘12345’

Yandamoori Veerendranath is one of my favorite authors of Telugu literature. In his novel “Vennello Adapilla” a fantasy story, the female character teases the male character. She makes a puzzle out of her name and challenges the hero to crack it, ofcourse he cracks it in few moments. It is goes something like,

“The name consists of five English letters. Put 26 dots on the paper each dot corresponds to each letter of English language. The name ends at the dot where it starts. What would be my name?”

With the inspiration of the above puzzle, a Telugu song from the movie “పల్లకిలో పెళ్లి కూతురు” was written, it was composed by Keeravani. The name mentioned in song is Raani. The answer to above puzzle is also near.

Horse Race

June 22, 2010

The following question is on races, similar to the previous post…

The tricky question, given 25 horses of different caliber, intent is to find best 3 horses in minimum possible number of races under the constraint that only 5 horses are allowed per race.

We can generalize the question as, set of N² horses and allowed N horses per race. How many minimum races are required to find best 3 horses?

Hint: Generalisation has the clue. You need to be aware of matrix optimization techniques. Also try, how to find 4^th best horse?

Find the second element

June 22, 2010

How can we find second best player in a tennis tournament? In other words, how can we find second largest element in an unordered array? Assume that the array is having all distinct elements. What is the affect on algorithm if the array contains duplicates?

In most of the standard text books on algorithms, we can see solution to the above problem. There are various ways; each method has its specialty in different scenarios.

Hint: Keep track of players/elements. Explore various methods of book keeping.

Bit Reversal

3^rd June, 2010.

In Embedded Systems Programming, it is often required to reverse bits in the machine word (it can be of any length). Usually in desktop programming we will have high speed processors that operate in the order of few Giga Hz. Where as in embedded systems such as cell phone the core operates in the order of hundreds of Mega Hz. Hence, every byte and every instruction is counted for best optimum algorithm. Note that computing power is not determined by processor speed. We have Param Padma super computer constructed on 630 nodes (processors) operating at low frequency.

It is important to select an optimum algorithm than playing with tricks. Further optimization can be achieved by fine tuning the algorithm implementation. A bit reversal would be required in places such as Fast Fourier Transform in implementing DSP algorithms. Here is algorithm to reverse bits of 32 bit word,

• Swap adjacent bits in the word, i.e. bit position pairs are (0, 1), (2, 3)…(28, 29), (30, 31).
• Swap adjacent 2 bits in the word, i.e. bit position pairs are (01, 23), (45, 67)…
• Swap adjacent 4 bits in the word
• Swap adjacent 8 bits in the word
• Swap adjacent 16 bits in the word

It can be done in log(32) = log(2⁵) = 5 steps. It is analogous to binary search algorithm. Similar technique can be used to count number of 1 bits in the word. Try it.

Dropping a Ball

1^st June, 2010

The puzzle is from famous puzzlest Sam Lyod.

A ball is dropped from building of 100 m height. The ball bounces 10 % of previous height due to Earth reaction. Question is how long the ball traveled before ceasing its motion?

If you get the answer as [h + h/10 + h/100 + h/1000 + so on], you have a lacuna in the problem understanding.  Because except the first instance, the ball travels twice the distance of drop height. The solution fall into G. P. of infinite series. The answer is 122.22 m. Try it.

Here is a hint,

S(n) = h + h ² + h ³ + h ⁴ + …

h x S(n) = h ² + h ³ + h ⁴ + …

After simple subtraction we get the following simplification for S(n)

S(n) [1 – h] = h ==> S(n) = h/(1-h)

Workers and Wages

9^th May, 2010

The following question I heard during my childhood from an old “Cha Cha”…

There are 100 people including Male, Female and Children working in a paddy field. The landlord is liberal in allowing any number of male, female and children, at total of 100 workers per day.

As per daily wages, each male is paid Rs.7/-, each female is paid Rs.5/- and each kid is paid Rs.1/-. Concerning the quality of work, the landlord is not willing to pay more than Rs.250/- worth of work per day.

The question is, with in the limit of 100 workers per day, how many ways the worker’s leader can shuffle male, female and children such that they can yield Rs.250/- worth of work every day.

As usual, the emphasis is not in getting the answer, a school kid can guess atlest one solution by trail and error method. Interestingly, there are 13 possible solutions.

How to solve it…, simple, apply mathematics?