---
# System prepended metadata

title: Microsoft intern (China) online test

---

# Microsoft intern (China) online test
* The UI was extremely similar to LeetCode 
    * 3 questions; 1.5 hours
    * Screen recording + web-cam recording
    * No magnitude of input data specified
    * Exception: The function signature was read-only and was ugly like 醜得跟?一樣
```
int function_1(int input1, int input2[]){
    // Delete the line below and start writing your code
    throw(some not implemented error i don't remember);
}
```
* I used C++, and yes the only version was c++95 or something :)

## P1
* Given n numbers, put them into groups of k. In each group, all elements are distinct. k divides n. 總之可以整除
* Score := sum( max-min of each group )
* Return the min score
```
int problem1(int n, int k, int numbers[]);
```
### Example:
Input: ```6, 2, {1,1,2,2,3,3} ```
by grouping them into ```{1,2}, {1,3}, {2,3}```
we get ```(2-1)+(3-1)+(3-2) = 4```
Returns: ```4```

## P2
* Given a string (印象中舉例是數字，忘記有沒有specify element範圍),
* Each "shot" removes a consecutive palindrom in the string
* Shoot until there's no letter
* Return the min number of shots
```
int problem2(int strlen, char* cstring);
```
### Example:
Input: ```"124321"```
Step 1. Shoot ```"4"``` -> ```"12321"```
Step 2. Shoot ```"12321"``` -> ```""```
=> 2 shots in total
Returns: ```2```

## P3
There is an island with n cities: from 0 to n-1.
* The first one is the starting point
* The last one is the ending point.

Originally, there are roads connecting the cities, and each of them takes 1 unit of time. Nonetheless, there are different kinds of cities:
* Type I: Normal ones
* Type II: Make you spend 2x units of time for the next 2 roads. 
* Type III: Make you spend 0.5x units of time for the next 2 roads.
* Type IV: You'll die there. Don't go.

Output the path from starting with the minimum time.