C/C++ Puzzles

[Andy Nguyen]

Some companies certainly ask for these puzzles. If you interview for a quant developer position, these are popular questions.

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

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

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

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

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

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

7. Remove duplicates in array

8. Finding if there is any loop inside linked list.

9. Remove duplicates in an no key access database without using an array

10. Convert (integer) number in binary without loops.

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

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

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

 

[Richard]

Some interesting problems.

Andy,
is it ok to discuss the answers here?

 

[Andy Nguyen]

Andy,
is it ok to discuss the answers here?

Absolutely. That's why I posted here. I think I did post my solutions to questions similar to 1,2,3,4 somewhere on QN last summer. I'll give the rest a try. These are really good quant interview questions.

 

[Wallstyouth]

Some companies certainly ask for these puzzles. If you interview for a quant developer position, these are popular questions.

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

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

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

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

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

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

7. Remove duplicates in array

8. Finding if there is any loop inside linked list.

9. Remove duplicates in an no key access database without using an array

10. Convert (integer) number in binary without loops.

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

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

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

Can someone post the solution to #1

 

[Andy Nguyen]

Can someone post the solution to #1

Here you go C++ brainteasers - Have fun and learn. You may get a job too

Those are solutions to some of the questions. As for #1, it's interesting that we can only do it in C, but not in C++

 

[Chris]

One way to answer #1:

int main(int argc, char *argv[])
{
    
    if (printf("Hello World")) {}
                      
}

 

[Andy Nguyen]

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

int main()
{    cout <<"enter an integer number to see if it's a power of 2  "<<endl;
   int x;
   cin >> x;
   cout <<  (  (x != 0) && ( ( (x-1) & x ) == 0 ) ) ? 1   :  0 ;
}

A return of 1 means it's power of 2, and 0 otherwise

enter an integer number to see if it's a power of 2
512
1
Press ENTER to continue...

enter an integer number to see if it's a power of 2
510
0
Press ENTER to continue...

 

[Richard]

Andy,

I think if the question wants to answer negative integer, we can add a line (bold below) to get the absolute value of x before we evaluate. For example, -512 will return 0 with your original code, but after taking abs, it will return 1. Just a small point.

int main()
{    cout <<"enter an integer number to see if it's a power of 2  "<<endl;
   int x;
   cin >> x;
[B]  [U]x = abs (x);[/U][/B]
   cout <<  (  (x != 0) && ( ( (x-1) & x ) == 0 ) ) ? 1   :  0 ;
}

A return of 1 means it's power of 2, and 0 otherwise

enter an integer number to see if it's a power of 2
512
1
Press ENTER to continue...

enter an integer number to see if it's a power of 2
510
0
Press ENTER to continue...

 

[Andy Nguyen]

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

My first thought would be to replace * by + since 7*x = x+...+x (7 times)
Or more generally, finding product of x*y without using *
This should work for the most part. If you want, you can put a check for 0 in there.

int main()
{ cout <<"enter a number and its mutiplier  "<<endl;
  double x,y, i =1;
   cin >> x >>y;
   double temp =x ;
   while (i < fabs(y) )
   {
   temp += x ;
   ++i;
    }
temp = (y >= 0) ? temp : -temp ;
cout << temp;
}

 

[Richard]

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

If we just want to multiply by 7, another way to do this is to get it as 8x-x. 8x can be done by shifting the bits if the number is not too large. Honestly, I am not sure what this question wants to test. If it wants to test bit operator, it will be fair to just say so.

cout<<"enter a number to multiply by 7:\n";
int x;
cin >> x;
x = (x<<3) - x;
cout << "result:" <<x;
return;

 

[Richard]

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

What does this question mean?

By the way, for programming jobs, there is a book called "programming interview exposed". It is well written, and I think covers more reasonable aspects with a focus on data structure. I have an old version which gave examples in C. There is new version that just came out, but I am not sure whether the example is still in C or is changed to C++. Regardless, it should be worth reading.

Also, I came across a page of quiz here: Test A.
The question is less tricky but I think is a good one to check out some basics.

 

[alain]

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

If we just want to multiply by 7, another way to do this is to get it as 8x-x. 8x can be done by shifting the bits if the number is not too large. Honestly, I am not sure what this question wants to test. If it wants to test bit operator, it will be fair to just say so.

cout<<"enter a number to multiply by 7:\n";
int x;
cin >> x;
x = (x<<3) - x;
cout << "result:" <<x;
return;

This won't work for doubles.

 

[Richard]

This won't work for doubles.

Yes, Alain you are right. This won't work for large numbers. I was thinking that this question must have some tricks but I am not a hard core coder and I can't think of better ways of doing this. Hmm, what's so special about multiplying by 7?

 

[Wallstyouth]

