Sunday, March 28, 2010

A new language

Why, oh why, would I curse the world with another programming language? The answer is my typical, "Why not?". More seriously, there are minor deficiencies that I would like to address in the modern mainstream languages. The language I will design will be an incremental improvement over what we currently have. I don't expect it to gain much traction, but it should be enjoyable to program in and it will make for a nice side project.

Here are the major things I wish to have in my language
1. Type inferencing
2. Mutable/Immutable variables - you should be able to specify if a variable is mutable or immutable. By default, local variables are mutable. Non local variables (member variables and static variables) are by default immutable.
3. Non-nullable types - By default all types are non-nullable. You can wrap the type in a Nullable<T> and use the Nullable<T>.Null object to represent null.
4. Generic types - types can be generic.
5. "Duck" interfaces - types can be cast to an interface that they don't implement so long as they implement the correct functions. It must be an explicit cast (unless the interface is unnamed), but the cast will succeed.
6. Unnamed interfaces - When defining a generic function, you can specify an interface that the parameter must implement. The incoming object will be implicitly cast to this unnamed interface.
For example:
int f<T implements { void foo(); }>(T incoming)
7. immutable methods - methods are, by default, immutable. They can not change any of the mutable or immutable members. A method may be specified as mutable, but mutable methods may not be called on immutable objects.
8. Metaprogramming support - Compile time support for metaprogramming should come from a few different sources. First, a standard AST will be provided that can be manipulated through annotation. Basically, an annotation is like a macro that takes a statement and transforms the AST into a different statement. For example, you could write a "memoize" functional annotation that accepts a function declaration and replaces it with a different declaration that is memoized. In addition, metaprogramming can come through compiler event hooks such as "onInheritance", "onCast", "onDeclaration", etc...
9. Unit test support - I'm not yet sure what this will end up looking like, but I do plan on having the ability to write short, inline unit tests at the point of method declaration. It will act as both a user guide as well as a documented test.
10. No "new" keyword - I have never understood the point of the "new" keyword in Java and C#. Therefore, it is gone.
11. No more try - I really hate the try/catch thing. In The Design and Evolution of C++, Bjarne writes about how he had a version without try, but it was confusing. I think it is time to resurrect his experiments. I'm not yet sure of the final form, but I'm sure it will be tryless.
12. Inheritance is deprecated - Other than interfacing with other languages, there should be no need or desire for inheritance. Much of what it was designed to accomplish can be done better through syntax macros and composition. Inheritance will be kept for compatibility with Java/C#/etc..., but its use in native libraries will be deprecated.

Ok, that's 12 things that I see for my language. I don't have a name for it yet, but will accept any suggestions :) I plan to target the .net runtime at first, but the JVM should be a target as well. Comments are welcome.

Friday, March 19, 2010

Passing the Microsoft Interview

As you know, I work for Microsoft - specifically on the team, more specifically on the core core relevance team (yes, that's two cores...don't ask). Even more specifically on the anchor team in the core core relevance team of in Microsoft. Wow, that's a mouthful.

Anyway, bing is hiring and that means I'm interviewing a lot these days. I'm doing at least one interview every other week, sometimes more. In addition, not many people are passing. So, to help everyone out, I thought I would put together a list of tips to help you pass the Microsoft Interview.

Tip #1: Know your stuff

Yeah, easier said than done. However, there are a number of resources out there that can help you. I've listed them in a previous blog post, so study up and have a good understanding of data structures, algorithms, and Big O notation before getting here.

Tip #2: Understand the problem

A lot of people encourage you to ask lots of clarifying questions. I think that is good practice and would also encourage you to do it. In addition, I think you should also spend quite a bit of time at the beginning to list out examples, both positive and negative.
Let's use a concrete example. One question that I see posted all over the web is to write a function to take a string as input and reverse the order of the words in the string. So, for example, "Hello World" would get reversed to "World Hello".
The first thing you should do is ask clarifying questions. Here are some examples:
1) Should I reverse the string in place, or create a new string?
2) What is the return value for the empty string?
3) How should a null pointer be handled?
4) What constitutes a word separator?
5) ASCII or Unicode?
6) How should punctuation at the end of the string be handled?
7) What about capitalization?
8) Is it a c style string or are embedded nulls allowed?

Now that you have fleshed out the problem, the next thing to do is think of some example inputs and see what the outputs would be. I would think of this in a tabular format with input on the left and output on the right

nullassertion failure
"Hello world""world Hello"
"Hello from Microsoft""Microsoft from Hello"

There may be more examples depending on the answer to the clarifying questions, but these would be the minimum examples necessary. Go through each example with your interviewer and make sure he or she agrees with your mapping function.

Tip #3: Describe the algorithm

After you have created your examples, but before you start to code, describe, in English, the algorithm you have devised. First, this helps you to think about the algorithm before you code it and second it gives your interviewer a chance to hint at the right solution if you missed it. If, instead, you immediately start coding a poorly performing algorithm, you give your interviewer no choice but to sit idly by while you waste his time coding something he knows won't work. If you, instead, discuss the algorithm with the interviewer, it gives him or her the chance to point you in the right direction and lets you write code that the interviewer wants to see.

In our word reversal example, you might start by describing an algorithm whereby you find the first space and the last space and then swap the words and repeat until the spaces are the same. The interviewer might ask you about the complexity of this approach and then ask if there is a less expensive algorithm. Doing things in this order makes sure that you are coding the algorithm the interviewer wants to see.

Tip #4: Don't mention a naive algorithm to fill time

The interviewer has asked you a difficult question. You're not sure of the correct way to solve it. Don't just mention the first, most naive, solution that pops into your head. If you think your first solution is a good one, then by all means mention it, but if you know it sucks and is O(n!) or some such nonsense, then stop, think, and come up with something better. By giving a poor solution to begin with you are just giving the interviewer a reason to reject you. You don't have to get the right solution to begin with, just make sure it's not horrible.

Tip #5: When coding, make sure you check your boundary conditions

Nothing sets me off more than when someone forgets a null check or a boundary condition check. This is just Engineering 101 and is critical for a system such as bing. If you can't be bothered to check for null in all the right situations, then don't even apply. Sure, everyone makes mistakes, but in the interview keep null checks on the top of your mind.

Tip #6: After coding, run through your examples and make sure your code works

I've seen too many people write code on the whiteboard, spend 5 seconds looking at it, and then say "Yes, that looks good." There is NO way you have tested it in your head after 5 seconds. Even if it is correct, how do you know? The best thing to do is to use your examples that you generated to walk through your code. You might discover, for instance, that you assumed there would always be a space, when there might not. This gives you a chance to correct your own mistakes without forcing the interviewer to intervene.

Tip #7: Ask questions about the interviewer

This is just good psychology. Make the interviewer feel important by spending a few minutes at the end asking about the interviewer's team and work. The benefit to you is that you get to hear about the day to day activities and make sure they sound interesting. The benefit to the interviewer is that he or she gets to talk about his or her exciting projects. This leaves the interviewer with a good feeling leaving the interview, which is always a good thing. So, the next time you are stuck without a question, ask the interviewer to tell you about a recent project - and hopefully it excites you both!

There you have it, 7 tips on getting through a Microsoft interview. Of course, I honed in on coding, but many of the same ideas apply to the design based interview questions, as well. Regardless, be prepared, be confident, and most of all, have fun!