聊聊在私立文理读cs的两年感受

一亩三分地论坛

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

Snapchat 电面面经

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

2016(1-3月) 码农类General 硕士 全职@Snapchat - 内推 - 技术电面  | Fail | 在职跳槽

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

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

x
Question 1:
Leetcode 128 Valid Palindrome 原题. more info on 1point3acres

Question 2:. From 1point 3acres bbs
Given a string, every step you can add/delete/change one character at any position. Minimize the step number to make it a palindrome.
.留学论坛-一亩-三分地
解法为DP. 牛人云集,一亩三分地

评分

1

查看全部评分

ykwwind 发表于 2016-4-11 14:15:04 | 显示全部楼层
  1. public static int help(char[] letters, int size) {.留学论坛-一亩-三分地
  2.         int[][] dp =  new int[size][size];
  3.         for(int k = 1; k < size; ++k) {.留学论坛-一亩-三分地
  4.             for(int i = 0; i+k < size; ++i) {
  5.                 int j = i+k;. 牛人云集,一亩三分地
  6.                 if(letters[i] == letters[j]) {
  7.                     dp[i][j] = k==1?0:dp[i+1][j-1];. more info on 1point3acres
  8.                 }
  9.                 else {
  10.                     dp[i][j] = Math.min(Math.min(dp[i+1][j], dp[i][j-1]), k==1?0:dp[i+1][j-1])+1;
  11.                 }
  12.             }
  13.         }. 1point3acres
  14.         return dp[0][size-1];
  15.     }
复制代码
回复 支持 3 反对 0

使用道具 举报

TsengJuiWang 发表于 2016-4-14 12:02:03 | 显示全部楼层
abrahamf 发表于 2016-4-11 16:04
int minStepToPal(string &str) {
    if (str.empty())
        return 0;

是不是应该是dp[j]哇? 另外s = "abcd"的话,结果应该是几?我觉得是3哇,可是程序输出的是2

补充内容 (2016-4-14 12:06):
抱歉,楼主,我理解了,可以通过将c改成a然后删除最后的d实现,你的代码是对的。谢谢!
回复 支持 1 反对 0

使用道具 举报

 楼主| abrahamf 发表于 2016-4-11 16:04:41 | 显示全部楼层
lfy249 发表于 2016-4-11 13:52
目测第二题非常难,楼主解得怎么样呢

int minStepToPal(string &str) {-google 1point3acres
    if (str.empty())
        return 0;
   
    vector<vector<int>> dp(str.length(), vector<int>(str.length()));. Waral 博客有更多文章,
    for (int i = str.length() - 1; i >= 0; --i) {
        for (int j = i; j < str.length(); ++j) {
            if (i == j)
                dp[j] = 0;
            else if (i + 1 == j)
                dp[j] = (str == str[j] ? 0 : 1);
            else {
                if (str == str[j]). 1point3acres
                    dp[j] = dp[i + 1][j - 1];
                else
                    dp[j] = min(dp[i + 1][j - 1], min(dp[j - 1], dp[i + 1][j])) + 1;
            }
        }
    }
    return dp[0][str.length() - 1];. From 1point 3acres bbs
}


dp[j]代表从下标i到下标j的sub string需要多少步才能成为palindrome。那个三项求min的为主要状态表达式,楼主思路都对的,但写完后漏了其中一项,后来时间不够,所以跪了,可惜。
回复 支持 1 反对 0

使用道具 举报

lfy249 发表于 2016-4-11 13:52:31 | 显示全部楼层
目测第二题非常难,楼主解得怎么样呢
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-4-11 14:08:03 | 显示全部楼层
同问第二题,dp的状态方程怎么写。。完全没有头绪。。
回复 支持 反对

使用道具 举报

stephenshaw 发表于 2016-4-11 16:58:20 | 显示全部楼层
mingzhou1987 发表于 2016-4-11 14:08
同问第二题,dp的状态方程怎么写。。完全没有头绪。。

我感觉是这样:

m,,n 表示string 的index范围:
if m <= n:
    dp[m][n] = 0; //如果只是单个字符,则不用变

if string[m] == string[n]:
    dp[m][n] = dp[m-1][n-1]; //若头尾相等,则去头去尾看中间
else:. 一亩-三分-地,独家发布
    dp[m][n] = 1 + dp[m-1][n-1]; //若头尾不等,则把尾变成头相同的字符,再弄中间

补充内容 (2016-4-11 16:59):
错了。。。第一个应该是 . 围观我们@1point 3 acres
if m>=n:
    dp[m][n] = 0;

补充内容 (2016-4-11 17:03):
原来还可以添加/删除啊。。。。无视我吧
回复 支持 反对

使用道具 举报

 楼主| abrahamf 发表于 2016-4-14 13:41:29 | 显示全部楼层
TsengJuiWang 发表于 2016-4-14 12:02
是不是应该是dp[j]哇? 另外s = "abcd"的话,结果应该是几?我觉得是3哇,可是程序输出的是2

. 1point3acres补充内容 ( ...

是的,有增删改三种方法,很容易漏掉一个。我就是漏了个结果悲剧了。。。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| abrahamf 发表于 2016-4-14 15:12:57 | 显示全部楼层
对不起,之前发的code不知为什么把""都吞掉了,再发一遍。。。
. visit 1point3acres for more.
. visit 1point3acres for more.
  1. int minStepToPal(string &str) {
  2.     if (str.empty())
  3.         return 0;.1point3acres网
  4.     . 1point 3acres 论坛
  5.     vector<vector<int>> dp(str.length(), vector<int>(str.length()));
  6.     for (int i = str.length() - 1; i >= 0; --i) {
  7.         for (int j = i; j < str.length(); ++j) {. 留学申请论坛-一亩三分地
  8.             if (i == j)
  9.                 dp[i][j] = 0;
  10.             else if (i + 1 == j)
  11.                 dp[i][j] = (str[i] == str[j] ? 0 : 1);
  12.             else {
  13.                 if (str[i] == str[j])
  14.                     dp[i][j] = dp[i + 1][j - 1];
  15.                 else
  16.                     dp[i][j] = min(dp[i + 1][j - 1], min(dp[i][j - 1], dp[i + 1][j])) + 1;. more info on 1point3acres
  17.             }. 一亩-三分-地,独家发布
  18.         }
  19.     }
  20.     return dp[0][str.length() - 1];. From 1point 3acres bbs
  21. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-21 07:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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