亞馬遜校招筆試題

　　亞馬遜校招筆試題，就2個題，時間2.5小時

　　Question 1 / 2

　　Question:

　　Given an array with positive integers and another integer for example{7 2 4} 9, you are required to generate an equation, by inserting operator add ("+") and minus ("-") among the array . The left side of equation are consist of the array and the right side of equation is the integer. here the result is 7-2+4=9

　　Rules:

　　Don't include any space in the generated equation.

　　In case there is no way to create the equation, please output "Invalid". For example {1 1} 10, output is "Invalid"

　　The length of the integer array is from 1 to 15( include 1 and 15). If the length is 1, for example the input {7} 7, the output is 7=7

　　There is no operator "+" or "-" in front of the first number:

　　Don't change the order of the numbers. For example: {7 2 4} 9. 7-2+4=9 is correct answer, 4-2+7=9 is wrong answer.

　　There could be multiple input, meaning your function could be called multiple times. Do remember print a new line after the call.

　　Sample Input and Output:

　　Input:

　　1 2 3 4 10

　　1 2 3 4 5

　　Output:

　　1+2+3+4=10

　　Invalid

　　Question 2 / 2

　　Question:

　　There is a 5*5 matrix; the elements in this matrix are different integer from 0 to 24. The elements in this matrix are disordered. 0 is a special element. The upper element, under element, left element and right element of 0 can be exchanged with 0. Such exchange operations are named as ‘U’, ‘D’, ‘L’ and ‘R’.

　　Operation "U" means 0 exchanged with its upper element.

　　Operation "D" means 0 exchanged with its under element.

　　Operation "L" means 0 exchanged with its left element.

　　Operation "R" means 0 exchanged with its right element.

　　For example, the original matrix is

　　[20, 18, 7, 19, 10

　　24, 4, 15, 11, 9

　　13, 0, 22, 12, 14

　　23, 16, 1, 2, 5

　　21, 17, 8, 3, 6]

　　With the operation sequence “URRDDL”, the new matrix will be

　　[20, 18, 7, 19, 10

　　24, 15, 11, 12, 9

　　13, 4, 22, 2, 14

　　23, 16, 0, 1, 5

　　21, 17, 8, 3, 6]

　　Now, we know the original matrix, the matrix after the operations and all the operations made on the original matrix. Please provide the correct sequence for the operations.

　　The input will be the original matrix, the target matrix and an operation sequence with wrong order.

　　If there is a correct sequence for this input, then print the correct sequence. Otherwise, print “None”.

　　Rules and example:

　　The elements in the original matrix are different.

　　The elements in the original matrix are random ordered.

　　The max lenght of operatoins is 15.

　　If "0" is already on the boundary, it is not possible to do further movement. for example, if 0 is in the top row, then there is no more "U".

　　The input will be the original matrix, the target matrix and an operation sequence with wrong order.

　　The output will be a correct operation sequence.

　　In case there is no way to get the target matrix with the input operations, please output “None”

　　Don’t include any space in the generated operation sequence.

　　For examples, the original matrix is