FastPrepReservation-station Tag Match
Problems/Reservation-station Tag Match

Reservation-station Tag Match

Xilinx logoXilinx● EasyNEW GRADONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report says to find a matched entry in RS but does not provide entry fields or match rules. This exercise authors valid/tag rows, exact tag equality, lowest-index priority and a -1 miss result. It does not claim the original reservation-station organization was recovered. Approximate source match: 65%.

Model tag matching in a reservation station. Each row of entries is [valid,entryTag], where valid1 means occupied and valid0 means unused. Given tag, return the smallest zero-based index whose row is valid and whose entryTag equals tag. Return -1 when there is no match.

For this exercise, a row has one tag only. Duplicate tags may occur, and the lowest matching index wins. This is a bounded tag-lookup model; it does not model instruction issue, operand wakeup or an entire out-of-order processor.

Function

matchingEntry(entries: int[][], tag: int) → int

Examples

Example 1

entries = [[1,7],[0,7],[1,9]]tag = 7return = 0

Entry0 is valid and has tag7. Entry1 is invalid, and entry2 has a different tag.

Example 2

entries = [[0,4],[1,5]]tag = 4return = -1

The only row with tag4 is invalid, so no entry matches.

Example 3

entries = [[1,3],[1,3]]tag = 3return = 0

Both rows match. The authored priority rule chooses the smallest index,0.

Constraints

  • 0 <= entries.length <= 1000.
  • Every entry has exactly 2 integers.
  • Every entry value is from 0 to 1000000.
  • Each entry is [valid, entryTag], where valid is 0 or 1.
  • 0 <= tag <= 1000000.

More Xilinx problems

  • Count Ones in a 16-bit WordONSITE INTERVIEW · Seen Feb 2019
  • Delete a Given Linked-list NodeONSITE INTERVIEW · Seen Feb 2019
  • Sort with Two-input ComparatorsONSITE INTERVIEW · Seen Feb 2019
All Xilinx interview questionsSee Xilinx hiring insights
Saved
public int matchingEntry(int[][] entries, int tag) {
    return -1;
}
Checking account…