Coding interviews
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
var cache=new ByteCache(5);
Console.WriteLine(cache.Put("a",3)); Console.WriteLine(cache.Put("b",3)); Console.WriteLine(cache.Put("a",2)); Console.WriteLine(cache.Put("b",3));
Console.WriteLine("accounted bytes:"+cache.Used);
sealed class ByteCache(int budget) {
private readonly Dictionary<string,int> sizes=new(StringComparer.Ordinal); public int Used { get; private set; }
public string Put(string key,int bytes) { if(budget<0 || bytes<0) return "invalid"; int old=sizes.GetValueOrDefault(key); long proposed=(long)Used-old+bytes; if(proposed>budget) return "rejected"; sizes[key]=bytes; Used=(int)proposed; return "stored"; }
}
Reveal answer and reasoning
The output lines, in order, are “stored”; “rejected”; “stored”; “stored”; “accounted bytes:5”. Storing a at three consumes three. Adding b at three would require six and is rejected without mutation. Replacing a with two frees one accounted byte, so b at three then fits and Used becomes five. The sequence checks that a rejected proposal leaves the old state intact and that updates are not double-counted.
The rejected b insertion tests nonmutation under pressure, while the a replacement tests subtract-before-add accounting. Reading the output as payload allocation would be wrong because the program never stores byte arrays. It stores only keys and integer metadata, making the model's budget boundary especially explicit.
Expected dictionary operations are constant-time, with O(u) metadata for u keys and key-text storage in addition to the stated payload budget. A zero-byte entry can still consume metadata, so a payload-byte limit alone does not bound entry count or actual process memory. Calling the counter a memory limit would overstate what it measures. It excludes keys, objects, allocator overhead and concurrency.
A compound update also needs synchronization under shared access. The implementation chooses reject rather than eviction, expiration or persistence; those policies are deliberately left for the design discussion.
What a strong answer covers
- Exact output: stored | rejected | stored | stored | accounted bytes:5
- Storing a at three consumes three.
- Calling the counter a memory limit would overstate what it measures.
Common pitfall
Calling the counter a memory limit would overstate what it measures. It excludes keys, objects, allocator overhead and concurrency. A compound update also needs synchronization under shared access. The implementation chooses reject rather than eviction, expiration or persistence; those policies are deliberately left for the design discussion.
Follow-up questions
- Test an oversized replacement of a and verify its previous size remains counted. Add many zero-byte distinct keys and explain why Used stays constant while metadata grows. Hint: a budget is meaningful only relative to the resource actually counted.
- Why can arbitrarily many zero-byte keys defeat a payload-only budget?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.