Programming Puzzle

[Jatinder]

I found these questions on a web site and wish to share with all of u
out there,Can SomeOne Solve these Porgramming puzzles.
Programming Puzzles

Some companies certainly ask for these things. Specially Microsoft.
Here are my favorite puzzles. Don't send me emails asking for the
solutions.

Q1 Write a "Hello World" program in 'C' without using a semicolon.
Q2 Write a C++ program without using any loop (if, for, while etc) to
print numbers from 1 to 100 and 100 to 1;
Q3 C/C++ : Exchange two numbers without using a temporary variable.
Q4 C/C++ : Find if the given number is a power of 2.
Q5 C/C++ : Multiply x by 7 without using multiplication (*) operator.
Q6 C/C++ : Write a function in different ways that will return f(7) =
4 and f(4) = 7
Q7 Remove duplicates in array
Q8 Finding if there is any loop inside linked list.
Q9 Remove duplicates in an no key access database without using an
array
Q10 Write a program whose printed output is an exact copy of the
source. Needless to say, merely echoing the actual source file is not
allowed.
Q11 From a 'pool' of numbers (four '1's, four '2's .... four '6's),
each player selects a number and adds it to the total. Once a number
is used, it must be removed from the pool. The winner is the person
whose number makes the total equal 31 exactly.
Q12 Swap two numbers without using a third variable.
Given an array (group) of numbers write all the possible sub groups of
this group.
Q14 Convert (integer) number in binary without loops.

Q3,12 are similar , Q7 is simple & I know there answer For the Rest
please Help
Wiating for reply.

[Julie]

Howard wrote:

"Ioannis Vranos" <iv*@guesswh.at .grad.com> wrote in message
news:cb******** **@ulysses.noc. ntua.gr...

You are right about that, however in reality a decent swap
implementation would check if the passed arguments have the same value
so as to avoid unneeded operations.

And the need for that check is exactly one of the arguments for why this
choice of implementation was no better than using a temporary variable in
the first place. If you can afford the space for the code to check this
condition, then you can surely afford the space for the temporary integer
variable instead.

-Howard

You don't need the 'check' -- it is a precondition of the function: swap two
variables (numbers) w/o using a temporary.

Not everything has to have checks:

free((void*)123 45);

is going to die, as well it should as the spec clearly defines what is a valid
parameter, anything else is undefined.

[Julie]

josh wrote:

Julie wrote:

Please describe (in code) a situation where two variables share the same memory
location.

union
{
int x;
int y;
} a;

&a.x == &a.y

-josh

Yes, my good friend, unions, forgot all about them.

Still, you really only have 1 variable, just two different ways of looking at
it.

[Ioannis Vranos]

Julie wrote:

You are right about that, however in reality a decent swap
implementatio n would check if the passed arguments have the same value
so as to avoid unneeded operations.

Regards,

Ioannis Vranos

or simply state the precondition that the swap operates on 2 variables, no
check is necessary or warranted.

A decent swap function should perform a value equality check both for
safety and run-time efficiency, especially when this does not impose any
space/time concerns, perhaps in the style:
template<class T>
void swap(T &a, T &b)
{
if(a!=b)
{
// ...
}
}

In any case, we should stick with std::swap and provide specialisations
when necessary.


Regards,

Ioannis Vranos

[Howard]

"Julie" <ju***@nospam.c om> wrote in message
news:40******** *******@nospam. com...

Howard wrote: Break given.
Thanks! :-)

Your example doesn't swap two integers, it swaps one.

I know exactly what is meant -- using the xor technique on two variables will never fail; using the xor technique on the same variable (same literal
variable, reference, or pointer -- still all *ONE* variable) will fail for most cases.

You have given example(s) of the latter, *not* the former. There is no
disagreement on the latter.

There is no disagreement on the former, either. Just a difference in the
wording of the problem. To me, two pointers or references that refer to the
same memory location are still two differrent variables. But you are
correct...the memory locations being swapped in such a case are identical,
thus you could rightfuly call them "the same".

The importance, though, as it relates to actually *writing* a swap function,
is that the swap function itself cannot guarantee in advance that the
reference or pointer parameters passed into it will not at some point refer
to the same location in memory. Therefore, it is vital that such a swap
function include a guard against swapping the "same" variable. (Unless, of
course, you clearly document that the function does *not* guard against such
behavior, and declare such usage of the function as a violation of its
contract, generating undefined behavior.)

-Howard

[Julie]

Ioannis Vranos wrote:

Julie wrote:

You are right about that, however in reality a decent swap
implementatio n would check if the passed arguments have the same value
so as to avoid unneeded operations.

Regards,

Ioannis Vranos

or simply state the precondition that the swap operates on 2 variables, no
check is necessary or warranted.

A decent swap function should perform a value equality check both for
safety and run-time efficiency, especially when this does not impose any
space/time concerns, perhaps in the style:

