G家店面

• Given a matrix, perform a transpose action in place
• A c

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

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

  
  第二题不是很会做。。最后也没有写完code，贴上来大家集思广益一下吧
  
  

第二题：

1. public class QueryMangerImpl implements QueryManger{
   
2. 
   
3.     Map<Integer, Integer> employmentMap;
   
4. 
   
5.     public QueryMangerImpl () {}
   
6. 
   
7.     @Override
   
8.     public void setManger(int manager, int employee) throws CyclicRelationFoundException {
   
9.         if (queryManager(employee, manager)) {
   
10.             throw new CyclicRelationFoundException(String.format("There is management relation from %s to %s",
    
11.                     manager, employee));
    
12.         }
    
13.         employmentMap.put(employee, manager);
    
14.     }
    
15. 
    
16.     @Override
    
17.     public void setPeer(int managerFrom, int employee) throws EmployeeNotFoundException, CyclicRelationFoundException {
    
18.         if (!employmentMap.containsKey(managerFrom)) {
    
19.             throw new EmployeeNotFoundException(String.format("Employee %s is not found"));
    
20.         }
    
21.         int newManager = employmentMap.get(managerFrom);
    
22.         if (queryManager(employee, newManager)) {
    
23.             throw new CyclicRelationFoundException(String.format("There is management relation from %s to %s", newManager, employee));
    
24.         }
    
25.         employmentMap.put(employee, newManager);
    
26.     }
    
27. 
    
28.     @Override
    
29.     public boolean queryManager(int manager, int employee) {
    
30.         if (manager == employee) {
    
31.             return false;
    
32.         }
    
33.         while (employmentMap.containsKey(employee)) {
    
34.             employee = employmentMap.get(employee);
    
35.             if (employee == manager) {
    
36.                 return true;
    
37.             }
    
38.         }
    
39.         return false;
    
40.     }
    
41. 
    
42. }
    
43. 
    
44. public interface QueryManger {
    
45.     public void setManger(int manager, int employee) throws CyclicRelationFoundException;
    
46.     public void setPeer(int managerFrom, int target) throws CyclicRelationFoundException, EmployeeNotFoundException;
    
47.     public boolean queryManager(int manager, int employee);
    
48. }
    
49. 
    
50. public class CyclicRelationFoundException extends Exception {
    
51.     public CyclicRelationFoundException(String message) {
    
52.         super(message);
    
53.     }
    
54. }
    

复制代码

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

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

第二题链表一类的方法就差不多了吧，再用一个map把每个人都映射到他们的链表元素上

A和B的manager不一样 set_peer是要怎么设置呢？

plich 发表于 2018-5-6 07:15
第二题链表一类的方法就差不多了吧，再用一个map把每个人都映射到他们的链表元素上

A和B的manager不一样 ...

看起来像是个 union find 的问题

求教楼主 第一题有说是n*n吗? 如果是m*n matrix，应该返回是n*m matrix啊，怎么in place呢？

第二题就是union find

abcdldzy 发表于 2018-5-6 08:00
看起来像是个 union find 的问题

如果题目是让你设计interface的话，大概是不需要union find的，在set peer和set manager的时候动态更新一下应该是可以的

Fioooooona 发表于 2018-5-6 08:07
求教楼主 第一题有说是n*n吗? 如果是m*n matrix，应该返回是n*m matrix啊，怎么in place呢？

是的，不是n*n没法in place，是个大水题

第二题我当时也是想用union fine，不过没太想明白应该怎么写，最后还是写了个dfs

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

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