All the prep and things I wrote while trying to get an internship at Microsoft for the summer of 2015.

### Interview prep

Microsoft Interview preparation:

Should I email them telling them about the 50% extra time? No.

What’s going to happen: I’m going to review the chapters on the linked lists and other data structures, and then I’ll consider myself prepared. I’ll do this only once I’ve pretty much completed my math pset.

Q1. Design an algorithm to create a puzzle

Q2. Ordered binary tree

Q3. Palidrome string

Q4. Implement IndexOf() function

Make a program that writes a Binary Search Tree to a file. Now create a program that reads those files and recreates a Binary Search Tree

1. Search element in rotated sorted array. 2 Find top two biggest elements in array. 3. Inorder tree traversal (implement iterator). linked lists

Recall search algorithms.

How would you write a program to show a stack trace given a raw stack dump.

### Data structures - Review & Interview Questions

```Linked Lists:

Singly-linked lists: where each node has some data and a pointer to the next node.

Doubly-linked lists: Where each node has data, and a link to the previous and next node.

Implementing a Stack:

It’s best to use a linked list over a dynamic array because the dynamic array would require 	occasionally resizing which is a time consuming endeavor and its flexibility of indexing doesn’t 	offer any benefit because the stack is FIFO. This depends on the size of the stack though.

Stack would have Push and Pop methods. You would structure it with the head at the top.

Binary Trees:

Binary search tree: left child < it. Right child > it. So farthest right is the smallest, and farthest right is the largest. For searching you’d input a value, and then you’d go through the tree and if your value is less than the current node, you’d go to its left child, similarly for right. Just in a while loop. This operation is O(log_2(n)), where n is the number of nodes! Of course, this is for a balanced BST, if you’re unbalanced, say the worst case is when you only have one child for every node, then you’re O(n) because that’s just a linked list.

Finding a node in a BST can be done very easily recursively: you call on the head, then you say if the node’s value < valueTryingToFind, then call the function again on the currentNode’s right child, and if node’s value > valueTryingToFind then you call the function on the left child to get to items smaller than it. Again, this is O(log_2(n)). Time to print out nodes in sorted order is O(n).

Heaps: binary trees with a twist: both children are less than or equal. So essentially the root is the biggest value. The maximum can be found in constant time, obviously. Insertion/deletion: O(log(n)). Time to print out nodes in sorted order is O(n) (not sure why???).

Traversing Binary Trees: you call a function search(node), and then at the very start you say “if node is null, then return nothing”. Else, you would do whatever you wanted to the node. And then you would call the function on node.left and then node.right. This way it would go through everything, first going down all the lefts, then it would continue recursively going right gradually.

Why I want to work at Microsoft?

Microsoft is in the perfect position to unify the computing experience across all platforms (mobile, desktop, gaming, etc). I think that this is a critical point in that transition, and I’d like to be a part of it. I’ve also experienced what it’s like to work at a small software company, and a large networking company, but not a large software company.

The chance to work with people who have a lot more experience with me, and experience in areas of development that I haven’t been exposed to at all.

Questions for interviewer:

Would you describe the majority of the work that interns/full-times do as collaborative or individual? I experienced a lot of individual work at Cisco which was a drawback.

How open is the company internally? When things aren’t going well, when share in a certain market segment is slipping, is leadership open about that?

Possibly: Would you say that within Microsoft, there exists groups of individuals working independently almost as a startup within Microsoft in order to make a completely new product?
```

### Phone Interview - The Questions that were asked

What the questions ended up being.

What’s the difference between a process and a thread?

What is a Binary Search Tree?

If you’re trying to find an element in the tree, how long does it take? (this question sounded like, if you’re trying to find an element, what is the time compression?)

### Candidate survery

What's your name and what do you go by?

Joe Puccio. I go by Joe.

Have you ever been to Seattle before? What are your thoughts on relocating?

Yes, I have been to Seattle before. I'm totally happy to relocate.

What factors will be key as you decide where to take a position and why are they important?

My major factors are: company atmosphere, the team I'd be working with, how much I'd be contributing, and the fellow interns. What it’s like to work at the company daily is important because it’s going to penetrate everything that I do, that is, I can’t escape it even if all the other factors are ideal. The team I’d be working with is important because I’m really looking for a collaborative experience this summer (my last two internships were mostly individual work), and the team I’m on is going to determine how much I enjoy that experience. How much I’d be contributing is important because it’s going to have an effect on my personal drive to do a perfect job, and I’m only going to want to work somewhere where I’m able to contribute a lot. Fellow interns is important because at my last internship (Cisco), the bright and motivated friends I made in the intern pool significantly added to my enjoyment of the summer.

What type of roles or projects do you envision yourself working on in the next 5 years after school?

I could see myself as a lead developer for a project in a large company or working at almost any position in a startup. But I love making new things on the side, so I'll probably be doing more of that. For instance, in the past two months, I’ve created and released three new projects (which haven’t made it onto my resume yet): 6tracker.com (a site that notifies users when an iPhone 6/6 Plus is available to buy; it’s had 40,000 sign ups since its launch on September 21st), an iOS app that I’ve submitted to the iTunes App Store (pending approval), and estipaper.com (a small tool for students).

Our goal is to get you results as soon as possible. Are you considering any other opportunities? If so, please share them, including deadlines.

I'm in the interview phase with IBM, Palantir, Square, GE, Epic, Weebly, and some others. I'm also considering getting funding for and working on one of my startups over the summer.

Please feel free to share any additional information with us (may include dietary concerns, etc.).

I'm sure you'll get a chance to learn more on Friday :)