Cracking the Coding Interview Problem 2.2

Posted on by
3

I don’t blog often. And I haven’t blogged about coding for a while; but I think I should. So here goes.

Having recently graduated from UCLA, I’m now trying to get a solid job at a solid company making some solid money. My skills primarily consist of writing code and running startups so that’s my target. Apart from the obvious choices (Google, Facebook, Microsoft, and so on), I’m also applying to a slew of startups around LA and the Bay Area. If you’re not familiar with the interview processes for tech companies, they go something like so: HR interview, phone tech interview 1, phone tech interview 2 … phone tech interview n, campus tech interview 1, campus tech interview 2 … campus tech interview n, offer or no offer.

Now I’m all up for hiring smart people that know how to get things done, but I really really loathe the technical interview. To explain why, let me cite an example from Cracking the Code Interview — the de facto bible of tech interviews.

2.2 Implement an algorithm to find the nth to last element of a singly linked list.

Easy, right? Well, not so fast, skipper. Here is the proposed solution (by an apparent Googler):

public static LinkedListNode nthToLast(LinkedListNode head, int n) {
	LinkedListNode p1 = head;
	LinkedListNode p2 = head;

	if (n <= 0) return null;

	// Move p2 n nodes into the list. Keep n1 in the same position.
	for (int i = 0; i < n - 1; i++) {
		if (p2 == null) {
			return null; // Error: list is too small.
		}
		p2 = p2.next;
	}
	if (p2 == null) { // Another error check.
		return null;
	}

	// Move them at the same pace. When p2 hits the end,
	// p1 will be at the right element.
	while (p2.next != null) {
		p1 = p1.next;
		p2 = p2.next;
	}
	return p1;
}

Feel free to scratch your head and go “what the hell” because I know I am. The above is considered a solution to Problem 2.2. First, let me mention what’s wrong with it:

  • Using two pointers is dumb.
  • It’s difficult to read. I needed 10 minutes to get my head around it when the function should be doing something trivial
  • It’s simply bad design. More on this in a few.

Now let’s solve the problem like real software engineers, not hipster programmers that thrive on esoteric nonsense:

// this is how normal people find the length of a linked list
public int getLength(Node head) {
	int length = 0;
	Node n = head;
		
	// iterate through the list
	while (n != null) {
		// yay more length
		++length;

		// go forward!
		n = n.next;
	}
	return length;
}
	
// this is how normal people find the nth to last node of a linked list
public Node getnthFromLast(Node head, int nth) {
	int length = getLength(head);
	Node n = head;
	int location = 0;
		
	// if list is empty or we want to go too far back or we want zeroth to last, return null
	if (length == 0 || nth > length || nth <= 0) return null;
		
	// 1st to last = last
	// 2nd to last = penultimate (length-1)
	// 3rd to last = length - 2
	// .. and so on
	while (n != null) {

		// right location?
		if (location == length - nth) return n;
			
		// next spot
		++location;
			
		// next node
		n = n.next;
	}
}

Simple, concise, readable. What irks me most is that not only will interviewers think code like the one from the book is good, but so will interviewees. Oh well, c’est la vie.

Back in black

Posted on by
1

After a Dreamhost blunder that left thousands with their websites hanging by a thread (or by a noose), my blog was also deemed infected with some sort of virus. I have no idea what kind of vulnerability DH was trying to fix, but I couldn’t find anything that was compromised. Even so, my WordPress installation wouldn’t start up. So I had to re-install the whole thing, find a new theme, mess around with it a bit and re-launch.

I’m back in black. And to all of my imaginary fans: I love you!

Resolutions

Posted on by
2

I’m not very goal oriented. Maybe I should be. So here are some resolutions for 2012.

  • Continue getting straight A’s
  • Launch E-Sports Rankings and make it successful
  • Gain 10-20lb of muscle mass
  • Read at least 12 books
  • Do some stand-up
  • Release a game on the Android market
  • Update this blog daily
  • Moar?

Here’s hoping I’ll at least get through half of those!

A Tale of Two Games: ToR and WoW – Review!

Posted on by
Reply

(The following review was taken from this thread on the ToR forums.)

It was the best of times, it was the worst of times. For ToR, unfortunately, mostly the worst. This isn’t my first review – I reviewed the game during the beta several times, but I was shunned by incredulous and overzealous fans. After all, it was “just” a beta. Well here we are, at the dawn of release – no longer in the beta. So where does this game stand in the grand scheme of things? How does it compare to WoW, SWG, Rift, GW2? Lets find out.

Who am I? I’m some dude that led a top-US CS:S team for many years, was a part of two top-10 WoW guilds, and played in several WoW Arena Tournies (including the CGS invitational) and many many CS tournaments, including the CPL. I also had a stint working for an indie game developer several years ago. I like to think that I know what I’m talking about, and usually, I do.

Story

Story. Story. Story. We’ve heard it over and over again. Bioware has really hammered this home – much how Vincent Chase is Queens Boulevard, The Old Republic is story. And story is one of the few battles ToR wins. The voice over quality is top notch and primary class quests are mostly interesting and engaging. Some may be deterred by the incessant use of family drama as a plot device since it gets old pretty fast. With that said, don’t expect Chaucer, but the writing is sufficient.

