473,839 Members | 1,480 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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
please Help
Wiating for reply.
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.


Chapter and verse, please.


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
Jim
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
variable leads to undefined behavior.


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:

http://groups.google.fi/groups?selm=...y.DIALix.oz.au

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


In post
http://groups.google.com/groups?selm...mindspring.com
in the function n_sort, the variable (*node),
has the same address as either (tail) or (head) after this line:

node = GT(head, tail) ? &tail : &head;

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


Chapter and verse, please.


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.

Could you please provide your preferred definition of "variable".
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.

Similar topics

270
3990
by: Jatinder | last post by:
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.
12
8490
by: G. | last post by:
Hi all, During my degree, BEng (Hons) Electronics and Communications Engineering, we did C programming every year, but I never kept it up, as I had no interest and didn't see the point. But now I really want to get back into it as I see a point with GNU/Linux. I want to get my old skills back and write something or help on some projects etc. I need some good books. I used to have one called "A Book On C", but sold it,
11
2230
by: John Salerno | last post by:
Similar to the Python Challenge, does anyone know of any other websites or books that have programming puzzles to solve? I found a book called "Puzzles for Hackers", but it seems like it might be a little advanced for me, and I've also read that it focuses too much on encryption and security issues and doesn't really have coding problems, exactly. But something like that book would be fun to have.
1
13120
by: xavier vazquez | last post by:
I have a problem with a program that does not working properly...when the program run is suppose to generate a cross word puzzle , when the outcome show the letter of the words overlap one intop of the other....how i can fix this the program look like this import java.util.ArrayList; import java.util.Random;
0
2031
by: xavier vazquez | last post by:
have a problem with a program that does not working properly...when the program run is suppose to generate a cross word puzzle , when the outcome show the letter of the words overlap one intop of the other....how i can fix this this run the random words for the program import javax.swing.JOptionPane; import java.util.ArrayList; import java.util.Random; public class CrossWordPuzzleTester {
44
3577
by: Jon Harrop | last post by:
Microsoft Research are developing a functional programming language called F# for .NET and I've been playing with it recently. I've uploaded some demos here: http://www.ffconsultancy.com/dotnet/fsharp/ I'm keen to see what Windows developers think of this language as we're considering using it to develop commercial applications on the Windows platform.
5
4477
by: ashish0799 | last post by:
HI I M ASHISH I WANT ALGORYTHMUS OF THIS PROBLEM Jigsaw puzzles. You would have solved many in your childhood and many people still like it in their old ages also. Now what you have got to do is to solve jigsaw puzzles using the computer. The jigsaw puzzle here is a square of dimension d (a puzzle with d^2 pieces) and the jigsaw pieces (all same dimensions) are of dimensions H x W (Which means the pieces have ‘H’ rows of ‘W’...
3
3213
by: oncue01 | last post by:
Word Puzzle Task You are going to search M words in an N × N puzzle. The words may have been placed in one of the four directions as from (i) left to right (E), (ii) right to left (W), (iii) up to bottom (S), or (iv) bottom to up (N). The program will print the starting place and the direction of each word. Limitations The number of words to be searched can be at most 100, the size of the puzzle N can be minimum 5 maximum 20....
4
20015
by: honey777 | last post by:
Problem: 15 Puzzle This is a common puzzle with a 4x4 playing space with 15 tiles, numbered 1 through 15. One "spot" is always left blank. Here is an example of the puzzle: The goal is to get the tiles in order, 1 through 15, from left to right, top to bottom, by just sliding tiles into the empty square. In this configuration, the goal would be to get the 14 and 15 to switch places, without affecting any of the other squares. Your...
13
3130
by: btkuhn | last post by:
Hi guys, I'm learning Python by teaching myself, and after going through several tutorials I feel like I've learned the basics. Since I'm not taking a class or anything, I've been doing challenges/programs to reinforce the material and improve my skills. I started out with stuff like "Guess my number" games, hangman, etc. and moved on to making poker and card games to work with classes. For GUIs I created games like minesweeper, and a...
0
9854
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
10903
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10584
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
9425
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7827
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5681
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
5865
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4482
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
3
3131
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.