帮朋友发google onsite面经

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

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

The following is my JAVA solution, similar to 163'.

1. 
   
2. import java.util.*;
   
3. class Solution{
   
4.     static long solve(int n){
   
5.         Map<List<Integer>,Long> map=new HashMap<>(), alt=new HashMap<>(), temp;
   
6.         List<Integer> stat=new ArrayList<>();
   
7.         for(int i=0; i<n; i++) stat.add(0);
   
8.         map.put(stat,1l);
   
9.         for(int j=1; j<=n*n; j++){
   
10.             alt.clear();
    
11.             for(Map.Entry<List<Integer>,Long> entry:map.entrySet()){
    
12.                 stat=entry.getKey();
    
13.                 long count=entry.getValue();
    
14.                 for(int i=0; i<n; i++){
    
15.                     if((i==0 && stat.get(i)<n) || (i>0 && stat.get(i)<stat.get(i-1))){
    
16.                         List<Integer> newStat=new ArrayList<>(stat);
    
17.                         newStat.set(i,stat.get(i)+1);
    
18.                         Long newC=alt.get(newStat);
    
19.                         if(newC==null)
    
20.                             alt.put(newStat,count);
    
21.                         else
    
22.                             alt.put(newStat,newC+count);
    
23.                     }
    
24.                 }
    
25.             }
    
26.             temp=alt; alt=map; map=temp;
    
27.         }
    
28.         System.out.println(map);
    
29.         return 1;
    
30.     }
    
31.     public static void main(String[] args){
    
32.         System.out.format("%d: %d\n", 5, solve(5));
    
33. 
    
34.     }
    
35. }
    

复制代码

第一题follow up是不是最小费用流？

每个点拆成i->i'，流量1（起点流量为2），费用为格子数值的负数
相邻的格子连边i'->j，流量1，费用为0
源点就是左上角的点，汇点就是最右下角的点
答案就是: abs(最小费用) - 原点格子的值 - 终点格子的值（后两个算了两遍，所以要减掉）

您好！
本帖隐藏的内容需要积分高于 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

您好！
本帖隐藏的内容需要积分高于 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

pushazhiniao 发表于 2016-8-29 01:41
每个hash里的value指的是到当前状态的填法，一个都不填的填法是1
i-1排填的数量必须大于等于i排，你试着 ...

我明白了， i 是当前要往里填的数。

谢谢

第一题是双调欧几里得回路。
当做两个人同时往下走就好了，状态很好推。状态划分是斜线。

南慕伦 发表于 2016-8-30 07:02
第一题是双调欧几里得回路。
当做两个人同时往下走就好了，状态很好推。状态划分是斜线。

能不能给稍微详细一点的解法呢？多谢！