Lessons learned from an interview with Microsoft

Three steaks in three nights. Medium-well, medium, and medium. I'll name them Hopeful, Rejected, and Consoled. The names describe the gamut of emotions I felt last weekend. I'm normally an emotionally stable individual but job interviews with anyone tend to psyche me out. Such was the case with my interview for an SDE (Software Development Engineer) Internship with Microsoft's Windows team.

Five interviews, actually. The first one was reminiscent of the interview for my entry-level web development job. It was fairly easy, I hardly had to sell myself, and the technical question was almost trivial. That interview took place in my university's career center. It's just a trial run to see if I was at least somewhat competent. The next four, however, took place at Microsoft's campus in the heart of Redmond, Washington. And what a treat the whole thing is! They pay for round-trip flights, two nights at the Westin, a rental car for the duration of the trip, $75 per day for fine dining (which explains the steaks), and a few other treats. If you've got one of these coming up, I would highly suggest working through these problems, finding a good answer, and seeing if you can find a better one. Each interview lasts 45 minutes so you've got to think quick.

First was kind of a tricky math problem. I was given an array of integers of length n. The values stored in the array were restricted to values from 1 to n-1, inclusive. My task was to come up with a way to find the first duplicate value in the array. A brain dead solution is easy, but can you come up with an algorithm that runs in linear time and does not use a secondary array?

The next one dealt with an interesting linked list. You're given a singly-linked list. Each node actually has two links to a 'next' node, link1 and link2. The two links in a node will not necessarily point to the same node. Think of it as a list of people. One set of links could be the list sorted by height. The other set of links could represent the list sorted by age. The task is to reverse the order of one set of links while preserving the order of the other. (I assume there was more to this problem, but I didn't get very far on the first part so I never heard the second part). Here's a visual for clarification:

Link1 path: A--->B--->C--->D
Link2 path: A--->C--->B--->D


The third one was very similar to the second (thankfully). You have an n-ary tree (a tree where each node has 0 or more child nodes). The tree is stored as a type of linked list. Each node has two links: one to the next 'sibling' node and one to the first child node. My task was to reverse the order of sibling nodes while preserving the parent-child relationship. For example, if you have this tree:

A
|
B------------->C
|              |
D--->E--->F    H--->I

After reversing the order of the siblings, you'd have:

A
|
C-------->B
|         |
I--->H    F--->E--->D

Notice that in the first tree, B's first child is D, but in the second tree, its first child is F. Since we had a few minutes left after I gave a working solution, my interviewer then asked me to write another function which prints out the contents of the tree in order.


The fourth and final one was fairly straightforward. I was given a binary search tree that contains ints. Remember that a binary search tree is one where each node has 0, 1, or 2 child nodes and that the left child (and all of its descendants) has a value that is less than the node and the right child (and all of its descendants) has a value that is greater than the node. I was supposed to determine whether a given binary tree was valid.

