473,839 Members | 1,480 Online

# Programming Puzzle

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
Nov 14 '05
271 20376
Da*****@cern.ch (Dan Pop) wrote in message news:<cb******* ****@sunnews.ce rn.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.go ogle.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.

Well, you should, depending on compiler flags. gcc -Wall gives you:

foo.c: In function `main':
foo.c:10: warning: control reaches end of non-void function

Which is besides the point as I was making a joke about how shitty MS
programs are. Obviously, this will segfault.

Dan

Nov 14 '05 #161
In article <cb**********@o ravannahka.hels inki.fi>,
Joona I Palaste <pa*****@cc.hel sinki.fi> wrote:
Siemel Naran <Si*********@re move.att.net> scribbled the following
on comp.lang.c:
"Jerry Coffin" <jc*****@taeus. com> wrote in message
news:b2******** *************** **@posting.goog le.com...
Almost anything you'd normally do with iteration can also be done with
tail recursion.

What is "tail" recursion? Are there other types of recursion?

Tail recursion is first doing the computation, then recursing. Head
recursion is the other way around.

There's a generally-accepted definition that pins it down more precisely
than this.

A "tail call" is a call to a function where the return value of that
function is returned directly from the calling function without any
further processing:
--------
int foo(int i)
{
int j;
j=do_nontail_ca ll(i);
return do_tail_call(j) ;
}
--------
(Or even:
--------
int foo2(int i)
{
return do_tail_call(do _nontail_call(i ));
}
--------
which when untangled does the exact same thing, but doing the untangling
may lead to a clearer idea of where exactly the boundary is.)
It's possible, in theory at least (though some parameter passing
mechanisms make it too difficult to be worth the effort), to remove
the invocation record for the function making the tail call from the
invocation-record stack and have the tail-called function return directly
to the function that made the last non-tail function call.

"Tail recursion" is recursion accomplished using tail calls. Note that
this is a property of the calls made and not simply of the function
itself, and it's possible to make a tail-recursive and non-tail-recursive
call to the same function:
--------
void untested_and_pr obably_buggy_qu icksort(int *data,size_t n)
{
int middle_index;

/*Make sure the recursion terminates*/
if(n<2)
return;

/*Hand-waving to avoid having to do too much thinking*/
middle_index=un tested_and_prob ably_buggy_part ition(data,n);

/*Non-tail-recursive call*/
untested_and_pr obably_buggy_qu icksort(data,mi ddle_index-1);

/*Tail-recursive call*/
untested_and_pr obably_buggy_qu icksort(data+mi ddle_index+1,
n-middle_index-1);
/*Note that even though we're not actually returning anything,
we're not doing anything between when the tail call returns
and when we return.
*/
}
--------
The aforementioned invocation-record-stack optimization for tail calls
has the effect of converting tail recursion into iteration, so the above
is exactly equivalent (assuming this optimization does indeed occur) to:
--------
void untested_and_pr obably_buggy_qu icksort(int *data,size_t n)
{
int middle_index;

/*A compiler may not be clever enough to convert the exit
condition from the if(...)return form to while(...) directly,
but a good optimizer should generate the same code for
both forms.
*/
while(n>1)
{
/*These are the same as the tail-recursive version*/
middle_index=un tested_and_prob ably_buggy_part ition(data,n);
untested_and_pr obably_buggy_qu icksort(data,mi ddle_index-1);

/*Here we're replacing the old parameters with the values
they'd have in the next (tail-recursive) invocation,
then going back to the top of the loop
*/
data=data+middl e_index+1;
n=n-middle_index-1;
}
}
--------
dave

--
Dave Vandervies dj******@csclub .uwaterloo.ca
[Knuth] writes that some authors have declared the method optimal, but he is
kind enough to spare them embarrassment by omitting their names; clearly they
forgot to consider cases like n==15. --Eric Sosman in comp.lang.c
Nov 14 '05 #162
>> #include "card_t.h" /* This is part of the program, NOT the
#implementation */ define DECKSIZE 52
...
int i,j;
card_t deck[DECKSIZE];

/* bogo-shuffle the cards */
for (i = 0; i < DECKSIZE; i++) {
for (j = 0; j < DECKSIZE; j++) {
/*
* DO NOT CHANGE THE LINE OF CODE BELOW.
* Note: rand() % 2 is used here because it is
* a poor random number generator in many
* implementations , and if it isn't possible to
* cheat, *THEY* will break your legs repeatedly
* and cut off your supply of semicolons.
*/
if (rand() % 2) {
swap(&deck[i], &deck[j]);
}
}
}

Hi,

I apologize, for this might not be the topic of this thread, however I feel
compelled to comment on this bogo-shuffle: is that taken from a text on how
*not* to generate a random permutation?

No, it was not taken from a text. It is original code written for
the post. I needed an excuse for why I might want to swap two
elements of an array, possibly even if they happen to be the same
element.
a) The use of rand() % 2 is bad. In a different thread I came across a
random number generator that would produce a strictly alternating sequence
of bits when used this way. The funny comment indicates that the author was
acutally aware of this shortcoming.
An implementation of rand() can SUCK(tm) without producing a strictly
alternating sequence of bits, although it's hard to make it suck
strictly worse than that (I suppose always returning 1 or always
returning zero qualifies as sucking worse, though). Why do you
think the comment was in there?
b) The method has quadratic runtime in DECKSIZE. Clearly a random-shuffle
can and should be done in linear time.
Clearly a performance criteria for a method does not have to specify
a MAXIMUM runtime; sometimes it is desired for performance to be
at least so BAD and worse is possible (for example, making the
algorithm HARD to implement efficiently was one concern in the
original design of UNIX password encryption). Another example is
the use of 16 nested infinite loops where a single infinite loop
would do.
c) Finally, even with a perfect random number generator, this method is
guaranteed *not* to give equal probabilities to the different permutations.
For small DECKSIZE, the difference is even noticable.

A bogosort sorts by generating all possible permutations of the
input, then (bubble) sorting the permutations by the number of
elements out of order, and returning the one with the least number
of elements out of order. In other words, it replaces the job of
sorting N elements to one of sorting N! elements. A recursive
bogosort uses bogosort instead of bubble sort to sort the permutations,
thus replacing the job of sorting N elements with one of sorting
N!!!!!!!!!!!!!! !!!!!!!!!!!!!! ... It is also likely to cause the
heat death of at least 2**(N!) universes before it finishes (by
crashing due to trying to use more memory than there are particles
in the universe).

A bogo-shuffle, named after bogosort, is a poorly-implemented, SLOW
shuffle but it doesn't come close to the inefficiency of the recursive
bogosort. You probably won't ever get to use it enough to discover
that the probabilities aren't equal. Nobody lives that long.

Gordon L. Burditt
Nov 14 '05 #163
On Mon, 28 Jun 2004 13:48:36 -0700, Julie <ju***@nospam.c om> wrote:
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

Isn't this exectly what C99's 'restrict' type qualifier is for?

Jim
Nov 14 '05 #164
On Mon, 28 Jun 2004 04:16:52 +0300, Ioannis Vranos wrote:
Jatinder wrote:

Ok I couldn't resist so I 'll give my answers to these questions. As a
poster has done previously, where "C" is mentioned I consider C++98 (I
view these from clc++).

Me neither.
> Q2 Write a C++ program without using any loop (if, for, while etc) to
> print numbers from 1 to 100 and 100 to 1;

Note: There is a restriction for if statements, but if statements do not
constitute a loop.

<snip recursive version>

I suspect what they meant was something of this sort:

#include <iostream>

template <int i> class Count
{
Count<i-1> c;
public:
Count() : c() { std::cout << i << std::endl; }
};

template <> class Count<1>
{
public:
Count() { std::cout << "1" << std::endl; }
};

int main(void)
{
Count<100> c;
return 0;
}

With a modification to count back down.

Tim.
Nov 14 '05 #165

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

Could you please post the relevant code that sets up two variables that share the same memory location?

This is a good start:

- Risto -
Nov 14 '05 #166
Julie wrote:
Please describe (in code) a situation where two
variables share the same memory location.

In post
in the function n_sort, the variable (*node),
has the same address as either (tail) or (head) after this line:

--
pete
Nov 14 '05 #167
In <a7************ **************@ posting.google. com> fo******@yourem ailbox.com (Foobarius Frobinium) writes:
Da*****@cern.c h (Dan Pop) wrote in message news:<cb******* ****@sunnews.ce rn.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.go ogle.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.

Well, you should, depending on compiler flags.

Sez who?
gcc -Wall gives you:

foo.c: In function `main':
foo.c:10: warning: control reaches end of non-void function

