CHAPTER 3 · easy · 50 EXERCISES

Card Catalog.

Maps, sets, counting and sorting

Chapter 3 is open. Type when you're ready.

Before you start typing.

A drawer is ordered, but a catalog answers questions about identity. A set remembers whether a reading has appeared. A map associates each key with a value, such as a frequency. With these structures, you can scan once instead of repeatedly searching every earlier item. Check membership before inserting when you need to recognize a new arrival. Increment the stored count when every occurrence matters.

Output order remains a separate requirement. A map's iteration order is not a substitute for the task's numeric ordering. Count first, collect the distinct keys, then sort those keys when requested. For shared drawers, use membership to identify common readings and a set to avoid reporting the same reading repeatedly.

A comparator expresses a complete ordering. Magnitude sorting needs an absolute-value comparison followed by a numeric comparison to settle ties. Specify both so that negative and positive readings with equal magnitude have predictable positions. Grouping by remainder needs care across languages: some produce a negative remainder for negative inputs. Normalize it before selecting a box. Each unit ends with a weighted receipt that reuses your earlier accumulator work. The data structure solves the identity question; the final loop computes the particular receipt printed on your card.

A LITTLE EXAMPLEReadings [-2, 3, -2, 3, 3] give counts 2 for -2 and 3 for 3, so the frequency sequence is [2, 3].

Try your hand.

Frequency files

Count how many times each different number appears in readings. Sort the different numbers from smallest to largest. Put their counts in that order in the result list. For [5, 2, 5], the numbers are 2 and 5, so the result list is [1, 2]. Each card builds this result list, then asks for a different answer. Start with the first card. The last card also uses position numbers that start at 1.

Frequency files: Proof strip

Warm-up

Uses: Frequency maps, lists and loops, receipt rules

easy 2

Frequency files: Total receipt

Variation

Uses: Frequency maps, lists and loops, receipt rules

easy 3

Frequency files: Threshold file

Edge-case trap

Uses: Frequency maps, lists and loops, receipt rules

easy 4

Frequency files: First qualifying slip

Combine

Uses: Frequency maps, lists and loops, receipt rules

easy 5

Frequency files: Peak ticket

Optimize

Uses: Frequency maps, lists and loops, receipt rules

easy 6

Frequency files: Floor ticket

Boundary variation

Uses: Frequency maps, lists and loops, receipt rules

easy 7

Frequency files: Even-key census

Counting variation

Uses: Frequency maps, lists and loops, receipt rules

easy 8

Frequency files: Positive-ink invoice

Filtered variation

Uses: Frequency maps, lists and loops, receipt rules

easy 9

Frequency files: Positive proof strip

Sequence variation

Uses: Frequency maps, lists and loops, receipt rules

easy 10

Frequency files: Boss receipt

Boss · revisit · Level 0: loop accumulators

Uses: Frequency maps, lists and loops, receipt rules

easy

First arrivals

Keep the first copy of each number in readings. Skip any later copies of the same number. Keep the order in which the numbers first appear. For [4, 2, 4, 3, 2], the result list is [4, 2, 3]. Each card builds this result list, then asks for a different answer. Start with the first card. The last card also uses position numbers that start at 1.