Programming Puzzle

[xarax]

Mabden <mabden@sbc_global.net> scribbled the following





Unbelievable. I rmemember *my* latest job interview. The company's CEO
and I sat in the corridor of a Finnish technology enterprise building,
where the company's offices were located at the time, and talked for a
few hours about what I'm like as an employee. Later, I, the CEO and the
company's chief programmer met in a restaurant and talked about what I
am like as a programmer. The company paid for my dinner. Then I was
going about minding my own business when I got a call that I had got the
job. That's all there was to it. No tests, no panel hearings, just a few
hours of talk.

Yup. Those are the best kinds of "interviews", and generally
only happen for highly-qualified candidates. My last 2 jobs
were like that, and both were 6 figure programming jobs. Ah,
those were the days...

Those BS interviews asking about how to twiddle bits are a
waste of time. If I can't recall an exact algorithm, I just
look it up in one of my many reference books, including the
3 volumes of Knuth. The overall approach to solving a problem
and how I think about designing a solution is what's really
important. Don't sweat the small things, that's what junior
programmers are for.

 

[Ioannis Vranos]

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?


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

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?


"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

 

[Mabden]

(x || 1) evaluates to true,
(!true) evaluates to false,

So this is equivalent to:

return false;

But the question was if x is a power of 2.

Ooops.. return !(x | 0x0001);

 

[Peter Ammon]

Assuming that these questions are from an interview for a programming
job, I must say that most of them are incredibly useless at finding a
good programmer.

To play some devil's advocate here:

