Bloomberg NG 挂经

[llzzl]

店面

• https://leetcode.com/problems/insert-delete-getrandom-o1/

Onsite:

第一轮

• https://leetcode.com/problems/validate-binary-search-tree/
• Find the kth missing element in a sorted array

第二轮

• Design two classes:
  • Document that keep tracks of pages. Method to add a page, and one to retrieve a page.
  • Page that keeps tracks the order of words on that page. Method to add words.
    Return a list of words, in order, with their respective page numbers, in order.

然后让我走了，本来应该有4轮的
第2轮做的太慢了吧

[818]

我也挂了，写一下吧

Phone Screen (1 hr?):

• Two City Scheduling (https://leetcode.com/problems/two-city-scheduling/)

First On Campus (1 hr):

• Island Perimeter (https://leetcode.com/problems/island-perimeter/)
  • Changes:
    • Can have multiple islands
    • Input of island and coordinates
    • Return the perimeter of island at the coordinates, otherwise 0
• Copy List with Random Pointer (https://leetcode.com/problems/copy-list-with-random-pointer/)

Second On Campus (1 hr):

• LRU Cache (https://leetcode.com/problems/lru-cache/)

Final Round On Campus:

• Problem solving round (~45 min)
  • Question:
    • Josephus Problem (https://en.wikipedia.org/wiki/Josephus_problem)
    • Given a circle of people of size n, and kill every other person (k = 1)
    • Find the remaining person when k is 1. Be able to do better than brute force.
  • Tips:
    • Start out running through a few examples starting from 1
    • You’ll see when n is 1, 2, 4, 8, and so on, that the remaining person is always 1 (the first person)
    • You can use this to give a formula for the solution which is better than brute force
    • Remember this question is asked to see your thought process so clearly elaborate what you are thinking and be able to explain what you are doing
    • If you get this easily, be ready for follow ups, such as what if k = 2.
    • A close but not quite leetcode question is elimination game (https://leetcode.com/problems/elimination-game/)
  • Possible ways to reach solution:
    • Using closest number underneath n -> 2(n - lgn) + 1
      • ex) n = 100
        • Closest number underneath where solution is 1 would be 64 -> lg n
        • to get from 64 to 100 would be 36 -> n - lgn
        • Advance 2 people for each (Move one person, kill one person) so 36 * 2 -> 2(n - lgn)
        • The steps are move one, kill one, so we have just killed person 72. The next person is 73 -> 2(n - lgn) + 1
    • Using closest number above n -> n - (2lgn - n) + 1, which is the same as 2(n - lgn) + 1
      • ex) n = 100
        • Closest number above is 128 -> 2lgn
        • Find the difference. 128 - 100 = 28 -> 2lgn - n
        • Apply difference. 100 - 28 = 72 -> n - (2lg - n)
        • Move over one. 72 + 1 = 73 -> n - (2lg2 - n) + 1
• Behavioral (Forgot duration)
  • Tell me about yourself, why Bloomberg, the usual.