Running with Code Like with scissors, only more dangerous

1Jul/140

Dear Internet, please stop auto-playing videos

Posted by Rob Paveza

There is nothing more irritating than when going through a list of news articles that I want to read while having music on, and all of a sudden some video starts playing in one of the tabs that I opened. The video is almost always an ad, which I don't have particular objections to, but the automatic play when I wanted to read, not watch, because I'm listening to music.

Please STOP.

6Apr/141

The technical interview, part 2: Deck of Cards

Posted by Rob Paveza

Last time, I talked about how to dazzle an interviewer who asks you to write some code to test whether a given input is a palindrome. This time, it's my favorite interview question to ask.

Interviewer: Write some code that creates a deck of cards. If you ask for more details, I'll tell you something to the effect of, Imagine I want to write a game like poker or solitaire. I need to create a standard deck of cards.

This question is deliberately open-ended to test a few things:

  • Can you identify what kinds of objects are needed?
  • Can you design good APIs?
  • Can you choose effective data structures?
  • Can you design and implement good algorithms?

As a candidate, I would want to start out by establishing what cards are: they are a collection of a suit and a rank. These are each discrete values, and could be implemented as an enumeration in languages which support them, or else constants:

var Suit = {
    clubs: 1,
    diamonds: 2,
    hearts: 3,
    spades: 4
};
var Rank = {
    ace: 1,
    two: 2,
    three: 3,
    four: 4,
    five: 5,
    six: 6,
    seven: 7,
    eight: 8,
    nine: 9,
    ten: 10,
    jack: 11,
    queen: 12,
    king: 13
};
public enum Suit 
{
    Clubs,
    Diamonds,
    Hearts,
    Spades,
}

public enum Rank
{
    Ace,
    Two,
    Three,
    Four,
    Five,
    Six,
    Seven,
    Eight,
    Nine,
    Ten,
    Jack,
    Queen,
    King,
}
enum Suit {
    clubs,
    diamonds,
    hearts,
    spades,
}

enum Rank {
    ace,
    two,
    three,
    four,
    five,
    six,
    seven,
    eight,
    nine,
    ten,
    jack,
    queen,
    king,
}

Try this in the TypeScript playground.

An enumeration is a kind of type that provides a set of named constants. Not all languages support enumerations, but they're fairly easy to simulate in most, like I did in JavaScript above.

Now that we have the suit and rank set up, we can create a class or structure to represent a Card. Why have I chosen to do this? The problem asks for a deck of cards; clearly a Deck is a discrete object which is composed of some number of other discrete objects (Cards).

function Card(suit, rank) {
    if (suit < Suit.clubs || suit > Suit.spades)
        throw new RangeError('Invalid suit.');
    if (rank < Rank.ace || rank > Rank.king)
        throw new RangeError('Invalid rank.');

    this.suit = suit;
    this.rank = rank;
}
public class Card
{
    // The readonly modifier should only be used for immutable value-types.
    // In this case since they're enumerations which are value-types, it's good.
    private readonly Suit _suit;
    private readonly Rank _rank;

    public Card(Suit suit, Rank rank) 
    {
        // Checking range is also valid (like the other language examples).
        // This is a pretty good API to know about though.
        if (!Enum.IsDefined(typeof(Suit), suit))
            throw new ArgumentOutOfRangeException("suit");
        if (!Enum.IsDefined(typeof(Rank), rank))
            throw new ArgumentOutOfRangeException("rank");

        _suit = suit;
        _rank = rank;
    }

    public Suit Suit 
    {
        get { return _suit; }
    }

    public Rank Rank 
    {
        get { return _rank; }
    }
}
class Card
{
    // TypeScript supports a shorthand for declaring properties.
    // The code that this emits will be (almost) identical to the JavaScript sample,
    // except that the range check will be done after the property assignment.
    constructor(public suit: Suit, public rank: Rank) {
        if (suit < Suit.clubs || suit > Suit.spades)
            throw new RangeError('Invalid suit.');
        if (rank < Rank.ace || rank > Rank.king)
            throw new RangeError('Invalid rank.');
    }
}

Try this in the TypeScript playground.

In object-oriented programming, a class is the definition of a custom data type. Classes create an abstract "view" of data in the same way we can think of categories of objects (for example, "books" or "animals") which have some common sets of characteristics. Classes aren't the data themselves, however; we refer to individual datums as "objects" or "object instances." Each object of a given class should have the same kinds of data and similar behaviors, but each individual object might have specific nuances or individual data. For example, any given book might have a different number of pages, but all books have *some* number of pages.

Cards are simple data types. They have two properties - rank and suit - and once the card is created, you shouldn't be able to change those values. (The samples for JavaScript and TypeScript don't enforce that restriction, and if you point that out, you'll probably get bonus points). Given these constraints, it may also be worthwhile for the C# developer to point out that a Card could be a struct because structs should represent immutable values, but it's also not invalid to use a class here.

Classes have a desirable characteristic: they represent composition (or aggregation) of multiple values. That leads us to believe that a Deck, which is composed of multiple Cards, should also be a class:

function Deck() {
    this._cards = [];
}

Deck.prototype.addCard = function(card) {
    // Don't need to do checking specifically but if you want to be really fancy:
    if (!(card instanceof Card))
        throw new RangeError("Can only add a Card to the deck.");

    this._cards.push(card);
}

Deck.prototype.dealCard = function() {
    if (this._cards.length === 0)
        throw new RangeError("No cards to deal.");

    return this._cards.pop();
}

Deck.prototype.shuffle = function(numTimes) {
    // numTimes is an optional parameter.  If it's not a number, set a reasonable default.
    if (typeof numTimes !== 'number')
        numTimes = 5;

    var cards = this._cards;
    var cardCount = cards.length;

    // Do the shuffle operation numTimes times.
    for (var time = 0; time < numTimes; time++) {
        // Visit every card position once per "time"
        for (var index = 0; index < cardCount; index++) {
            // Create a random number in the range of [0, length)
            var numToSwap = Math.floor(Math.random() * cardCount);
            // Swap the cards at index and numToSwap
            var temp = cards[numToSwap];
            cards[numToSwap] = cards[index];
            cards[index] = temp;
        }
    }
}

// Not a prototype function.
Deck.createPokerDeck = function() {
    var result = new Deck();

    // Note these operators should be <= because we want to ensure we include all suits and ranks.
    for (var suit = Suit.clubs; suit <= Suit.spades; suit++) {
        for (var rank = Rank.ace; rank <= Rank.king; rank++) {
            var card = new Card(suit, rank);
            result.addCard(card);
        }
    }

    return result;
}
public class Deck
{
    private List<Card> _cards;
    private int _curPos;

    // The keen observer will notice that _curPos always equals _cards.Length - 1.
    // Can optimize this away but it's good for illustrative purposes.
    public Deck()
    {
        _cards = new List<Card>();
        _curPos = -1;
    }

    public void AddCard(Card card)
    {
        if (card == null)
            throw new ArgumentNullException("card");

        this._cards.Add(card);
        this._curPos++;
    }

    public Card DealCard()
    {
        if (this._curPos < 0 || this._cards.Count == 0)
            throw new InvalidOperationException("There are no cards to deal.");

        var card = this._cards[this._curPos];
        this._cards.RemoveAt(this._curPos);
        this._curPos--; // Optionally, decrement operation can be combined into the previous line as long as it's postfix.

        return card;
    }

    public void Shuffle(int numTimes = 5)
    {
        List<Card> cards = this._cards;
        int cardCount = cards.Count;
        Random rng = new Random();

        // Do the shuffle operation numTimes times.
        for (int time = 0; time < numTimes; time++)
        {
            // Visit every card position once per "time"
            for (var index = 0; index < cardCount; index++)
            {
                // Create a random number in the range of [0, length)
                int indexToSwap = rng.Next(cardCount);
                // Swap the cards at index and indexToSwap
                Card temp = cards[indexToSwap];
                cards[indexToSwap] = cards[index];
                cards[index] = temp;
            }
        }
    }

    public static Deck CreatePokerDeck()
    {
        Deck result = new Deck();

        // Note these operators should be <= because we want to ensure we include all suits and ranks.
        for (int suit = (int)Suit.Clubs; suit <= (int)Suit.Spades; suit++) {
            for (int rank = (int)Rank.Ace; rank <= (int)Rank.King; rank++) {
                var card = new Card((Suit)suit, (Rank)rank);
                result.AddCard(card);
            }
        }

        return result;
    }
}
class Deck
{
    private _cards: Array<Card>;
    constructor() {
        this._cards = [];
    }

    addCard(card: Card): void {
        // You can bypass runtime type checking here if you're using all TypeScript,
        // because the TypeScript compiler will emit a warning.  Otherwise, see 
        // the JavaScript sample for runtime type checking.

        this._cards.push(card);
    }

    dealCard(): Card {
        if (this._cards.length === 0)
            throw new RangeError('No cards to deal.');

        return this._cards.pop();
    }