Question #2 solution

#2

#include <stdio.h>
int main(a)
{
  printf("%d\n",a);
  return a<100?main(++a):0;
}

 

[bob]

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

I'm not much of a coder, but this one was simple enough for me:

// exchange the values of doubles x and y
x += y;
y += x;
x = y - x;
y -= 2.*x;

I suppose they might be after something related to pointers/references, but this was the way that occurred to me....

 

[Adam]

A Very Simple Answer to #5

double multBy7(double x)
{
int i;
double y = 0;
for(i = 0; i < 7; i++) y += x;
return y;
}

 

[bob]

10. Convert (integer) number in binary without loops.

Whoever wrote these questions appears to like bitshift operators. I'd never used them before.

The loop here isn't instrumental; it just tests the function with a range of input values. I hope doing this recursively doesn't count as looping....

#include <iostream>

using namespace std;

void show_binary (int n) {
	if ((n == 1) || (n == 0)) cout << n;
	else {
		int r = n%2;
		show_binary (n>>1);
		cout << r;
	}
}

int main (int argc, char * const argv[]) {
    for (int i = 0; i <= 1024; i++) {
		cout << i << " in binary is ";
		show_binary(i);
		cout << endl;
	}
	cout << endl;
	
    return 0;
}

 

[alain]

Bob, here is my solution to the same problem. It is almost identical:

string convert_to_binary(const int& pNum)
{    
    stringstream ret;
    if (pNum < 2){
        ret << pNum;
        return ret.str();
    }
    ret << convert_to_binary(pNum>>1) << (pNum%2);
    return ret.str();
}

 

[alain]

Here is another solution to the multiply by 7 problem. Two routines one that multiplies any positive number by an integer and another that actually does the multiplication by 7:

double mult_xy(const double& pNum, const int& pMultiplier)
{
    if (pNum == 0. || pMultiplier == 0) return 0.;
    if (pMultiplier == 1) return pNum;
    return pNum + mult_xy(pNum, pMultiplier-1);
}
double mult_by_7(const double& pNum)
{
    return mult_xy(pNum, 7);
}

 

[bob]

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

This solicits a list of integer inputs from the user, then outputs the number of subsets of each size, and lists the subsets. There's a more efficient way to code this, I'm sure, but this is what I came up with on a first pass.

#include <iostream>
#include <vector>
#include <stdexcept>
#include <sstream>
#include <string>

using namespace std;

vector< vector<int> > choose (int set_size, int subset_size) {
	if (subset_size > set_size) throw invalid_argument ("You asked me for a subset of size greater than the set size.");
	if ((subset_size <= 0) || (set_size <=0)) throw invalid_argument 
			("You asked for a set or subset size that wasn't positive.");
	
	vector< vector<int> > result;
	if (set_size == subset_size) {
		vector<int> temp;
		for (int i = 0; i < set_size; i++) temp.push_back(i);
		result.push_back(temp);
		return result;
	}
	if (subset_size == 1) {
		for (int i = 0; i < set_size; i++) {
			vector<int> temp;
			temp.push_back(i);
			result.push_back(temp);
		}
		return result;
	}
	for (int i = 0; i <= set_size-subset_size; i++) {
		vector< vector<int> > temp = choose (set_size-1-i, subset_size-1);
		for (vector< vector<int> >::iterator outer = temp.begin(); outer != temp.end(); outer++) {
			for (vector<int>::iterator inner = (*outer).begin(); inner != (*outer).end(); inner++) {
				*inner += (i+1);
			}
			(*outer).insert((*outer).begin(), i);
			result.push_back(*outer);
		}
	}
	return result;
}

void show_int_lists (const vector< vector<int> >& source) {
	cout << "Listing:" << endl;
	for (vector< vector<int> >::const_iterator outer = source.begin(); outer != source.end(); outer++) {
		bool first = true;
		for (vector<int>::const_iterator inner = (*outer).begin(); inner != (*outer).end(); inner++) {
			if (!first) cout << ", ";
			cout << *inner;
			first = false;
		}
		if ((*outer).size() == 0) cout << "(empty)";
		cout << endl;
	}
}

vector< vector<int> > subsets (const vector<int>& set_list) {
	vector< vector<int> > result;
	cout << "A set of size " << set_list.size() << " has" << endl;
	cout << "1 subset of size 0" << endl;
	vector<int> temp;
	result.push_back(temp);
	for (int i = 1; i <= set_list.size(); i++) {
		vector< vector<int> > sub_temp = choose(set_list.size(), i);
		
		cout << sub_temp.size();
		if (sub_temp.size() == 1) cout << " subset";
		else cout << " subsets";
		cout << " of size " << i << endl;
		
		for (vector< vector<int> >::iterator outer = sub_temp.begin(); outer != sub_temp.end(); outer++) {
			temp.clear();
			for (vector<int>::iterator inner = (*outer).begin(); inner != (*outer).end(); inner++) {
				temp.push_back(set_list.at(*inner));
			}
			result.push_back(temp);
		}
	}
	cout << endl;
	return result;
}

