stripe 电面

面到的是wishlist，面之前没仔细看，后来看了下，应

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

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

自己加一些。面完过了两天收到下一轮。

no worry, let's crack the stripe

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

复制代码

求米求米啊