Interview Question - Mergesort in C#

public List<int> MergeSort(List<int> m) {
if (m.Count() <= 1) return m;
int mid = m.Count() / 2;
List<int> left = new List<int>(), right = new List<int>();

for (int i = 0; i < mid; i++) left.Add(m[i]);
for (int i = mid; i < m.Count(); i++) right.Add(m[i]);

left = MergeSort(left);
right = MergeSort(right);
return Merge(left, right);
}

public List<int> Merge(List<int> a, List<int> b) {
int aCount = 0, bCount = 0;
List<int> m = new List<int>();

while (m.Count() < a.Count() + b.Count()) {
if (aCount < a.Count() && bCount < b.Count())
m.Add(a[aCount] < b[bCount] ? a[aCount++] : b[bCount++]);
else
m.Add(aCount < a.Count() ? a[aCount++] : b[bCount++]);
}

return m;
}

I realize that nowadays when I practice interview questions I'm tending less towards readability and convention (using var for local variables in C#) in favor of less lines of code (using var means you have to declare each variable on a separate line of code) - when doing interview practice you just wanna get the answer on the page and move on.  I could have refactored the while loop in my Merge function into many more lines of code but opted for the a cryptic version instead, which makes me feel like a boss but may be more confusing to readers the first time through.  So I apologize for that

Interview Question - Write an algorithm to determine if n is a power of 2

If I have the idea correctly, you can actually do this in constant time.

First piece of useful information: Any power of 2 is represented in memory as 0...010...0

Examples:
2 is 00000010
4 is 00000100
8 is 00001000
16 is 00010000

Second piece of useful information: x & (x - 1) is a neat little hack that will return x with its least significant bit cleared out.
What does that do for the examples above?  Just makes them all 0!

So here's the code I wrote:

bool IsPowerOf2(int x) {
   return x > 0 && (x & (x - 1)) == 0;
}

///Update: Crap. This was on stackoverflow already.  Oh well

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!