int main (int argc, char * const argv[]) {
try{
    vector<int> set;
	string entry = "garbage";
	while (!entry.empty()) {
		stringstream ss;
		entry.clear();
		cout << "Enter the next integer for your set, or leave blank to continue. ";
		getline (cin, entry);
		cout << endl;
		if (!entry.empty()) {
			ss << entry;
			int temp_int;
			ss >> temp_int;
			set.push_back(temp_int);
		}
	}
	
	vector< vector<int> > subs = subsets(set);
	show_int_lists (subs);
    return 0;
}
catch (const exception& exc) {
	cerr << exc.what() << endl;
}
}

Sample output:

Enter the next integer for your set, or leave blank to continue. 1

Enter the next integer for your set, or leave blank to continue. 3

Enter the next integer for your set, or leave blank to continue. 5

Enter the next integer for your set, or leave blank to continue. 7

Enter the next integer for your set, or leave blank to continue. 9

Enter the next integer for your set, or leave blank to continue. 11

Enter the next integer for your set, or leave blank to continue. 13

Enter the next integer for your set, or leave blank to continue. 

A set of size 7 has
1 subset of size 0
7 subsets of size 1
21 subsets of size 2
35 subsets of size 3
35 subsets of size 4
21 subsets of size 5
7 subsets of size 6
1 subset of size 7

Listing:
(empty)
1
3
5
7
9
11
13
1, 3
1, 5
1, 7
1, 9
1, 11
1, 13
3, 5
3, 7
3, 9
3, 11
3, 13
5, 7
5, 9
5, 11
5, 13
7, 9
7, 11
7, 13
9, 11
9, 13
11, 13
1, 3, 5
1, 3, 7
1, 3, 9
1, 3, 11
1, 3, 13
1, 5, 7
1, 5, 9
1, 5, 11
1, 5, 13
1, 7, 9
1, 7, 11
1, 7, 13
1, 9, 11
1, 9, 13
1, 11, 13
3, 5, 7
3, 5, 9
3, 5, 11
3, 5, 13
3, 7, 9
3, 7, 11
3, 7, 13
3, 9, 11
3, 9, 13
3, 11, 13
5, 7, 9
5, 7, 11
5, 7, 13
5, 9, 11
5, 9, 13
5, 11, 13
7, 9, 11
7, 9, 13
7, 11, 13
9, 11, 13
1, 3, 5, 7
1, 3, 5, 9
1, 3, 5, 11
1, 3, 5, 13
1, 3, 7, 9
1, 3, 7, 11
1, 3, 7, 13
1, 3, 9, 11
1, 3, 9, 13
1, 3, 11, 13
1, 5, 7, 9
1, 5, 7, 11
1, 5, 7, 13
1, 5, 9, 11
1, 5, 9, 13
1, 5, 11, 13
1, 7, 9, 11
1, 7, 9, 13
1, 7, 11, 13
1, 9, 11, 13
3, 5, 7, 9
3, 5, 7, 11
3, 5, 7, 13
3, 5, 9, 11
3, 5, 9, 13
3, 5, 11, 13
3, 7, 9, 11
3, 7, 9, 13
3, 7, 11, 13
3, 9, 11, 13
5, 7, 9, 11
5, 7, 9, 13
5, 7, 11, 13
5, 9, 11, 13
7, 9, 11, 13
1, 3, 5, 7, 9
1, 3, 5, 7, 11
1, 3, 5, 7, 13
1, 3, 5, 9, 11
1, 3, 5, 9, 13
1, 3, 5, 11, 13
1, 3, 7, 9, 11
1, 3, 7, 9, 13
1, 3, 7, 11, 13
1, 3, 9, 11, 13
1, 5, 7, 9, 11
1, 5, 7, 9, 13
1, 5, 7, 11, 13
1, 5, 9, 11, 13
1, 7, 9, 11, 13
3, 5, 7, 9, 11
3, 5, 7, 9, 13
3, 5, 7, 11, 13
3, 5, 9, 11, 13
3, 7, 9, 11, 13
5, 7, 9, 11, 13
1, 3, 5, 7, 9, 11
1, 3, 5, 7, 9, 13
1, 3, 5, 7, 11, 13
1, 3, 5, 9, 11, 13
1, 3, 7, 9, 11, 13
1, 5, 7, 9, 11, 13
3, 5, 7, 9, 11, 13
1, 3, 5, 7, 9, 11, 13