Open-Close doors puzzle

August 25, 2010

I come across an interesting puzzle on Gulli’s blog.

Given a number N, how may factor does it have? For example 4 has 1, 2 and 4 as factor, total 3. Can we generalize? Yes, we can.

Any number can be expressed as powers of prime numbers. Assume ‘x’ is prime in the following,

N = x^m – then N will have (m+1) factors. It is not necessary that N limits to one prime, an number can be power of more than one prime number.

N = x^m * yⁿ – in this case N will have (n+1)*(m+1) factors.

Here is interesting puzzle from the book introduction to algorithms by Anany V. Levitin,

“Locker doors: There are N lockers in a hallway, numbered sequentially from 1 to N. Initially all the locker doors are closed. You make N passes by the locker, each time starting with locker #1. on the k^th pass. K = 1, 2, … N, you toggle the door of every k^th locker, i.e. if the door is locked, open it and if the door is closed, open it. On the second pass toggle 2^nd, 4^th, 6^th … so on doors. After last pass (N^th) how many doors are closed and how many are opened?”

From the Euler’s analogy, each number except perfect square will even number of factors and perfect squares will have odd number of factors. Using the fact, we can conclude those number which are perfect squares must be toggled odd number of times, and other doors even number of times. Hence only those doors represent perfect square numbers will be toggled from their original position (i.e. they will be in open position if initially closed and vice versa). All other doors will be in their initial position.

Similar sort of puzzle we can found in the book “Heard on the Street”.

http://geeksforgeeks.org/

24^th, August 2010
Few months ago I found one interesting website regarding computing related queries. You can visit the same on http://geeksforgeeks.org/ maintained by group of REC friends. Worth reading who interested in learning. I suggest those who comments to be precise. I am also posting as member Venki.

Script Engines in Browser

20^th, August 2010

Most of us not aware of the technology behind a web browser. A script will be used for client side scripting to enhance user interface in dynamic websites. Inside the browser an engine (script engine) will be running to parse this script and renders the image.

Web browser will be next generation computing platform. I have come across two advanced Java Script engines. These technologies are interesting, you can see them in the following links.

http://en.wikipedia.org/wiki/Chakra_(JScript_engine)

http://en.wikipedia.org/wiki/V8_(JavaScript_engine)

What do you say? Browser war started again between two digital revolution giants? Who will be the winner?

In my opinion “common man” is the ultimate winner.

Care about small thinks as well during interview

14^th August, 2010

Don’t do it! J

I come across interesting interview story on the web. It goes as following…

Courtesy: http://niniane.org/interview_howto.html

A final story

I'd like to leave you with a story of an unfortunate interview. Draw hope that no matter how your interview goes, you will likely be more lucky than this candidate.

At Microsoft, we always offered drinks to our candidates, and one candidate "Jeff" took a pepsi. We got into my office, and he set it down on the desk. We started discussing his experiences and then launched into the whiteboard coding question, and he didn't get around to opening his pepsi.

We stood at the whiteboard, and Jeff started to write a line of code. He stopped to think about the overall algorithm, and absentmindedly took a step back in order to see the entire whiteboard. In doing so, he inadvertently knocked against the desk, and the pepsi fell off the edge.

This pepsi was still unopened. Thus, when it hit the ground, it exploded on impact.

Pepsi sprayed in foamy gusts in all directions from the can. It was a slow-motion moment as beige spots of soda splashed onto my white walls, my bookshelf, my keyboard. We both stood there frozen, our hands halfway out (too slow to catch the pepsi), looking at the dripping liquid coating the entire inside of my office.

We took a 5-minute break to get paper towels and mop up the mess. (Though my books always stuck together after that day, and my walls were never the same again.)

We then returned to the whiteboard question. Jeff was nervous by this time (understandably). He wrote some code, erased it, wrote more. He erased using his fingers against the board instead of using the eraser. Then sweat formed on his forehead, and he wiped it off using the same hand. By the end of the interview, his face was covered in streaks of red, green, and blue whiteboard marker.

I said, "I think you have some marker on your hands. I'll show you the restroom." and let the bathroom mirror show him the problem.

Moral: Caring small things value lot.

P ≠ NP - Vinay Deolalikar

12^th August, 2010

An interesting paper about class P and class NP problems. I read it on Gulli blgo, the same published on Bangalore Mirror next day. You can find the article here…

http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

Thanks to Gulli for posting it on his blog.

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.