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.

Adventures in Interviewing #1: The Coin Jar

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 first in the series.

Implement a coin jar in C#. The coin jar will only accept US coinage and has a volume of 32 fluid ounces. Additionally, the jar has a counter to keep track of the total amount of money collected and has the ability to reset the count back to $0.00.

Evaluation

My first consideration is how complex to make this thing.  They did not give any guidance about time frames to complete it, whether they wanted actual code that would compile versus a text file of pseudocode, whether they wanted unit tests, etc.  The above was the sole beginning and end of it.  Since this was the third question in an overall coding "test", I decided to give them a working solution that would compile and met the requirements - and nothing further (no unit tests).  In hindsight, the lack of unit tests might have been my undoing for this specific position, but without any feedback from them on my chosen solution, I really don't know.

So now we need to figure out some stuff.  Since this seems to be a volume question, we need to know the volume of standard US coins, and the volume of the jar.  Mister Google helps us out there.

US Mint Coin Specifications
Fluid Ounce to Cubic Centimeter Calculator

Of course there's other considerations too - the capacity of the jar would also be influenced by its physical dimensions and whether the jar cylindrical or rectangular.  For the coins themselves, how the coins fall into the jar, and the mixture of coins have an impact on just how many the jar could "hold" before it became full.  But I think that these considerations are likely out of scope for an interviewing question, so I took the perfect storm approach - the coins would fall perfectly and magically arrange themselves inside a jar that changes its shape magically so that all available space would be used, as long as 32 fluid ounces of coins were involved.

Bases covered, time to start coding.  I decided to make this a console application, as it would be less code and could be sent back to them as a text document that they could cut/paste into VStudio or whatever to compile.

The Classes

So obviously we need a couple of classes here - a Coin class, and a Jar class.

public class Coin {
    public string CoinName { get; set; }
    public double Diameter { get; set; }
    public double Thickness { get; set; }
    public int CoinValue { get; set; }

    //Note: Volume is the cylindrical volume of the coin.  BoxVolume is the effective space occupied by the coin.
    //Not using Volume in this implementation but for sake of completeness it's present.
    public double Volume { get { return Math.Pow((Diameter / 2), 2) * Math.PI * Thickness; } }
    public double BoxVolume { get { return Diameter * Diameter * Thickness; } }

    public Coin(string name, double diameter, double thickness, int coinValue) {
      CoinName = name;
      Diameter = diameter;
      Thickness = thickness;
      CoinValue = coinValue;
   }
}

The class is pretty straight forward - a few relevant properties and a couple of calculations. I included two Volume calculations - one for the actual cylindrical calculation and a more simple "box volume" to see how much space the coin as a whole takes up. The actual volume would be useful if going into granular determination of how the coins mesh together, but for this project in my magic jar, I just wanted their basic volume.

public class Jar {
    //define the volume of the jar in cubic millimeters
    //source.. http://www.asknumbers.com/CubicCentimeterToOunce.aspx
    const double UsFluidOunceInCubicMM = 29573.5296;

    private double _volumeRemaining;
    private int _totalCoinValue;

    //storing the individual coins would allow for future functionality such as
    //listing a count by coin type, removing all quarters, etc.
    private List _bankedCoins;

    public Jar(int fluidOunces) {
      _volumeRemaining = fluidOunces * UsFluidOunceInCubicMM;
      _totalCoinValue = 0;
      _bankedCoins = new List();
    }

    public bool AddCoin(Coin coinToAdd) {
      //check to see if there's enough space in the jar to hold the coin
      if (coinToAdd.BoxVolume < _volumeRemaining) {
        _bankedCoins.Add(coinToAdd);
        _totalCoinValue += coinToAdd.CoinValue;
        _volumeRemaining -= coinToAdd.BoxVolume;
        return true;
      }
      return false;
    }

    //return the current value of the jar's contents
    public int GetCurrentValue() {
      return _totalCoinValue;
    }

    //empty the jar of coins
    public void EmptyTheJar() {
      _totalCoinValue = 0;
      _bankedCoins.Clear();
    }
  }

For the Jar class, again, some basic properties and a magic number to convert fluid ounces into cubic millimeters (the online calculator was in centimeters, but changed it to millimeters here to match the dimensions of the coins.. the alternative was to convert the coins into cubic centimeters.. six of one, half dozen the other..).  As an unneeded caveat, I added a collection to the Jar class to store individual coins, in case someone wanted to remove all of a particular coin type, or count up the dimes, etc.  The rest is pretty self-explanatory.. a method to get the current value inside the jar, and empty it -- the latter a requirement of the problem.

The Program

All that's left is to write the program to initialize everything and print out a few test statements.

class Program {

    //define the allowed coins.  using a dictionary for easier lookup.
    private static Dictionary<int, Coin> _allowedCoins = new Dictionary<int, Coin>();
    private static Jar _theCoinJar;

