0 like 0 dislike
824 views
| 824 views

0 like 0 dislike
Uber
The given questions was asked in the UBER HACKERRANK, OA
Slolt Machine 2.0
Given: n = 4
spins
['712','246','365','312']
We remove the largest value in each row, and add the max to the resutl.
E.g. Take 7, remove from each row 7, 6, 6, 3
now we have
[1, 2]
[2, 4,]
[3, 5]
[1, 2]
take 5, remove from each row 2, 4, 5, 2
[1]
[2]
[3]
[1]
take 3 remove 1, 2, 5, 1
answer is 7 + 5 + 3 = 15, return 15
Example 2:
1 3 7
1 1 5
3 6 4
1 1 5
7 2 4
take 7 and remove max from each row
1 3
1 1
3 4
1 1
2 4
take 4 and remove max from each row
1
1
3
1
2
take 3 and remove max from each row
7 + 3 + 4 = 14, return 14

The given function was

int slotwise(vector history)
by Expert (111,330 points)
0 like 0 dislike

I would use a heap.

• The heap stores an array `[value, row_number]` and is sorted by value.
• We have an array of size n where a[i] tracks number of elements removed from row i
• Maintain a variable that tracks count of maximum values from a single row counted towards result
• Then while the heap is not empty do the following:
• If the top of heap's row == max row counted towards result
• add the value as part of result and update variables
• else pop the element and update variables

The code will make things a bit more clear. It is as follows:

``````public class SlotMachine {
public void solve() {
int[][] matrix = new int[][]{{7,1,2}, {2,4,6}, {3,6,5}, {3,1,2}};
int[][] matrix2 = new int[][] {{1,3,7},{1,1,5},{3,6,4},{1,1,5},{7,2,4}};
printLargestValue(matrix);
printLargestValue(matrix2);
}
private void printLargestValue(int[][] matrix) {
int[] usedRows = new int[matrix.length];
int rowsCountedTowardsResult = 0;
int result = 0;
// [value, row]
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
return b[0] - a[0];
});

for(int i = 0; i<matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
}
}

while(!pq.isEmpty()) {
if(usedRows[pq.peek()[1]] == rowsCountedTowardsResult) {
int[] top = pq.remove();
usedRows[top[1]]++;
result += top[0];
rowsCountedTowardsResult = Math.max(rowsCountedTowardsResult, usedRows[top[1]]);
} else {
int[] top = pq.remove();
usedRows[top[1]]++;
}
}
System.out.println(result);
}
}``````
by Expert (111,330 points)