    shuffle(numTimes: number = 5): void {
        var cards = this._cards;
        var cardCount = cards.length;

        // Do the shuffle operation numTimes times.
        for (var time = 0; time < numTimes; time++) {
            // Visit every card position once per "time"
            for (var index = 0; index < cardCount; index++) {
                // Create a random number in the range of [0, length)
                var numToSwap = Math.floor(Math.random() * cardCount);
                // Swap the cards at index and numToSwap
                var temp = cards[numToSwap];
                cards[numToSwap] = cards[index];
                cards[index] = temp;
            }
        }
    }

    static createPokerDeck(): Deck {
        var result = new Deck();

        // Note these operators should be <= because we want to ensure we include all suits and ranks.
        for (var suit = Suit.clubs; suit <= Suit.spades; suit++) {
            for (var rank = Rank.ace; rank <= Rank.king; rank++) {
                var card = new Card(suit, rank);
                result.addCard(card);
            }
        }

        return result;
    }
}

Try this in the TypeScript playground.

Let's unpack this piece-by-piece:

Use of an Array to store the Cards in JavaScript/TypeScript, List in C#

An Array is the default collection type in JavaScript and there isn't really a compelling reason to switch. Since an Array automatically grows and shrinks as you add and remove items, and these are such common operations that the engines optimize for them, there isn't a good reason to switch to another data type. In C#, the choice of a List is an interesting one. Alternatives include a linked list, Queue, or Stack, particularly because the JavaScript variants use Stack semantics (push/pop). However, the most computationally-intensive function of a Deck, Shuffle, requires random-access, and none of those alternatives is the right data type for random access.

AddCard

This method is pretty straightforward; it adds a new card to the end of the existing collection. You might call out that you're not checking for equality; this allows a Deck to contain multiple copies of the same value Card (for example, two Kings of Diamonds), for example. One thing that you might want to check for is reference equality (so that you're not adding two of the same exact Card variable, which would be impossible with real cards). However, that shouldn't be required unless you're really, really trying to dazzle your interviewer.

DealCard

This method is also pretty straightforward. It should take one card from one end of the array. In JavaScript, it's equally valid to use pop as shift, but I would balk at an implementation using splice as too complex. Range checking is a requirement for this method.

Basic operations and constructor