Add a -std=c99 to your gcc invocation and the warning goes away.

My point was that it is sheer nonsense to say "you'll get a warning about
that" if the standard doesn't *require* a diagnostic.

I entirely agree that the code deserves a diagnostic, even when compiled
in C99 mode, but this is something completely different.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #168
In <40************ ***@nospam.com> Julie <ju***@nospam.c om> writes:
Dingo wrote:

Julie <ju***@nospam.c om> wrote in message news:<40******* ********@nospam .com>...
> Gordon Burditt wrote:
> >
> > >> >Not one, but *two* ways to do it have been
> > >> >shown in this thread. Of course it will break down if those variables
> > >> >happen to share the same memory location, which can be the case if using
> > >> >pointers and indirecting through them.
> > >
> > >Please describe (in code) a situation where two variables share the same memory
> > >location.
> >
> > A union?
>
> Nope -- a union is still a single variable, with just different ways to access
> it.

I wish to understand why you think a union member is not one.

I'll retract my statement -- I'll agree that a union does allow for two
variables to share the same memory address.

And, if you think even harder, you'll realise that it's the same thing
with pointers: *p and *q are two different variables, but they may share
the same memory address, depending on how the p and q variables have been
initialised (e.g. one may be pointing to one member of the union, the
other may be pointing to the other member of the union mentioned in the
union example :-)

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #169
In <cb**********@u lysses.noc.ntua .gr> Ioannis Vranos <iv*@guesswh.at .grad.com> writes:
Dan Pop wrote:

What is a *variable* length array with a small *fixed* size? Looks like
an oxymoron to me...

C++'s std::vector for example is of variable length, however usage in
the style:

vector<int> somearray(5);

is too common.

Which has nothing to do with *your* usage of the term VLA, which has a
very well defined meaning in C99.
Nope, plain char is NOT exempt from trap representations . Furthermore,
even without trap representations , plain char can have padding bits and
a -0 may become a +0 when copied via a char on one's complement and
sign-magnitude implementations :

I do not know/have understood what "trap representations " actually are,
however in C++98 it is guaranteed to be safe to read POD types as
sequences of chars and unsigned chars:

It doesn't matter: in the common subset of the two languages, it is
*always* the most restrictive language that "wins".

However, if C++ allows one's complement and sign-magnitude, the guarantees
about plain char are a lie: because -0 and +0 are different
representations of the *same* value and you're effectively losing
information when reading a byte through a plain char: bytes with all
bits zero and bytes with all bits one will be read as having the *same*
value. And if you copy this value to another place, you have no guarantee
that the same representation will be used.

That is, assuming that plain char has the same semantics in both
languages: a type *different* from both signed char and unsigned char, but
sharing the semantics of one of them.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #170

This thread has been closed and replies have been disabled. Please start a new discussion.