食跩普店面

Wishlist 原题

说至少要做两问，做到第三问最好。

您好！
本帖隐藏的内容需要积分高于 180 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 180 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

关于第三问，如果swap之后在指定的index没有mutual rank，那是不是就return original mutual rank 就行了？

楼主什么时候面的呀？有没有收到后续

Let's crack stripe!

1. /*
   
2.   Mutual Ranking
   
3.   Question comes from https://www.1point3acres.com/bbs/thread-769296-1-1.html
   
4.                       https://www.1point3acres.com/bbs/thread-674646-1-1.html
   
5.                       https://www.1point3acres.com/bbs/thread-793699-1-1.html
   
6.                       https://www.1point3acres.com/bbs/thread-806739-1-1.html
   
7. 
   
8. 
   
9.    user and wishlist represented with Map<Character, Character[]> wishlist
   
10.    a, [b,c,d]
    
11.    b, [a,c,d]
    
12.    c, [d,a]
    
13.    d, [a,c]
    
14.    index 0 is the highest rank
    
15. 
    
16.    question 1: boolean hasMutualFirstChoice(String username)
    
17.                mutual at the first rank
    
18.    question 2: boolean hasMutualRanking(char, int)，
    
19.                hasMutualRanking(a, 1) = true
    
20.                explain:   a's  ranking 1 is c， c's ranking 1 is a.
    
21.                hasMutualRanking(a, 0) = true
    
22. 
    
23.    question 3-1
    
24.               changePair(char user, int index) ：swap user rank index with index-1
    
25.               return matched all users before and after swap with same mutual ranking
    
26. 
    
27.               changePair(c,1) then c ranking list is [a,d]
    
28.               result is [a, d], because before swap result is a, after swap result is d
    
29. 
    
30. 
    
31.               a -> [b, c, d],
    
32.               b -> [a, d, c],
    
33.               c -> [d, a, b],
    
34.               d -> [a, c].
    
35. 
    
36.               changePair(c, 1)
    
37.               result is a b d
    
38. 
    
39.               Every wishlist entry in the network is either "mutually ranked" or "not mutually ranked"
    
40.               depending on the rank the other user gives that user's apartment in return.
    
41. 
    
42.               The most common operation in the network is incrementing the rank of a single wishlist entry on a single user.
    
43.               This swaps the entry with the entry above it in that user's list.
    
44.               Imagine that, when this occurs, the system must recompute the "mutually-ranked-ness" of any pairings that
    
45.               may have changed.
    
46. 
    
47.               Write a function that takes a username and a rank representing the entry whose rank is being bumped up.
    
48.               Return an array of the users whose pairings with the given user *would* gain or lose mutually-ranked
    
49.               status as a result of the change, if it were to take place.
    
50.               Call your function changed_pairings()
    
51.               data = {
    
52.                'a': ['c', 'd'],
    
53.                'b': ['d', 'a', 'c'],
    
54.                'c': ['a', 'b'],
    
55.                'd': ['c', 'a', 'b'],
    
56.               }
    
57.               if d's second choice becomes their first choice, a and d will no longer be a mutually ranked pair
    
58.               changed_pairings('d', 1) // returns ['a']
    
59. 
    
60.               if b's third choice becomes thei‍‌‍‌‌‍‍‌‍‍‌‍‌‍‍‍‍‌r second choice, c and b will become a mutually ranked pair (mutual second-choices)
    
61.               changed_pairings('b', 2) // returns ['c']
    
62. 
    
63.               if b's second choice becomes their first choice, no mutually-ranked pairings are affected
    
64.               changed_pairings('b', 1) // returns []
    
65. 
    
66.               if d's second choice becomes their first choice, a and d will no longer be a mutually ranked pair
    
67.               if b's third choice becomes their second choice, c and b will become a mutually ranked pair (mutual second-choices)
    
68.               if b's second choice becomes their first choice, no mutually-ranked pairings are affected
    
69. 
    
70.     question 3-2
    
71.      after swap（rank， rank -1)
    
72.      return the changed part of mutual list.
    
73. 
    
74. 
    
75.    question 4 Anti-ra‍‌‍‌‌‍‍‌‍‍‌‍‌‍‍‍‍‌nk
    
76.      boolean hasAntiMutualRank(char user)
    
77.      a: [b,c,d]  b is a's first rank，
    
78.      b: [d,c,a]  a is b's last rank
    
79. 
    
80.    boolean hasAntiMutualRankWithSwapOption(char user) can swap
    
81.      assume: index 0 and 1 swap
    
82.              index N-1 and N-1 swap
    
83. 
    
84. 
    
85.     */
    
86.   private Map<Character, Character[]> wish;
    
87. 
    
88.   public MutualRanking(Map<Character, Character[]> wishList) {
    
89.     wish = wishList;
    
90.   }
    
91. 
    
92.   public boolean hasMutualFirstChoice(char user) {
    
93.     return hasMutualRanking(user, 0, 0, false);
    
94.   }
    
95.   // rank is 0-based
    
96.   public boolean hasMutualRanking(char user, int rank) {
    
97.     return hasMutualRanking(user, rank, rank, false);
    
98.   }
    
99. 
    
100.   private boolean hasMutualRanking(char user, int myRank, int muRank) {
     
101.     return hasMutualRanking(user, myRank, muRank, false);
     
102.   }
     
103. 
     
