Question

Uber | OA Coding Questions and Solutions | Set - 9 | 2022

Answer 1

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)

Answer 2

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++) {
                pq.add(new int[] {matrix[i][j], i});
            }
        }

        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);
    }
}