一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2943|回复: 24
收起左侧

snapchat面经 求rp

[复制链接] |试试Instant~ |关注本帖
d1987115w 发表于 2015-10-24 09:35:23 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Snapchat - 网上海投 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
电面
设计big int类,提供add函数. 1point 3acres 璁哄潧
combination sum
merge k sorted lists 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

onsite要带电脑 跑code。讨论简历的时候,可以给面试官用电脑show下自己的project
1 given [1, [2,3], [[4]]], return sum. 计算sum的方法是每向下一个level权重+1, 例子的sum = 1 * 1 + (2 + 3) * 2 + 4 * 3。follow up:每向下一个level 权重 - 1, sum = 3 * 1 +(2 + 3)* 2 + 4 * 1 . Waral 鍗氬鏈夋洿澶氭枃绔,
2 majority number
3 clone graph. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
4 设计一个数据结构 能支持 insert(int val), getRandom(), delete(int val) 均在 O(1) time完成
5 给一个字符串,问最少删去多少个字符可以得到一个是回文的字符串, 只能删去头尾处的字符 eg "abxyyxc" -> 3
6 给一个整数n,输出俩数x和y,使得x*y的值在 [n, n+2] 的范围内,同时保证 |x - y| 最小, e.g. n=25, return x=y=5 或  n=22, return x=4 y=6.鐣欏璁哄潧-涓浜-涓夊垎鍦
7 given an int n, write a function to generate false in a probability of 1/(2^n), e.g. n = 3, 那么函数以1/8的概率返回false, 以7/8的概率返回true. Waral 鍗氬鏈夋洿澶氭枃绔,
8 给一个二次函数y=ax^2+b,求这个函数与x y轴截出的图形的面积。这轮是写完一个题后,面试官说还有时间,问个他自个儿想的新题,积分早就忘光了,只是讨论了下的思路,估计挂在这里或是那个求sum的题了

4轮onsite中2轮国人大哥 还有 中午一起吃饭的国人小哥,人都非常nice,还说他们明年打算把engineer team double,真是难得有个扩招的公司。。找工作不容易,继续加油!. Waral 鍗氬鏈夋洿澶氭枃绔,

. 1point3acres.com/bbs


评分

5

查看全部评分

本帖被以下淘专辑推荐:

 楼主| d1987115w 发表于 2015-10-25 07:26:38 | 显示全部楼层
f1371342385 发表于 2015-10-25 06:23
给一个整数n,输出俩数x和y,使得x*y的值在 [n, n+2] 的范围内,同时保证 |x - y|  LZ这题你是如何做的?

从x=y=sqrt(n+2) 开始搜索,第一次碰到一对x和y,能满足[n,  n+2], 那这对x y就是要返回的结果。
  1. int[] searchXandY(int n) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  2.                 int[] result = new int[2];
  3.                 if(n <= 0) {
  4.                         throw new IllegalArgumentException("Illegal input");
  5.                 }
  6.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.                 int cand1 = (int)Math.sqrt(n+2);
  8.                 int cand2 = (int)Math.sqrt(n+2);
  9.                
  10.                 while(true) {
  11.                         . From 1point 3acres bbs
  12.                         if(cand1 * cand2 >= n && cand1 * cand2 <= n +2) {
  13.                                 result[0] = cand1;. 1point 3acres 璁哄潧
  14.                                 result[1] = cand2;
  15.                                 break;
  16.                         } else if(cand1 * cand2 < n) {
  17.                                 cand1++;. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.                         } else {
  19.                                 cand2--;
  20.                         }
  21.                 }
  22.                 return result;
  23.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

f1371342385 发表于 2015-10-25 06:23:13 | 显示全部楼层
给一个整数n,输出俩数x和y,使得x*y的值在 [n, n+2] 的范围内,同时保证 |x - y|  LZ这题你是如何做的?
回复 支持 0 反对 1

使用道具 举报

liyanjia92 发表于 2015-10-24 10:58:40 | 显示全部楼层
最后一轮没有hr或者manager嘛?

补充内容 (2015-10-24 11:17):
1 given [1, [2,3], [[4]]], return sum. 1point3acres.com/bbs
这里输入是一个list 然后4是在一个list<list<list<integer>>>吗?

补充内容 (2015-10-24 11:19):
还有请问第四题getRandom()具体是什么意思呢?是随机的从这个数据结构中取一个数,还是random access呢?
回复 支持 反对

使用道具 举报

snowwolf 发表于 2015-10-24 11:06:15 | 显示全部楼层
真的假的?不是说snapchat都半死不活了吗?领导层都离职了,还能扩招?
回复 支持 反对

使用道具 举报

 楼主| d1987115w 发表于 2015-10-25 00:28:46 | 显示全部楼层
liyanjia92 发表于 2015-10-24 10:58
最后一轮没有hr或者manager嘛?

补充内容 (2015-10-24 11:17):
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
求sum的题 是让自己定义数据结构来表示它,我用了个wapper class
     class Wrapper {
                int val;
                List<Wrapper> nodes;
    }

getRandom()函数是随机从这个数据结构已有的值中 取一个数返回

4轮都主要是coding,其中有一轮面试官是manager,最后面完hr talk了几分钟。。
回复 支持 反对

使用道具 举报

 楼主| d1987115w 发表于 2015-10-25 00:33:06 | 显示全部楼层
