San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2012|回复: 16
收起左侧

刚刚做完Twitter online test

[复制链接] |试试Instant~ |关注本帖
daniel.kong 发表于 2014-8-25 13:27:09 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类General 硕士 全职@Twitter - 网上海投 - 在线笔试  | Other |

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

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

x
刚刚做了twitter HR发过来的online test面试,现在分享一下:两道题:. 一亩-三分-地,独家发布
1. get the shortest sequence to reach a number.

Rules:

  • A[0] is always 1
  • Either A = A[i-1]*2 or A = A[i-1]+1

For example, if my input number is 17, my output should be 6, because A[0]=1, A[1]=2, A[2]=4, A[3]=8, A[4]=16, A[5]=17

run time should be O(log(n))

2. A non-empty zero-indexed array A consisting of N integers is given.

                A pair of integers (P, Q) is called K-complementary in array A if 0 ≤ P, Q < N and A[P] + A[Q] = K.. more info on 1point3acres
               
                For example, consider array A such that:
               
                  A[0] =  1  A[1] = 8  A[2]= -3
                  A[3] =  0  A[4] = 1  A[5]=  3
                  A[6] = -2  A[7] = 4  A[8]=  5
                  
                The following pairs are 6-complementary in array A: (0,8), (1,6), (4,8), (5,5), (6,1), (8,0), (8,4).
                For instance, the pair (4,8) is 6-complementary because A[4] + A[8] = 1 + 5 = 6.
                . 1point 3acres 论坛
                Write a function:.1point3acres网
               
                        class Solution { public int solution(int K, int[] A); }

                returns the number of K-complementary pairs in array A..本文原创自1point3acres论坛
                  A[0] =  1  A[1] = 8  A[2]= -3
. 牛人云集,一亩三分地                  A[3] =  0  A[4] = 1  A[5]=  3
                  A[6] = -2  A[7] = 4  A[8]=  5. Waral 博客有更多文章,
第一题就是DP,第二题我用的hashmap,感觉online test和leetcode难度差不多。
希望对大家有帮助。. 1point3acres


评分

3

查看全部评分

notbad 发表于 2014-8-25 22:01:13 | 显示全部楼层
第一道题好像可以直接做。两个操作 *2 也就是向左边移1位,+1 就是在最低位变成1。所以这个最优解就是:这个数二进制表示的位数+(表示中1的个数-1)。例如(17)2=10001,可以得到答案是5+(2-1)=6.
回复 支持 1 反对 0

使用道具 举报

littlecoolblaxk 发表于 2014-8-25 14:22:32 | 显示全部楼层
谢谢lz分享! 最近在刷题 就跟着做了一下 leetcode已刷差不多。。就是没有面试TT.留学论坛-一亩-三分地

第一题 貌似是O(n)到 logN之间的复杂度。。?我不太会分析诶- -。。只能说最坏是N 最好是logN
public static void main(String[] args) {
       int a = shortest(17);
       System.out.println(a);
    }
   
    public static int shortest(int target) {
        if (target < 1) {
            return -1;
        }
        int count = 1;
        while (target != 1) {
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target -= 1;
            }
            count ++;.本文原创自1point3acres论坛
        }. 一亩-三分-地,独家发布
        return count;
    }
. more info on 1point3acres
第二题 2sum 简单版本 我也是 hashmap 但是似乎需要假设A数组内没有重复数字出现 不然map不好办 或者把map的value改成数组 这样把相同值的下标都存下

public static void main(String[] args) {
       int[] A = {1, 8, -3, 0, 1, 3, -2, 4, 5};
       int a = Kc(6, A);. Waral 博客有更多文章,
       System.out.println(a);
    }
   
    public static int Kc(int K, int[] A) {. Waral 博客有更多文章,
        //assuming A has no duplications
        if (A == null || A.length == 0) {
            return 0;. 牛人云集,一亩三分地
        }
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            map.put(A[i], i);
        }
        . more info on 1point3acres
        for (int i = 0; i < A.length; i++) {
            int tmp = K - A[i];
            if (map.containsKey(tmp)) {
                int index = map.get(tmp);
                //if (index > i) {. Waral 博客有更多文章,
                    res++;
                //}. from: 1point3acres
            }
        }
        return res;.本文原创自1point3acres论坛
    }
回复 支持 反对

使用道具 举报

sqzhang17 发表于 2014-8-25 14:42:24 | 显示全部楼层
感谢分享~第二道题跟2sum好像~
回复 支持 反对

使用道具 举报

TonyJang 发表于 2014-8-25 22:22:12 | 显示全部楼层
LZ online test过了直接onsite吗?T家没有电面?
回复 支持 反对

