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.

[Ioannis Vranos]

Mabden wrote:

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

In C90 a return statement is required, in C99 it is not.


Regards,

Ioannis Vranos

[Ioannis Vranos]

Julie wrote:

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

There.

Why?


Regards,

Ioannis Vranos

[Howard]

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

Julie wrote:

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

There.

Why?

Oooh, I know, I know! If used in a bubble sort, then you're *reducing*
efficiency, because you only call the swap after first determining that two
values are out of order...and that means you've already *done* the
comparison! :-)

-Howard

[Ioannis Vranos]

Howard wrote:

Oooh, I know, I know! If used in a bubble sort, then you're *reducing*
efficiency, because you only call the swap after first determining that two
values are out of order...and that means you've already *done* the
comparison! :-)

Yes I realised it myself after pressing the send button, however the
whole topic with xor is really stupid already.
And in this case, using xor for swapping in bubble sort...
I think this xor joke must end sometime now. After all it is a
specialised solution.


Regards,

Ioannis Vranos

[Xenos]

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

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

I don't think so. If I understand you correctly, you are optimizing for
the special (both object are the same), at the expensive of the normal case.
Unless your code is swapping big objects and tried to swap the same object
with itself often, you save nothing. The swap times of the normal case
(objects are different) will increase, although it will probably be
unnoticably small. The point being, the check added nothing for efficiency.

DrX

[Default User]

Mabden wrote:

"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:

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

Chapter and verse, please.

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

Just because your compiler decides to issue one doesn't mean it is
required (it's not) or that it will happen on other platforms.

Compilers are free to issue whatever diagnostics they wish. Many produce
a warning for things like:

if (a = 1)
{
}
They could issue warnings about misspellings in your comments if they
felt like it.

Brian Rodenborn

[Andre Kostur]

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

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?).

Actually, no. Consider:

1) The comparison of the two objects may be "expensive" (let's assume on
the order of seconds, just to be extreme)
2) The number of times in my own code that I'm going to attempt to swap
two variables that are equal is 0.

This means that I have to pay for this equality check every time I swap
two variables, just on the off chance that they might be the same.

Insert standard quotes about "premature optimization is the root of all
evil" (Knuth), and "More computing sins are committed in the name of
efficiency (without necessarily achieving it) than for any other single
reason - including blind stupidity." (W.A. Wulf)

[Ioannis Vranos]

Andre Kostur wrote:

Actually, no. Consider:

1) The comparison of the two objects may be "expensive" (let's assume on
the order of seconds, just to be extreme)
2) The number of times in my own code that I'm going to attempt to swap
two variables that are equal is 0.

This means that I have to pay for this equality check every time I swap
two variables, just on the off chance that they might be the same.

Insert standard quotes about "premature optimization is the root of all
evil" (Knuth), and "More computing sins are committed in the name of
efficiency (without necessarily achieving it) than for any other single
reason - including blind stupidity." (W.A. Wulf)

Indeed regarding this particular swap implementation concerning
integrals with the use of XOR, you are right. There are not efficiency
gains from such a comparison.
However for the general case where a temporary is used, such a
comparison produces efficiency gains (for the general use).
How would you implement the general form of std::swap for example?


Regards,

Ioannis Vranos

[Dik T. Winter]

In article <cb**********@u lysses.noc.ntua .gr> Ioannis Vranos <iv*@guesswh.at .grad.com> writes:

(For main:)

In C90 a return statement is required, in C99 it is not.

This is wrong. In both a return statement is not required, but in
C90 when the return statement is missing an undefined value is
returned to the environment, in C90 the value is defined. (Note
that it does *not* make it undefined behaviour in C90. It becomes
undefined behaviour when you call the function from within your
program and attempt to use the "returned" value.)

BTW, C90 also allows:
int main(void) { return;}
with the same effect; according to the draft this is not allowed in C99.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Tom]

JKop wrote:

Am I the only person here that thinks it's complete bullshit to think you
can swap the values of two variables without a temporary variable?! It
simply cannot be done. Why? Consider this, you have two containers, each of
capacity 3 litres. Each of them is filled with 2 litres of water. Swap the
water from the containers. Okay... let's just poor all of one of them into
the other. Mammy mammy! It was an accident, I didn't realize you can't put 4
litres of water into a 3 litre container.

Depends what you mean by "temporary variable." Most or all of the
standard containers (std::vector, std::list, std::map, etc.) have a
swap member function that performs the swap by swapping the internal
pointers behind the scenes - no temporary container is used. The
standard utility function std::swap (in <algorithm>), in turn, is
specialized on the standard containers to use the swap member
function. So at the end of the day, a temporary pointer is used
internally, but no temporary container is used. For example:

std::vector<int > a, b;
a.push_back(1);
a.push_back(2);
b.push_back(100 0);
b.push_back(200 0);
b.push_back(300 0);
std::swap(a, b);

No temporary std::vector is required for the call to std::swap in the
above code. Internally, a's and b's pointers to their respective data
are swapped - no data is actually copied into a temporary. Obviously,
there is a temporary pointer used, though.

The non-specialized version of std::swap uses a temporary.

Best regards,

Tom