[Python] Reservoir Sampling Solution
Hello, thanks for the visit. Here is my solution to the problem using Algorithm L for the reservoir-sampling (https://en.wikipedia.org/wiki/Reservoir_sampling).
Hello, thanks for the visit. Here is my solution to the problem using Algorithm L for the reservoir-sampling (https://en.wikipedia.org/wiki/Reservoir_sampling). Once we find the random location for the matrix, we simply check if the location has been visited before. If so, we continue the same process. \n\n```\nclass Solution:\n\n    def __init__(self, m: int, n: int):\n        self.chosenIdx = set()\n        self.m = m\n        self.n = n\n\n    def flip(self) -> List[int]:\n        while True:\n            rscope = 1\n            chosen_row = 0\n            for row in range(self.m):\n                if random.random() < 1 / rscope:\n                    chosen_row = row\n                rscope += 1\n\n            cscope = 1\n            chosen_col = 0\n            for col in range(self.n):\n                if random.random() < 1 / cscope:\n                    chosen_col = col\n                cscope += 1\n            \n            if (chosen_row, chosen_col) not in self.chosenIdx:\n                self.chosenIdx.add((chosen_row, chosen_col))\n                return [chosen_row, chosen_col]\n        \n\n    def reset(self) -> None:\n        self.chosenIdx = set()\n```\n\nThank you for your time! I know that the runtime is quite slow because of many factors (while loop for checking, L-Algorithm, etc..), so I would greatly appreciate any comments on the improvements.
['Python']