一亩三分地论坛

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

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

twoSigma oa 新题面经

[复制链接] |试试Instant~ |关注本帖
haling27188 发表于 2016-2-18 11:54:26 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@TwoSigma - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
刚做了twosigma的面经,以为和地里和网上搜到的题一样。。。还好,没那么难,虽然是比较新的。第一题: substring panlindrome 的个数,不能有重复的: 跟leetcode差不多,要用dp做,不然有2个testcase过不了,超时;

第二题:Encircular, 还好可以google, 在网上搜搜答案,自己改了改就交了,testcase全过。类似于从原点出发,Forward, left, right, 问最后能不能回到原点。
             第二题的reference: https://angshukutu.wordpress.com/2016/01/12/encircular/
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

2

查看全部评分

xt85 发表于 2016-2-29 01:22:54 | 显示全部楼层
请问楼主, 提交以后怎么查看哪个test case 没有过啊? Hackerrank上我做完提交以后没有任何feedback. 谢谢!
回复 支持 反对

使用道具 举报

 楼主| haling27188 发表于 2016-2-29 04:37:46 | 显示全部楼层
xt85 发表于 2016-2-29 01:22
请问楼主, 提交以后怎么查看哪个test case 没有过啊? Hackerrank上我做完提交以后没有任何feedback. 谢谢!

你run以后,就有显示啊,你还可以下载前三个test case,其他的case都是隐藏的
回复 支持 反对

使用道具 举报

如我意 发表于 2016-3-2 12:02:10 | 显示全部楼层
求问楼主第一题dp的做法,现在只想到一个O(n^2)的依次检查+hashset的办法
回复 支持 反对

使用道具 举报

 楼主| haling27188 发表于 2016-3-2 12:12:14 | 显示全部楼层
如我意 发表于 2016-3-2 12:02. more info on 1point3acres.com
求问楼主第一题dp的做法,现在只想到一个O(n^2)的依次检查+hashset的办法

public class Solution {
    public String longestPalindrome(String s) {
    // dynamic programming
    if(s.length()==0 || s.length()==1). 1point 3acres 璁哄潧
       return s;. from: 1point3acres.com/bbs
    boolean[][] dp  = new boolean[s.length()][s.length()];.鏈枃鍘熷垱鑷1point3acres璁哄潧
    String res = "";
    int maxlen =0;
.1point3acres缃    for(int i=s.length()-1; i>=0;i--). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        for(int j=i;j<s.length();j++)
        {
            if(s.charAt(i)==s.charAt(j) && (j-i<=2 || dp[i+1][j-1])). 1point3acres.com/bbs
              {
                  dp[j]=true;
                  if(j-i+1>maxlen)
                  {
                      maxlen = j-i+1;
                      res = s.substring(i,j+1);
                  }
              }
        }
   return res;
}
}
回复 支持 反对

使用道具 举报

如我意 发表于 2016-3-2 12:52:21 | 显示全部楼层
haling27188 发表于 2016-3-2 12:12
public class Solution {. 1point 3acres 璁哄潧
    public String longestPalindrome(String s) {
    // dynamic programmi ...

LZ提供的是longestPalindrome的解法吧... 但是题目是substring panlindrome 的个数 我是想问这个的解法来着
回复 支持 反对

使用道具 举报

如我意 发表于 2016-3-2 12:56:36 | 显示全部楼层
haling27188 发表于 2016-3-2 12:12
public class Solution {
    public String longestPalindrome(String s) {
    // dynamic programmi ...

never mind 所以LZ的代码中间判断的部分修改一下就可以了 但是这个方法也是O(n^2) 一个疑问就是LZ特别说到超时的问题,那么是对比那种方法呢?
回复 支持 反对

使用道具 举报

aifer 发表于 2016-3-9 06:03:09 | 显示全部楼层
第一题统计那个需要统计单独字符么?单独字符也算在palindrome里么?
回复 支持 反对

使用道具 举报

howyoudoing 发表于 2016-3-10 05:26:29 | 显示全部楼层
aifer 发表于 2016-3-9 06:03
第一题统计那个需要统计单独字符么?单独字符也算在palindrome里么?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
需要,input "xxyxx", 答案是5个: x, xx, xyx, xxyxx, y
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 14:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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