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.

[Gordon Burditt]

>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
You can, for certain variable types. But the bullshit I see most
often related to this topic is a claim that swapping the values of
two values without a temporary variable is in some way FASTER
(usually such a claim is made in a platform-independent manner. A
claim that B is faster than or slower than or about as fast as C
is usually false when the platform is not specified (and I'm not
even sure about the case where C is "execute B one billion times").),
CLEARER, or BETTER.
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.

Unsigned int variables have better-defined overflow characteristics than
hypothetical water-bucket variables.

Gordon L. Burditt

[Joona I Palaste]

Mabden <mabden@sbc_global.net> scribbled the following
on comp.lang.c:

"Nick Landsberg" <hu*****@worldnet.att.net> wrote in message
news:uC*******************@bgtnsc05-news.ops.worldnet.att.net...

> The "xor" method will *not* work on two variables with the same memory
> location. You'd expect the swap to be a no-op, but it ends up setting
> both variables to 0, because it "xors" the first variable with itself,
> yielding 0, and then keeps "xorring" this 0 with itself.
You are correct. I should have said two different/distinct
memory locations.

Uuuuhhh... if the two "variables" point to the same location, then the swap
is done!

The post-condition of a swap algorithm is indeed satisfied without even
running any algorithm. But if you nevertheless *do* run the "xor"
algorithm, both variables end up being 0.

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"Shh! The maestro is decomposing!"
- Gary Larson

[Ioannis Vranos]

Foobarius Frobinium wrote:

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:

/* vim:ts=4
*/

#include <stdio.h>

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

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

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

Undefined behaviour (probably crash).


Regards,

Ioannis Vranos

[JKop]

Gordon Burditt posted:

Unsigned int variables have better-defined overflow characteristics
than hypothetical water-bucket variables.

This I don't even want to understand.

If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.
-JKop

[JKop]

Mabden posted:

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

No he won't.
#include <iostream>

int main(void)
{
std::cout << "Hello World!";
}

If that doesn't compile, then you haven't got a C++ compiler.
-JKop

[Richard Bos]

JKop <NU**@NULL.NULL> wrote:

Gordon Burditt posted:

Unsigned int variables have better-defined overflow characteristics
than hypothetical water-bucket variables.

This I don't even want to understand.

If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

Note that this is cross-posted to c.l.c. I presume Gordon was speaking
from a C POV, not from C++. I don't know whether C++ does this
different, but...

# A computation involving unsigned operands can never overflow, because
# a result that cannot be represented by the resulting unsigned integer
# type is reduced modulo the number that is one greater than the largest
# value that can be represented by the resulting type.

That's from C99, 6.2.5#9.

I don't know how you get from that to "an amorphous blob of memory being
wasted", and frankly, I'm not sure I want to.

Richard

[Joona I Palaste]

JKop <NU**@null.null> scribbled the following
on comp.lang.c:

Gordon Burditt posted:

Unsigned int variables have better-defined overflow characteristics
than hypothetical water-bucket variables.

This I don't even want to understand. If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

The overflow of unsigned integer types is perfectly defined in ISO
standard C. The values "roll over", which means that if a value is
larger than the maximum, the maximum is substracted from it. For
example suppose a 16-bit unsigned short. Attempting to store 65536
into it will store 0, attempting to store 65537 will store 1, and so
on.
The overflow of *signed* integer types is not defined.

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"This is a personnel commuter."
- Train driver in Scientific American

[Joona I Palaste]

Joona I Palaste <pa*****@cc.helsinki.fi> scribbled the following
on comp.lang.c:

JKop <NU**@null.null> scribbled the following
on comp.lang.c:

Gordon Burditt posted:

Unsigned int variables have better-defined overflow characteristics
than hypothetical water-bucket variables.

This I don't even want to understand. If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

The overflow of unsigned integer types is perfectly defined in ISO
standard C. The values "roll over", which means that if a value is
larger than the maximum, the maximum is substracted from it. For
example suppose a 16-bit unsigned short. Attempting to store 65536
into it will store 0, attempting to store 65537 will store 1, and so
on.
The overflow of *signed* integer types is not defined.

Dang, made a fencepost error. I meant, if a value is larger than the
maximum value, the *number of possible values* is substracted from it.
As the minimum value is 0, the number of possible values is equal to
the maximum value plus one.

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"'I' is the most beautiful word in the world."
- John Nordberg

