October 18, 2016 9:00 AM
Today’s exercise is an interview question from Amazon:
You are to write a program that reads a stream of characters from the input and returns a random character from the stream. Any character should have an equal probability of being returned. You may only use a single character of storage space; in particular, you may not save multiple characters from the input stream.
Your task is to write a program that solves the Amazon interview task. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
In Python.
from random import randrange from collections import Counter def random_char(seq): result = None for i, c in enumerate(seq, 1): if randrange(i) == 0: result = c return result test = (random_char("abcd") for i in range(1000000)) print(Counter(test).most_common()) # [('a', 250848), ('d', 250520), ('b', 249523), ('c', 249109)]By Paul on October 18, 2016 at 9:32 AM
@Paul. Kudos for such an elegant piece of code! I have my own implementation of this in Julia but I don’t think it’s any better than yours (though it’s probably faster due to the nature of the language). Anyway, I’m glad there are people like you who don’t take the term “impossible” very seriously. Thank you for sharing.
By Zack on October 18, 2016 at 12:41 PM
Doesn’t your solution have higher probabilities to return initial numbers (the question asks for equal likeliness) ? For a 3 character sequence, the probabilities would be 1/2, 2/3, 1/3 for the characters, respectively, right?
By nims11 on October 18, 2016 at 6:29 PM
My bad, the probabilities are indeed equal
By nims11 on October 18, 2016 at 6:35 PM
@Zack. Thank you. You make me blush.
By Paul on October 18, 2016 at 7:28 PM
Solution in Ruby
The tricky part of this one is the condition:
> Only 1 character of storage space; in particular, you may not save multiple characters from the input stream
What is storage? variables? ram? disk?
Anyway here is my solution which might not comply with the storage condition.
def pick_random(stream) stream.chars.uniq.sample end # test input = "an impossible interview question" puts 1_000_000.times .map { pick_random(input) } .group_by(&:itself) .sort_by {|k, v| k } .map {|k, v| "#{k}: #{v.count}" }Output (How many times each letter was picked?)
: 58765
a: 58743
b: 58609
e: 58692
i: 58765
l: 58512
m: 58883
n: 58760
o: 58570
p: 59486
q: 58672
r: 59039
s: 58658
t: 58681
u: 59169
v: 58940
w: 59056
By V on October 19, 2016 at 1:56 AM
Here’s a solution in Java.
There’s a Wikipedia page on Reservoir Sampling: https://en.wikipedia.org/wiki/Reservoir_sampling
import java.util.Random; public class ReservoirSampling { private static Random rng = new Random(); // a stream of characters with unknown length. public static class Stream { // the unknown remaining size of the stream. (stream size starts between 1 and 5000) private int n = rng.nextInt(5000) + 1; private static final String alphabet = "abcdefghijklmnopqrstuvwxyz"; public boolean hasNext() { return n > 0; } // get the next character in the stream (or null if stream is empty) public Character next() { if (n > 0) { --n; return alphabet.charAt(rng.nextInt(alphabet.length())); } else { return null; } } } public static Character sample(Stream stream) { int i = 1; Character c = stream.next(); for (Character next = stream.next(); next != null; next = stream.next()) { ++i; if (rng.nextDouble() < 1.0/i) { c = next; } } return c; } public static void main(String[] args) { System.out.println("Sample: " + sample(new Stream())); } }Output:
By Daniel on October 19, 2016 at 3:56 AM
There was a Praxis exercise on Reservoir Sampling a while back.
By Jussi Piitulainen on October 19, 2016 at 6:47 AM
The proposed solution stores one character, but it also stores one integer counter worth of state. Not sure it meets the requirements of this shibboleth.
By Nyet Ya Koshka on November 16, 2016 at 11:47 PM
The problem statement is ambiguous. Does it mean that the probability of choosing a character in the running text (a token) is equal, or that the probability of choosing a distinct character (a type) is equal? If the latter, I think the problem truly is impossible, because you must know what characters appear or do not appear.
As for the counter problem, I would weasel it as follows: you are allowed to have only one character, but that says nothing about keeping integer state in addition. (Obviously this doesn’t mean keeping the characters in ints!)
(There’s nothing inherently wrong with inherent or impossible interview questions, especially if they get the answerer to ask counter-questions, something interviewees are normally quite unwilling to do, although they need this skill for actual work.)
By John Cowan on July 21, 2020 at 9:14 PM