If your experience as a programmer is confined entirely to the academic
or professional spheres, you may never see questions like that, and so
wouldn't get the answer. But if you investigate and discuss programming
independently (like on this newsgroup), then you probably will. So they
may be a good way of finding people who are passionate self starters,
which could be particularly important in an industry where 70% of people
have left after 6 years (so I've read).

Take Q3: The correct answer is: Why would anyone want
to do that? Take Q10: You know the answer or you don't. If your name is
Gödel or Turing, you might find a solution on your own, but otherwise
this just tests some very obscure knowledge.

We sometimes give Q4 in our interviews. I'd expect any programmer to be
able to come up with *some* solution, even if it's only testing whether
the value equals any of 32 powers of 2. What usually happens is that
the candidate tries to realize a more sophisticated solution but fails,
and rather than dropping back to a more obvious algorithm gets bogged
down. That's an all too common warning flag.

I guess these questions are
only used to check your reaction to a stressful situation (which is also
an incredibly useless way at finding a good programmer).

There's useful information to be gained by observing how people approach
a problem even if they don't get the right answer. If, given Q10, the
candidate says immediately "It can't be done" and then struggles to back
up their claim, that's bad news. If they say "I'd guess it
could/couldn't be done, but I'm not sure, and I might go to find out
here..." then that's a plus.

We sometimes give questions that are too specific to our work for a new
candidate to know, the idea being to see whether they'd guess, guess and
verify, give up, etc. The quine isn't a good choice for that because,
as you said, there's no motivation.

If I was given this list of questions, I would tell them that most of
them are pointless and then examine Q11, because it is the only
interesting one. Maybe a different response if you are desperate for a
job.

Way to think "outside the box"

 

[Ioannis Vranos]

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.

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

Q1 Write a "Hello World" program in 'C' without using a semicolon.

#include <iostream>


int main()
{
if(std::cout<<"Hello World!\n") {}
}

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

#include <iostream>

template<class T>
inline void printinc(T i, const T limit)
{
std::cout<<i<<" ";

if(i<limit)
printinc(++i, limit);
}


template<class T>
inline void printdec(T i, const T limit)
{
std::cout<<i<<" ";

if(i>limit)
printdec(--i, limit);
}





int main()
{
using namespace std;

printinc(1, 100);

cout<<endl<<endl;

printdec(100, 1);
}

Q3 C/C++ : Exchange two numbers without using a temporary variable.

#include <algorithm>

int main()
{
using std::swap;

int x=1, y=2;

swap(x,y);
}

Q4 C/C++ : Find if the given number is a power of 2.

#include <bitset>
#include <limits>
#include <cstddef>

bool IsPowerOfTwo(unsigned long x)
{
using namespace std;

// It is safe for unusual implementations where bytes
// are more than 8 bits.
bitset<numeric_limits<unsigned char>::digits>bitRep=x;

unsigned nonZeroBits=0;

for(size_t i=0; i<bitRep.size(); ++i)
if(bitRep)
nonZeroBits++;

if(nonZeroBits==1)
return true;

else
return false;
}

Q5 C/C++ : Multiply x by 7 without using multiplication (*) operator.

Obscure question, addition can be used as others mentioned or

#include <iostream>

int main()
{
using namespace std;

int x=3, temp=x;

x<<=3;

x-=temp;

cout<<x<<endl;

}

Q6 C/C++ : Write a function in different ways that will return f(7) =
4 and f(4) = 7

inline somefunc(int x)
{
return x==7?4:7;
}

Q7 Remove duplicates in array

std::sort, std::unique.

Q8 Finding if there is any loop inside linked list.

One has already suggested the use of two pointers advancing which is
really a very good solution.

Q9 Remove duplicates in an no key access database without using an
array

SQL.

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.

I have seen it somewhere in the web sometime in the past.

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.

And what is the programming question?

Q12 Swap two numbers without using a third variable.

Already answered:


#include <algorithm>

int main()
{
using std::swap;

int x=1, y=2;

swap(x,y);
}

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

std::next_permutation and std:rev_permutation. An example:


#include <algorithm>
#include <string>
#include <iostream>


int main()
{
using namespace std;

string s="abcd";


do
cout<<s<<endl;
while(next_permutation(s.begin(), s.end()));
}

Q14 Convert (integer) number in binary without loops.

I assume it means the binary representation as a string since numbers
are already stored in binary, and such "conversion" has not any meaning.


With std::bitset this is too easy.






Regards,

Ioannis Vranos

 

[Ioannis Vranos]

Ioannis Vranos wrote:


Well some errata.

#include <iostream>


int main()
{
if(std::cout<<"Hello World!\n") {}
}

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

#include <iostream>

template<class T>
inline void printinc(T i, const T limit)
{
std::cout<<i<<" ";

if(i<limit)
printinc(++i, limit);
}


template<class T>
inline void printdec(T i, const T limit)
{
std::cout<<i<<" ";

if(i>limit)
printdec(--i, limit);
}





int main()
{
using namespace std;

printinc(1, 100);

cout<<endl<<endl;

printdec(100, 1);
}





#include <bitset>
#include <limits>
#include <cstddef>

bool IsPowerOfTwo(unsigned long x)
{
using namespace std;

// It is safe for unusual implementations where bytes
// are more than 8 bits.

bitset<numeric_limits<unsigned char>::digits>bitRep=x;

bitset<numeric_limits<unsigned char>::digits*sizeof(x)>bitRep=x;

unsigned nonZeroBits=0;

for(size_t i=0; i<bitRep.size(); ++i)
if(bitRep)
nonZeroBits++;

if(nonZeroBits==1)
return true;

else
return false;
}

Regards,

Ioannis Vranos

 

[Ioannis Vranos]

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.

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

Q1 Write a "Hello World" program in 'C' without using a semicolon.

#include <iostream>


int main()
{
if(std::cout<<"Hello World!\n") {}
}

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.



#include <iostream>

template<class T>
inline void printinc(T i, const T limit)
{
std::cout<<i<<" ";

if(i<limit)
printinc(++i, limit);
}


template<class T>
inline void printdec(T i, const T limit)
{
std::cout<<i<<" ";

if(i>limit)
printdec(--i, limit);
}





int main()
{
using namespace std;

printinc(1, 100);

cout<<endl<<endl;

printdec(100, 1);
}

Q3 C/C++ : Exchange two numbers without using a temporary variable.

#include <algorithm>

int main()
{
using std::swap;

int x=1, y=2;

swap(x,y);
}

Q4 C/C++ : Find if the given number is a power of 2.

#include <bitset>
#include <limits>
#include <cstddef>

bool IsPowerOfTwo(unsigned long x)
{
using namespace std;

// It is safe for unusual implementations where bytes
// are more than 8 bits.
bitset<numeric_limits<unsigned char>::digits*sizeof(x)>bitRep=x;

unsigned nonZeroBits=0;

for(size_t i=0; i<bitRep.size(); ++i)
if(bitRep)
nonZeroBits++;

if(nonZeroBits==1)
return true;

else
return false;
}

Q5 C/C++ : Multiply x by 7 without using multiplication (*) operator.

Obscure question, addition can be used as others mentioned or

#include <iostream>

int main()
{
using namespace std;

int x=3, temp=x;

x<<=3;

x-=temp;

cout<<x<<endl;

}

Q6 C/C++ : Write a function in different ways that will return f(7) =
4 and f(4) = 7

inline somefunc(int x)
{
return x==7?4:7;
}

Q7 Remove duplicates in array

std::sort, std::unique.

Q8 Finding if there is any loop inside linked list.

One has already suggested the use of two pointers advancing which is
really a very good solution.

Q9 Remove duplicates in an no key access database without using an
array

SQL.

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.

I have seen it somewhere in the web sometime in the past.

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.

And what is the programming question?

Q12 Swap two numbers without using a third variable.

Already answered:


#include <algorithm>

int main()
{
using std::swap;

int x=1, y=2;

swap(x,y);
}

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

std::next_permutation and std:rev_permutation. An example:


#include <algorithm>
#include <string>
#include <iostream>


int main()
{
using namespace std;

string s="abcd";


do
cout<<s<<endl;
while(next_permutation(s.begin(), s.end()));
}

Q14 Convert (integer) number in binary without loops.

I assume it means the binary representation as a string since numbers
are already stored in binary, and such "conversion" has not any meaning.


With std::bitset this is too easy.






Regards,

Ioannis Vranos

 

[Ioannis Vranos]

Ioannis Vranos wrote:

std::next_permutation and std:rev_permutation. An example:

#include <algorithm>
#include <vector>
#include <iostream>


int main()
{
using namespace std;

int array[4]={1,2,3,4};

for(int*p=array, *r=&array[4]; p!=r; --r)
{
vector<int>temparray(p,r);

do
{
for(vector<int>::size_type i=0; i<temparray.size(); ++i)
cout<<temparray<<" ";

cout<<endl;

}while(next_permutation(temparray.begin(), temparray.end()));

}
}






Regards,

Ioannis Vranos

 

[Nick Landsberg]

Yup. Those are the best kinds of "interviews", and generally
only happen for highly-qualified candidates. My last 2 jobs
were like that, and both were 6 figure programming jobs. Ah,
those were the days...

Those BS interviews asking about how to twiddle bits are a
waste of time. If I can't recall an exact algorithm, I just
look it up in one of my many reference books, including the
3 volumes of Knuth. The overall approach to solving a problem
and how I think about designing a solution is what's really
important. Don't sweat the small things, that's what junior
programmers are for.

Amen.

Back in the "good old days" in my company, the interview
process was actually partially scripted in the sense
that there was a "seller," a "buyer" and a social
encounter.

The "seller's" job was to point out all the whiz-bang things
that we were doing in order to make the candidate want
to come to work for us. At the technical level it was
mostly about the technologies we used and the kinds of
problems we were trying to solve and why it was important
to solve those kinds of problems. The candidate's interest
was noted. ("What aspect of this problem most interests you?")

The "buyer's" job was to discretely ask about the candidate's
technical background. e.g. "Tell me more about this project (on your
resume). What did you do on it? What was the most interesting
aspect of it? What was the most troublesome problem you faced?
How did you solve it?" (We, of course, didn't use the exact
phrasing noted above, but we evaluated the candidate's
responses as to the level of understanding. e.g. if the
candidate focused on design flaws, they got higher mental
marks than if the candidate focused on coding errors.)

