富士山下

2008/03/13

科技公司的面試都喜歡考IQ題,不是腦筋急轉彎那種,永世唔會估仲答案的,而是可以讓考官觀察面試者應付難題的能力。M$有很出名的題 目:「如果把富士山移走?」於是林夕就反問一句:「誰能憑愛意要富士山私有?」呢啲咪叫高招,成首歌啲歌詞都唔知講乜(我知我知,google一下就有幾 十個解釋,但我覺得好牽強囉),但係又好好聽喎!

女子,火闌gag言冓完。

同學飛到palo alto面試fb,又是考IQ題。其中一題問:

兩個人,每人有個pattern(分別是「公公字」,同埋「公字字」),另有一枚公正的銀(公字機會各半),一路咁擲,直至出現其中一個人既pattern,果個人就贏。

問題係,邊個人贏面大啲?

廣告

28 回應 to “富士山下”

  1. Yun Says:

    Do you know that, fb subsidizes it’s employees $600/month of house expenses if they live within one mile radius of fb’s location?

    Nice perk!

    But I always wonder, can fb really make profits in a long run?!! I’m skeptical about that…

  2. Justin Says:

    i know that!!! $600!!!

    my classmate did told me that fb ppl believes they are going to defeat google in the future, and interviews in fb are much hard-core than google’s.

    though, up to this point, there is no useful application in fb yet, for me, it is another online game site, i am skeptical about the future of fb too.

  3. Scorpio Says:

    More hard-core interviews don’t mean much. I find that bigger corporations tend to ask less difficult interviews.

    To answer your quiz, the head-head-tail person has a bigger chance at winning. Consider a series of tails. If we get a head next, both persons will have equivalent chances in the next two throws. But in the case of a series of heads, if we get a tail next, the head-head-tail person already wins while the other still need an extra tail to win.

  4. Max Says:

    Wah martingale! I learned that in traffic engineering but forget almost everything afterwards. I guess the H-T-T guy has better chance? (idea: restart)

    This is really harder than the Fuji mountain or “# of piano tuners in a country" class of questions. It’s not just difficult… it’s completely unintuitive!

  5. Billy Ng Says:

    >兩個人,每人有個pattern(分別是「公公字」,同埋「公字字」),
    >另有一枚公正的銀(公字機會各半),一路咁擲,直至出現其中
    >一個人既pattern,果個人就贏。

    http://acm.zju.edu.cn/show_problem.php?pid=2619

    >問題係,邊個人贏面大啲?
    我個program話expected value一樣

  6. Billy Ng Says:

    >我個program話expected value一樣
    但係"公字字"出現之前可能已經出左"公公字"
    所以應該"公公字"贏面大啲

    再寫個program計下先

  7. Alex Says:

    I think of a formal way to prove that “HHT" is more likely than “HTT", although it requires some explanation. Let’s say

    P(i) = probability of winning at the i-th toss

    P(HHT) = P(3) + P(4) + P(5) + …
    = P(HHT) + P(XHHT) + P(XXHHT) + …
    = 1/2^3 + N(1)/2^4 + N(2)/2^5 + ….

    where N(i) is the number of patterns that do not have any “HHT" and “HTT" given i spaces, i > 0

    Now, consider P(HTT)

    P(HTT) = P(3) + P(4) + P(5) + …
    = P(HTT) + P(XHTT) + P(XXHTT) + …
    = 1/2^3 + M(1)/2^4 + M(2)/2^5 + …

    where M(i) is the number of the patterns that do not have any “HHT" and “HTT" given i spaces and that the patterns cannot end in a “H", i > 0. We do not count the patterns end in a “H" because that would form a “HHTT" which make the other person wins first.

    Given the extra restriction, we conclude that N(i) >= M(i) and we can actually take the equal sign away because the sets of patterns consisting of all H’s (H, HH, HHH, …) do not have any “HHT" and “HTT" inside so it makes N(i) larger than M(i) for at least 1.

    Since N(i) > M(i), we thus conclude that P(HHT) > P(HTT).

  8. Alex Says:

    Can anyone figure out how to calculate the exact values of P(HHT) (or P(HTT)) though? It seems pretty tough to me….

  9. Justin Says:

    The basic intuition is that if we see any pattern of HH, for sure HHT is going to win.

    Scorpio: Really?? ppl just say google and m$ ask all kinds of interesting problems. Some of my classmates were asked about randomized algorithm in their first interview with googol.

    Max, I dun understand what do u meant by Restart. Do you mean there are repeated state in the game tree?

    Billy, seems your case only applies to random pattern.

    Responding to Alex, I have just came out with a sketch using an extensive game tree, go to the following link. Main observation the prob of getting HHT of some branches are the same.

    And i get, P(HHT) = 2/3

    IMG_0009.JPG

    Feel free to kick my ass if i am wrong~

  10. Justin Says:

    For Billy, I recall my last statement.
    I think, the expected length might be the same, but you are more likely to get the HHT instead of HTT.

    Btw, the first answer came out of my mind is HHT and HTT have the same probability.

  11. Alex Says:

    Great! Yeah you’re absolutely right. Didn’t thought that it can be solved by conditional probabilities.. Good job 🙂

  12. LP Says:

    Actually, if you draw the finite state machine, you can see that the first H can be ignored. Let the guy choosing HHT (or just HT) be A and the other be B.

    If at some point the outcome is H, then A will certainly win; but if the outcome is T, B is still not guaranteed to win because something like “HTHHT" will make A win.

    Since the probability of A winning = 0.5(1) + (0.5)u (where u is nonnegative real number). A’s chance of winning is certainly greater without even calculating u.

  13. LP Says:

    Correction: u is positive 🙂

  14. Henry Says:

    P(match HHT come first)
    Summation i=1,2,3… (0.5)^2i-1

    P(match HTT come first)
    Summation i=1,2,3… (0.5)^2i

    which HHT has much higher chance to win

  15. cowmoo Says:

    this is a question i had in previous semester’s (take-home) midterm:

    what about HHTT vs HTHT?

  16. Max Says:

    My original idea is that if you want to get HTT and now you have “H", but screws up at the next toss (i.e. you get HH instead of HT), then you can pretend to start over and try to get TT in the next two tosses. However I missed the case that an extra T will immediately make HHT a winner… so now I think Alex’s argument is correct.

    For your game-tree solution, what does the probabilities mean?
    (for example, P_HH = 1 means… ?)
    I like the “ineq" tag haha ~

  17. Justin Says:

    P_HH means the probability of winning for HHT when we have already seen HH from the init point.

  18. Justin Says:

    cow, what course is that???

    HHTT vs HTHT is not trivial wor…

  19. cowmoo Says:

    justin: systems modelling and analysis

    max: originally i thought you were right, but then i realized justin’s question is different…

  20. tsw Says:

    你即係話我牽強?
    人在他方係大膽d

  21. gordon Says:

    應該公公字,岩唔岩?

  22. Lo Says:

    = =; You guys are so quick.

    I’ve played my answer to LP, oh well, I don’t want to type here lu. =) Well done guys.

  23. Justin Says:

    Cow: Are there any systematical method to calculate that??

    Tsw: 我淨係記得你寫過兄妹同歲月如歌,如果我知你寫過呢首,我未乜會咁/敢寫。

    Gordon: 對。可以試下計埋prob.

    Henry: u hv skipped a number of steps wor!!

    Lo: 竟然出iq題會咁多人覆!

  24. Emily Says:

    haha… this is a Markov Chain problem can be found in the textbook exercise. I can show you later how we are taught to deal with it (if you want, MSN me). But the general principal is to choose later 2 patterns as your 1st 2 pattern…probability can be calculated too!

  25. Max Says:

    Umm but why P_HH = 1 le? You can get another H…

    Yes Markov Chain is one way to do this. Another way is to make use of the “Martingale" and “Stopping Time" concepts in queueing theory. There’s a one-sequence version of your problem: what’s the expected number of coin tosses until a certain sequence, say HTH, turns up? (answer = 14, why?)

    Apparently I applied the one-sequence reasoning to the two-sequence problem and got a wrong answer.. no wonder I only got a B- in the course. If you want some reference, you can go to the IEG4140 course homepage and look at the end of Chapter 1, part 2.

  26. Says:

    係「如何把富士山移走」,定係「如果把富士山移走」?

    第二題有d似liar game裡面的抽牌遊戲。

  27. cowmoo Says:

    justin:
    if i were to do it, i would assume an infinite coin flip sequence
    and consider the event of reaching a pattern (e.g. HHT) a renewal process (“restart")

    then the problem is equivalent to asking which renewal process has a smaller expected time to “restart"

  28. Justin Says:

    Emily: oh yes!! i markov chain is a better model. but, how to calculate the prob for markov chain??

    Max: when you get HH, 100% of chance you will reach HHT before HTT.

    btw, I learnt some similar things in John Lui’s Queueing theory class.

    嘉:「如何」我成日打錯字。包括我個新post。

    Cow: oh! i get what u meant by “restart"

    check it out! i hv the markov model.

    Markov chain


發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

%d 位部落客按了讚: