Good News :)

After months and months of studying, interviewing, and (mostly) getting rejected from many, various, companies, I finally feel like all of this was worth it.

I just accepted an offer from Microsoft, although I also passed my Google interviews and would be in "Google limbo" where I would get matched up with a potential future team.  Getting this close to a Google offer is certainly very enticing, but I'm really drawn to the Microsoft Explore program where I would get to experience all three roles of software (development, testing, and program management).  It's a program that I haven't seen implemented in other companies and it's a once-in-a-lifetime opportunity; after this year I would no longer be eligible for it.

I can't even put into words how good it finally feels to have an (awesome!!) internship in tow for the summer.  After averaging 3 interviews a week for about two months, stressing out before hand, ditching class in the hope that an extra few hours of studying would pay off during interviews, or thinking about this summer and not having a place to call home - it's finally all done and I have an offer I am so very proud of, in my favorite city in this country.  So often I have imagined myself living in Seattle among all of the other tech geeks, now it's finally going to happen.

This post has no benefit to anyone else, just me.  It's my self-congratulatory message to myself.  After months and months of difficulty I feel like I am allowed to pat myself on the back, just this once.  Thanks to my family, friends, and friendly Microsoft recruiters for their support :)

This is what happens when Google and Pixar work together

http://www.wired.com/business/2013/10/motorola-google-mouse/

It's.. I don't even know.  I read about it before I saw it in person today.  The descriptions don't do it justice.  I was shrieking with joy as I panned my friend's phone across all 360 degrees and watched the virtual reality of a mouse losing his hat unfold.

Ice Cream Delegates

Because programming concepts are always so much more delicious when you add ice cream to them.

delegate string IceCreamShop(string iceCreamFlavor);

static string Jenis(string iceCreamFlavor)
{
    string betterFlavor = "no jenis for you";

    switch (iceCreamFlavor.ToLower()) {
        case "chocolate":
            betterFlavor = "Askinosie Dark Chocolate";
            break;
        case "vanilla":
            betterFlavor = "Ugandan Vanilla Bean";
            break;
        case "peanut butter":
            betterFlavor = "Buckeye State";
            break;
    }

    return betterFlavor;
}

static string CheapIceCreamStore(string iceCreamFlavor)
{
    string ickyFlavor = "no cheap ice cream for you but that's probably not a bad thing";

    switch (iceCreamFlavor.ToLower())
    {
        case "chocolate":
            ickyFlavor = "mysterious brown stuff";
            break;
        case "vanilla":
            ickyFlavor = "mayonnaise";
            break;
        case "peanut butter":
            ickyFlavor = "dirt";
            break;
    }

    return ickyFlavor;
}

And this is how you use it:

static void Main(string[] args)
{
    IceCreamShop iceCreamShop = Jenis;
    Console.WriteLine(iceCreamShop("chocolate"));

    iceCreamShop = CheapIceCreamStore;
    Console.WriteLine(iceCreamShop("chocolate"));
}

The output is, predictably:

Askinosie Dark Chocolate
mysterious brown stuff

I can also pass in my ice cream shop delegate as a parameter!

static void PrintMenu(List<string> flavors, IceCreamShop iceCreamShop)
{
    foreach (string flavor in flavors)
    {
        Console.WriteLine(iceCreamShop(flavor));
    }
}

static void Main(string[] args)
{
    var flavors = new List<string> { "chocolate", "vanilla", "peanut butter"};

    IceCreamShop iceCreamShop = Jenis;
    Console.WriteLine("Delicious Jeni's menu:");
    PrintMenu(flavors, iceCreamShop);

    Console.WriteLine();

    iceCreamShop = CheapIceCreamStore;
    Console.WriteLine("icky other ice cream store menu:");
    PrintMenu(flavors, iceCreamShop);
}

With the output:

Delicious Jeni's menu:
Askinosie Dark Chocolate
Ugandan Vanilla Bean
Buckeye State

icky other ice cream store menu:
mysterious brown stuff
mayonnaise
dirt

Columbus natives will appreciate the Jeni's reference. If you don't know what Jeni's is, I'm sorry to know that but it's such a good ice cream store that it's spreading across the country and you will hopefully soon know what I am talking about.  I recommend Salty Caramel to all Jeni's first timers.

Cool websites

http://www.lifehack.org/articles/technology/25-killer-websites-that-make-you-cleverer-2.html

Interview Question - Get Permutations of a String

My algorithm follows the same idea as Gayle's in Cracking the Coding Interview, I've just implemented it iteratively instead of recursively

public static List<string> GetPermutations(string input)
{
   var permutes = new List<string>();
   for (int i = 0; i < input.Length; i++)
   {
      if (i == 0)
      {
         permutes.Add(input[i].ToString());
      }
      else
      {
          var newPermutes = new List<string>();
          foreach (string word in permutes)
          {
             AddCharToEveryPosition(input[i], word, newPermutes);
          }
          permutes = newPermutes;
      }
  }
  return permutes;
}

private static void AddCharToEveryPosition(char c, string word, List<string> newPermutes)
{
   for (int i = 0; i <= word.Length; i++)
   {
      string newWord = word.Insert(i, c.ToString());
      newPermutes.Add(newWord);
   }
}

I'll run through the algorithm a bit since it helps me to understand what's going on.

Say input is "meh"
We take the first letter 'm'
Then we take the second letter 'e' and add it wherever we can to the first letter.  For now we can't go too crazy, we just get { "em", "me" }
Third letter is slightly more interesting, since we now get { "hem", "ehm", "emh", "hme", "mhe", "meh" }
You can imagine how crazy it gets with more letters.

Yay permutations!

Interview Question - Add two integers without using + sign

This seems simple enough but to those not too comfortable with bits, it's a bit tricky (ha...)

public int AddWithBits(int a, int b) {
   while (b > 0) {
      var sum = a ^ b;
      var carry = (a & b) << 1;
      a = sum;
      b = carry;
   }

   return a;
}

Interview Question - Determine if a Tree is a Binary Search Tree

Well it's interview season.  That basically means it's the time of year I spend way more time studying for interviews than I do for actual class work.  Which doesn't bode well for my next week of midterms but I guess getting a summer internship is more important in the long run than acing one midterm.

Here's a question I remember I attempted a year ago, gave up, tried again recently, and got a working solution:

Determine if a binary tree is a binary search tree.
Solution in C#.  I defined previous and current as ints above because I didn't want to distract from the logic of the code.

const int previous = 1;
const int current = 0;

static bool IsBSTHelper(BSTNode node, int[] a)
{
    if (node == null) return true;

    var isValidBST = IsBSTHelper(node.left, a);

    a[previous] = a[current];
    a[current] = node.data;

    if (a[current] < a[previous])
    {
        return false;
    }

    return isValidBST && IsBSTHelper(node.right, a);
}

static bool IsBST(BSTNode root)
{
    return IsBSTHelper(root, new int[] {int.MinValue, int.MinValue});
}

I started out with the classic pre-order tree traversal.  Since it prints out the elements in the right order, I figured I would save the last printed element in the recursive call and compare it with the next printed element.  I was running into problems with that until I decided to use an array of two ints to store the values instead.  And now.. it works for all of my test cases.

Here I assume the tree is nice.  This wouldn't return false if a tree has more than two children per node, or if the tree has a loop.