Snap VO挂经

比较混乱的面试，体验比较差。电面其实没有表现好，托一个国人大哥照顾，让我过了。VO总共5轮。recruiter之前告诉我是两轮design，两轮coding再加一轮behavior。结果就问了一轮design 。

round 1: 30min past projects + 30min design snap story. Similar to design news feed, with one caveat that, snaps are only valid for 24 hours.
round 2: almost 30min behavior. The interviewer wanted to leave 5 minutes for QA, which means I need to solve the coding problem in about 25 minutes. It's actually LC 霸气一 but I didn't know. Spent some time figuring out the solution and was asked to write code. It was a mess. Definitely failed.
round 3: 30min behavior interview with an EM. Nothing to highlight. One que

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

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

As experienced candidate, I was expecting more focus on design and less coding. Instead they asked me three coding problems and just a little bit design. Two of the three coding problems (rounds 2 and 5) are hard. The other one (round 4) is definitely not that easy, even though it doesn't involve fancy idea. You'll see when I post my code later.

求大米

这是我的代码：

1. public class PayChange {
   
2. 
   
3.     // This keeps track all the denominations the cashier has in the register.
   
4.     // We use a reverse ordered TreeMap because we always want to find the change
   
5.     // with larger denominations. For example, if we want to find $2.65, we'll first
   
6.     // check if there is any $100, then $20, then $10, $5 and $1, etc.
   
7.     // All the denominations are converted to cents. For example if we have 3 dollars
   
8.     // in the register, it would be stored as 100 -> 3.
   
9.     private final TreeMap<Integer, Integer> register;
   
10. 
    
11.     public PayChange(TreeMap<Integer, Integer> register) {        assert Collections.reverseOrder().equals(register.comparator());
    
12.         this.register = register;
    
13.     }
    
14. 
    
15.     /**
    
16.      * When you buy something in grocery, the cashier needs to pay the change. Write a method simulating how the cashier
    
17.      * find all the changes. For example you paid $5 for something worth $2.35, the cashier needs to find 2 $1, 6 dimes
    
18.      * and 5 one cents if there are enough of these.
    
19.      */
    
20.     public boolean payChange(Map<Integer, Integer> paid, int price) {
    
21.         int totalPaid = 0;
    
22.         for (int denomination : paid.keySet()) {
    
23.             totalPaid += denomination * paid.get(denomination);
    
24.         }
    
25. 
    
26.         // Not enough to cover the price.
    
27.         if (totalPaid < price) {
    
28.             return false;
    
29.         }
    
30. 
    
31.         // First we need to check if there is a solution, w/o actually paying the change.
    
32.         // Maybe there isn't a solution.
    
33.         int change = totalPaid - price;
    
34.         Map<Integer, Integer> possibleChange = new HashMap<>();
    
35.         for (int denomination : register.keySet()) {
    
36.             int needed = change / denomination;
    
37.             // We also have to consider what we have from the customer, not just what we have in the register.
    
38.             int nReduced = Math.min(needed, register.get(denomination) + paid.getOrDefault(denomination, 0));
    
39.             if (nReduced > 0) {
    
40.                 change -= nReduced * denomination;
    
41.                 possibleChange.put(denomination, nReduced);
    
42.             }
    
43. 
    
44.             if (change == 0) {
    
45.                 break;
    
46.             }
    
47.         }
    
48. 
    
49.         // This means we cannot find the proper combination.
    
50.         if (change > 0) {
    
51.             return false;
    
52.         }
    
53. 
    
54.         // Add back what the customer paid to the register.
    
55.         for (int denomination : paid.keySet()) {
    
56.             register.put(denomination, register.getOrDefault(denomination, 0) + paid.get(denomination));
    
57.         }
    
58. 
    
59.         // Actually remove denominations from the register.
    
60.         for (int denomination : possibleChange.keySet()) {
    
61.             int nRemaining = register.get(denomination) - possibleChange.get(denomination);
    
62.             if (nRemaining == 0) {
    
63.                 register.remove(denomination);
    
64.             } else {
    
65.                 register.put(denomination, nRemaining);
    
66.             }
    
67.         }
    
68.         return true;
    
69.     }
    
70.     @Override
    
71.     public String toString() {
    
72.         return register.toString();
    
73.     }
    
74. 
    
75.     public static void main(String[] args) {
    
76.         TreeMap<Integer, Integer> register = new TreeMap<>(Collections.reverseOrder());
    
77.         register.put(100, 5);
    
78.         register.put(25, 4);
    
79.         register.put(1, 20);
    
80.         PayChange payChange = new PayChange(register);
    
81. 
    
82.         Map<Integer, Integer> paid = new HashMap<>();
    
83.         paid.put(500, 1);
    
84.         System.out.println(payChange.payChange(paid, 235));
    
85.         System.out.println(payChange);
    
86.     }
    
87. 
    
88. }

复制代码

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

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

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

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

很赞，谢谢分享，感觉你差一点就都做出来了

辛苦楼主了

请问round 4 是刷题王 散儿儿吗？

加米加米
请问第五题是LC哪道啊？
谢谢

onsite可以分两天面吗？这样是不是好一点，一天面5轮有点累？

第5题看起来应该是sliding window来做？

noi10 发表于 2021-5-6 15:46
请问面额是固定的吗？就是dollor，dime，cent这样？
要是面额是 1，3，4，5  各一个， target amount是7 ...

我感觉这个应该得用dfs+memo做？主要每个硬币有数量的话，感觉还是得dfs