[Peter Nilsson]

"JKop" <NU**@NULL.NULL> wrote in message news:U_*****************@news.indigo.ie...

Gordon Burditt posted:

Unsigned int variables have better-defined overflow characteristics
than hypothetical water-bucket variables.

This I don't even want to understand.

If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

C99 states... [C90 and C++ are not dissimilar...]

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

Although, there is slight catch. For unsigned types promotable to int, there are potential
problems...

unsigned short x = 1024;
unsigned short y = 1024;
unsigned short z = x * y;

The unsigned short operands of * will likely be promoted to int, and the calculation 1024
* 1024 can overflow a 16-bit int.

--
Peter

[Richard Herring]

In message <zo****************@newssvr27.news.prodigy.com>, Mabden
<mabden@sbc_global.net> writes

"Foobarius Frobinium" <fo******@youremailbox.com> wrote in message
news:a7**************************@posting.google. com...

js*******@sancharnet.in (Jatinder) wrote in message

news:<22**************************@posting.google .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.

Not on this side of the crossposting ;-)

--
Richard Herring

[Richard Herring]

In message <22**************************@posting.google.com >, Jatinder
<js*******@sancharnet.in> writes

Given an array (group) of numbers write all the possible sub groups of
this group.

Beware that this can't be using "group" in its normal mathematical
sense, since it doesn't specify an operator. If it really does mean
group, you need to remember that not every subset constitutes a
subgroup.

--
Richard Herring

[Ioannis Vranos]

JKop wrote:

Unsigned int variables have better-defined overflow characteristics
than hypothetical water-bucket variables.

This I don't even want to understand.

If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).


Regards,

Ioannis Vranos

[Ioannis Vranos]

JKop wrote:

Unsigned int variables have better-defined overflow characteristics
than hypothetical water-bucket variables.

This I don't even want to understand.

If you're telling me that unsigned ints overflow in nice eloquent way, then
my only conclusion is that there's an amorphous blob of memory being wasted.

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).


Regards,

Ioannis Vranos

[JKop]

Ioannis Vranos posted:

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).

Okay, then it depends on one's definition of "over-flow".

I'd call your example "over-flow".
Consider (on an 8-Bit char system):
unsigned char a = 200;

unsigned char b = 100;

unsigned char c = ( a + b );
I'd call that over-flow, ie. you want it to be 300, but the storage system
can't accomodate it.
Let's try swap the values of a and b without a temp variable:
int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b; // a == 300, b == 100

b = a - b; // a == 300, b == 200

a = a - b; // a == 100, b == 200

}
That's what'll happen it the beautiful land of jelly, where nobody gets sick
and everyone stays young for ever.

Here's what'll really happen:

int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b // a == 45, b == 100

b = a - b // a == 200, b == 100

a = a - b // a == 100, b == 100

}
Now, as far as I know, if you switch

a == 200, b == 100
you don't get:

a == 100, b == 100
But that's just human observation.
-JKop

[Walter Tross]

JKop 2004-06-28 :

Ioannis Vranos posted:

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).

Okay, then it depends on one's definition of "over-flow".

I'd call your example "over-flow".
Consider (on an 8-Bit char system):
unsigned char a = 200;

unsigned char b = 100;

unsigned char c = ( a + b );
I'd call that over-flow, ie. you want it to be 300, but the storage system
can't accomodate it.
Let's try swap the values of a and b without a temp variable:
int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b; // a == 300, b == 100

b = a - b; // a == 300, b == 200

a = a - b; // a == 100, b == 200

}
That's what'll happen it the beautiful land of jelly, where nobody gets sick
and everyone stays young for ever.

Here's what'll really happen:

int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b // a == 45, b == 100

b = a - b // a == 200, b == 100

a = a - b // a == 100, b == 100

}
Now, as far as I know, if you switch

a == 200, b == 100
you don't get:

a == 100, b == 100
But that's just human observation.

Jkop, you didn't observe anything.
I must tell you: you forgot to switch on your brain before writing,
as usual. Please don't fill this newsgroup with useless, wrong and
misleading posts.

Walter Tross

[Richard Herring]

In message <WB*****************@news.indigo.ie>, JKop <NU**@NULL.NULL>
writes

Ioannis Vranos posted:

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).

