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.