使用道具 举报

 楼主| daniel.kong 发表于 2014-8-26 00:33:22 | 显示全部楼层
littlecoolblaxk 发表于 2014-8-25 14:22
谢谢lz分享! 最近在刷题 就跟着做了一下 leetcode已刷差不多。。就是没有面试TT

第一题 貌似是O(n)到 ...

你说的对,第一题的worst case是O(N)第二题不用考虑重复的情况,要hashmap的value为key在array中出现的次数就可以了。你觉得呢
回复 支持 反对

使用道具 举报

 楼主| daniel.kong 发表于 2014-8-26 00:33:59 | 显示全部楼层
notbad 发表于 2014-8-25 22:01
第一道题好像可以直接做。两个操作 *2 也就是向左边移1位,+1 就是在最低位变成1。所以这个最优解就是:这 ...

嗯,你的方法也可以
回复 支持 反对

使用道具 举报

 楼主| daniel.kong 发表于 2014-8-26 00:35:04 | 显示全部楼层
TonyJang 发表于 2014-8-25 22:22
LZ online test过了直接onsite吗?T家没有电面?
. more info on 1point3acres
sorry,我昨天晚上刚刚做的online test 还没有任何结果,应该会有电面,再onsite
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

jingi08 发表于 2014-8-26 01:05:07 | 显示全部楼层
notbad 发表于 2014-8-25 22:01
.留学论坛-一亩-三分地第一道题好像可以直接做。两个操作 *2 也就是向左边移1位,+1 就是在最低位变成1。所以这个最优解就是:这 ...

这个解法很巧妙阿。int转换成二进制形式时间也是O(logn),正好满足要求。
回复 支持 反对

使用道具 举报

laughingvito 发表于 2014-8-26 01:12:29 | 显示全部楼层
好,非常感谢,楼主好人
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-8-26 01:32:00 | 显示全部楼层
daniel.kong 发表于 2014-8-26 00:33. 围观我们@1point 3 acres
你说的对,第一题的worst case是O(N)第二题不用考虑重复的情况,要hashmap的value为key在array中出现的 ...

恩恩!!对的!我想复杂了 我老是生搬硬套leetcode原题都没仔细分析这道题。。第一题想了一下楼里说的二进制解法 感觉确实更好 这样就确保了一定可以到到logN的复杂度。lz面试加油啊~
回复 支持 反对

使用道具 举报

tyr034 发表于 2014-10-13 08:02:20 | 显示全部楼层
littlecoolblaxk 发表于 2014-8-25 14:22
谢谢lz分享! 最近在刷题 就跟着做了一下 leetcode已刷差不多。。就是没有面试TT

第一题 貌似是O(n)到 ...
. more info on 1point3acres
我觉得一直之 logN; 因为可以这样做, 不用 n--: . 1point 3acres 论坛
public static int shortest(int n){. From 1point 3acres bbs
     int result = 0;
     while(n!=1 ){
          if(n % 2 !=0){. 牛人云集,一亩三分地
             result++;
         }
         n = n /2;.本文原创自1point3acres论坛
     
         result ++;
}
. 一亩-三分-地,独家发布
return result;. From 1point 3acres bbs
        

}
回复 支持 反对

使用道具 举报

lhh_NJU 发表于 2014-10-13 14:08:12 | 显示全部楼层
我当时也是这两道题, 居然挂掉了..
回复 支持 反对

使用道具 举报

tyr034 发表于 2014-10-14 05:50:49 | 显示全部楼层
littlecoolblaxk 发表于 2014-8-25 14:22
谢谢lz分享! 最近在刷题 就跟着做了一下 leetcode已刷差不多。。就是没有面试TT

第一题 貌似是O(n)到 ...

关于第二题我想了一种case 比如 array 是{3,3}  K =6,
这样子我们应该是有4个pair把(0,1)(1,0),(0,0),(1,1) 来源一亩.三分地论坛.
如果用的是你的解法,应该只return 2.
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-10-14 07:36:58 | 显示全部楼层
tyr034 发表于 2014-10-13 08:02. from: 1point3acres
我觉得一直之 logN; 因为可以这样做, 不用 n--:
public static int shortest(int n){.留学论坛-一亩-三分地
     int resul ...

对的! 这样每次循环都能让n变成一半儿! good point
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-10-14 07:53:47 | 显示全部楼层
tyr034 发表于 2014-10-14 05:50
关于第二题我想了一种case 比如 array 是{3,3}  K =6,.留学论坛-一亩-三分地
这样子我们应该是有4个pair把(0,1)(1,0) ...

我注释里写了假设数组没有重复 当然这个应该和面试官讨论一下 如果有重复就稍微改一下 大致思路还是这样 用hashmap降低查找时间
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-26 12:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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