Two Things

Gaming and Programming.. maybe programming for some games, who knows. Either way, I'm a geek, right?

Adventures in Interviewing #2: Shuffle This

Interviewing for a programming position usually involves some sort of programming test - either verbally, or on a whiteboard, or occasionally something more interesting.  I've dug around my emails for some of the more interesting (or challenging) ones.  I don't expect to get much feedback from these, but felt like posting them anyway.

This is the second in the series, which came from the posted job position itself, not from an interview.  They asked that you tackle this problem and send it in along with your resume.  Unfortunately they were in California and this was not a remote position - but at the time I was bored and the challenge looked interesting so I went ahead and completed it.

A client has an existing web-based system for delivering a test containing multiple choice questions. They ask that you modify this code so that the test questions are delivered in a random order every time the test is attempted. Furthermore, the order in which the answers to the questions are presented should also be randomized.

 

The existing framework for creating and displaying a test has been provided. Your task is to comprehend the client's code and data structure then implement the RandomizeTest function to perform the randomization of the question and answer order.

 

Please explain your work and thought process.

 

Some background on the project from the client that may affect your solution:

 

-There are over 600 of these tests deployed to hundreds of thousands of users
-There are never more then 20 questions or so per test, each with no more than 6 answers but the code should be able to handle an arbitrary number or both questions and answers
-This code is maintained by several developers in different organizations
-The code is only required to work in all modern browsers

And the existing code:

<html>
<head>
<script>

//definition of the test object
function Test(aryQuestions, aryChoices, aryAnswers){
	this.questions = aryQuestions;
	this.choices = aryChoices;
	this.answers = aryAnswers;
}


//displays the sample test in the browser with the correct answer highlighted
function WriteTest() {

	var tst = CreateSampleTest();	
	tst = RandomizeTest(tst);
	document.write("<table border=0 cellspacing=3 cellpadding=3><form name=test id=test>");
	for (i=0; i < tst.questions.length; i++) {
		document.write("<tr><td valign=top>&nbsp;</td>")
		document.write("<td><p>" + (i+1) + ".&nbsp;" + tst.questions[i]);
		for (j=0; j < tst.choices[i].length; j++) {
			var correctcount = 0;
			var setblue = "";
			for (k=0; k<tst.answers[i].length; k++) {
				if (tst.answers[i][k] == 1) {
					correctcount++;
				}
			}
			if (tst.answers[i][j] == 1) {
				setblue="class=blue"
			}
			if (correctcount == 1) {
				document.write("<br><input type=radio name=check"+i+" value="+j+" onclick='return false;'>");
				document.write("<span "+setblue+">"+tst.choices[i][j]+"</span>");
			} 
			else {
				document.write("<br><input type=checkbox name=check"+i+" value="+j+" onclick='return false;'>");
				document.write("<span "+setblue+">"+tst.choices[i][j]+"</span>");
			}
		}
		document.write("</td></tr><tr><td colspan=2><br></td></tr>");
	}
	document.write('</form></table>');
}

function CreateSampleTest(){

	var questions = [
		"What can you find in our office?",
		"All of our employees are expected to work no more than ____ hours per week.",
		"The end users of our products number in the _________",
		"Our company is a (choose all that apply):",
		"Tim likes to wear:"
	];

	var choices = [
		[
			"Dart Board",
			"Ping Pong Table",
			"Cubicles",
			"Laptops with dual monitors",
			"TPS reports, ummm yeah"
		],
		[
			"80",
			"40",
			"50",
			"60"
		],
		[
			"Tens",
			"Hundreds",
			"Thousands",
			"Millions",
			"Billions"
		],
		[
			"Great place to work",
			"Respected leader in its field",
			"Place where people don't matter, just results"
		],
		[
			"Capri pants",
			"Goth attire",
			"Sport coat",
			"T-shirt and shorts"
		]
	];

	var answers = [
		[1,1,0,1,0],
		[0,1,0,0],
		[0,0,0,1,0],
		[1,1,0],
		[0,0,0,1,0]
	];	
	
	return new Test(questions, choices, answers);
}

