Facebook onsite跪经

第一轮三哥：

• k个二进制数相加
• 给一个数组，每个元素有一个概率，写一个函数按照每个元素的概率每次返回一个元素。比如1：0.2，2：0.3，3：0.5    返回1的概率是0.2，返回3的概率是0.5
  

第二轮美国人behavior：

• 自我介绍
• project dive deep
• coding：反向打印链表
  

第三轮中国人：

• serialize和deserialize二叉树
  

写了个代码，准备去睡，没时间测试。大家看看。

package facebook;

import java.util.LinkedList;
import java.util.Queue;

public class add_k_binary_numbers {
       
        public static String addBinary(String[] strs)
        {
                if(strs.length==0||strs==null) return "";
                StringBuilder sb = new StringBuilder();
                Queue<String> q = new LinkedList<>();
                for(String str: strs)
                {
.鏈�鏂囧師鍒涜嚜1point3acres璁哄潧                        if(str.length()>0)
                        {
                                q.add(str);
                        }
                }
                int sum =0;
                while(!q.isEmpty())
                {
                        int size = q.size();
                       
                        for(int i =0; i < size;i++)
                        {
                                String temp = q.poll();
                                char c = temp.charAt(temp.length()-1);
                                if(temp.length()>1)
                                {
                                        q.add(temp.substring(0, temp.length()-1));
                                }
                                sum+=(c-'0');       
                        }
                        sb.append(sum%2);
                        sum=sum/2;
                }
                while(sum!=0)
                {
                        sb.append(sum%2);
                        sum=sum/2;
                }
                return sb.reverse().toString();
        }
       
        public static void main(String[] args)
        {
                String[] test1 = {"11110",
                                                 "11000",
                                         "11001"};
                System.out.println(addBinary(test1));
                String[] test2 = {"1111",
                                                  "1000",
                                                "111111"};
               
                System.out.println(addBinary(test2));
                String[] test3 = {"11111100111",
                                                        "1",
                                                        "100111001",
                                                        "111",
                                                        "1"};
                System.out.println(addBinary(test3));
        }
}[/code]

补充内容 (2016-10-21 16:30):
time complexity应该是m*n, n是string 个数， m是每个词的平均长度。

第一题。跟merge sort很像吧。keep divide k until reach two bianry num。然后相加。然后再上一层加。直到 log k。至于prob。  应该是例如树的来specify range

LZ什么时候onsite的？

smellycat 发表于 2016-10-21 02:15
LZ什么时候onsite的？

10.11  字数字数

zhan8803705 发表于 2016-10-21 02:16
10.11  字数字数

LZ加油。。。

楼主能说说为什么挂了吗？第一轮k个二进制数相加怎么做？等概率返回怎么做呢？

同问第一轮lz怎么答得？

我也是10.11，刚刚悲剧。。。。

请问lz被要了reference吗？

iwknow 发表于 2016-10-21 02:35
我也是10.11，刚刚悲剧。。。。

遇到新题了？

返回概率有要求O(1)的run time吗

lz nsite只有 3轮？ 为啥我有4轮。。。。 这个跟时间有关么？

timpark4 发表于 2016-10-21 04:00
lz nsite只有 3轮？ 为啥我有4轮。。。。 这个跟时间有关么？

你是周一Onsite
对吧

zj45499 发表于 2016-10-21 04:04
你是周一Onsite
对吧

对的。。。跟时间有关系？

timpark4 发表于 2016-10-21 04:09
对的。。。跟时间有关系？

据说长得丑的一般都是四轮























我也是四轮

zj45499 发表于 2016-10-21 04:13
据说长得丑的一般都是四轮

我也4轮.. 在网上还要被鄙视颜值呜呜呜呜呜

请问楼主要了reference吗

三轮还有一轮behavior。。。所以就两轮coding？感觉第二轮的链表都不算coding。。。

timpark4 发表于 2016-10-21 04:09
对的。。。跟时间有关系？

欸楼上 我也是17号面的4轮 any update? 我刚被要reference了 你呢

leixiang5 发表于 2016-10-21 02:47
第一题。跟merge sort很像吧。keep divide k until reach two bianry num。然后相加。然后再上一层加。直到 ...

merge sort和直接相加有什么区别？