    static void Main(string[] args) {
      //define the jar for 32 fluid ounces
      _theCoinJar = new Jar(32);

      //define the coins.. just in case the dimensions change
      //current source.. http://www.usmint.gov/about_the_mint/?action=coin_specifications
      _allowedCoins.Add(1, new Coin("Penny", 19.05, 1.55, 1));
      _allowedCoins.Add(5, new Coin("Nickel", 21.21, 1.95, 5));
      _allowedCoins.Add(10, new Coin("Dime", 17.91, 1.35, 10));
      _allowedCoins.Add(25, new Coin("Quarter", 24.26, 1.75, 25));
      _allowedCoins.Add(50, new Coin("Half Dollar", 30.61, 2.15, 50));

      //usage
      AddCoin(10);
      AddCoin(5);
      AddCoin(25);
      AddCoin(50);
      AddCoin(75); //should be rejected.
      Console.WriteLine("The jar contains {0} cents.", _theCoinJar.GetCurrentValue()); //should be 90 cents
      _theCoinJar.EmptyTheJar();
      Console.WriteLine("The jar contains {0} cents.", _theCoinJar.GetCurrentValue()); //should be 0 cents
    }

    static void AddCoin(int coinValue) {
      if (_allowedCoins.ContainsKey(coinValue)) {
        if (_theCoinJar.AddCoin(_allowedCoins[coinValue])) {
          Console.WriteLine("{0} added to the jar.", _allowedCoins[coinValue].CoinName);
        }
        else {
          Console.WriteLine("The jar doesn't have enough space for a {0}.", _allowedCoins[coinValue].CoinName);
        }
      }
      else {
        Console.WriteLine("Please insert a standard US coin.");
      }
    }
  }

Set up a couple of global variables to hold the coin dictionary and the jar itself, define the individual coins, add a method to add the coins into the jar with some rudimentary error checking to see if the jar is full, or an invalid coin is dropped in.. and that's it. 

Adventures in AngularJS

I recently ran through the AngularJS Tutorial.  I'd heard good things about Angular so I wanted to see what it was all about. The tutorial is in 12 parts and slowly constructs a list / detail application for some cell phones, using a MVC pattern on the client side.  All the server did was feed in the .js files and the .json data via http calls, and further into the tutorial, a RESTful method.

I run in a MS Windows environment, so I followed along the instructions to install node.js, then Karma (for testing), Git, and finally the Angular tutorial environment which dumped everything into a folder, ready to go.  Sorta.

They give you the option of using a node.js webserver to host the application, or you can use whatever server you have laying around - in my case, IIS 7.5.  I opted to use IIS.

Setting up IIS was simple - I merely added a new Site and pointed it to the tutorial folder, fired up a browser and.. no.  There was a permission problem.  This makes sense because the new folder created by the angular Git installer wouldn't have the necessary permissions for IUSR_Whatever to read from it.  A few clicks later and this was resolved - the application was running in the browser and I could proceed through the tutorial.

Tutorial 5

Things ground to a halt at Tutorial 5, where things switched from hard-coded data to fetching data more dynamically from the server - in this case, a .json file.  No errors appeared on the page, just no data.  After adding an .error function to the Angular $http call, I learned it was returning a 404.

Well this didn't make sense.  The file was there.  I saw it.  But even if I tried to directly access it in the browser, I'd get a 404.  Then it occurred to me.. a .json file was probably not listed in the IIS MIME types so it had no idea how to serve it.

I checked in IIS Manager and sure enough, no .json in the MIME types.  Added it (application/json) and bingo, there's the data.  The tutorial could continue.

Tutorial 7

My next head-scratcher was Tutorial 7, where the detail page was added and the links on the list page would go to the new detail page (nothing more than a placeholder at this point, but still.. detail).  I'd click on the links, the URL in the browser window changed, but the page itself stayed on the list page.

After clicking about, I finally F5'd the page and the detail page appeared.  I'm guessing it was some odd caching problem, probably in IE 11.  After that initial refresh, all of the links started working as intended, with fresh detail pages appearing.  I don't have an exact answer for this one.

Tutorial 8

This one wasn't a head-scratcher, only that the tutorial usually gives you some idea of what to do during the Experiment section to accomplish what they are wanting you to learn.  This time around, they give you a task but don't spell out how to do it.  In the interests of knowledge sharing, I decided I'd post it.

Within the Phone Detail View section of scenario.js add the following:

it('should have 4 thumbnail images', function() {
	expect(repeater('.phone-thumbs li').count()).toBe(4);
});

Tutorial 12

Lastly, I'm just guessing that Tutorial 12 cuts off, both in IE and Chrome, because there are no conclusions or detailed tests or experiments or Summary on that one.  If I get a chance to fire up Firebug or something that will let me see the dynamic content (View Source doesn't), I'll see if there's just some bad markup that's cutting the rest of the article off.  For now I really wasn't that concerned because it dealt with Animations, which are pretty low on my list of interests.

Conclusion

The tutorial was interesting.  It was pretty basic by what is possible with Angular, I'm sure - but it was enough to whet my appetite and want to dig into it a little more.  Being able to perform MVC structures easily on the client side is useful, I believe, as more apps seem to want to shuffle off duties from the servers down to the clients.