104.   public Character[] changePair(char user, int rank) {
     
105.     char u = user;
     
106.     int r = rank;
     
107.     if (wish.containsKey(u) && wish.get(u).length > r) {
     
108.       List<Character> ans = new ArrayList<>();
     
109.       Character[] iwish = wish.get(u);
     
110.       for (int i = 0; i <= iwish.length; i++) {
     
111.         if (hasMutualRanking(u, i)) ans.add(iwish[i]); // as usual
     
112.       }
     
113.       if (r > 0) {
     
114.         // swap index and index-1
     
115.         if (hasMutualRanking(u, r, r - 1)) ans.add(iwish[r]);
     
116.         if (hasMutualRanking(u, r - 1, r)) ans.add(iwish[r - 1]);
     
117.       }
     
118. 
     
119.       Character[] a = new Character[ans.size()];
     
120.       return ans.toArray(a);
     
121.     }
     
122.     return new Character[0];
     
123.   }
     
124.   /*
     
125.   after swap（rank， rank -1)
     
126.   the changed part of mutual list. do not change the provided wishlist map
     
127.   */
     
128.   Character[] changed_pairings(char user, int index) {
     
129.     char u = user;
     
130.     int i = index;
     
131.     if (wish.containsKey(u) && wish.get(u).length > i) {
     
132.       ArrayList<Character> r = new ArrayList<>();
     
133.       Character[] iwish = wish.get(u);
     
134.       if (i > 0) {
     
135.         if (hasMutualRanking(u, i) != hasMutualRanking(u, i, i - 1)) r.add(iwish[i]);
     
136.         if (hasMutualRanking(u, i - 1) != hasMutualRanking(u, i - 1, i)) r.add(iwish[i - 1]);
     
137.       }
     
138.       Character[] a = new Character[r.size()];
     
139.       return r.toArray(a);
     
140.     }
     
141.     return new Character[0];
     
142.   }
     
143. 
     
144.   /*
     
145.   a: [b,c,d]  b is a's first rank，
     
146.   b: [d,c,a]  a is b's last rank
     
147.    */
     
148.   boolean hasAntiMutualRank(char user) {
     
149.     return hasMutualRanking(user, 0, 0, true);
     
150.   }
     
151. 
     
152.   private boolean hasMutualRanking(char user, int uRank, int muRank, boolean anti) {
     
153.     if (uRank < 0) return false;
     
154.     if (wish.containsKey(user) && wish.get(user).length > uRank) {
     
155.       char mu = wish.get(user)[uRank];
     
156.       return wish.containsKey(mu)
     
157.           && wish.get(mu).length > muRank
     
158.           && wish.get(mu)[anti ? (wish.get(mu).length - 1 - muRank) : muRank].equals(user);
     
159.     }
     
160.     return false;
     
161.   }
     
162.   /*
     
163.   Followup: can swap
     
164.   assume:
     
165.   index 0 and 1 swap
     
166.   index N-1 and N-1 swap
     
167.    */
     
168.   boolean hasAntiMutualRankWithSwapOption(char user) {
     
169.     return false;
     
170.   }
     
171. 
     
172.   public static void main(String[] args) {
     
173.     Map<Character, Character[]> wish = new HashMap<>();
     
174.     wish.put('a', new Character[] {'b', 'c', 'd'});
     
175.     wish.put('b', new Character[] {'a', 'c', 'd'});
     
176.     wish.put('c', new Character[] {'d', 'a'});
     
177.     wish.put('d', new Character[] {'a', 'c'});
     
178. 
     
179.     MutualRanking t = new MutualRanking(wish);
     
180.     System.out.println(t.hasMutualRanking('a', 1));
     
181.     System.out.println(t.hasMutualRanking('a', 9) == false);
     
182.     System.out.println(t.hasMutualRanking('a', 0));
     
183.     System.out.println(Arrays.toString(t.changePair('a', 1)).equals("[b, c]"));
     
184.     System.out.println(Arrays.toString(t.changePair('a', 9)).equals("[]"));
     
185. 
     
186.     wish = new HashMap<>();
     
187.     wish.put('a', new Character[] {'b', 'c', 'd'});
     
188.     wish.put('b', new Character[] {'a', 'd', 'c'});
     
189.     wish.put('c', new Character[] {'d', 'a', 'b'});
     
190.     wish.put('d', new Character[] {'a', 'c'});
     
191.     t = new MutualRanking(wish);
     
192.     System.out.println(Arrays.toString(t.changePair('c', 1)).equals("[a, b, d]"));
     
193. 
     
194.     wish = new HashMap<>();
     
195.     wish.put('a', new Character[] {'b', 'c', 'd'});
     
196.     wish.put('b', new Character[] {'a', 'c'});
     
197.     wish.put('c', new Character[] {'d', 'a'});
     
198.     wish.put('d', new Character[] {'c', 'b'});
     
199.     t = new MutualRanking(wish);
     
200.     System.out.println(Arrays.toString(t.changed_pairings('a', 1)).equals("[c, b]"));
     
201.     System.out.println(Arrays.toString(t.changed_pairings('a', 2)).equals("[c]"));
     
202. 
     
203.     wish = new HashMap<>();
     
204.     wish.put('a', new Character[] {'b', 'c', 'd'});
     
205.     wish.put('b', new Character[] {'d', 'c', 'a'});
     
206.     wish.put('c', new Character[] {'d', 'a'});
     
207.     wish.put('d', new Character[] {'c', 'b'});
     
208.     t = new MutualRanking(wish);
     
209.     System.out.println((t.hasAntiMutualRank('a')));
     
210.   }

复制代码

求米 求米