Ohloh Values MyEPICS at Over $1,000,000
As I have talked about Ohloh.net earlier, I submitted the MyEPICS project to the site for fun. What I got back was that the MyEPICS 2 project was valued at over $1,000,000 dollars and would take approximately 19 person years to develop. Amazing!
Last week (10/19/07) I ended up going on an interview with Microsoft to try and obtain a position as a Software Development Engineer. Microsoft ended up flying me out and putting me into a hotel for the night (and I stayed an extra night to sight see). During my interview, I was going to be talking with the Internet Explorer and Windows Live Experience teams.
My first interview was with a dev lead for Internet Explorer. From him, I got two technical questions.
The first one I got fairly quickly, but it was the second one that gave me some of the biggest trouble. I’ll leave it as an activity to the reader to find out the soulutions.
My second interview was with another development manager. During this interview I mainly touched upon one subject, that being binary tree’s. There were several things that were asked which include:
The non-recursively is what made me think the hardest, and which made me have to add more properties to the structure that I already made.
My third interview was when I finally switched over to interviewing with the Windows Live Experience group. My questions mostly consisted mostly of HR type of questions such as:
I’m never exactly sure what to say, but the classic book How to Win Friends and Infulence People I bet helped me out in these area’s.
My fourth interview was what I thought was my best, but also most nerve wrecking of them all. I first stared out by outlining my MyEPICS projects that I have been working out and the different types of challenges that I encountered. Then I was asked to implement a queue using a stack. What I ended up coming up with was a solution that was O(1) for sequential push/pop’s, but O(n) for all other push/pop’s. At the end of the interview, I was made aware that there is a solution which is mostly O(1) for push/pops, not for just sequential ones. After finding the answer, I realized that I was actually quite close to the solution, only a minor detail off. At the end of the interview, one of the questions I asked was what he thought of how well I did. When he replied, it was quite awakening! He noticed quite a few errors (albeit small errors, but errors none the less), which abruptly I thought there was NO WAY I was going to get an offer. After all, Microsoft only hires the best and the brightest, right?
So at around 4:15pm I finally headed to my last interview. It was with a VP of the Windows Live Experience group. At the beginning of the interview, I was asked to tell him about one of my school projects. I decided to talk about my Rubix Cube Project. After talking to him about it for about 10 minutes, he finally decided to inform me that I was going to be given an offer within his group!
After hearing this, I was extremely excited and overwhelmed. After I thought I was for sure not going to be given a position, they finally ended up offering me one, and on the same day of my interview! After he gave me the offer, we talked about a bunch of the things that the Windows Live Experience team is doing, and some of the things that I would be able to contribute to.
So the things that you should be familiar with are the following:
For the data structures, you should know how to insert, delete, and search for each given one, and you should know the order of complexity for each one.
Even if you don’t normally eat breakfast (like myself), you will be glad that you did, but you probably won’t have a lot of time at lunch to scarf down a 4 course meal (although their cafeteria rocks).
Related to an earlier post I believe one of the things that made me stand out was about how excited I am about technology and all of the different ways that I can help change the world. If you aren’t passionate about something you are doing, then why are you in the field? If you do have something that you are passionate about, find a way to talk about it in your interview. Every time someone asks you “so, tell me a little about yourself”, find a way to put it into that conversation.
I know that this is easier to say than to do, but really, don’t dress up if you don’t like to. Dress how you want to (within reason i.e. don’t wear a see through shirt). I felt that I was really relaxed this time compared to last time I interviewed with Microsoft because I knew that if things didn’t go through, I had another company that had a great offer.
Go look at reverse interviewing and ask them some questions. This will definitely help out! If you get stuck in a technical problem, ask a question, they will most likely be able to help you out!
So I have been doing some more Gnary Queries for MyEPICS.
We have a table called TeamChoice that has 3 columns, userid, teamid, and choice. These represent a person’s 5 choices that they make when registering for EPICS. There is one special row for each person. If the person is not assigned to a team, they are given a choice=0 with their current team choice. So with 5 team choices, each user has 6 rows in the database.
What I wanted to do is find all the students who are currently in their first team’s bucket. So that means that for each user, I wanted to get the teamid where choice=0, and compare it to where choice=1. If they are the same teamid, I wanted to return the result. This probably could be accomplished by some script, but a database should be able to give me the results w/o any scripting.
The way to accomplish this is through subqueries. I realized that I am essentially querying against two tables, then doing a join on the userid. The first table all the records for students and their first choice, the second table is the records for students and their current choice. If I then join the two tables together on their userid, then I will have what their first choice is, and their current choice. All I need to do next is add a where clause that makes sure that I only get records with the two results are the same and it’s over.
SELECT User.username FROM ( SELECT TeamChoice. * FROM User INNER JOIN TeamChoice ON User.id = TeamChoice.userid WHERE TeamChoice.choice =1 ) AS firstchoice INNER JOIN ( SELECT TeamChoice. * FROM User INNER JOIN TeamChoice ON User.id = TeamChoice.userid WHERE TeamChoice.choice =0 ) AS currentchoice ON currentchoice.userid = firstchoice.userid INNER JOIN User ON User.id = currentchoice.userid WHERE firstchoice.teamid = currentchoice.teamid
Today I finished up some of the coding for the my Rubix Cube project using Direct X and LINQ. Luke Hoersten and Nate Hobbs were my partners in developing the program. All of us worked on coming up with designing a sufficient data structure. I worked on implementing the data structure and the user interface / Direct X stuff. Luke focused on refactoring the code, and coming up with parts of the solving algorithm. Nate worked on parts of the solving algorithm.
I have outlined some problems we had while developing the application and also some design decisions that were made to include LINQ. The way our program solves it is that it goes about it the way that a human would.
The program starts with trying to solve the bottom layer, then solve the middle layer, then finally the top layer. Luke would be able to give a much better explanation of how it worked. It was suggested by our professor that we create a tree by attempting every move, then for every move try every move, etc… This we thought would not be a great way to solve it for two reasons. The first being that there are 18 possible moves to make on a cube, and if you want to try and go n levels deep, it would have to compute 18n states. Not only that, but it would have to store every state, score them, then take the path with the best score. To go 6 levels deep, you need to compute 34 million different states, for 7 levels deep, you need to compute 612 million states. Computers are good, but they aren’t that good.
This would not be completely terrible, if you had a smart heuristic for scoring. If every time you computed every one of those states, you were guaranteed to get closer to the solution, then you would only be spending time solving it, and time a computer has. The heuristic that was presented was to find proximity of where a block is to where it should be. This is not the greatest either because what happens when you are almost finished solving it, and you have only one or two cubes out of place (or oriented wrong). You have to end up messing up your cube really bad in order to solve it, and if you’re algorithm doesn’t go deep enough, you won’t find your solution because your current state will always be better than where you are going.
Basically, here is the outline of the program:
Block.cs - A tiny block within the rubix cube. The rubix cube contains 27 of these blocks.
Cube.cs - The cube structure, contains helper functions to orient and move sides of the cube.
Solver.cs - The class that solves the rubix cube.
UI.cs - Handles the DirectX and drawing of the rubix cube.
We haven’t formally licensed the program, but I’m sure Luke and Nate wouldn’t mind if we say it’s GPL’d. Basically give us credit for whatever you do with it and don’t sell it.
URL: Rubix Cube in C# using LINQ
Alternatively, you can also check out the Mercurial sources at: Luke’s Mercurial Sources
Let me first prefix by saying I know Gutsy Gibbon is in beta. So now that we have that out of the way, I have recently upgraded my Ubuntu laptop from Fiesty Fawn to Gutsy Gibbon. For the most part, I am pleased with it, except for a few items. Most of my problems relate to Gnome, X, and ATI drivers.
When I first updated, I got terrible vertical lines on the left and middle of my screen. These were about one inch long and rand the whole length of my screen. After a few hours of messing around with my xorg.conf file, I finally realized that it was not a problem with X, but rather an ATI driver problem. I downgraded my driver by downloading the latest drivers from Feisty Fawn. These seemed to fix the problem. I then started to incrementally upgrade my drivers to xserver-xorg-video-ati_6.7.193-1ubuntu1 which happened to work well. After buzzing around on Launchpad, I noticed Bug #150361. In the details, a developer noted a new version of the drivers (6.7.195-1ubuntu2). I tested these out and they fixed the issue.
Now what happens is whenever I try to play Warcraft 3, randomly the game crashes and the terminal spits out: X connection to :0.0 broken (explicit kill or server shutdown). I can only assume that this has to do with an update to X, which I will probably have to spend some time trying to find out what happened :(. Thus is the life of a beta tester!
Job Hunting and How to be Recognized
Over the past two weeks I have been searching for a job and have come across some amazing opportunities. I have been extended an offer by one of these companies, and it seems that after this initial offer, about 1/2 a dozen more companies have contacted me to interview with them. I was really excited to hear my first offer and I am extremely pleased with it. I am very grateful that the company has given me a lot of time to think about the offer and allows me to get a good feel of what other companies can offer.
When I told my adviser about the offer, she was really excited for me. One of the first questions that she had asked me is what I felt made me stand out as opposed to other candidates. I have given this a lot of really deep thought in the past and I feel that if I had to pick one trait of mine that I have that gets me recognized, it’s that I get really passionate about my side projects. My one project that I have worked on over the past three years I am really proud of and feel that I have matured and learned a lot through it. Whenever I start to talk about the project, the challenges that I have faced and the skills that I have learned, I get extremely excited and it really shows. I get the other people excited about the project which in turn gets them excited about me.