Okay, then it depends on one's definition of "over-flow".

I'd call your example "over-flow".
Consider (on an 8-Bit char system):
unsigned char a = 200;

unsigned char b = 100;

unsigned char c = ( a + b );
I'd call that over-flow, ie. you want it to be 300, but the storage system
can't accomodate it.

So it takes the result mod 256. That's 44.

Let's try swap the values of a and b without a temp variable:
int main()
{
unsigned char a = 200;
unsigned char b = 100;
a = a + b; // a == 300, b == 100
b = a - b; // a == 300, b == 200
a = a - b; // a == 100, b == 200
}
That's what'll happen it the beautiful land of jelly, where nobody gets sick
and everyone stays young for ever.

Here's what'll really happen:

int main()
{
unsigned char a = 200;
unsigned char b = 100;
a = a + b // a == 45, b == 100
Bzzzt. Out by 1. Overflow, so subtract 256. a == 44, b == 100
b = a - b // a == 200, b == 100
What? a doesn't change. b underflows, so add 256. a = 44, b == 200
a = a - b // a == 100, b == 100
a underflows, so add 256. a == 100, b == 200
}
Modulo 256, the two "programs" are identical.

Now, as far as I know, if you switch

a == 200, b == 100
you don't get:

a == 100, b == 100
But that's just human observation.

My observation would be "when in hole, stop digging."

--
Richard Herring

[John Cochran]

In article <WB*****************@news.indigo.ie>, JKop <NU**@NULL.NULL> wrote:

Ioannis Vranos posted:

Unsigned integer types have a well defined behaviour both in C and C++.
If the variable gets increased past the maximum value then it wraps
around (begins from 0 again).

SNIP
Here's what'll really happen:

int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b // a == 45, b == 100

b = a - b // a == 200, b == 100

a = a - b // a == 100, b == 100

}

You need to check your math. You have
made a mistake. Here is what really happens...

bash-2.05b$ cat demo.c
#include <stdio.h>

int main()
{
unsigned char a = 200;
unsigned char b = 100;

printf("1. %u %u\n", a, b);
a = a + b;
printf("2. %u %u\n", a, b);
b = a - b;
printf("3. %u %u\n", a, b);
a = a - b;
printf("4. %u %u\n", a, b);

return 0;
}

bash-2.05b$ make demo
cc -O -pipe -march=pentium3 demo.c -o demo
bash-2.05b$ ./demo
1. 200 100
2. 44 100
3. 44 200
4. 100 200
bash-2.05b$

[Richard Delorme]

JKop a écrit :

Here's what'll really happen:

int main()
{
unsigned char a = 200;

unsigned char b = 100;

a = a + b // a == 45, b == 100
should be:
a = a + b; // a == 44, b == 100
b = a - b // a == 200, b == 100
should be:
b = a - b; // a == 44, b == 200
a = a - b // a == 100, b == 100
should be:
a = a - b; // a == 100, b == 200 }
Now, as far as I know, if you switch

a == 200, b == 100
you don't get:

a == 100, b == 100
No, you get a == 100, b == 200.

But that's just human observation.

^^^^^

hmmm... next time use a computer.

--
Richard

[JKop]

John Cochran posted:

1. 200 100
2. 44 100
3. 44 200
4. 100 200

I see! I thought that yous weren't paying attention to over/under-flow.
Nobody mentioned it at all, so I just pressumed. So is this non-undefined
behaviour?

-JKop

[John Cochran]

In article <9K*****************@news.indigo.ie>, JKop <NU**@NULL.NULL> wrote:

John Cochran posted:

1. 200 100
2. 44 100
3. 44 200
4. 100 200

I see! I thought that yous weren't paying attention to over/under-flow.
Nobody mentioned it at all, so I just pressumed. So is this non-undefined
behaviour?

-JKop

Overflow and underflow for unsigned integers is very well defined in C and C++,
that's what people have been attempting to tell you in this thread for quite
some time.

[Ioannis Vranos]

JKop wrote:

John Cochran posted:

1. 200 100
2. 44 100
3. 44 200
4. 100 200

I see! I thought that yous weren't paying attention to over/under-flow.
Nobody mentioned it at all, so I just pressumed. So is this non-undefined
behaviour?

For *unsigned integers*, the behaviour is well-defined both for overflow
and underflow (it wraps around). So you can get the maximum value of an
unsigned integer by using -1. This one is used *extensively*.

For example:
// Equivalent to unsigned long li=numeric_limits<unsigned long>::max();
unsigned long li=-1;
unsigned char uc=-1;

and so on.


Regards,

Ioannis Vranos

[Dan Pop]

In <zo****************@newssvr27.news.prodigy.com> "Mabden" <mabden@sbc_global.net> writes:

"Foobarius Frobinium" <fo******@youremailbox.com> wrote in message
news:a7**************************@posting.google. com...

js*******@sancharnet.in (Jatinder) wrote in message

news:<22**************************@posting.google .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.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Dan Pop]

