dxmio.com

The latest in this series makes a shift from C++ to Java since that’s what I’ve been mucking about with lately. I’m in a little bit of a time squeeze at the moment so explanations will have to come later (though this code should be fairly readable and obvious what its doing).

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;
 
public class Program
{
	public static void main(String[] args)
	{
		doMatrixSearch();
		doMissingNumberSearch();
		doFirstUnrepeated();
	}
 
	public static void doFirstUnrepeated()
	{
		String testString = "nnnnnnnnxxnnpnn";
		char[] testStringChars = testString.toCharArray();
 
		class EntryInfo
		{
			int count;
			int firstPos;
		}
 
		HashMap<Character, EntryInfo> stuff = new HashMap<Character, EntryInfo>();
 
		for(int i = 0; i < testStringChars.length; i++)
		{
			EntryInfo thisInfo;
 
			if(stuff.containsKey(testStringChars[i]))
			{
				thisInfo = stuff.get(testStringChars[i]);
				thisInfo.count++;
			}
			else
			{
				thisInfo = new EntryInfo();
				thisInfo.count = 1;
				thisInfo.firstPos = i;
			}
 
			stuff.put(testStringChars[i], thisInfo);
		}
 
		int minPosition = testStringChars.length - 1; 
 
		Collection<Character> coll = stuff.keySet();
		Iterator<Character> iter = coll.iterator();
		while(iter.hasNext())
		{
			Character thisChar = iter.next();
			EntryInfo thisInfo = stuff.get(thisChar);
			if(thisInfo.count == 1 && thisInfo.firstPos < minPosition)
				minPosition = thisInfo.firstPos;
		}
 
		System.out.println("doFirstUnrepeated():\t First non-repeater: " + testStringChars[minPosition]);
 
	}
 
	public static void doMissingNumberSearch()
	{
		int minInclusive = 1;
 
		int[] arr = {1,2,5,6,7,8,9};
 
		int[] missingNums = new int[2];
		int missingNumsPtr = 0;
 
		int shouldExist = minInclusive;
 
		for(int i = 0; i < arr.length && missingNumsPtr < 2; i++)
		{
			if(arr[i] != shouldExist)
			{
				missingNums[missingNumsPtr] = shouldExist;
				missingNumsPtr++;
			}
			shouldExist++;
		}
 
		System.out.println("doMissingNumberSearch():\t Missing nums: " + missingNums[0] + " and " + missingNums[1]);
 
	}
 
	public static void doMatrixSearch()
	{
		int numRuns = 1000;
		int numSteps = 0;
 
		for(int z = 0; z < numRuns; z++)
		{
			Random rnd = new Random();
 
			int[][] arr = new int[5][5];
			int last = 0;
 
			for(int y = 0; y < 5; y++)
			{
				for(int x = 0; x < 5; x++)
				{
					int newval = rnd.nextInt(5) + last;
					arr[x][y] = newval + 10;				
					last = newval;
				}
			}
 
			int toFind = 30;
 
			numSteps += matrixSearch(arr, toFind);
		}
 
		double averageSteps = (double)numSteps / (double)numRuns;
 
		System.out.println("doMatrixSearch():\t Average steps: " + averageSteps);
	}
 
	public static int matrixSearch(int[][] arr, int toFind)
	{
		int numSteps = 0;
 
		int x = arr[0].length - 1;
		int y = 0;
 
		while(x >= 0 && y < arr.length)
		{
			numSteps++;
 
			if(toFind < arr[y][x])
				x--;
			else if(toFind > arr[y][x])
				y++;
			else if(toFind == arr[y][x])
				break;
		}
 
		return numSteps;
 
	}
}

Today’s potential interview question is to reverse a linked list, without recursion. This one can be rather tough on the brain if you don’t think visually, but the basic idea here is to keep a pointer to:

• Keep a pointer to the next node so that you don’t lose a way to access it once you reverse the direction of the prior node’s ‘next’ pointer.
• Keep a pointer to the last node so that you have a way of pointing the current node back (the above is required so that you don’t lose where it formerly pointed.)
• ‘Inchworm’ your way forward in this manner until you’ve hit everything, and at the end repoint the head to be where you’re at.

Here’s the code (Note that NodePtr is simply a typedef of a boost::shared_ptr – it’s a ’smart’ pointer.):

void LinkedList::reverse()
{
	if((_head == NULL) || (_length == 1))
	{
		return;
	}
	else
	{
		NodePtr previous = NodePtr();
		NodePtr current = _head;
		NodePtr next = NodePtr();
		while(current)
		{
			next = current->next;
			current->next = previous;
			previous = current;
			current = next;
		}
 
		_head = previous;
 
	}
}

Interviews in the field of programming are all very similar, usually involving a whiteboard and an algorithm. Sometimes these questions are so incredibly simple, yet for whatever reason you can’t craft an answer on the spot. I’m going to start a series on some code snippets that are common to see in interview situations. All this code is in C++, for no other reason than it happens to be what I’m playing with the most right now.

The first in this series is one that comes easily to most, but I figured I’d start with something simple.

Problem:
Write a function to determine if a string starts with an upper case letter between A and Z.

Solution:

bool starts_with_uppercase(std::string suspect)
{
	if(suspect[0] > 'A' && suspect[0] < 'Z')
		return true;
	else
		return false;
}

More soon.

Do you remember the first time you had coffee? A lot of people relate their first experience as a bad one, and that coffee is an acquired taste. I can’t relate to that because I’ve always loved coffee, from my very first taste, but I understand the notion, and I want to relate that idea to C++ for a minute. C++ is a language that by all modern standards is an awful mess, but one that is arguably most important to learn and understand due to the manual management of the heap and stack.