As an interviewer, I would expect a candidate to at minimum identified AddCard and DealCard as fundamental operations. I would strongly hope that the candidate would also have identified a need to shuffle the cards, and shuffling should also identify the need to have a basic set of cards to populate as well (or, the candidate may want a basic set of cards, and realize that they won't be shuffled). However, I would advise against populating the deck within the constructor. The Deck is the container of Cards; you use a Deck for Euchre, but it doesn't have the same set of Cards within it as a Deck for Texas hold 'em.

CreatePokerDeck

The most obvious way to implement this is to go through each of the ranks and suits, creating a Card for each, and adding it to an originally-empty Deck. There are a number of ways to do this; you might see the following implementation:

Deck.createPokerDeck = function () {
    var result = new Deck();

    var suits = [Suit.clubs, Suit.diamonds, Suit.hearts, Suit.spades];
    var ranks = [Rank.ace, Rank.two, Rank.three, Rank.four, Rank.five, Rank.six, Rank.seven, Rank.eight, Rank.nine, Rank.ten, Rank.jack, Rank.queen, Rank.king];
    suits.forEach(function (suit) {
        ranks.forEach(function (rank) {
            var card = new Card(suit, rank);
            result.addCard(card);
        });
    });

    return result;
}
    public static Deck CreatePokerDeck()
    {
        Deck result = new Deck();

        foreach (int suit in Enumerable.Range((int)Suit.Clubs, (int)Suit.Spades))
        {
            foreach (int rank in Enumerable.Range((int)Rank.Ace, (int)Rank.King))
            {
                var card = new Card((Suit)suit, (Rank)rank);
                result.AddCard(card);
            }
        }

        return result;
    }
    static createPokerDeck(): Deck {
        var result = new Deck();

        var suits: Array<Suit> = [Suit.clubs, Suit.diamonds, Suit.hearts, Suit.spades];
        var ranks: Array<Rank> = [Rank.ace, Rank.two, Rank.three, Rank.four, Rank.five, Rank.six, Rank.seven, Rank.eight, Rank.nine, Rank.ten, Rank.jack, Rank.queen, Rank.king];
        
        suits.forEach(suit => {
            ranks.forEach(rank => {
                var card = new Card(suit, rank);
                result.addCard(card);
            });
        });

        return result;
    }

Try this in the TypeScript playground.

I would raise a flag about complexity of this kind of implementation with the candidate. You might ask about performance and if there's a better way, particularly for the JavaScript versions, but also somewhat for the C# version. Each of these introduces new method calls which are really unnecessary, because you can get the same values just by doing addition.

Shuffle

Shuffle is my favorite problem of all. There are any number of ways to do it. It tests if candidates know about and understand how to use the random number generator in their language, and also lets you glimpse into reasoning. Almost always, candidates try to swap two random cards somewhere in the deck. The most obvious question to ask, though, is how do you know how many total times to actually perform swaps? You might shuffle 104 times for a 52-card deck, but even with that, there's a reasonable chance you might have never touched a particular card. Not that such an action is unreasonable; a card in a real deck might not change position either. But iterating through every card in a deck and then generating a random number is a sure way to ensure that every card is visited once.

One interesting pivot on this problem is using the JavaScript forEach function on your array, and then swapping. In general, I prefer not to see this; forEach implies an enumeration, and modifying an object being enumerated over is kind of a no-no. JavaScript engines apply a consistent behavior, but C# will barf on it (it's invalid to modify a collection while an enumerator is active on it in C#).

For JavaScript also, the developer needs to have clearly called Math.floor(Math.random() * count). Math.random() generates a double-precision floating point number in the range of [0, 1). Multiplying this value by the length of our array gives us a floating point number in the range of [0, length), but it'll still possibly have a fractional component; calling floor gives an integer in the range of [0, length-1].

Summary

This problem exercises basic problem-solving skills, some algorithms, some bits and bytes, and really focuses on object-oriented design skills. It also happens to be the exact problem I was given during my very first technical screening for a marketing agency in Phoenix.

Next time: Reasoning about linked lists.


4Apr/141

Are you a developer? Come work at Microsoft.

Posted by Rob Paveza

I've been posting about technical interviews, but with Build 2014 going on right now, I wanted to make a point about work.

If you're a developer, you should seriously think about coming and joining us at Microsoft.

Why? For the same reason that our developer-customers should build for Windows and Microsoft. Satya said it best (2:39:05):

You want to build for Windows because we are going to innovate with a challenger mindset.

I can't talk about what we're doing right now, but what I can say is that it's going to be amazing. The stuff that we're working on is going to be very compelling. If you've ever wanted huge challenges to come in and win a market, with a huge playing field (millions to billions) of customers, you should come join us. The problems we solve are big and fun.

So, come do it. If you're interested, leave me a comment and we'll connect offline. Feel free to leave an email; comments get moderated and it won't get crawled.

Tagged as: , , 1 Comment
3Apr/140

The technical interview, part 1: Palindrome

Posted by Rob Paveza

Last time, I talked about what I expect of an interview candidate as a technical job interviewer. This time, we're going to go through an initial question.

Interviewer: Write a function/method/subroutine to determine whether a particular string is a palindrome, i.e., is the same text when reversed as it is forward.

This is a common question for an interview because it allows you to demonstrate basic problem-solving skills and you can also show your interviewer that you know how to dive into the requirements. It requires that you can implement a simple algorithm, have an understanding of how strings work in your particular language, and can work through optimizations of your algorithm. Because the problem itself is so simple, you get a chance to dazzle your interviewer with good programming practices.

Understanding the problem

A palindrome is a string like kayak which you can reverse and end up with the same string. This gives you the naïve implementation:

    IsPalindrome(test)
        let reversed = ReverseString(test)
        return reversed equals test
    end

Most languages will have a baked-in function to reverse a string. So you could do that, but could you do it better?

Interviewer: Tell me about the performance characteristics of that baseline implementation.

You've allocated a new string, and depending on that particular implementation, it could have been costly. But you've got at least an O(n)* memory usage. String equality testing is going to be character-by-character, so that's going to be O(n) execution. So, if you're testing a string that has 2 million characters, the naïve algorithm allocates an additional 2mb string and does (in theory) up to 2 million comparisons.

How can we optimize? Well, let's start with understanding the basic problem again. Let's consider kayak:

k a y a k
0 1 2 3 4

Given this string layout, what would we need to do to go faster?

  1. Compare 0 to 4. Match, continue.
  2. Compare 1 to 3. Match, continue.
  3. Only one uncompared character is remaining, therefore return true.

This can be generalized to an algorithm:

  1. Initialize start and end indices to 0 and length - 1 (or 1 and length for 1-based index programming languages).
  2. Compare characters at the start and end indices. If they don't match, return false (fast exit).
  3. Increment start and decrement end.
  4. If the end index is less than or equal to start, return true. Otherwise, loop back to the step 2.

We now know enough to author a simple method to do this:

function isPalindrome(stringToTest) {
    var start = 0, end = stringToTest.length - 1;
    for (/* already initialized */ ; start < end; start++, end--) {
        if (stringToTest[start] !== stringToTest[end])
            return false;
    }
    // got to the end with no mismatches, implies success
    return true;
}
class Utilities 
{
    public static bool IsPalindrome(string toTest) 
    {
        int start = 0, end = toTest.Length;
        for (/* already initialized */ ; start < end; start++, end--)
        {
            if (toTest[start] != toTest[end])
                return false;
        }
        // got to the end with no mismatches, implies success
        return true;
    }
}
bool isPalindrome(const wchar_t* toTest const) {
    auto len = wcslen(toTest);
    wchar_t* start = const_cast<wchar_t*>(toTest);
    wchar_t* end = start + len - 1;
    for (/* already initialized */ ; start < end; start++, end--) {
        if (*start != *end)
            return false;
    }
    return true;
}

This is a fairly optimal solution.

Interviewer: What about error cases? What kind of error cases exist, and how can you work around them?

In JavaScript, because we don't do compile-time type validation, it's possible for types to mismatch. A caller can pass in a number, an object, undefined, no value, null, a Boolean, etc. Each of these has different odd behaviors; for an Array, for example, the behavior will effectively match how things work with strings. But, for most other values, because there isn't any string coercion, and math is performed directly against the value's length property (which will generally result in NaN), and therefore that will return true. isPalindrome(true) definitely should return false, but it doesn't!

There are a couple of ways to guard against this. You can test the input parameter for its type and fail with a TypeError. You could combine this by attaching the method to the String prototype, which would enable the function to be called against any String object as an instance method.

In C#, if you pass in a null reference, the method will fail with a NullReferenceException on the first dereference of toTest.Length. This is acceptable but likely not ideal; instead, it would be preferable to fail with an ArgumentNullException. You can also show nice API design intuition by making it into an extension method.

If you're authoring in C++, a great question to ask would be the kind of error environment you need to deal with. In COM, for example, you don't want to use structured exception handling, or at least allow SEH exceptions to cross the ABI boundary. Depending on your environment, you may be able to use SEH, but be prepared to author a COM version of the API. Of course, COM also advises a different type system. COM strings tend to be BSTRs, where a null value is equivalent to a zero-length string. (WinRT uses HSTRINGs, which behave similarly to BSTRs).

String.prototype.isPalindrome = function() { // argument removed, it is "this"
    if (typeof this !== 'string' && !(this instanceof String)) // In case of call, apply, or bind
        throw new TypeError('Can only call against a string.');

    var start = 0, end = this.length - 1;
    for (/* already initialized */ ; start < end; start++, end--) {
        if (this[start] !== this[end])
            return false;
    }
    // got to the end with no mismatches, implies success
    return true;
}
static class StringExtensions
{
    public static bool IsPalindrome(this string toTest) 
    {
        if (toTest == null)
            throw new ArgumentNullException("toTest");

        int start = 0, end = toTest.Length;
        for (/* already initialized */ ; start < end; start++, end--)
        {
            if (toTest[start] != toTest[end])
                return false;
        }
        // got to the end with no mismatches, implies success
        return true;
    }
}
// This sample is using WRL and Windows Runtime (because it's the C++ COM library that I know)
// IDL file:
namespace MyApi 
{
    [uuid(...)]
    [version(...)]
    interface IPalindromeTest 
    {
        HRESULT IsPalindrome([in] HSTRING toTest, [out, retval] boolean* result);
    }
}

// header:
using namespace ABI::MyApi;
class PalindromeTest : public RuntimeClass<IPalindromeTest>
{
    InspectableClass(InterfaceName_MyApi_IPalindromeTest, BaseTrust)

public:
    PalindromeTest();
    virtual ~PalindromeTest();
    HRESULT RuntimeClassInitialize();

    IFACEMETHOD(IsPalindrome)(_In_ HSTRING toTest, _Out_ boolean* result);
}

// implementation:
// Other stuff - RuntimeClassInitialize, etc. - goes here
IFACEMETHODIMP PalindromeTest::IsPalindrome(_In_ HSTRING toTest, _Out_ boolean* result)
{
    IfNullReturnError(result, E_POINTER);
    HRESULT hr;
    size_t len;
    const wchar_t* strVal;

    strVal = WindowsGetStringRawBuffer(toTest, &len);
    wchar_t* start = const_cast<wchar_t*>(strVal);
    wchar_t* end = start + len - 1;
    for (/* already initialized */ ; start < end; start++, end--) {
        if (*start != *end) 
        {
            *result = false;
            return S_OK;
        }
    }
    *result = true;
    return S_OK;
}

Interviewer: This is a pretty good solution. What are some of the pitfalls or problems with it? What are some possible variations that you might do?

This is an open-ended question intended to see what you might consider for your implementation and also to gauge what you know and maybe don't know. Possible answers include:

This implementation fails to work with Unicode characters above U+FFFF. JavaScript, modulo ES6, doesn't support characters outside of the UCS-2 range. They can go back and forth to a host which does, but intrinsically, JavaScript didn't understand the idea of surrogate pairs. C++'s wchar_t and C#'s string don't directly support surrogate pairs because the underlying character type is 16-bit. In order to fix the code, you'd need to get the "real" length of the strings (factoring in the code points) and then going code-point-by-code-point instead of index-by-index.

I could implement this function recursively instead of iteratively. Generally, this implementation is better as an iterative function than a recursive function. But recognizing that it's possible, because the algorithm is really about solving progressively simple sub-problems, is a good thing to do. In languages which support tail-call recursion, this can be as well-performing as the iterative implementation.

(function() {
    function isPalindrome(toCheck, startIndex, endIndex) {
        if (endIndex >= startIndex)
            return true;

        if (toCheck[startIndex] !== toCheck[endIndex])
            return false;

        return isPalindrome(toCheck, startIndex + 1, endIndex - 1);
    }

    String.prototype.isPalindrome = function() { 
        if (typeof this !== 'string' && !(this instanceof String)) 
            throw new TypeError('Can only call against a string.');

        return isPalindrome(this, 0, this.length - 1);
    }
})();

Interviewer: Great. How would you validate this implementation?

This gives you a few options for approaches. This problem is simple enough that you could intuit the sets of cases:

  • A null value
  • A zero-length string
  • An odd-length string
  • An even-length string

You might also walk through your code to identify all of the different code paths. Doing so will help you get to the same set of cases.

Summary

If you've talked through all of this, then chances are I already think you're a pretty strong candidate. This isn't a complete list of things I might ask you to talk about, but I'm hoping it's taken 15-20 minutes, and we can talk about more next.

Up next: a deck of cards.


* O(n) notation is a mechanism by which we describe the worst-case performance characteristics of a system. For memory, it's referring to the number of bytes allocated; for CPU utilization, it's the number of times a particular loop operation must be executed. It's generally described as the largest factor in the equation; O(n) is linear time, O(n2) is polynomial time, O(log n) is logarithmic time, etc. This is a simplification, but I'd suggest having a strong grasp of this concept.


2Apr/140

The technical job interview, part 0

Posted by Rob Paveza

I've had the opportunity to be on interview loops for the last six months or so at Microsoft. I had previously done interviews as part of my job at Terralever as well, and at least for the technical part of the job, it hasn't really changed. This post isn't really about interviewing specifically at Microsoft. I'm a Program Manager, but on a programming language team, which means that my job is much more technical than most PM jobs on, for example, Office products. My expectations as a technical interviewer for PM are probably more in line with a developer's job in other parts of the company. As such, I'd also expect that they're in line for other development jobs throughout the industry.

I'd expect the specific problems are going to vary based on the team or the job you're interviewing for, but some problems are good universal fits. In general, I try to ask questions which will fit within the following buckets:

  • Basic problem-solving skills. If I give you a simple problem statement, can you talk through how you would solve the problem and then turn it into code? Can you do it on a whiteboard without a code editor? What level of detail do I need to provide? What levels of detail are you going to ask me for?
  • Performance analysis and trade-offs. While approaching your basic problems, almost always, the problems have multiple possible solutions. I hope you're identifying the alternatives as we go, but if you don't, can you discuss them when I ask you about them?
  • Bits and bytes. Do you understand the basic number operations, endianness, and two's-complement arithmetic? Do you know about specific implications for your target environment (e.g., number representation and optimization in JavaScript has special considerations)? Do you understand why this post is called "Part 0"?
  • Data structures and algorithms. Do you understand LIFO/FIFO, linked lists vs. arrays, hash tables, etc.? If you're a junior candidate and are unfamiliar altogether with the data structures, do you understand what I'm talking about if I explain them to you?
  • Object-oriented design. Can you decide what should be a class, a function, global variables, etc.? Do you know how to represent these kinds of constructs in your language of choice (e.g., prototype inheritance in JavaScript)?
  • Job-specific skills. On my team, I generally ask about JavaScript questions (looking for a PM), but I know C, C++, C#, Java, and JavaScript well, and so generally, I'm interested in asking about fundamental understanding of at least one programming language. For a web app developer, I'm going to likely ask about jQuery, perhaps Angular, Node.js, or other common libraries. But, unless I'm interviewing a senior person who should be able to join the team and immediately contribute, APIs and libraries generally get de-prioritized, because a fundamental understanding of the language is going to make it easy to quickly grok a library.
  • Debugging. What are the tools you could use to debug a problem that might crop up? Do you know the sequence of steps to diagnose a bug that I might have introduced, or that you introduced?
  • Testing. Do you know how to test and validate your code? What are the ranges of inputs you might want to test?
  • How up to date are you? Do you love your trade? Are you watching for ES6 features and specs coming out of the JavaScript language design committee? Do you have personal projects? (This isn't a required category but it generally gives bonus points).

Over the next few posts, I'm going to talk through some common interview problems, what a candidate's answers might be, and then what the interviewer might try to discuss about the answers and questions. This isn't a comprehensive guide, and you shouldn't expect to get these questions if you actually interview with me. The purpose is really to give you the mindset for an interview. What will make you successful? What do you need to know? How can you build up your skills to be ready?

Up next: testing for a palindrome. (Yes, it's super-common).

18Feb/140

When SEO goes way too far

Posted by Rob Paveza

Please remember that my comments are my own and do not necessarily reflect those of my employer.

SEO, or Search Engine Optimization, is a technique in online marketing that deals with driving traffic to your site via search engine rankings. There are two main channels, active and passive, which differ primarily via ad spend (specifically, active SEO involves spending money on ads and passive does not). From there, there are a bunch of different ways to improve your credibility with customers: have a targeted domain name (e.g., MyBusiness.com), have meaningful paths within your domain name (e.g., MyBusiness.com/BusinessUnit/WorkingGroup), ensuring that the words on your site are relevant to your topic, or having other sites about your topic linking to your site (for example, a site about puppies being linked-to by a site about Beagles), which is referred to as organic traffic. I learned a lot about SEO when I worked at Terralever, where as a developer I did a lot of work to implement the SEO designs our marketing team put together. SEO in and of itself isn't a problem; in fact, it's important to allow sites to be found by search engines.

But SEO can be abused. Search engines have rules that detect when website operators are trying to break into their heuristics, and if these rules are violated it can lead to a black-listing of your site or business. One of the most famous occurrences of these was JC Penney in 2010-2011, where Penney had hired an SEO firm to optimize their inbound traffic. The SEO firm in question created thousands of other sites, linking to Penney's main site, and driving the site to the top of Google's rankings. When search engines' crawlers detect inbound links to a site from other sites about the same topic, that's termed an organic link, and it substantially boosts the credibility of the site. Google famously (at least in marketing circles) punished Penney by substantially reducing its ranking (one example was from #1 to #68).

I know a lot about SEO from my old days working in that field. And yet, I was still fooled by this one.

Dylan, our new puppy

Dylan, our new puppy

My wife and I have been talking about adopting a puppy for about a year and a half. I've never raised a puppy, and our other dog, Samson, recently turned four years old. With us hoping to have a human child soon, Meredith thought that if I ever wanted to raise a puppy (for it to still be my dog), we should do it soon. I've wanted to get a Beagle for a long while, and after having been watching local shelters for a Beagle puppy for a long while and rarely if ever seeing one come available, we concluded that we'd need to find a breeder. I'm not generally a huge fan of breeders, but I also don't necessarily feel bad going to one if I think the arrangement will be good. We did some searching, found a site called Washington Beagle Breeders, and found a pup we thought would be a good fit for us. We chatted to one of the reps for a bit, and Dylan sounded like he'd be a good pup for us. And the arrangement with the people from the website seemed pretty cool - a way for breeders to just go through an internet presence and not have to worry about managing a website and all of that on their own. I thought, hey, if I was a breeder, that's a service I'd probably like!

When we were making our final decision, we were missing one crucial piece of information. One piece that was explicitly deceptive about the website.

Dylan wasn't from a breeder in Washington. Dylan was from a breeder outside of St. Louis, Missouri.

By now we were emotionally invested in going forward with Dylan. The breeder's rep informed us that there would be an additional travel fee on top of the base price of the dog, that we wouldn't be able to meet Dylan before the adoption, and that we'd be on the hook for a return fee and a service fee if we decided not to move forward with the adoption. I couldn't imagine we'd want to return the dog, but that put me off. But by now, like I said, we were pretty emotionally invested, and decided that would be okay. I figured it was within the same general measure of distance of flights we usually take - 3-4 hours - and that wouldn't be too bad. We arranged the travel and planned all of the timing, etc. Dylan was scheduled to arrive this afternoon.

This morning, checking the flight status, I found out:

  • Dylan wasn't on a direct flight from STL to SEA, but instead had a connection in Salt Lake City.
  • Although he was scheduled to arrive at SEA at 12:20pm local time, he was dropped off at 10pm the night before in St. Louis for a 6:45am flight out.

If you read up on raising puppies, you'll find out that puppies generally need to go to the restroom every 4-5 hours. You might be lucky enough to have a dog who can sleep through the night at 13 weeks, but you need to let him out. But by my calculations, he was in his crate for at least 15 hours. That meant he slept in his pee and poop for a long while. He's got a lot of energy and can't get out of his crate.

Keeping the dog confined for that long, I'd understand. I think it'd suck, but I get it. But since the dog is unable to control his bowel and bladder for that long, I think it's just rotten.

Never again will I go through an online breeder. We'll only ever go through a local rescue or a local breeder.

I want to show you the specifics. Check out these sites:

washingtonbeaglebreeders.com and beagle.washingtonpuppiesforsale.com

washingtonbeaglebreeders.com and beagle.washingtonpuppiesforsale.com

californiabeaglebreeders.com

californiabeaglebreeders.com

newyorkbeaglebreeders.com

newyorkbeaglebreeders.com

Will I ever do business again with a breeder? Maybe. I don't think breeders themselves are the problem. And I even think a middleman isn't necessarily bad -- like I said, I probably would have been excited to find a broker like this if I were a breeder. If Purebred Breeders (the company really behind all of these sites) was actually based in Washington, I wouldn't have had a problem with them. But the fact that these dogs aren't actually in Washington, or California, or Arizona, or New York - and the fact that the sites work so hard to make it feel like they are (Washington Beagle Breeders' site uses a Washington-based phone number - area code 206) - it just disgusts me.

And I'm disappointed with myself for not having realized that I was being played.

All of that being said, happily, my puppy and our current dog seem to be getting along just splendidly now that they've settled in:

Tagged as: , , No Comments
3Oct/131

I’m going to be on Channel9

Posted by Rob Paveza

I went and hung out with Larry Larson and Andrew Richards from the Channel9 show Defrag Tools today to record an episode! It was way cool, even though I got a little lost heading to the building which was literally right across the street from my own. (In my defense, I was up really early and I thought the building was further down the street).

All said and done, I got a cool Channel9 dude and I got to take a picture in the studio!

I'm @ Channel9 on 10/14/2013

I'm @ Channel9 on 10/14/2013

Be sure to check out Defrag Tools on 10/14 to see it, because I'll be talking about Just My Code in Visual Studio. If you haven't seen the blog I linked to last time, it's definitely worthwhile, but at the very least, you ought to watch the video, because it's AWESOME!

Update: It's live! Check it out!

19Sep/130

Just My Code for JavaScript

Posted by Rob Paveza

Super-excited that we FINALLY get to talk about a new feature that went out in Visual Studio 2013 RC last week. Check out the details in Andrew Hall's blog post on MSDN.

15Mar/130

A Loop for WinJS Promises

Posted by Rob Paveza

I had a co-worker ping me from an internal mailing list recently because he was having trouble reading from a network stream. I dug this out of mothballs from Win8 Consumer Preview:

WinJS.Class.define('Game', function() { /* constructor */ },
    { /* instance prototype */ },
    { /* static members */ 
        LoopWhileTrue: function (context, testCallback, actionReturningPromise, state) {
            /// <summary>Loops an action (that returns a promise) until another callback (that returns a Boolean) indicates that it should no longer continue.</summary>
            return new WinJS.Promise(function (success, error) {
                function evalActContinueLoop() {
                    if (testCallback.call(context, state)) {
                        var innerPromise = actionReturningPromise.call(context, state);
                        innerPromise.then(evalActContinueLoop, function (e) {
                            error(e);
                        });
                    }
                    else {
                        success(state);
                    }
               }
                evalActContinueLoop();
            });
        }
    });

This code was used for managing game state in a card-playing game app that I never finished. Usage might look like this:

var gameplay = Game.LoopWhileTrue(game, game.isGameInPlay, game.playHand, game.state);

gameplay’ then became a Promise that:

  • is fulfilled when the entire game completes (all hands have been played or a terminal score is achieved, based on the value returned by calling game.isGameInPlay(state)).
  • results in an error-fulfillment state if an internal call results in an error.
  • iteratively calls game.playHand(game.state), passing in ‘game’ as the this pointer (important in JS) until it is fulfilled (see 1st bullet).
  • if game.playHand completes synchronously, this method could cause a stack overflow. This can be broken with periodic use of setImmediate.

This method can conveniently be used to emulate a for-loop or a while-loop. It doesn't quite as well emulate a do-while-loop because it checks the terminal condition, but you could write a simple adapter method to always return true for the first call to the method.

11Jan/130

Modern Dilbert Reader v1.3 is in the Store!

Posted by Rob Paveza

I got the new Modern Dilbert Reader uploaded to the Windows App Store. It now has Favorites support as well as Offline Viewing support.

Favorites list

Offline Viewing settings

Get it and enjoy!!!