Unfortunately, the side quests are problematic and suffer from trivial subject matters (“blah blah click some turrets”) or endless fetch questing (go to X, come back to Y, go to X again, now back to Y). This wouldn’t have been a problem 10 years ago, but 2012 is almost here. WoW has moved us past the trivialities of fetch questing and now we do cool stuff like lassoing dragons, bombing runs or mind-controlling giants. ToR pretends like there hasn’t been an entire generation of MMORPGs since KOTOR and suffers for it greatly. Bonus quests are an interesting touch, but more often than not, they insult the player. Here you are doing the most trivial of tasks (ex: clicking control panels – a Bioware favorite) and a bonus quest pops up that asks you to kill 30 of the same type of mob. And just like that, we’re all sent back to the late 90s. Bioware has a lot to learn from Jeff Kaplan.

On many levels, however, the VO is a technical achievement. Ordinarily, I’d have no problem with pouring so much money into something like voice over, but the gameplay significantly suffered from it. To me, that’s unforgivable.

Combat

The crux of a good MMORPG is solid combat. I expect combat to be fluid, responsive, and logical. ToR has a pretty good grasp of what it wants to do, but doesn’t quite reach the bar set by better MMOs. First of all, the “heroic” combat Bioware preached for years and years isn’t as heroic as they made it out to be. Animations are often choppy and blocking animations seem to happen at random times (as opposed to having weapons make contact). But lets face it, it’s not a big deal. What is a big deal, however, is the lack of an auto-attack.

This quizzical gameplay choice hurts more than it helps. It means that the gamer needs to manually press 1-1-1-1-1 (or right-click like a madman) to use the regular “white attack” ability and to generate resources that one may use (in the case of the Warrior-archetypes). Not only is this boring, but it literally provides zero gameplay improvement – what is the reasoning behind no auto-attack? Who knows.

Stealth and cover are very underwhelming. Cover, in particular, is nigh worthless in PvP. The conical radius, the spent GCD, the fact that 4 classes can easily close range, and the fact that almost every class has a knock-back should be very clear indicators that a mechanic like cover is a terrible, terrible idea.

Stealth, as mentioned, is very odd. On one hand, it tries to mimic what stealth is in WoW (a fundamental mechanic of classes like rogues and feral druids), while more often than not it becomes merely a trivial escape mechanism. It needs to be fundamentally reworked – stealth should be a game mechanic, not a novelty.

PvE and Leveling

Admittedly, a high point of the game are the instances (known as flashpoints). Black Talon, Athiss, Hammer Station, etc. are all fairly well-designed. Mechanics are tried and true: get out of the fire, interrupt heals, kite bad stuff. This is where ToR really does feel like “WoW in space” and it’s also arguably the best part of the game. As a matter of fact, the only reason I’m still playing is because I’m curious to see if the large-scale Operations will be as good as Flashpoints.

Leveling is fairly smooth, but the fact that the world is sharded can be distracting and does discourage grouping. Heroic 2+ man quests can be fun, but I found myself skipping them more often than not – the time invested doesn’t seem worth it. During hardcore leveling periods, I also found myself skipping all VO. I don’t care about your life story, I just want to get this quest out of the way. I feel somewhat guilty about it, but these are the scenarios that make me feel like side-quest VO is a swing and a miss – a very expensive miss.

PvP

PvP is a joke, there’s not much more to say. It’s an insult to any form of competitive activity. Huttball is one of the worst ideas I’ve ever seen implemented in an MMO: Warsong Gulch with a passable flag? Really? What irks me most is that someone actually made money coming up with such a terrible idea. Inconsistent traps, obnoxious commentators, bad layout, Huttball has it all. There are 15-year-olds that designed better Unreal Tournament maps. Sure, there may be some occasional mindless fun to be had with Huttball, but there’s no real value here.

Alderaan is significantly better, but doesn’t even compare to the wide variety of BGs present in MMOs like WoW or Rift. Ignoring WoW’s trailblazing here, Rift’s “Black Garden” was a particularly awesome innovation. World PvP is more or less nonexistent.

If ToR was Communist Russia, PvP would be human rights.

Companions

Companions were lauded by Bioware as being an evolutionary step as far as the genre is concerned. Unfortunately, they turned out to be glorified pets. They even have an ability pet bar just like in WoW! Some companions are interesting, some are boring. They do seem to break up the monotony of the often morose landscapes, but they are basically just pets.

Companion crafting is a great idea, however. Not having to worry about crafting stuff yourself is pretty neat. ToR sometimes surprises you with interesting and progressive innovations. Unfortunately, these moments are far and few in between.

DOA

Does The Old Republic have a chance? Not with what we see on day 1. No chance. Fanboys and fangirls may try to make a case for ToR, but the reality is that there is no case for ToR. There are many changes that need to make their way into ToR for it to be a competitor to 2nd tier MMOs, let alone giants like WoW.

UI mods have been requested since beta. A combat log has been requested since beta. There are absolutely no features that even begin to address the social element of the game: guild achievements, guild skill trees, etc. There’s a need for competitive PvP, LFG finders, etc, etc. These shouldn’t be post-release patches, this is 2012! These are basic elements of modern MMORPGs. I don’ think ToR is finished.

The only reason ToR won’t die in 6 months is “Bioware” and “Star Wars.” Will these two names carry the burden for a year? Two? I doubt it. But then again, I could be wrong. http://warhammeronline.com/ is still going. Don’t fool yourself though. It’s dead.

You may berate me now, but don’t forget this review 1 year down the line. ToR is dead. Long live Titan?