ForUsAll一轮电面

刚面完了ForUSAll。
第一题，给你n个点和一组边，返回连通分量的个数。Union Find做

第二题，实现一个minstack，有push(), pop(x),

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

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

不到就走了，中间也听的不是很认真。我问问题他总没反应，也不是特别热情，总之感觉不是太好。

1. class UnionAndFind{
   
2.         int[] parents;
   
3. 
   
4.         UnionAndFind(int n){
   
5.                 parents = new int[n];
   
6. }
   
7. 
   
8.         public int findParent(int p){
   
9.                 if(parents[p] = p){
   
10.                         return p;
    
11. }else{
    
12.         return findParent(parents[p]);
    
13. }
    
14. }
    
15. }
    
16. 
    
17. public int conntectedComponent(int n, int[][] edges){
    
18. int num = n;        
    
19.         for(int[] edge : edges){
    
20.                 if(findParent(edge[0]) != findParent(edge[1])){
    
21.                         parents[findparent(edge[0])] = findParent(edge[1]);
    
22.                         num--;
    
23. }
    
24. }
    
25. Return num;
    
26. }
    

复制代码

1. Stack<Integer> st = new Stack();
   
2. Stack<Integer> minValue = new Stack();
   
3. 
   
4. public void push(int x){
   
5.         st.push(x);
   
6.         minValue.push(Math.min(x, minValue.peek()));
   
7. }
   
8. 
   
9. public int pop(){
   
10.         minValue.pop();
    
11.         return st.pop();
    
12. }
    
13. 
    
14. public void popMIn(){
    
15.         Stack<Integer> st1 = new Stack();
    
16. 
    
17.         while(st.peek() != minValue.peek()){
    
18. st1.push(st.pop());
    
19.                 minValue.pop();
    
20. }
    
21. 
    
22. st.pop();
    
23. minValue.pop();
    
24. 
    
25. while(!st1.isEmpty()){
    
26.         int x = st1.pop();
    
27.         minValue.push(Math.min(minValue.peek(), x));
    
28.         st.push(x);
    
29. }
    
30. }
    

复制代码

求问lz 面试官是谁啊 ？

楼主投的什么职位呀，他家没看到new grad

感谢楼主分享，这个题是利口原题min stack，应该所有操作都是O(1)的，空间是O(2n)，请问楼主有收到后续吗

tjuwdz95 发表于 2018/10/23 22:09:14
感谢楼主分享，这个题是利口原题min stack，应该所有操作都是O(1)的，空间是O(2n)，请问楼主有收到后续吗

并不是那道题，这周二面