Ok, so lets say you dive into C++ because you’re interested in knowing everything there is to know about programming. You discover it’s like your coffee experience; It’s bitter, it smells funny, and gives you jitters, but you keep on sipping it because you know it will give you benefits. Fast forward 6 months, and you’re practically hooking it up to your arm with an IV needle. Now you feel very comfortable with it, and you’ve learned a significant amount of other related knowledge as a result of your endeavours. You’re ready to move on to new things, satisfied that you used it as a learning tool, but are you really done with it? Ohh no.

And in that sense, it’s more like cocaine than coffee.

The gaming industry, or any industry that possesses an interest in high-performance computing applications, is addicted to C++. Regardless of how far garbage collection has come, or how good virtualization abstractions have gotten, they cling to it proclaiming “JUST ONE MORE HIT MAN, JUST ONE MORE HIT”. I sympathize on the one hand because C++ ought to be mandatory learning material for computer science students, but at the same time, haven’t we come far enough with the performance of other languages that we can just go ahead and take C++ out back of the shed?

Today I take another paragraph from one of Joel Spolsky’s posts and quote it here for emphasis on something I find very important:

“When a programmer complains about “politics”, they mean—very precisely—any situation in which personal considerations outweigh technical considerations. Nothing is more infuriating than when a developer is told to use a certain programming language, not the best one for the task at hand, because the boss likes it. Nothing is more maddening than when people are promoted because of their ability to network rather than being promoted strictly on merit. Nothing is more aggravating to a developer than being forced to do something that is technically inferior because someone higher than them in the organization, or someone better-connected, insists on it.”

“You do have to pay competitively, but all said, of all the things that programmers look at in deciding where to work, as long as the salaries are basically fair, they will be surprisingly low on their list of considerations, and offering high salaries is a surprisingly ineffective tool in overcoming problems like the fact that programmers get 15″ monitors and salespeople yell at them all the time and the job involves making nuclear weapons out of baby seals.”

“If somebody tells you that the job of a bricklayer is to lay bricks on bricks then you will probably not want to be a bricklayer. But what if somebody told you about building a cathedral? It is the same with programming. You need a vision to make it meaningful.”

Today I went back and re-read Joel Spolsky’s advice The Law of Leaky Abstractions and it hits a nail on the head about what peers from EWU were missing:

“Learn how to do it manually first, then use abstractions to save time. Code generation tools which pretend to abstract out something, like all abstractions, leak, and the only way to deal with the leaks competently is to learn about how the abstractions work and what they are abstracting. So the abstractions save us time working, but they don’t save us time learning. And all this means that paradoxically, even as we have higher and higher level programming tools with better and better abstractions, becoming a proficient programmer is getting harder and harder.”

New gaming system on its way from Newegg:

• Antec Nine Hundred Black Steel ATX Mid Tower Case
• Dell 2408WFP 24″ Monitor
• GIGABYTE GA-P55-UD4P Intel P55 ATX Intel Motherboard
• BFG Tech GeForce GTX295 1792MB 896-bit GDDR3 PCI-E2 x16 Video Card
• CORSAIR CMPSU-850TX 850W Power Supply
• Intel Core i5 750 Lynnfield 2.66GHz Quad-Core Processor
• G.SKILL 4GB DDR3 SDRAM DDR3 1600 Dual Channel Memory
• Western Digital Caviar WD15EADS 1.5TB SATA 3.0Gb/s Hard Drive
• Logitech G5 7 Button USB Wired Laser Mouse
• Microsoft Digital Multimedia Pro Keyboard

I spent several months trying to locate a job in Seattle, but the economic situation displaced a lot of software developers who are now vying for the same positions as college graduates. I had many interviews and leads in Seattle, but in the end it proved too competitive to break into. Now that the ink has dried, I can reveal that instead I’ve been hired by a government research lab to do software maintenance in the Tri-Cities. This works out in the end since I have friends and family here. I know the area, the pay is good, and I’ll be doing what I like.

Since moving back, I’ve reconnected with friends from years past. There are two groups of friends, both of which who hold LANparties on a frequent basis, which is great. A lot of the problems that I’ve alluded to in the past about friends in this town have worked themselves out, so maybe karma exists after all. At any rate (I seem to be using the cliche ‘At any rate’ often this week…), Susanna and I have a great new apartment, things to keep me entertained, friends to hang out with, and a stable job with great potential for advancement.

Seeing as how the Tri-Cities is wine country, I figured I’d ought to educate myself on wine and try all the different types around here. I’ll probably create a page on this website with wine reviews, and possibly open it to others to add to. So far, my favorites are a 2005 Hogue Late Harvest Reisling, and a 2006 Maryhill Cabernet Sauvignon. I have an iPhone app that gives me pointers on local wines that have won awards and where to find them, which is handy. Any advice on wine is greatly appreciated.

With all the LANparties I’ve gone to, I’ve started gaming more. So far I’ve been playing Team Fortress 2, Call of Duty 4, and a new game Demigod. Demigod is interesting because it’s the same idea as Warcraft 3: DOTA, but simplified and streamlined. Apparently the network code for the game was atrocious at release, but has since been greatly improved due to the popularity of the game.

Susanna and I haven’t moved all of our things from our old apartment yet, because my new employer is processing paperwork to pay for my relocation. Instead, we’ve moved the small stuff; Computers, food, hygiene, TV, couch, etc. It’s a very large apartment and without our furniture, it seems vacant at times.

Look for that wine review page soon.

“Valve co-founder Gabe Newell announced during a DICE keynote today that last weekend’s half-price sale of Left 4 Dead resulted in a 3000% increase in sales of the game, posting overall sales (in dollar amount) that beat the title’s original launch performance.”