FastPrepSort with Two-input Comparators
Problems/Sort with Two-input Comparators

Sort with Two-input Comparators

Xilinx logoXilinx● EasyNEW GRADONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report twice asks for sorting4 values, and once mentions6, given a2-input comparer. This practice uses fixed compare-exchange schedules, integer values and an unchanged-input API. No optimal gate-count, HDL interface or synthesis result was reported or is claimed. Approximate source match: 80%.

Sort four or six integer values using only two-input compare-exchange operations. A compare-exchange takes two values and places the smaller first and the larger second. Return a sorted copy, preserving duplicates and leaving the input unchanged.

The sequence of index pairs must depend only on the array length, not on its values. You may conditionally exchange the two values inside a comparator. Do not call a general sorting routine. No minimum comparator count or network-depth objective is required. The software tests check the returned values; this exercise does not synthesize or grade an RTL netlist.

Function

comparatorSort(values: int[]) → int[]

Examples

Example 1

values = [4,1,3,2]return = [1,2,3,4]

The four values are returned in ascending order using two-input compare-exchange operations.

Example 2

values = [6,5,4,3,2,1]return = [1,2,3,4,5,6]

All six occurrences are preserved and sorted.

Example 3

values = [2,2,2,2]return = [2,2,2,2]

Equal values need no exchange and remain four occurrences.

Constraints

  • values.length is either 4 or 6.
  • -2147483648 <= values[i] <= 2147483647.

More Xilinx problems

  • Count Ones in a 16-bit WordONSITE INTERVIEW · Seen Feb 2019
  • Delete a Given Linked-list NodeONSITE INTERVIEW · Seen Feb 2019
  • Reservation-station Tag MatchONSITE INTERVIEW · Seen Feb 2019
All Xilinx interview questionsSee Xilinx hiring insights
Saved
public int[] comparatorSort(int[] values) {
    return new int[0];
}
Checking account…