Puzzles & notes
Round table serving problem
Problem Statement: Consider a round table with people sitting at fixed positions. Food is distributed starting from a marked position, the "head" of the table. At each step, the person currently serving chooses to give the food to either the person on their immediate left or right, with equal probability. This process continues: any person who receives the food then chooses left or right with equal probability, and so on. A person may be served multiple times during this process.
Your task is to determine at which position to sit in order to maximize the probability of being served last.
Solution
We will formulate the following idea: regardless where we sit, the only way we can be served last if both of ours neighbours are served before us. Once one of our neighbour is served (which side is served first with higher chance depends on our location, but doesn't matter), then what is the probability that the other side is served before us? This 2nd part doesn't depend on our location.
Notation and Observations: Let us fix a position at the round table and define the following events:
- \(L\): the person to the left of us is served before we are.
- \(R\): the person to the right of us is served before we are.
- \(\mathcal{L}\): the left side of the table is served before the right side.
- \(\mathcal{R}\): the right side of the table is served before the left side.
Note that:
- Eventually, one side must be served before us:
$$ \mathbb{P}(L \cup R) = 1 $$
- \(\mathcal{L}\) and \(\mathcal{R}\) are disjoint and cover the whole probability space:
$$ \mathcal{L} \cap \mathcal{R} = \varnothing, \quad \mathcal{L} \cup \mathcal{R} = \Omega $$ $$ \Rightarrow \mathbb{P}(\mathcal{L}) + \mathbb{P}(\mathcal{R}) = 1 $$
- If a side is served before the other side, then the person on that side is served before us:
$$ \mathcal{L} \subseteq L, \quad \mathcal{R} \subseteq R $$
We want to compute the probability that we are served last — that is, both neighbors are served before us:
Note that \(L \cap R = (L \cap \mathcal{R}) \cup (R \cap \mathcal{L})\).
We could reason with a Venn diagram, but let's show the previous statement formally. We decompose both \(L\) and \(R\) using the partition \(\mathcal{L} \cup \mathcal{R} = \Omega\):
Then:
\(\mathcal{L}\) and \(\mathcal{R}\) are disjoint events, so:
Now apply the definition of conditional probability (if \(\mathbb{P}(\mathcal{R}) > 0\) and \(\mathbb{P}(\mathcal{L}) > 0\)):
Note that for symmetry, \(\mathbb{P}(L \mid \mathcal{R}) = \mathbb{P}(R \mid \mathcal{L})\), so we can write:
Then:
Note how \(p\) does not depend on the position we choose at the round table: it is the probability that once the person on the one side is served, the person on the other side is served before us.
Why the logic applies with the conditional probability even when \(\mathbb{P}(\mathcal{R}) > 0\) and \(\mathbb{P}(\mathcal{L}) > 0\)? If the first person served sit on our right, then \(\mathbb{P}(R) = \mathbb{P}(\mathcal{R}) = 1\), and with \(p := \mathbb{P}(L \mid \mathcal{R}) = \mathbb{P}(L)\) the equation \(\mathbb{P}(L \cap R) = p\) still holds. So we can conclude that the probability of being served last is independent of the position we choose at the round table.
Python coding challenges
Coin exchange I
Source code
from typing import List
from functools import lru_cache
class Solution:
def __init__(self):
self.memo = {}
def coinChange2(self, coins: List[int], amount: int) -> int:
# bottom up
# coins 1, 2, 7
# 1 2 3 4 7 8 9 ... 40
# 1 1 2 2 # not this
# [1] [2] [1,2] [2,2] [] # but this
if amount == 0:
return 0
coins = sorted(coins)
largest = coins[-1]
exchngs = [[] for i in range(amount+1)] # at i stores the smallest list of coins summing up to i
for i in range(1,amount+1):
for coin in coins:
last_amount = i-coin
if last_amount < 0:
continue
if last_amount == 0:
exchngs[i] = [coin]
elif len(exchngs[last_amount]) == 0:
continue
if len(exchngs[i]) == 0:
exchngs[i] = exchngs[last_amount] + [coin]
elif len(exchngs[i]) > len(exchngs[last_amount]) + 1:
exchngs[i] = exchngs[last_amount] + [coin]
length = len(exchngs[amount])
if length == 0:
return -1
return length
def coinChange(self, coins: List[int], amount: int) -> int:
# top down
if amount == 0:
return 0
res = self.coinChgLst(coins, amount)
return len(res) if res is not None else -1
def coinChgLst(self, coins: List[int], amount: int) -> List[int]:
if amount in self.memo:
return self.memo[amount]
best = None # shortest list of coins summing up to amount
for coin in coins:
rem = amount-coin
if rem == 0:
self.memo[amount] = [coin]
return [coin]
if rem < 0:
continue
cand = self.coinChgLst(coins, rem)
if cand is None:
continue # no solution for this amount
if best is None or len(best) > len(cand):
best = cand + [coin]
self.memo[amount] = best
return best
Coin exchange II
Source code
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
if amount == 0:
return 1
coins = sorted(coins, reverse=True)
exchngs = [0 for i in range(amount+1)] # at i stores the number of ways to exchange i amount
for coin in coins:
for i in range(1,amount+1):
last_amount = i-coin
if last_amount < 0:
continue
if last_amount == 0:
exchngs[i] += 1
elif exchngs[last_amount] == 0:
continue
exchngs[i] += exchngs[last_amount]
return exchngs[amount]
Source code
class Twitter:
def __init__(self):
self.tweetsByUsers = defaultdict(deque) # userID, tweetID
self.subscripts = defaultdict(set) # who they are subscribed to
self.timer = 0
self.increment = -1 # choose 1 or -1 depending on whether you want to use be memory efficient or time efficient
def postTweet(self, userId: int, tweetId: int) -> None:
self.tweetsByUsers[userId].appendleft(tuple((self.timer, tweetId)))
self.timer += self.increment
if len(self.tweetsByUsers[userId]) > 10:
self.tweetsByUsers[userId].pop()
def getNewsFeed(self, userId: int) -> List[int]:
if self.increment == 1:
ret = [] # heapq with maxsize 10, (time, tweetId)
users = list(self.subscripts[userId]) + [userId]
for user in users:
tweets = self.tweetsByUsers[user]
for tweet in tweets:
if len(ret) >= 10:
heapq.heappushpop(ret, tweet)
else:
heapq.heappush(ret, tweet)
ret = sorted(ret, reverse=True)
ret = [val[1] for val in ret]
return ret
else:
ret = [] # list with maxsize 10, (time, tweetId)
users = list(self.subscripts[userId]) + [userId]
potentialTweets = defaultdict(deque) # copy of tweetsByUsers, but only for the users we are interested in
nominees = [] # heapq with the next most recent tweet from each of the users, storing (time, tweetId, userId)
for user in users:
potentialTweets[user] = self.tweetsByUsers[user].copy()
if potentialTweets[user]:
heapq.heappush(nominees, potentialTweets[user].popleft() + (user,))
while nominees:
_, tweetId, user = heapq.heappop(nominees)
ret.append(tweetId)
if potentialTweets[user]:
heapq.heappush(nominees, potentialTweets[user].popleft() + (user,))
if len(ret) == 10:
break
return ret
def follow(self, followerId: int, followeeId: int) -> None:
self.subscripts[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
self.subscripts[followerId].discard(followeeId)