This is purely subjective. Stating preconditions in the functional interface
description is perfectly appropriate.

Sanity checks can be implemented when/where warranted, but mostly serve to
verify that the user is obeying the preconditions.
template<class T>
void swap(T &a, T &b)
{
if(a!=b)
{
// ...
}
}

In any case, we should stick with std::swap and provide specialisations
when necessary.

Yeah, yeah, but that isn't what we are talking about.

[Ioannis Vranos]

Ioannis Vranos wrote:

A decent swap function should perform a value equality check both for
safety and run-time efficiency, especially when this does not impose any
space/time concerns, perhaps in the style:
template<class T>
void swap(T &a, T &b)
{
if(a!=b)
{
// ...
}
}

In any case, we should stick with std::swap and provide specialisations
when necessary.

That said, I would not place the equality/inequality check for the
possibility of the same variable passed in mind, but for efficiency. But
I would use a temporary variable anyway. :-)


Regards,

Ioannis Vranos

[Julie]

Howard wrote:

"Julie" <ju***@nospam.c om> wrote in message
news:40******** *******@nospam. com...

Howard wrote:

Break given.

Thanks! :-)

Your example doesn't swap two integers, it swaps one.

I know exactly what is meant -- using the xor technique on two variables

will

never fail; using the xor technique on the same variable (same literal
variable, reference, or pointer -- still all *ONE* variable) will fail for

most

cases.

You have given example(s) of the latter, *not* the former. There is no
disagreement on the latter.

There is no disagreement on the former, either. Just a difference in the
wording of the problem. To me, two pointers or references that refer to the
same memory location are still two differrent variables. But you are
correct...the memory locations being swapped in such a case are identical,
thus you could rightfuly call them "the same".

The importance, though, as it relates to actually *writing* a swap function,
is that the swap function itself cannot guarantee in advance that the
reference or pointer parameters passed into it will not at some point refer
to the same location in memory. Therefore, it is vital that such a swap
function include a guard against swapping the "same" variable. (Unless, of
course, you clearly document that the function does *not* guard against such
behavior, and declare such usage of the function as a violation of its
contract, generating undefined behavior.)

-Howard

Agreed.

For me, saying that 'swap operates on two variables' would be sufficient, but
for the sake of clarity, it could be documented that references to the same
variable leads to undefined behavior.

[Ioannis Vranos]

Julie wrote:

Agreed.

For me, saying that 'swap operates on two variables' would be sufficient, but
for the sake of clarity, it could be documented that references to the same
variable leads to undefined behavior.

However the whole approach is funny, since an equality check should be
placed for efficiency reasons anyway.

On the other hand if someone used the swap function passing the same
object twice explicitly, he would be an idiot (but the operation would
be safe).
In any case, an equality check is reasonable to be placed for efficiency
reasons (come on, doesn't this sound natural to you?).


Regards,

Ioannis Vranos

[Mabden]

"Dan Pop" <Da*****@cern.c h> wrote in message
news:cb******** ***@sunnews.cer n.ch...

In <zo************ ****@newssvr27. news.prodigy.co m> "Mabden" <mabden@sbc_glo bal.net> writes:

"Foobarius Frobinium" <fo******@youre mailbox.com> wrote in message
news:a7******* *************** ****@posting.go ogle.com...

js*******@sanch arnet.in (Jatinder) wrote in message

news:<22****** *************** *****@posting.g oogle.com>...

You mentioned MS often use these sorts of puzzles to test their
programmers. I got an even better one to stump even the best MS
programmers:
#include <stdio.h>

int main(void) {
int *foo = NULL;

fprintf(stdout, "%i\n", *foo);
}

What will happen if I compile and run this program??

You'll get a warning saying main() has no return value.

Chapter and verse, please.

C:\TEMP>type test.c
#include <stdio.h>

int main(void) {
int *foo = NULL;

fprintf(stdout, "%i\n", *foo);
}
C:\TEMP>cl -c test.c
Microsoft (R) C/C++ Optimizing Compiler Version 8.00c
Copyright (c) Microsoft Corp 1984-1993. All rights reserved.

test.c
test.c(7) : warning C4035: 'main' : no return value
--
Mabden

[Julie]

Ioannis Vranos wrote:

Julie wrote:

Agreed.

For me, saying that 'swap operates on two variables' would be sufficient, but
for the sake of clarity, it could be documented that references to the same
variable leads to undefined behavior.

However the whole approach is funny, since an equality check should be
placed for efficiency reasons anyway.

On the other hand if someone used the swap function passing the same
object twice explicitly, he would be an idiot (but the operation would
be safe).

In any case, an equality check is reasonable to be placed for efficiency
reasons (come on, doesn't this sound natural to you?).

Regards,

Ioannis Vranos

It definitely wouldn't be necessary (or warranted!) if using the xor swap in an
implementation of bubble sort.

There.