/***************************************************************/
//YOUR CODE HERE

function RandomizeTest(tstObject) {

}

/***************************************************************/

</script>
<style type="text/css">
.blue {font-size : 14px; font-family : arial, helvetica, sans-serif; color : #336897; font-weight:bold;}
</style>
</head>
<body>
<script>
WriteTest();
</script>
</body>
</html>

And that's it. We get to fill in the blank.

The Thought Process

Well as an overview it looks like we need to randomize the questions, randomize the choices of answers, and make sure that the "correct" answers stay in sync with the randomized choices.

Easiest way I could think to do that would be to use some extra arrays to hold the "new" order of the questions and choices after they've been randomized.

The Shuffler

Since this seemed like a real world challenge, to come up with a way to do the actual randomizing I adopted a real world method.. I hit StackOverflow until I found a method that I liked rather than re-inventing the wheel.  I settled on this method from http://dzone.com/snippets/array-shuffle-javascript

function shuffle(o){
    for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
};

Seemed simple enough.

Arrays

Since we'd be doing some shuffling around of items that needed to stay in sync, I figured we'd need a few holding arrays to maintain where the "original" array items ended up after they got randomized.  To do that, I crafted a little helper function to build an array of integers matching the number of entries in the original array -- example, for a five item array of choices or questions, the holding array would contain [0,1,2,3,4] before it was shuffled.

//create an array of integers, zero-based, up to n elements
function buildZeroIntArray(n) {
	var retArr = [];
	if (isNaN(n)) return retArr;
	for (var i = 0; i < n; i++) {
		retArr.push(i.toString());
	}
	return retArr;
}

After shuffling this helper array -- e.g. [3,0,4,1,2] it's just a matter of reconstructing the question, choices, and correct answer arrays into this new randomized order

The Result

So here's the final RandomizeTest function, using the above two helper methods and some verbose variable names!

//RandomizeTest accepts and returns a Test object. The questions in the returned object should be in a random order.
//The order of the choices within each question should also be randomized.
function RandomizeTest(tstObject){	
	//step 1.. before scrambling the questions we need to know how many there are and store their original order
	var numQuestions = tstObject.questions.length;
	var questionOrder = buildZeroIntArray(numQuestions);
	//for 5 questions we'll have the array [0,1,2,3,4]
	
	//step 2.. shuffle the order
	questionOrder = shuffle(questionOrder);
	//now we have our randomized set of questions.. e.g. [3,0,1,4,2]
	
	//step 3.. rebuild the questions array according to our new order
	var newQuestions = [];
	for (var q = 0; q < numQuestions; q++) {
		newQuestions.push(tstObject.questions[questionOrder[q]]);
	}
	tstObject.questions = newQuestions;
	
	//step 4.. for each question we need to retrieve the set of answers, shuffle the answers, and make sure the correct answers remain in sync.

	//define a couple of holding arrays
	var newChoices = [];
	var newAnswers = [];
	
	for (var q = 0; q < numQuestions; q++) {
		//store the current question # to save some array lookups
		var currentQuestion = questionOrder[q];
		//as with the question shuffle, build an array to shuffle the choices
		var numChoices = tstObject.choices[currentQuestion].length;
		var choiceOrder = buildZeroIntArray(numChoices);
		choiceOrder = shuffle(choiceOrder);

		//define temporary arrays to hold the shuffled choices & answers
		var holdChoices = [];
		var holdAnswers = [];
		for (var a = 0; a < numChoices; a++) {
			holdChoices.push(tstObject.choices[currentQuestion][choiceOrder[a]]);
			holdAnswers.push(tstObject.answers[currentQuestion][choiceOrder[a]]);
		}		
		
		//done with this question.. populate the parent holding array with the newly ordered choices
		newChoices.push(holdChoices);
		newAnswers.push(holdAnswers);
	}
	
	//populate the choices & answers with the reordered arrays
	tstObject.choices = newChoices;
	tstObject.answers = newAnswers;
	
	return tstObject;
}

Pretty as pie. If pie was a case sensitive client-side scripting language.

Loading