Each of the above was about 2-3 hours. After that, the candidate
would be taken out to dinner where we were supposed to judge
how he/she would interact with co-workers. (I know, totally
subjective, but actually the "dinne" was more important
then the previous sessions, assuming that the candidate had
impressed us in the previous sessions.)

Not very scientific. No "20 questions about trivial/obscure
software techniques". Just gut feelings on the part of
the interviewers. Unfair? Probably. Effective? Mostly
yes.

Some high-ego hard-cases got through, but not too many.

Just my $0.02 American.

NPL

 

[Peter Ammon]

Q3 (the same as the other you mentioned, basically) took me less than
a minute to solve, and I'm only 16:

/* vim:ts=4
*/

#include <stdio.h>

int main(void) {
int foo = 87;
int bar = 56;

foo += bar;
bar = foo - bar;
foo = foo - bar;

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

Try other values for foo & bar, even negatives and zero.

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

To stump Microsoft programmers, I prefer to ask them to write a
recursive factorial function.

See
<http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang/h
tml/_CLANG_Recursive_Functions.asp> for their answer. Prepare to wince.

 

[Julie]

Assuming that these questions are from an interview for a programming
job, I must say that most of them are incredibly useless at finding a
good programmer. Take Q3: The correct answer is: Why would anyone want
to do that? Take Q10: You know the answer or you don't. If your name is
Gödel or Turing, you might find a solution on your own, but otherwise
this just tests some very obscure knowledge. I guess these questions are
only used to check your reaction to a stressful situation (which is also
an incredibly useless way at finding a good programmer).

If I was given this list of questions, I would tell them that most of
them are pointless and then examine Q11, because it is the only
interesting one. Maybe a different response if you are desperate for a
job.

Presuming that the interviewer is competent: it is not the answer to the
question that is important, but _how_ you solve it.

 

[Julie]

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.

Explain to me how *two* variables can share the same memory address.

 

[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

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.

 

[Robbie Hatley]

#include <iostream>
int main(void)
{
std::cout << "an exact copy of the source" << std::endl;
}



Probably not what you had in mind... but really, with
a compiled language like C++, the executable file has
no clue as to what it's own source looks like. Even
if you wrote an elaborate un-assembler-and-un-compiler,
the resulting source code, while perhaps functionally
equivalent, would look NOTHING like the original source.

But there's also a basic logical problem with the
problem, isn't there? I mean, you could try to make
a program print itself, but the 7th line would be
infinitely long by necessity, because the program would
have to print the code that prints the code that prints
the code that ... (infinity) ... that prints the program:

01 #include <iostream>
02 int main(void)
03 {
04 std::cout << "#include <iostream> << std::endl;"
05 std::cout << "int main(void)"
06 std::cout << "{"
07 std::cout << "std::cout << \"std::cout << \"std...

I have seen it somewhere in the web sometime in the past.

Sort of like Goldberg's "marvelous proof which, unfortunately,
is too large to fit in this margin".


--
Cheers,
Robbie Hatley
Tustin, CA, USA
email: lonewolfintj at pacbell dot net
web: home dot pacbell dot net slant earnur slant

 

[Ioannis Vranos]

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]

Gordon Burditt posted:


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