snowwolf 发表于 2015-10-24 11:06
真的假的?不是说snapchat都半死不活了吗?领导层都离职了,还能扩招?
.1point3acres缃
听一起吃饭的国人小哥说在大量招人。。不过总共engineer team就100多人,扩招的话也没多少坑。。
回复 支持 反对

使用道具 举报

OracleDesire 发表于 2015-10-25 07:41:20 | 显示全部楼层
电面居然能做三个题?
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-10-25 07:49:03 | 显示全部楼层
d1987115w 发表于 2015-10-25 07:26
从x=y=sqrt(n+2) 开始搜索,第一次碰到一对x和y,能满足[n,  n+2], 那这对x y就是要返回的结果。

感谢LZ哈!
回复 支持 反对

使用道具 举报

 楼主| d1987115w 发表于 2015-10-25 14:52:32 | 显示全部楼层
OracleDesire 发表于 2015-10-25 07:41
. 1point 3acres 璁哄潧电面居然能做三个题?

木有啊,面了两轮电面。。
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-10-29 06:15:22 | 显示全部楼层
下周要面他家。。。请问楼主onsite第4题允许重复元素吗。。。。多谢拉
回复 支持 反对

使用道具 举报

 楼主| d1987115w 发表于 2015-10-29 12:35:15 | 显示全部楼层
yabay91 发表于 2015-10-29 06:15
下周要面他家。。。请问楼主onsite第4题允许重复元素吗。。。。多谢拉

我记得面试官说 void insert(int val) 如果插入的是重复元素,不用添加到数据结构里。。. from: 1point3acres.com/bbs
当时讨论的数据结构是用一个int size 和 俩hashmap, map1存<key:val, value: index> map2存<key: index, value: val>。 insert的话就直接更新俩hashmap, 并且size++。getRandom的话是产生一个[0, size-1]之间的随机数,用这个数作为index,返回map2.get(index)。void delete(int val)的话是
                int tempIndex = map1.get(val);
                int tempVal = map2.get(size - 1);
                map1.put(tempVal, tempIndex);
                map2.put(tempIndex, tempVal);
                map2.remove(size - 1);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                size--;
回复 支持 反对

使用道具 举报

han275 发表于 2015-11-2 06:30:36 | 显示全部楼层
设计big int类,提供add函数 这个题,函数什么样子哦
public String add(String num1, String num2) {
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        if (null == num1 || null == num2 || (num1.length() == 0 && num2.length() == 0)) {
            return "";
        }
        int len1 = num1.length();
        int len2 = num2.length();

        StringBuffer buffer1 = new StringBuffer(num1);
        StringBuffer buffer2 = new StringBuffer(num2);
        int len = len1;. 1point3acres.com/bbs
        if (len1 > len2) {
            for (int i = 0; i < len1 - len2; i++) {. from: 1point3acres.com/bbs
                buffer2.insert(0,"0");
            }
        } else if (len1 < len2) {
            len = len2;
            for (int i = 0; i < len1 - len2; i++) {
                buffer1.insert(0,"0");
            }
        }

        buffer1 = buffer1.reverse();
        buffer2 = buffer2.reverse();-google 1point3acres
        StringBuffer result = new StringBuffer();
        int carry = 0;
        for (int i = 0; i < len; i++) {. 1point3acres.com/bbs
            int cur = (buffer1.charAt(i) - '0') + (buffer2.charAt(i) - '0') + carry;
            carry = cur / 10;
            cur = cur % 10;
            result.insert(0, cur);
        }
        if (carry != 0) {
. Waral 鍗氬鏈夋洿澶氭枃绔,            result.insert(0, carry);
        }. 鍥磋鎴戜滑@1point 3 acres
        return result.toString();
. from: 1point3acres.com/bbs
    }

这样行吗??
回复 支持 反对

使用道具 举报

reality 发表于 2015-11-16 06:21:26 | 显示全部楼层
楼主咋被问了那么多偏数学的题目。。。
回复 支持 反对

使用道具 举报

ammmmy11 发表于 2015-11-18 05:30:34 | 显示全部楼层
求问楼主求SUM那题输入是string吗
回复 支持 反对

使用道具 举报

jxyfwrj 发表于 2015-12-4 03:37:33 | 显示全部楼层
同问楼主sum那题输入是array还是一个string。。。
回复 支持 反对

使用道具 举报

douch 发表于 2015-12-26 14:42:48 | 显示全部楼层
lz第五题是咋做的啊?
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-1-3 11:03:03 | 显示全部楼层
d1987115w 发表于 2015-10-29 12:35
我记得面试官说 void insert(int val) 如果插入的是重复元素,不用添加到数据结构里。。
当时讨论的数据 ...

这样直接用一个map+vector就好了吧~
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-1-3 11:03:39 | 显示全部楼层
jxyfwrj 发表于 2015-12-4 03:37
同问楼主sum那题输入是array还是一个string。。。

我猜是str
回复 支持 反对

使用道具 举报

sevensevens 发表于 2016-1-4 07:09:04 | 显示全部楼层
d1987115w 发表于 2015-10-25 00:28
求sum的题 是让自己定义数据结构来表示它,我用了个wapper class. more info on 1point3acres.com
     class Wrapper {
                int val;

求问楼主。。。按照这个class wrapper看 每层只有一个数字?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 18:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表