I wanted to share these questions with you, not so you can have an unfair advantage (which is why I didn't include any hints), but so that you can know what types of questions to prepare for. Be prepared to come up with a quick solution, make sure it works, then to optimize it as best you can. This was actually my second time going through the whole Microsoft interview process and these questions were fairly similar to those in my first round. I can't speak for all interviews since I only ever interviewed with the Windows team, but I would imagine that questions of the same difficulty would be asked in any SDE interview.

To be fair, I should include other questions they asked me that were of a more personal nature (these aren't word-for-word).

• Why do you want to work at Microsoft?
• What are the most important factors for you when considering a job?
• What has been the most challenging problem/bug you've dealt with in any of your projects at school or work? How did you solve that problem? Be specific!
• Have you ever had to convince someone else to use your plan/approach/strategy/solution over theirs? How did you do that?
• Do you enjoy writing code? Why?
• Do you like debugging?
• What are some personal projects outside of school or work that you've been involved in?
• What's been your favorite class in your college career so far? Why?
• Least favorite class? Why?

Motivation for proper ethics

Anger is a great motivator. Look at almost any video on Youtube and you'll see trolling and put-downs sprinkled amidst a few relevant comments. Couple that with the anonymity of the Internet and people who are otherwise quite friendly say some downright offensive things. However, if you give someone a good reason to do something -- a reason that both offers them success and lets them feel like they've helped out the world in some way -- they will generally do good things. All too often ethics and morals are branded as archaic or old-fashioned. No one who needs to stay afloat in a world that is constantly flooded with new technology wants to be considered old-fashioned. But if you convince people that following a code of ethics will actually benefit them more than following a selfish code of conduct, they will do the right things -- the ethical things -- all on their own. It's a matter of motivation.

Too much gaming

I lived with a gamer once. He spent most of his time hunched over his computer in his dimly-lit room. At night, he would continue playing, only stopping to use the bathroom and eat a frozen burrito or some cold cereal. Now and again, he would burst out in uncontrollable laughter, sometimes in the middle of the night. He chose to socialize virtually in his MMORPG rather than verbally with his roommates. The rest of us would occasionally invite him to go out and do things but he would politely decline. His hygiene had crumbled into ruin to the point where we could tell he'd walked in the room just by inhaling. To this day I regret that there wasn't a more concerted effort to encourage him to change. How does this happen to a 6'8" 18-year-old football player? Gaming was for him, as it is for many, a serious addiction in every sense of the word. It can start off as a healthy way to blow off some steam or spend time with friends. In rare but gradually more frequent cases, real life becomes a mere side effect of being alive; the game is where one's new life continues. Games are not inherently bad but severely skewed priorities are.

What's in store for family history?

Huge advances were made with family history in the 1980's and 1990's with the advent of personal computers. Although the physical copies of past family history work have their own intrinsic value, their purpose was better carried out by the digital revolution. In the late 2000's, the next innovation was FamilySearch Indexing, which was far more inspiring to those without a desire or time to compile a complete family history. Indexing names taps into the power of crowd-sourcing but, more importantly, it helps relieve a healthy amount of guilt from members of the LDS Church (myself included) who had yet to do any family history. What's next for this field? We've only just scratched the surface.

How to get the word out

How do you get the word out? Social media is really the answer in most cases. Take the Orabrush, for example. This ordinary oral hygiene tool with no real glamour has become a household name. Originally its owner considered sending it to the graveyard of advertising: the infomercial. This uninspiring, overenthusiastic and underwhelming format has doomed many great products. Instead of mercilessly beating his cherished invention, he took it to a group of marketing students at Brigham Young University. They leveraged the power of today's great social media sites, Youtube.com, and advertised it as a no-brainer product for young adults. The clever part is that they made something that people not only want to watch, but that they want to share. The rest is history. Once you tug on the world's heart strings or tickle its funny bone, you'll be able to get the word out.

What if indexing could be done by a computer?

This is a question that I've asked myself on a number of occasions. While I do believe that one feels a real sense of accomplishment after finishing another batch of names and that many who participate feel the Spirit of Elijah as they participate in this work, that's not the reason why indexing is still done by humans. The advent of computing has immensely streamlined many of the operations of the Church. Computers have saved countless hours, tons of paper, and millions of dollars. I'm sure that members of the Church before computers felt blessed to perform service by carrying out these sometimes tedious tasks, but that didn't stop the Church from replacing this service with a computer program. That same person can now bless the lives of others with the technology that took his previous service opportunity from him. So why doesn't the same thing happen with indexing name for temple ordinances? To put it simply, computers don't read cursive (yet). I'm sure that when the day comes that they can, members around the world will bless the one who creates the technology and speeds up the work, not curse the one who denied members the opportunity to serve by indexing names.

Get with the program

The beauty of Capitalism is that businesses are rewarded for doing more for their customers. Let's say we have two companies, A and B. Company A has been around for 60 years. During that time, it developed a ground-breaking business model and a brand-new product that revolutionized the industry. It's now grown to become the largest company of its type and nearly dominates the market. Company B started up 3 years ago with the help of 3 employees, a good product, and social media for advertising. Both companies offer a product designed to solve the same problem. Both have their advantages and disadvantages. This is where capitalism shines. What if Company B suddenly takes a huge hold of the market? It doesn't make sense to Company A; B's prices are higher. A closer inspection reveals that B's product is slightly better, and they offer better service to customers. Is this fair? What if Company A loses its grip on the market and, as a result, is in danger of going out of business? After all, it's been around for 60 years. Shouldn't it stay around? The only way to revive Company A is to do more for their customers. If they don't, they lose. However, if they do, everybody wins. Not only is A revived and the customers pleased, but B will be forced to either lower their prices or create an even better product. This cycle will continue in a glorious self-correcting fashion. That's the beauty of Capitalism.

Photo Copyright Laws

An encounter I had with United States Photo copyright laws earlier this year.

Better together

The whole is greater than the sum of its parts. This is clearly evident with the open-source software movement. It's astonishing how much great software comes from a loose network of freelance programmers who do it just because they like to. That's the case with many excellent software packages such as Gimp, Blender 3D, and the various flavors of Linux operating systems. The work that is created with these free tools is spectacular regardless of how much it cost to build them. Open-source software is challenging the current beliefs of big software companies.

Computing: Just for men?

This may sound like a brand of shampoo, in which case one might ask where they can find the feminine variety. They'd have to take two steps to the left where all the shampoo for women can be found. Then they might wonder why a brand of shampoo has such an odd name. But what if there is no alternative for women? Does there need to be another variety for women? Obviously there should be. There are far more varieties of women's shampoo than there are for men. No man (except those who either dearly love their wife or just don't care) would dream of buying and using women's shampoo. The same is true for women. They care about different criteria in their hair products. Shampoo is for everyone but the delicacies have been pushed onto women. Is this because women like shampoo more? Probably not. It's probably more due to the marketing of the product. Which brings us back to computing. Is computing and computer science just for men? Or has it merely been branded by popular culture and stereotypes as a guy thing? Computer science is not just for the guys. If anyone would like to see a stronger feminine presence in this field, it's going to take some considerable re-branding and clever marketing to do so, but it can be done.

War Games

Just because you can doesn't mean you should. We've all heard this phrase before. It rings true in every situation. The 1983 film WarGames embodies this principle. An intelligent slacker teenager figures out how to break into a military computer system using his telephone and dial-up modem. Why does he do this? Not because he doesn't like the military. Not because of some moral (or immoral) obligation. It's just because he can. And he gets in a load of trouble. While the unsecured computer networks of yesteryear have disappeared, the opportunities for fledgling young hackers are far from gone. As with most things digital, doing illegal things with a computer is much easier and far more removed than doing illegal things in person. Who's going to teach tech savvy youth not to do these things? While this question calls for a more general approach to morals, parents, teachers and church leaders would do well to instruct kids about ethics and how it relates to what they do on their computer.

Could you burn me a copy of your Oakley's, please?

No, seriously. I'd like a copy of your sunglasses. I don't want to trek over to the mall and waste my hard-earned, desperately needed cash just so I can shield my eyes in style. No, "Oakley's" is not the newest album by that one band you like; I am referring to the spectacles with which you adorn your face. Sounds ridiculous, no? Well, it's not as ridiculous as it sounds. 17 years ago, when CD's were still in their infancy, one might have scoffed at the idea of loaning out a CD so that a friend could make a copy. The technology, though it undoubtedly existed, was far outside the average consumer's budget. However, in a matter of a few years, 'CD burning' became rampant because of the ever decreasing cost of CD burners. The same thing is happening with 3D printers. Because early models were prohibitively expensive, engineers were driven to invent clever shortcuts using sub-par techniques producing less-than-desirable results. Given just a few years more, the once exorbitant prices of yesteryear were finally able to fall within the realm of possibility for regular people, not just multi-million dollar corporations. What are the repercussions of giving this ability to ordinary people? Is our cherished porcelain doll market being put at risk by this dishonest, dirty technology? Not likely. In fact, the most intriguing result of putting this technology into more hands is the surfacing of new engineering ideas that are simply impossible to create using existing manufacturing methods. 3D printing is paving the way to solving the most difficult manufacturing problems.

(first link takes you to the article)

Why does technology scare us so much?

You've seen it in movies. You've seen in on TV. Perhaps you've read it in books. Technology is dangerous. The smarter society gets, the smarter its computers get. In the mind of a mob, smart computers mean sentient computers. To an uneducated onlooker, it may seem as though new technology actually makes decisions and acts like humans do. While most will agree that beliefs of this variety are few and far between, the fact remains that we hold a special sort of fear and reverence for technology because we've entrusted some of it with the safety of human lives. When glitches occur, as they always do, we seek to find the cause of the glitches and ensure there are no repeats. Where did these unreasonable superstitions come from? They came from overzealous reporters and journalists trying to make their stories stand out from the rest. They came from observers who jumped to conclusions with a limited knowledge of the whole picture. We would do well to take a step back, challenge some of the claims that are widely believed about our gadgets, and apply what we learn toward increased convenience in our daily lives. That's why we advance technology, isn't it?

Censorship on the web

These days, it's becoming a common occurrence to hear about how the Chinese government has blocked Corporation X's website from their country. That's something you come to expect from them. In the United States, it's not quite nearly that bad....but it's slowly going in that direction. That's not to say that we'll ever see the same kind of widespread blocks of certain sites. However, certain companies are doing their best to wipe a couple of sites off the face of the Internet. One in particular is Pirate Bay, a popular website for downloading software, TV shows, Music, Movies, and all sorts of other stuff. Most, if not all, of what they do infringes a myriad of copyright laws (as evidenced by their proudly posting a list of companies that have threatened to take legal action against them). Most of us will agree that using this site is stealing. Hopefully all of us will agree that stealing is bad. Google thinks Pirate Bay is so bad that it's wiped them from their Autocomplete searches. Even though this is not the kind of full-scale censorship we see in other cases, it wreaks of user restriction. Google may do whatever they wish. After all, they're a business. But how far can a company go (or a government, for that matter) before crossing the line? Where is the line between protecting people from others (a sometimes difficult but worthy cause) and protecting them from the freedom of expression (a sometimes difficult and very controversial cause)?

Controlling the Web 2.0

Why is the outcome of the Tienanmen protests of 1989 so different from that of the mourning following the 2008 Sichuan earthquake? Clay Shirky in his TED talk in 2009 describes the immediate response of Chinese citizens to the massive quake. Even before official geological institutions could verify and report on the event, people were talking about the destruction on Twitter. He mentions a past earthquake and the Chinese government's response to it: they failed to acknowledge it for three months, and for 'good' reason. If you're a controlling communist government bent on maintaining your nation's image, why announce to the world the kind of destruction that probably ensued such a catastrophic event? It's clear that the same thing was probably desired for the 2008 quake, but not possible. The different response to the protests that followed is what is intriguing. In 1989, over 100 protesters were killed and 7,000 injured. Although there was an apparent out lash against protesters in 2008, why was the final outcome so drastically different?