10月20日FB电面

qingmubeio · 发表于 10-21-2015 01:47 AM

亲！马上注册或者登录会查看更多内容！

您需要登录才可以下载或查看，没有帐号？立即注册

x

10月20日FB电面

1. LC， H-index，不过换了种问法给一个数去，里面的数都是[0..n] 让你找出最大的一个值max, 在数组里面存在max 个>=max的数，
想了半天发现是H-index

[ans:]
way 1: sort the array, left tranverse, find the first arr【i】>=len-i;
public class Solution {
public int hIndex(int[] citations) {
      if(citations==null || citations.length==0) return 0;
      Arrays.sort(citations);
      int len=citations.length;

      for(int i=0; i<len; i++){
         if(citations【i】>=len-i) return len-i;
      }

      return 0;
}
}
way 2: sort the array, use binary search to find the arr【i】>=len-i;
public class Solution {
public int hIndex(int[] citations) {
      if(citations==null || citations.length==0) return 0;
      int len=citations.length;

      int begin=0, end=len-1;
      while(begin<=end){
         int mid=begin+(end-begin)/2;
         if(citations[mid]<len-mid) begin=mid+1;
         else end=mid-1;
      }
      // if(begin==len) return 0;
      return len-begin;
}
}
way 3: bucket sort idea,
public class Solution {
public int hIndex(int[] citations) {
      if(citations==null || citations.length==0) return 0;
      int len=citations.length;

      int[] arr=new int[len+1];
      for(int i=0; i<len; i++){
         if(citations【i】>=len) arr[len]++;
         else arr[citations【i】]++;
      }

      for(int i=len; i>=0; i--){
         if(arr【i】>=i) return i;
         if(i>0) arr[i-1]+=arr【i】;
      }
      return 0;
}
}
写了第一种方法，然后描述了第二种和第三种

名字查出来是波兰人，可是确是印度口音，小哥说只准备了1个题，所以就来了第二个
1. LC Reverse LinkedList, require inplace
[ans:]
way 1: recursive
way 2: iterative
写了iterative 的方法，结果小哥感觉意犹未尽，就又来了个follow up
1.1 Follow up
how to do it without change pointer, 有幸前两天在某海外论坛看到有google电面问这个，就大概描述了下，用recursive 方法带2个指针，
没让写code, 回来自己写了个，也过了LC OJ 了。
public class Solution {
ListNode left=null;
boolean meet=false;

public ListNode reverseList(ListNode head) {
      if(head==null || head.next==null) return head;
      left=head;
      meet=false;
      helper(head);
      return head;
}

public ListNode helper(ListNode head){
      if(head.next==null) return head;

      ListNode right=helper(head.next);
      if(!meet){
         int tmp=left.val;
         left.val=right.val;
         right.val=tmp;
         if(left==right || left.next==right) meet=true;
         left=left.next;
      }
      return head;
}
}

攒人品，发详细面经，希望下面的onsites 能给个offer.

hitowings · 发表于 10-21-2015 02:46 AM

还自己加了code 太感谢！

akluffy · 发表于 10-21-2015 08:21 AM

面完就给了onsite吗？

		自动登录	找回密码
密码			立即注册

[Facebook] 10月20日FB电面

亲！马上注册或者登录会查看更多内容！

评分

最佳新人