You and your friend go to a game arcade where you choose to play the lucky pick game. In the game,
there is a square grid and on each block some money is placed on it. When a player chooses a block, the
machine randomly chooses a block from the available neighboring and the chosen block (consider 8
neighborhood). The player is awarded the money that is placed on the block that the machine selects.
Your friend needs help choosing the block.
Your job is to return the block position(s) that will maximize the minimum amount your friend will win
for sure. If there are more than one such block positions, then output must return all these positions.
Input Format
You will be given a single input representing the Grid Description (in the form of string array)
(N rows each containing N numbers separated by '#', each number representing the amount of money
put on that block)
Output Format
You need to return the array of string containing the position(s) of a block choosing which will give the
maximum amount of money which your friend will definitely win.
Sample Test Case 1
Sample Input
3 12#45#33 94#54#23 98#59#27
Sample Output
3#1
Explanation: In the above example, if he selects the block (3,1), then under the best case, he could win is
98 and under the worst case the maximum he could win is 54. In such scenario, the worst case of block
(3,1) gives your friend more money than the worst case of other blocks.
Sample Test Case 2
Sample Input 4
12#45#33#27
94#54#23#53
98#59#27#62
11#51#67#13
Sample Output
1#3
1#4
2#3
2#4
Explanation
Note: If the output array contains multiple strings(block's positions), all the positions must be in the
row-wise traversal order. In Example 2, the output is {1 #3,1#4,2#3,2#4}. If your function is returning an
array that has same elements (block's position) but in the different order, then the output array will be
incorrect.
Function to implement:
public static String[] amount_value(String[] input1){
//implement your logic
}
I cannot think of something better than O(n^2) here. Brute-force scan every block and evaluate the lowest neighbour. The block with the highest lowest neighbor wins. (Build list of candidates if candidate equals current best). Is there something better than O(n^2)?
- prettyGood August 12, 2017