In <cb**********@oravannahka.helsinki.fi> Joona I Palaste <pa*****@cc.helsinki.fi> writes:

JKop <NU**@null.null> scribbled the following
on comp.lang.c:

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.

Fools.

The only foolish assumption is that bits behave like water...
It *can* be done! Not with all kinds of variables, but with unsigned
integer types, it's easy.
If you can do it with unsigned integer types, you can do it with all kinds
of objects, by aliasing them with arrays of unsigned char.
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.

OTOH, if you're using pointers, there's nothing preventing you from
testing the pointers for equality, before starting, is there?

So, the method can be universally used in C, if there is a *good* reason.
And the only good reason I can imagine is the failure to allocate memory
for a temporary object (some objects can be greater than others, some
systems can have smaller memories than others...).

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Dan Pop]

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

Joona I Palaste wrote:

It *can* be done! Not with all kinds of variables, but with unsigned
integer types,

I had somewhere in my mind the unsigned restriction, but then I checked
the standard and saw that XOR is safe to be applied on both integral
types and enumerations. Then how does this unsigned restriction come?

C99 answer:

4 Some operators (the unary operator ~, and the binary operators
<<, >>, &, ^, and |, collectively described as bitwise
operators) are required to have operands that have integer
type. These operators return values that depend on the internal
representations of integers, and have implementation-defined
and undefined aspects for signed types.

Consider, for example, 0 ^ 0, whose result (an int with all bits set) is
a trap representation, as explicitly allowed by C99 for one's complement.

It's hard to find an example for two's complement using the ^ operator,
but it can be done with ~INT_MAX, if the representation with the sign
bit set and all the value bits reset is a trap representation (again,
explicitly allowed by C99 for two's complement and sign-magnitude).

Whether real world implementations have such trap representations is a
completely different story...

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Julie]

Dan Pop wrote:

In <cb**********@oravannahka.helsinki.fi> Joona I Palaste <pa*****@cc.helsinki.fi> writes:

JKop <NU**@null.null> scribbled the following
on comp.lang.c:

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.

Fools.

The only foolish assumption is that bits behave like water...

It *can* be done! Not with all kinds of variables, but with unsigned
integer types, it's easy.

If you can do it with unsigned integer types, you can do it with all kinds
of objects, by aliasing them with arrays of unsigned char.

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.

OTOH, if you're using pointers, there's nothing preventing you from
testing the pointers for equality, before starting, is there?

So, the method can be universally used in C, if there is a *good* reason.
And the only good reason I can imagine is the failure to allocate memory
for a temporary object (some objects can be greater than others, some
systems can have smaller memories than others...).

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Julie]

Jerry Coffin wrote:

Q7 Remove duplicates in array

You can't really "remove" an element from an array, so this is poorly
defined. If it was a C++ vector (for example) std::sort and
std::unique would render it trivial, as would inserting the elements
into an std::set, and then copying them back out. Doing it quickly
while retaining the original order is a little more challenging.

How can you _not_ remove an element from an array?

Here is a trivial case:

size_t count = 2;
int * array = (int *)malloc(sizeof(int) * count);
array[0] = 42;
array[1] = 9000;
array = (int *)realloc(array, sizeof(int) * (--count));

Are you saying that an element hasn't been removed?

[Howard]

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

Jerry Coffin wrote:

Q7 Remove duplicates in array

You can't really "remove" an element from an array, so this is poorly
defined. If it was a C++ vector (for example) std::sort and
std::unique would render it trivial, as would inserting the elements
into an std::set, and then copying them back out. Doing it quickly
while retaining the original order is a little more challenging.

How can you _not_ remove an element from an array?

Here is a trivial case:

size_t count = 2;
int * array = (int *)malloc(sizeof(int) * count);
array[0] = 42;
array[1] = 9000;
array = (int *)realloc(array, sizeof(int) * (--count));

Are you saying that an element hasn't been removed?

Well, that's not *really* removing an element from the array, it's simply
reallocating data storage. How would your example look if you wanted to
remove an element from other than the last position? You'd have to write
code to shift the other elements to the front of the array, not just resize
the memory allocation.

-Howard

[Julie]

Howard wrote:

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

Jerry Coffin wrote:

> Q7 Remove duplicates in array

You can't really "remove" an element from an array, so this is poorly
defined. If it was a C++ vector (for example) std::sort and
std::unique would render it trivial, as would inserting the elements
into an std::set, and then copying them back out. Doing it quickly
while retaining the original order is a little more challenging.
How can you _not_ remove an element from an array?

Here is a trivial case:

size_t count = 2;
int * array = (int *)malloc(sizeof(int) * count);
array[0] = 42;
array[1] = 9000;
array = (int *)realloc(array, sizeof(int) * (--count));

Are you saying that an element hasn't been removed?

Well, that's not *really* removing an element from the array, it's simply
reallocating data storage.

Well, if that isn't removing, then I don't know what is... Reallocation is
merely an implementation detail, net result is that an element has been
removed.
How would your example look if you wanted to
remove an element from other than the last position? You'd have to write
code to shift the other elements to the front of the array, not just resize
the memory allocation.

Exactly. I started w/ the trivial case of removing the last element. Removing
any other position would merely involve calling memmove or similar to shift the
contents down and then reallocating.

Still sounds like removing an element from an array to me...

[Howard]

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

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 usingpointers and indirecting through them.

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

memory location.

Just like described, using pointers. (References can also be used.)

void pswap( int* px, int* py )
{
*px = *px ^ ^py;
*py = *py ^ *px;
*px = *px ^ *py;
}

....calling code:...
int x = 3;
int* px = &x;
int* py = &x;
pswap( px, py );
-Howard

[Branimir Maksimovic]

js*******@sancharnet.in (Jatinder) wrote in message news:<22**************************@posting.google. com>...

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.

#include <cstdio>
using namespace std;int main(){const char* s="#include <cstdio>%cusing
namespace std;int main(){const char*
s=%c%s%c;printf(s,10,34,s,34,10);}%c";printf(s,10, 34,s,34,10);}

Greetings, Bane.

[Dan Pop]

In <40***************@nospam.com> Julie <ju***@nospam.com> writes:

In <cb**********@oravannahka.helsinki.fi> Joona I Palaste <pa*****@cc.helsinki.fi> writes:

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

Since you seem to be unable to understand plain English:

#include <stdio.h>

void swap(int *p, int *q) { ... }

int main()
{
int i = 10;
swap(&i, &i);
printf("%d\n", i);
return 0;
}

Try this code for different implementations of the swap function, using
a temp var and using in-place swapping. Compare the results.

This example is trivial, but the situation can realistically arise in more
complex algorithms.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Julie]

Howard wrote:

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

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

Just like described, using pointers. (References can also be used.)

void pswap( int* px, int* py )
{
*px = *px ^ ^py;
*py = *py ^ *px;
*px = *px ^ *py;
}

...calling code:...
int x = 3;
int* px = &x;
int* py = &x;
pswap( px, py );

-Howard

Yes, but the two variables are pointers, and they do not share the same memory
location -- they may *point* to the same location.

So, I still haven't seen two variables that share the same memory location. I
think that you can probably do it w/ placement new (C++ only!), but using (C++)
references or pointers, you can't have two variables that share the same memory
location.

[Howard]

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

Yes, but the two variables are pointers, and they do not share the same memory location -- they may *point* to the same location.

So, I still haven't seen two variables that share the same memory location. I think that you can probably do it w/ placement new (C++ only!), but using (C++) references or pointers, you can't have two variables that share the same memory location.

Geez, give me a break! What I've shown exhibits *exactly* the kind of
problem that can happen when trying to swap two integers using the xor
technique. Just because someone used terminology that suggested the two
variables themselves had the same memory location, surely you knew what was
meant! The problem is when both memory locations are the same, which can
happen if using pointers or references. That's all that was meant, not that
there were two *different* variables occupying the *same* memory.
-Howard

