Some of the questions on the LSAT pre-law school exam are surprisingly similar to logic questions in a technical interview at companies like Microsoft and Google. I was surprised to see many combinatorics problems in LSAT preparation books. Apparently lawyers need a sense of logic to compensate for a lack of a sense of ethics. Here’s an example question. Suppose you have seven engineers. Four are developers — Adams, Baker, Chung, and Dunne — and three are testers — Rolen, Smith, and Taner. In each of two consecutive years exactly two of the developers and two of the testers serve as members of a four-person committee. Each year, one of the members is the chairman. There are five rules:
1.) Baker & Rolen are never on the committee in the same year.
2.) Chung & Smith never serve on the committee in the same year.
3.) Each year, either Dunne or Rolen, but not both, are on the committee.
4.) The chairman in the second year must have been on the committee in the first year.
5.) The chairman in the first year cannot be on the committee in the second year.
Given this information, if Adams is on the committee in a given year, who of the seven engineers cannot be on the committee?
With combinatorial problems like this, you can either list all combinations first and then answer, or go through each potential answer and try and determine if that answer is invalid or not. In this problem you can actually list every combination. So, let’s list all 18 combinations of committee members using just the first letter of their last names. The 18 possible combinations are:
(AB RS), (AB RT), (AB ST), (AC RS), (AC RT), (AC ST), (AD RS), (AD RT), (AD ST), (BC RS), (BC RT), (BC ST), (BD RS), (BD RT), (BD ST), (CD RS), (CD RT), (CD ST)
Rule #1 eliminates any combination that has both B and R, and rule #2 eliminates any combination that has both C and S leaving these 7 combinations:
(AB ST), (AC RT), (AD RS), (AD RT), (AD ST), (BD ST), (CD RT)
Rule # 3 eliminates combinations with both D and R, and also eliminates any combination that doesn’t have a D or an R leaving these 3 combinations:
(AC RT), (AD ST), (BD ST)
So, if Adams (A) is on the committee, then we are looking at only the first two combinations, which means the committee can also have C, D, R, S, and T; and so the committee cannot have Baker.
January 21st, 2012
Here is a question I ran across last week that is one I consider rather difficult. Write a function Foo(int n, int k) which generates all groups of size k from a list of n integers, where order doesn’t matter. For example, Foo(6,3) would generate all possible groupings of size 3 of the numbers 1 through 6:
1 2 3456
1 23 456
1 234 56
1 2345 6
12 3 456
12 34 56
12 345 6
123 4 56
123 45 6
1234 5 6
One solution is to generate the k-1 combinations from [0,n-2] and then use these as indexes to partition the original set of numbers. So, in the example above, imagine that you start with
1 2 3 4 5 6
and index 0 points between the 1 and the 2, index 1 points between the 2 and the 3, and so on, down to index 4 which points between the 5 and the 6. Now the Choose(n-1,k-1) = Choose(5,2) = 10 combinations are:
(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)
and each of these combinations, if interpreted as indexes, partition the original (1,2,3,4,5,6) set:
(0,1) -> 1 2 3456
(0,2) -> 1 23 456
etc.
The implementation details would be a bit tricky; based on my previous experience with such problems, I’d allow 4-8 hours to implement a working solution. Let me point out that I’m not sure that this is an optimal solution. Partition problems are notoriously tricky.
January 14th, 2012
I’ve been around the IT and software development world since the late 1960s and I’m a bit of a skeptic when it comes to whatever the latest and greatest buzz is but I think cloud computing really is one of those once-every-ten-years major paradigm shifts. So, how will the rise of cloud computing affect the job market? The answer is: nobody knows and it depends on what you mean by cloud computing. For the purposes of this blog post I’ll assume the cloud computing is SaaS (software as a service where applications are moved to the cloud as in Gmail and SkyDrive), PaaS (platform as a service where software development is moved to the cloud as in Azure), and IaaS (infrastructure as a service where server machines are moved to the cloud as in EC2). My guess is that the overall number of jobs in IT and software development will decline enormously compared to their current levels. My speculative scenario goes like this: all the tens of thousands of small and medium size companies that currently have a small (say 3 to 7 person) IT department will move most of their in-house functionality to the cloud and eliminate all but one or two positions. The positions left will tend to be at a higher level and broader in scope. The places where job growth will occur will likely be at the mega-companies that provide cloud services like Google, Microsoft, and Amazon. But those positions may well be stratified into high level jobs and low level jobs in much the same way that aircraft companies like Boeing have engineers and assembly workers. (Although there are still lots of middle skill jobs). If I were advising a young person in the field, I’d recommend continuous technical education, learning about project management, and learning about large data (as in SQL and MapReduce). Am I on target with my predictions? I have no idea but I think it’s at least safe to say cloud computing will have a huge impact on IT and software development careers. Maybe.
January 5th, 2012
It is not uncommon for technical interview questions to involve probability and games like Yahtzee. I heard the following interview question recently. Recall that in Yahtzee you have five dice and you get three rolls. After your first two rolls you can save any of the dice you like and roll the others. Here’s one question: What is the probability of getting three of a kind on your first roll? A specific roll with three-fives is 5, 5, 5, X, X which has probability 1/6 * 1/6 * 1/6 * 5/6 * 5/6 = 25/7776. But there are Choose(5,3) = 10 arrangements and 6 different die faces, so the final answer = 10 * 6 * 25/7776 = 1500/7776 which is about 0.19 or 1/5. Now suppose on your first roll you get three of a kind. What is the probability you will eventually get a Yahtzee (all five dice equal)? There are three ways you can (more…)
December 19th, 2011
One of the most common types of job interview questions at companies like Microsoft and Google is for the interviewer to ask you to write some function. And after you’ve answered this, usually by writing code on a whiteboard or piece of paper, a standard follow-up question from the interviewer is, “OK, now how would you test this function?” Let’s walk through a concrete example. Suppose you have written a function with signature int clockAngle(int hour, int minute) which returns the angle formed by the two hands of a clock when at hour and minute. The first thing to address is core function correctness. To do this you need (more…)
December 10th, 2011
I was observing a job interview for a technical position recently and the interviewer gave the candidate an interesting question I had not seen before. The question was along the lines of, “Write a function that accepts an Excel column number and returns the corresponding column name.” The first thing to do, as always, is qualify the question to make sure you understand it. To be honest I didn’t remember how Excel column names worked and I had to open up an Excel spreadsheet to see that they go like this:
A B C . . . Z AA AB AC . . . AZ BA BB BC . . . BZ CA CB CC . . . etc.
So if the input is 1 the function should return “A” (assuming you want to be 1-based and not 0-based) if the input is 29 the return value should be “AC”, if the input is 55 then the return should be “BC” and so on. This is actually a pretty tricky little function to write and there are several approaches you can take. One way is to take the input and compute a quotient and a remainder when divide by 26. The quotient determines the first letter of the column name and the remainder determines the second letter of the column name. For example, suppose the input is 30. If we divide 30 by 26 we get 1 with a remainder of 4. The 1 determines the first letter, A, and the 4 determines the second letter, D, giving “AD”. Unfortunately this simple approach only works work up to 26 * 26 = 676 columns (OK for some versions of Excel) but can be modified to the Excel 2010 maximum number of columns (which I think is 2^14 = 16,384).
December 2nd, 2011
This past week I did an informal survey of jobs sites at companies including Microsoft, Google, Amazon, and also staffing companies like CareerBuilder, Monster, and Volt. My goal was to get an idea of what kinds of technical jobs are open and what kind of skills employers are looking for. Listed below are the top five jobs and associated skills I found, roughly in order by demand. I focused on the Pacific Northwest area but I suspect that the results would be similar in other areas of the U.S.
1. Database developer (SQL)
2. Web developer (ASP.NET, Java/C#, PHP, HTML5, SQL)
3. Cloud developer (Java/C#, SQL, Web technologies)
4. Systems and embedded developers (C++)
5. Test automation engineer (C#/Java, SQL, Web technologies)
The results were not surprising to me. I chat a lot with human resource people who work at Microsoft and Volt and to a lesser extent at Amazon and Google, and I’ve heard many times that finding top technical talent is as hard as it’s ever been. I used to be a college professor and stay in touch with some of my former colleagues in academia and the impression I get is that the number of computer science and technical graduates is down compared to previously and is significantly lower than it needs to be to meet employer demands.
Interestingly, it seemed to me that the number of open positions for traditional IT work is down. I don’t have hard data to back that idea up, but it makes sense if you assume that companies are beginning to move to Infrastructure as a Service (IaaS) in the Cloud.
Maybe the moral is that if you work in the IT and software field, it’s important like it always has been to be continuously upgrading your skills to keep pace with changes.
November 27th, 2011
Last week I was observing a job interview at Microsoft and the interviewer asked the candidate a relatively common interview question, “What is the difference between generics and templates?” Both the newer (C# .NET Framework 2.0 and later) generics and the older (C++ style) templates are mechanisms to parameterize types. For example, both mechanisms allow you to create a collection (such as a Stack) of arbitrary types (such as Employee objects) rather than being forced to create a separate collection type for each data type. But both templates and generics can have alternate meanings so, as usual, you should start answering this interview question by (more…)
November 20th, 2011
A fairly obscure question in job interviews at technical companies like Microsoft is, “What is the difference between STA and MTA?” STA stands for single-threaded apartment model. MTA stands for multi-threaded apartment model. If you are interviewing for a quasi-technical position like Program Manager you would be expected to have an introductory level of knowledge. If you are interviewing for a semi-technical position (say, an application developer or test automation engineer) you would be expected to have a moderate level of knowledge of the differences between STA and MTA. And if you are interviewing for a fully technical position (such as a systems developer) you would be expected to have a deep knowledge of the differences. The STA and MTA models involve what I’ll call client code, such as an application program or software test automation, calling into what I’ll call server code, which is a COM class. STA and MTA are written in the client code and identify to the COM server code whether the client code is single-threaded or multi-threaded. An example in C++ is:
int main()
{
::CoInitializeEx(NULL, COINIT_APARTMENTTHREADED); // STA
// single-threaded C++ code
}
And an example in C# is:
[STAThread]
static void Main(string[] args)
{
// single-threaded C# code here
// that calls a COM object
}
A complete discussion of single- vs. multi- threading apartment models would literally take an entire book. However, in brief, an STA client is single threaded and so the process of calling COM objects can be relatively simple. However, an MTA client requires synchronization mechanisms to manage the COM-calling mechanism.
November 13th, 2011
Recently a software engineer (”Joe”) asked me about an interview question he received in a job interview at Microsoft last week. The question went something like, “What is the difference between == and the Equals() method?” Joe said he checked this question out on the Internet and saw all kinds of conflicting information, so I checked it out too and found Joe was right — there are an absolutely amazing number of completely incorrect answers to this question posted on the Web. The short answer is that the “==” operator returns true if two references are equal, false otherwise. The Equals() method, if implemented in a standard way, returns true if all the fields of one object are the same as the fields in a second object, false otherwise. For example, (more…)
November 7th, 2011
Previous Posts
