RePosted from C# Forums: A Job Exam Question

Bulky Fellow

My office is testing a bunch of folks who have applied for Java jobs. I don't know head and tails of the language other than that its syntax is stolen from here and there (I'm still partyin' with MFC/Win32, yay!). My buddy was the invigilator and got the questions' sheet. This was one of the easiest assignments, and shockingly, only 3 out of the 14 people that attempted this problem finished it correctly on time. Some took more than 45 minutes but got it right, and others didn't solve it at all! I tried it for the hell of it beat the time by 29 minutes, finishing at 16 minutes (C/DevCPP), which I guess is not bad. Post your times here, and see if you can bring it down below 16 minutes. ;)

Q7. (Note: You cannot answer Questions 8, 11 and 14 if you are answering this question.
Pick another 2 from the rest).
Write a command-line program as follows:

First the program will take as input a +ve integer from the user, let's call it
the TARGET.

It will then take in a set of +ve integers from the user, and here the user gets
to specify how many integers he/she wants to enter. Let's call this set the
RANGE.

Now the program should compute as follows:

Find all combinations in the RANGE, the sum of which add up to the
target. Print such combinations at the command prompt. In a combination,
repeats are not allowed. i.e. (x + x + y) = TARGET is forbidden. Every element
in the combination must be unique.
In case a user enters a RANGE element greater than the target, it should be immediately
discarded and the user must be prompted for the element again.
Order shifted cases don't count. i.e. (x+y) and (y+x) being printed
separately is unnecessary and MUST be avoided.
In case no combinations exist, the program should report so.
Add exception handling code where necessary.

Example Run:

Enter Target: 15
How many set elements?: 5
Enter Element1: 7
Enter Element2: 8
Enter Element3: 12
Enter Element4: 3
Enter Element5: 22
Sorry. That element is larger than your target. Try again.
Enter Element5: 4

Combinations are:
1] 7+8
2] 8+3+4
3] 12+3

Time: 45 mins.

(At the top of the source file, please comment in your ID details along with the reference
number at the back of the day-card you were provided by the examiner. Write your Full Name,
ID key, TDC number and most importantly the reference number. Good luck.)

ASP - AJAX is SEXY. PERIOD.

Lost User

Took roughly ~4mins, the next_combination function (similar to next_permutation) may someday end-up in the STL, if so probably 2mins or so.... :)

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

template <class BidirectionalIterator>
bool next_combination(BidirectionalIterator first,
BidirectionalIterator k,
BidirectionalIterator last);

int main()
{

std::vector<int> v;
v.push_back(7);
v.push_back(8);
v.push_back(12);
v.push_back(3);
v.push_back(4);

int target = 15;
int combination_count = 0;

std::sort(v.begin(),v.end());

for(unsigned int i = 1; i <= v.size(); ++i)
{
std::vector<int> tmp;
std::copy(v.begin(),v.end(),std::back_inserter(tmp));
do
{
if (std::accumulate(tmp.begin(),tmp.begin() + i, 0) == target)
{
std::cout << ++combination_count << "] ";
for(unsigned int j = 0; j < i; ++j)
{
std::cout << tmp[j] << (j < (i-1) ? "+" : "\n");
}
}
}
while(next_combination(tmp.begin(),tmp.begin() + i,tmp.end()));
}

if (0 == combination_count)
{
std::cout << "No combinations found." < std::endl;
}
return 0;
}

/*
Credits: Mark Nelson http://marknelson.us/
*/
template <class BidirectionalIterator>
bool next_combination(BidirectionalIterator first,
BidirectionalIterator k,
BidirectionalIterator last)
{
if ((first == last) || (k == first) || (k == last)) return false;
BidirectionalIterator i = first;
BidirectionalIterator ii = last;
++i;
if (i == last) return false;
i = last;
--i;

i = k;
--ii;
while (i != first)
{
if (*--i < *ii)
{ // Search down to find first comb entry less than final entry
BidirectionalIterator j = k;
while(!(*i < *j)) j++; // Find swap position [good-1-high|good-2-low]
iter_swap(i,j); // Swap [good-2-high|good-1-low]
i++;j++;ii=k; // Move to rotation positions
rotate(i,j,last); // Rotate [good-2-low-high-good-1]
while(j!=last){ ++j; ++ii;} // Find high good position
rotate(k,ii,last); // Rotate [good-2-(low/high>|good-1-<low/high)]
return true;
}
}
rotate (first,k,last);
return fa

Mark Churchill

My 10 mins. I really wanted to do something cool with yield, but the difficulty of nesting these really stuffed me. I wanted to recursively traverse the mask like a b-tree and yield out results along the way. :( class SubsetSummer { static IEnumerable< long> SubsetSumCore(IList< int> values, int target) { long mask = (1 << values.Count); while(mask-- > 0) { int total = 0; for(int bit = 0; bit< values.Count; bit++) { if ((mask & 1 << bit) > 0) total += values[bit]; } if (total == target) yield return mask; } } static IEnumerable< List< int>> SubsetSum(IList< int> values, int target) { foreach (var resultMask in SubsetSumCore(values,target)) { var results = new List< int>(); for (int bit = 0; bit < values.Count; bit++) { if ((resultMask & 1 << bit) > 0) results.Add(values[bit]); } yield return results; } } static void Main(string[] args) { var values = new []{7, 8, 12, 3, 4}; foreach (var result in SubsetSum(values, 15)) { Console.WriteLine(string.Join(" + ", result.ConvertAll(i => i.ToString()).ToArray())); } } } (wow that really shagged my generics)

Mark Churchill Director, Dunn & Churchill Pty Ltd Free Download: Diamond Binding: The simple, powerful, reliable, and effective data layer toolkit for Visual Studio.
Alpha release: Entanglar: Transparant multiplayer framework for .Net games.

riced

Sorry you have failed. The program does not meet the requirements. Where is the user input and validation? If it does not need to meet them then this program will do the job and take a lot less time and thought.

class SubsetSummer
{
static void Main(string[] args)
{
Console.WriteLine("3 + 4 + 8");
Console.WriteLine("3 + 12");
Console.WriteLine("7 + 8");
}
}

Bulky Fellow

You forgot to place this in the punintended namespace. ;)

ASP - AJAX is SEXY. PERIOD.

Mark Churchill

I guess if you find user input and validation challenging then you can focus on those parts. This is maths & algs, not "C# 101".

Mark Churchill Director, Dunn & Churchill Pty Ltd Free Download: Diamond Binding: The simple, powerful, reliable, and effective data layer toolkit for Visual Studio.
Alpha release: Entanglar: Transparant multiplayer framework for .Net games.