[Christopher Benson-Manica]

In comp.lang.c Joona I Palaste <pa*****@cc.helsinki.fi> wrote:

job. That's all there was to it. No tests, no panel hearings, just a few
hours of talk.

I bet they saw your postings to comp.lang.c ;)

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

[Julie]

Dan Pop wrote:

In <40***************@nospam.com> Julie <ju***@nospam.com> writes:

In <cb**********@oravannahka.helsinki.fi> Joona I Palaste <pa*****@cc.helsinki.fi> writes:

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

Since you seem to be unable to understand plain English:

#include <stdio.h>

void swap(int *p, int *q) { ... }

int main()
{
int i = 10;
swap(&i, &i);
printf("%d\n", i);
return 0;
}

Try this code for different implementations of the swap function, using
a temp var and using in-place swapping. Compare the results.

This example is trivial, but the situation can realistically arise in more
complex algorithms.

No, I do not understand your version of plain English.

Just because you have two pointers that _point_ to the same address, this
doesn't mean that they (the variables here which are still the **pointers**)
share the same memory location.

Your definition of swap doesn't take to variables, it takes two addresses.
Even in your example in main, you are passing in the same pointer.

Show me a case of two separate variables that share the same memory location,
without using placement new. You can even use your version of 'plain English'.

Here is the point in my version of 'plain English': you can't have two
variables that share the same memory address (excluding placement new). So, if
the precondition for swap is that it operates on two variables, then it will
always work provided the precondition is met.

[Tak-Shing Chan]

On 28 Jun 2004, Dan Pop wrote:

JKop <NU**@null.null> scribbled the following
on comp.lang.c:

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 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ [snip]

And the only good reason I can imagine is the failure to allocate memory
for a temporary object (some objects can be greater than others, some

^^^^^^^^^^^^^^^^^^

Your answer is completely irrelevant. ;-)

Tak-Shing

[Howard]

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

Here is the point in my version of 'plain English': you can't have two
variables that share the same memory address (excluding placement new). So, if the precondition for swap is that it operates on two variables, then it will always work provided the precondition is met.

So who ever sid the procondition was that you were swapping two non-pointer,
non-reference variables? If you're writing the swap as a function, you have
to use references or pointers, or else you'll only be swapping local copies.
That's what makes this an important consideration, because those pointer or
references parameters could be referring to the same memory location. The
swap function need to contain a check to handle that specific case.

-Howard

[Ioannis Vranos]

Julie wrote:

How can you _not_ remove an element from an array?

Here is a trivial case:

Since you use the malloc() family and this is cross posted to clc, I
assume you use C.

size_t count = 2;
int * array = (int *)malloc(sizeof(int) * count);

In C this casting is not needed.
array[0] = 42;
array[1] = 9000;
array = (int *)realloc(array, sizeof(int) * (--count));

In C this casting is not needed.


Regards,

Ioannis Vranos

[Tak-Shing Chan]

On Mon, 28 Jun 2004, Tak-Shing Chan wrote:

On 28 Jun 2004, Dan Pop wrote:

JKop <NU**@null.null> scribbled the following
on comp.lang.c:
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 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ [snip]

And the only good reason I can imagine is the failure to allocate memory
for a temporary object (some objects can be greater than others, some

^^^^^^^^^^^^^^^^^^

Your answer is completely irrelevant. ;-)

To comp.lang.c++: sorry I didn't notice the cross-post at
the beginning. You can safely ignore my out-of-context reply.
What my post really amounts to is a (rather subtle) critique of
Dan Pop's lack of clarity in the replied-to post. [It took me
three to four readings to get his logic!]

Tak-Shing

[Tak-Shing Chan]

On Mon, 28 Jun 2004, Christopher Benson-Manica wrote:

In comp.lang.c Joona I Palaste <pa*****@cc.helsinki.fi> wrote:

job. That's all there was to it. No tests, no panel hearings, just a few
hours of talk.

I bet they saw your postings to comp.lang.c ;)

I thought he is a Java programmer? ;-)

Tak-Shing

[josh]

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

[Joona I Palaste]

Tak-Shing Chan <es***@city.ac.uk> scribbled the following:

On Mon, 28 Jun 2004, Christopher Benson-Manica wrote:

In comp.lang.c Joona I Palaste <pa*****@cc.helsinki.fi> wrote:

