Skip to question

Q157FreeSystemVerilog

Return every page at the kth density rank

Difficulty
Medium
Topic
Memory Systems
Language
SV
Interview prompt

Question

Rank distinct page-density values from highest to lowest and return every 4 KiB page whose density equals the kth distinct level. The supported input contains at most 2,147,483,647 populated pages, so the materialized page-record and output queues remain within the signed 32-bit queue size/index domain. This is an input-storage premise; k retains its unsigned 32-bit domain and the stated invalid-rank behavior.

Candidate starting point

Implementation scaffold

typedef struct {
  longint unsigned page;
  int unsigned count;
} page_count_t;

function automatic void kth_dense_pages_4kb(
  input bit [31:0] mem[longint unsigned],
  input int unsigned k,
  output longint unsigned pages_at_rank[$],
  output int unsigned density
);
  int unsigned counts[longint unsigned];
  page_count_t records[$];
  int unsigned levels[$];
  // Implement here: kth_dense_pages_4kb.
endfunction
Reviewed example

Trace one case

Input
page densities={0x1000:3,0x2000:1,0x3000:3,0x4000:2}; k=2
Expected output
[0x4000]

Distinct density ranks are 3, 2, and 1, so the second rank contains only page 0x4000.

What to cover

Requirements

  1. Treat equal densities as one rank.
  2. Use one-based k and return empty for k equal to zero or out of range.
  3. Return all pages at the selected rank.
  4. Sort equal-density outputs by page base.
Continue practicing
Q013 · Memory SystemsFind the densest 4 KiB pageEasyQ223 · Memory SystemsEstimate the densest page in a bounded streamHardPQ266 · Memory SystemsReturn the top K densest pagesMediumP