I applied through Microsoft's website and received a phone call detailing the process.

First Interview - Technical: The atmosphere was great. After I introduced myself and learned about the position, I was asked a few questions:

1. Find the first node where two linked lists are merging. The solution should be O(n) and the lists have no cycles. Answer: Run through each list twice to find their sizes. The difference between the larger and smaller size gives you the offset. Advance the pointer on the longer list by this difference, then move both pointers in sync until they are equal.

2. Print and transfer a Binary Search Tree (BST) between two computers. Answer: Use a delimiter and print in order. Read the file node, then the left child. Every time you see the delimiter, go up one level, print the right child, and then all of its left children.

3. Write code for an ATM system. Then, address what happens when two ATMs are accessed simultaneously (sync with locks).

Second Interview - Technical: Again, after introducing myself and learning more about the position, I was asked to go to the whiteboard and design code for a Domino game system. I created the classes for the board and main methods, and then was asked to implement a few methods.

Third Interview - HR: This was very easy and ordinary. Questions included why I wanted to work for Microsoft, what I was looking for, and what my current manager would say about me.

Fourth Interview - AA Interview: I failed here. This is the last step before receiving a proposal. We started with me discussing my background and former projects from my current job (I couldn't share much due to confidential information). We also talked about a project I completed during my degree. For an unknown reason, the interviewer began asking strange questions, such as how much memory an integer uses. I stated (2^32-1), and then he asked how much memory int[3000][3000] would use. I wrote down the equation, and he then asked me to convert it to MB. I didn't remember the exact numbers, and I started to feel a bad premonition. He then asked me to provide the runtime complexity of merge sort, which I recalled as O(nlogn), but he did not seem impressed.

Four days later, I received a call informing me that I was not a fit for this position. It felt personal, but there was not much I could do about it.

How much memory is int[3000][3000] in bytes and then in MBs?

Should this size of memory be allocated or static?