job. That's all there was to it. No tests, no panel hearings, just a few
hours of talk.
I bet they saw your postings to comp.lang.c ;)

I thought he is a Java programmer? ;-)

I am, but I know some C as well, and my C skills *have* come to some use
in this job. I had to translate a few hundred lines of C code, written
by another company, to Java.

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"You will be given the plague."
- Montgomery Burns

[Ioannis Vranos]

Dan Pop wrote:

C99 answer:

4 Some operators (the unary operator ~, and the binary operators
<<, >>, &, ^, and |, collectively described as bitwise
operators) are required to have operands that have integer
type. These operators return values that depend on the internal
representations of integers, and have implementation-defined
and undefined aspects for signed types.

Consider, for example, 0 ^ 0, whose result (an int with all bits set) is
a trap representation, as explicitly allowed by C99 for one's complement.

It's hard to find an example for two's complement using the ^ operator,
but it can be done with ~INT_MAX, if the representation with the sign
bit set and all the value bits reset is a trap representation (again,
explicitly allowed by C99 for two's complement and sign-magnitude).

Whether real world implementations have such trap representations is a
completely different story...

However in C++98 I did not find anything else than this:
5.12 Bitwise exclusive OR operator

exclusive-or-expression:
and-expression
exclusive-or-expression ^ and-expression

The usual arithmetic conversions are performed; the result is the
bitwise exclusive OR function of the operands. The operator applies only
to integral or enumeration operands."


Regards,

Ioannis Vranos

[Ioannis Vranos]

Dan Pop wrote:

Since you seem to be unable to understand plain English:

#include <stdio.h>

void swap(int *p, int *q) { ... }

int main()
{
int i = 10;
swap(&i, &i);
printf("%d\n", i);
return 0;
}

Try this code for different implementations of the swap function, using
a temp var and using in-place swapping. Compare the results.

This example is trivial, but the situation can realistically arise in more
complex algorithms.

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.


Regards,

Ioannis Vranos

[Joona I Palaste]

Christopher Benson-Manica <at***@nospam.cyberspace.org> scribbled the following:

In comp.lang.c Joona I Palaste <pa*****@cc.helsinki.fi> wrote:

job. That's all there was to it. No tests, no panel hearings, just a few
hours of talk.

I bet they saw your postings to comp.lang.c ;)

This interview was for my current job, which is actually my second one.
After the dinner with the CEO and the chief programmer, I gave them the
e-mail address of my previous company's chief programmer. I don't know
if they ever mailed him but if they did, I figure he said I was your
average Java programmer.
In my *first* job interview, the CEO asked if I had any code samples to
show. (He was one of the founders of the company and knew quite a bit of
programming himself.) I later e-mailed him a few university and free-
time exercise programs. Later, when he called me for another meeting,
he said that my programs were pretty trivial. But somehow I got the job
anyway.

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"You can pick your friends, you can pick your nose, but you can't pick your
relatives."
- MAD Magazine

[Ioannis Vranos]

Dan Pop wrote:

Since you seem to be unable to understand plain English:

#include <stdio.h>

void swap(int *p, int *q) { ... }

int main()
{
int i = 10;
swap(&i, &i);
printf("%d\n", i);
return 0;
}

Try this code for different implementations of the swap function, using
a temp var and using in-place swapping. Compare the results.

This example is trivial, but the situation can realistically arise in more
complex algorithms.

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.


Regards,

Ioannis Vranos

[Ioannis Vranos]

Dan Pop wrote:

Since you seem to be unable to understand plain English:

#include <stdio.h>

void swap(int *p, int *q) { ... }

int main()
{
int i = 10;
swap(&i, &i);
printf("%d\n", i);
return 0;
}

Try this code for different implementations of the swap function, using
a temp var and using in-place swapping. Compare the results.

This example is trivial, but the situation can realistically arise in more
complex algorithms.

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.


Regards,

Ioannis Vranos

[Ioannis Vranos]

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

That was good :-)


Regards,

Ioannis Vranos

[Howard]

"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

[Ioannis Vranos]

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.

I think the non-temporary requirement is not for space concerns but to
find out how c00l we are. :-) Even under severe space concerns there is
always space for a *temporary* variable. If there are space concerns to
the extreme, then we should write numbers in its memory directly. :-)


Regards,

Ioannis Vranos