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.