11. Weighted Keys
Rank keys by weighted frequency and describe how you would handle collisions and tie scores.
I would first use a dictionary to add all weights for each key. Then I would sort the distinct keys by total weight descending. If two totals are equal, I would sort those keys in ascending ordinal lexicographic order. Dictionary equality checks keep different keys separate even when their hash codes collide. The expected time is O(n + m log m), where m is the number of distinct keys, and the auxiliary space is O(m).
See the Code while reading this explanation.
The input contains pairs of a text key and a numeric weight. The same key can appear more than once. We first add all weights that belong to the same key. Then we rank the distinct keys from the largest total weight to the smallest. When two totals are equal, we order those keys by ascending ordinal lexicographic order. A dictionary is a good fit because it keeps one running total for each key. After aggregation, we only need to sort the distinct dictionary entries.
- Should equal totals use case-sensitive ordinal string ordering?
- Can weights be negative or zero?
- Can the input be empty?
- Can accumulated totals be large enough to require long?
The input is a sequence of pairs. Each pair contains a string key and a numeric weight. The output contains each distinct key once. Keys with larger accumulated weights come first. If two keys have the same accumulated weight, their keys are compared in ascending ordinal lexicographic order.
For the diagram example, the input is (apple, 3), (banana, 2), (apple, 5), (carrot, 4), (banana, 2), and (date, 4). The final output is apple, banana, carrot, date.
Use a Dictionary<string, long> called weightByKey. Each dictionary key is one input key. Its value is the running total of all weights seen for that key.
The central invariant is: after processing any prefix of the input, weightByKey stores the exact accumulated weight for every key seen in that prefix. Repeated keys update the same entry. If two different keys happen to have the same hash bucket, Dictionary still keeps them separate by checking key equality.
Start with an empty dictionary.
Process (apple, 3). Apple is new, so its total becomes 3.
Process (banana, 2). Banana is new, so its total becomes 2.
Process (apple, 5). Apple already has 3, so its total becomes 3 + 5 = 8.
Process (carrot, 4). Carrot is new, so its total becomes 4.
Process (banana, 2). Banana already has 2, so its total becomes 2 + 2 = 4.
Process (date, 4). Date is new, so its total becomes 4.
The final totals are apple = 8, banana = 4, carrot = 4, and date = 4.
Sort the dictionary entries by total weight descending. Apple comes first because 8 is larger than 4. Banana, carrot, and date all have total 4, so the tie rule is used. Ascending ordinal lexicographic order gives banana before carrot before date.
The final ranked result is apple, banana, carrot, date.
The dictionary invariant guarantees that each stored value is the sum of all processed weights for its key. After the complete input has been processed, every stored total is final. Sorting by total descending gives the required weighted ranking. Applying the ordinal key comparison only when totals are equal gives the required tie order. Therefore the returned keys follow both ranking rules.
The method receives IEnumerable<(string Key, long Weight)>. It creates a Dictionary<string, long>. For each pair, it creates a zero total when the key is first seen, then adds the current weight. After aggregation, OrderByDescending sorts entries by total weight. ThenBy with StringComparer.Ordinal resolves equal totals by key. Select keeps only the keys, and ToList returns the ranked list.
Let n be the number of input items and m be the number of distinct keys. Dictionary lookup and insertion are O(1) on average, so aggregation takes O(n) expected time. Sorting m distinct entries costs O(m log m). The total expected time is O(n + m log m). Auxiliary space is O(m).
An empty input returns an empty list. Repeated keys accumulate into one total. Zero and negative totals still follow descending numeric order. Equal totals use ordinal lexicographic ascending order. The code uses long for larger accumulated totals.
Use two phases. First, aggregate every occurrence of the same key into one running total in a Dictionary<string, long>. The invariant is that after each processed item, the dictionary contains the exact accumulated weight seen so far for every key. Repeated keys update their existing total. Hash collisions do not combine different keys because Dictionary uses equality checks to distinguish them. Second, sort the distinct dictionary entries by total weight descending and then by key with StringComparer.Ordinal ascending. Finally, return only the keys.
using System;
using System.Collections.Generic;
using System.Linq;
public static class Program
{
public static List<string> RankByWeightedFrequency(IEnumerable<(string Key, long Weight)> items)
{
// Keep one accumulated total for every distinct key.
Dictionary<string, long> weightByKey = new Dictionary<string, long>();
foreach ((string key, long weight) in items)
{
// Start a new key at zero before adding its first weight.
// Dictionary resolves hash collisions by checking key equality,
// so different keys remain separate entries.
if (!weightByKey.ContainsKey(key))
{
weightByKey[key] = 0L;
}
// Add this occurrence to the running total for the key.
weightByKey[key] += weight;
}
// Sort larger totals first. When totals tie, compare keys
// with ordinal lexicographic ascending order.
List<string> ranked = weightByKey.OrderByDescending(kv => kv.Value)
.ThenBy(kv => kv.Key, StringComparer.Ordinal)
.Select(kv => kv.Key)
.ToList();
// Return each distinct key once in its final ranked position.
return ranked;
}
public static void Main()
{
// Use the exact verified example from the diagram.
(string Key, long Weight)[] input = { ("apple", 3), ("banana", 2), ("apple", 5),
("carrot", 4), ("banana", 2), ("date", 4) };
// Aggregate the weights and rank the distinct keys.
List<string> result = RankByWeightedFrequency(input);
// Expected output: apple, banana, carrot, date
Console.WriteLine(string.Join(", ", result));
}
}Let n be the number of input items and m be the number of distinct keys. Dictionary lookup and insertion are O(1) on average, so building the totals takes O(n) expected time. Sorting the m distinct entries takes O(m log m). Therefore the complete expected time is O(n + m log m). The dictionary and ranked result grow with the number of distinct keys, so the auxiliary space is O(m). Dictionary performance depends on average hash-table behavior, not guaranteed constant-time worst-case operations.
This pattern is useful when repeated keyed records must be combined and then ranked. Examples include weighted activity scores, search-term ranking, user score aggregation, product ranking, and category scoring. The same approach works when many input records share keys but the final output needs one ranked entry per distinct key.
This question tests whether a candidate can aggregate repeated keyed data correctly and then apply a multi-key ranking rule. It checks dictionary usage, repeated-key handling, hash-collision understanding, deterministic tie handling, and correct C# sorting. It also tests whether the candidate can explain the invariant behind the running totals and give accurate complexity that includes both expected hash-table operations and the O(m log m) sorting step.
A common mistake is sorting the original input records before first combining repeated keys. Another is replacing a previous weight instead of adding to the running total. A candidate may also forget the secondary ordering rule and leave equal totals in an unspecified order. Another mistake is assuming a hash collision means two different keys should be combined. Dictionary still compares keys for equality. Finally, claiming O(n) total time is incorrect because sorting the m distinct keys costs O(m log m).
State the two ordering rules before writing code: total weight descending first, then key ascending with StringComparer.Ordinal for equal totals. Then explain that the dictionary produces exactly one accumulated total per distinct key. This makes the correctness argument and the final LINQ ordering easy to verify.









