Returning a random subset with length k of N strings while only storing at most k of them
Use reservoir sampling.  This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$.  You always have one string in memory. When you read the first string, you store it in memory.  Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far.  At the end, output whatever is stored in memory. The end result is that each string in the input is equally  likely to be output.  See also Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space for description of this approach (thank you, Juho!).

This extends to arbitrary $k$.  See Wikipedia's description for details.