第 29 / 31 页
非代码面试题
显示 20 / 612 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
5927Minimize the Expected RankThree items arrive in random order; after each you learn its rank relative to those seen so far and must accept or reject irrevocably (the last is forced). Instead of trying to get the single best, you want to minimize the expected absolute rank of the item you finally accept (rank 1 = best, rank 3 = worst). Find the optimal policy and the minimum achievable expected rank.概率中等数值题未尝试免费5928Two Hiring AttemptsFour candidates arrive in random order with only relative ranks observable. You are allowed to make TWO irrevocable picks during the stream (you point at a candidate, that candidate is chosen, then later you may point at one more); you win if AT LEAST ONE of your two chosen candidates is the overall best. Choices are made online with no recall. What is the optimal strategy and the probability of winning?概率困难数值题未尝试面试订阅5929Pay-Per-Look With RecallYou may sample as many independent Uniform(0,1) values as you like, paying a cost c per sample. Recall is allowed, so at any time you may stop and collect the maximum value seen so far. With c = 0.125, find the optimal stopping rule (the reservation level r above which you stop) and the expected net payoff (max value collected minus total sampling cost).概率中等数值题未尝试免费5930Why Full Information Beats RanksTwo candidates have qualities drawn iid from a KNOWN Uniform(0,1) distribution, revealed as actual numerical values one at a time; you must accept one (reject-the-first forces the second). You win only if you accept the candidate with the higher quality. Compare the best win probability achievable by a full-information policy that uses the numerical value of candidate 1 against the best win probability of a rank-only policy that sees only relative order. Which is larger and by how much?概率简单derivation未尝试免费5932Catch the Last SuccessFive deals appear in sequence. Independently, each deal turns out to be 'live' with probability 0.2 (and 'dead' otherwise); you learn live/dead immediately when the deal appears and must accept or pass irrevocably with no recall. You win precisely if you accept the LAST live deal of the five. Using the odds-algorithm logic for such problems (sum the odds r i = p i/(1-p i) from the end until the running total first reaches 1, and start accepting any live deal from that index onward), find the optimal stopping index and your probability of winning.概率困难数值题未尝试面试订阅5933The Postdoc Problem (Pick Second-Best)Four applicants of distinct unknown qualities arrive in uniformly random order; after each you learn only its rank relative to those seen so far and must irrevocably accept or reject (if you reach the last you must take it). A famous twist: you win only if the applicant you accept is the SECOND-best of all four (the very best is taken by a rival institution, so picking the best is a loss). Find the optimal policy and the maximum probability of landing exactly the second-best.概率困难数值题未尝试面试订阅5934Sultan's Dowry with Five SuitorsA sultan offers a vizier the hand of one of 5 daughters, presented one at a time in uniformly random order. After meeting a daughter, the vizier learns only how she ranks (by dowry) relative to those already seen and must immediately and irrevocably accept or send her away; if he reaches the last he must take her. He wins only by choosing the single highest dowry. Among all 'skip the first r, then take the first daughter who beats every earlier one' rules, find the optimal r and the exact probability of winning.概率中等数值题未尝试免费5935Hiring With an Interview CostThree candidates of distinct unknown qualities arrive in uniformly random order; each candidate must be interviewed (in order) before you can judge their relative rank, and conducting each interview costs 0.05 utility. After interviewing a candidate you immediately and irrevocably hire or reject (if you reach the third you must hire). You receive payoff 1 if you hire the overall best candidate and 0 otherwise, minus the total interview cost incurred. Among the threshold rules 'reject the first r interviewed, then hire the first later record', find the optimal r and the resulting expected net payoff.概率中等数值题未尝试免费5937Reservation Wage With Exponential OffersJob offers arrive sequentially and independently, each an Exponential random variable with rate 1 (mean 1). After each offer you accept it (and stop) or reject it forever and pay a search cost c = 0.2 to see the next; there is no deadline. Find the optimal stationary reservation level a above which you accept, and the expected wage you end up accepting under that policy.概率中等数值题未尝试免费5939Secretary Selection When Ties Are PossibleThree items arrive in uniformly random order. Their qualities are NOT all distinct: two of them have quality 2 (tied for best) and one has quality 1. After each item you observe its quality relative to those seen so far, reported as 'higher', 'tied', or 'lower' (so a tie is visible). You accept irrevocably or reject (the last is forced). You want to maximize the expected quality of the item you accept. Find the optimal policy and the maximum expected quality, and explain how the possibility of an observed tie changes what you can guarantee.概率中等数值题未尝试免费5940Secretary With an Unknown Number of CandidatesCandidates arrive one at a time in uniformly random order, but the TOTAL number N is itself random: N = 2 with probability 1/2 and N = 3 with probability 1/2, and you do not learn N in advance. After each arriving candidate you observe its rank relative to those seen so far and must irrevocably accept or pass; once the stream ends, if you never accepted you lose. You win only if the candidate you accept is the overall best of all N who arrived. Find the policy that maximizes the win probability and that probability.概率困难数值题未尝试面试订阅5941The 1/e Law of Best ChoiceIn the classic secretary problem with n candidates (relative ranks only, irrevocable choices), the look-then-leap rule observes the first r candidates without choosing and then accepts the first later candidate who beats all seen so far. For large n, write r = t*n and derive the limiting win probability as a function of the skip fraction t in (0,1). Then find the t that maximizes it and the resulting optimal asymptotic probability of selecting the single best candidate.概率中等derivation未尝试免费5945Two of EverythingA machine outputs one of 3 equally likely tokens per play, independent across plays. What is the expected number of plays until you hold at least TWO copies of each of the 3 token types?概率困难数值题未尝试面试订阅5947Two Stickers to GoYou are collecting 6 equally likely sticker types (independent packs). You currently hold exactly 4 distinct types. What is the expected number of ADDITIONAL packs needed to complete the set of 6?概率简单数值题未尝试免费5955Buy Random or Buy the Missing OneYou need all 5 types and currently hold 4 distinct types (exactly one type missing). Each round you may either (a) buy a random coupon for 1 (uniform over all 5 types), or (b) directly buy your missing type from a reseller for 5. Acting optimally to minimize expected total future cost, what is your minimum expected cost to complete the set?概率中等数值题未尝试免费5960Every Bin Gets a PairBalls are dropped one at a time, each independently into one of 2 equally likely bins. What is the expected number of balls dropped until EVERY bin contains at least 2 balls?概率中等数值题未尝试免费5962Time to Climb One Step (Biased Walk)A walk starts at 0 and each step moves +1 with probability 2/3 and -1 with probability 1/3. Let T be the first time it reaches +1. Find E[T].概率中等数值题未尝试免费5963Wald's Identity from Optional StoppingLet X 1,X 2,... be i.i.d. with mean 4, and let N be a stopping time (with respect to the X's) with E[N]=10. Using the martingale M n = sum i<=n X i - 4n and optional stopping, find E[X 1+...+X N].概率简单数值题未尝试免费5964Polya Urn Limiting FractionAn urn starts with 1 red and 2 blue balls. Each step a ball is drawn uniformly at random, observed, and returned together with one additional ball of the same color. Let R n/T n be the fraction of red balls after n draws. This fraction is a bounded martingale converging to a limit L. Using optional stopping / martingale convergence, find E[L].概率中等数值题未尝试免费5965Branching Process Extinction ProbabilityA Galton-Watson branching process starts with one individual. Each individual independently has 0 offspring with probability 1/4, 1 offspring with probability 1/4, and 2 offspring with probability 1/2. Let q be the extinction probability. Using that q Z n is a martingale (where Z n is the generation-n population), find q.概率困难数值题未尝试面试订阅