买新车如何让dealer直接竞价?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 10560|回复: 40
收起左侧

狗家电面 fail,顺便问问第二题怎么做

[复制链接] |试试Instant~ |关注本帖
我的人缘0
sunnyroom 发表于 2016-11-13 01:38:40 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

2016(10-12月) 码农类General 硕士 全职@Google - 猎头 - 技术电面  | Fail | 在职跳槽

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

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

x
发个电面fail电面面经

1. leetcode 394
2.
游客,本帖隐藏的内容需要积分高于 133 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

. Waral 博客有更多文章,


. 1point3acres
补充内容 (2016-11-13 03:47):
aaabcbc 压缩成 3[a]2[bc] 这个例子举的不好,压缩后比压缩前还长,这种情况就不用压缩了,所以,好难好难

评分

参与人数 1大米 +30 收起 理由
candy_shmily + 30

查看全部评分


上一篇:Amazon intern OA2贡献面经
下一篇:Seattle小公司Whitepages两轮电面
我的人缘0
Frankluo 发表于 2016-11-25 18:26:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

  1. class Solution{
  2.         public static boolean checkRepeating(String s, int l, int r, int start, int end){
  3.                 if( (end-start) % (r-l) != 0 ){
  4.                         return false;
  5.                 }
  6.                 int len = r-l;
  7.                 String pattern = s.substring(l, r);
  8.                 for(int i = start; i +len <= end; i+=len){. 一亩-三分-地,独家发布
  9.                         if(!pattern.equals(s.substring(i, i+len))){. 1point3acres
  10.                                 return false;.本文原创自1point3acres论坛
  11.                         }
  12.                 } 来源一亩.三分地论坛.
  13.                 return true;
  14.         }

  15.         public static int getLength(int plen, int slen){
  16.                 return (int)(Math.log10(slen/plen)+1);
  17.         }

  18.         public static String shortestEncodeString(String s){
  19.                 int len = s.length();
  20.                 int[][] dp = new int[len+1][len+1];
  21.                 for(int i = 1; i <= len; ++i){
  22.                         for(int j = 0; j < i; ++j){
  23.                                 dp[j][i] = i-j;
  24.                         }
  25.                 }

  26.                 Map<String, String> dpMap = new HashMap<>();

  27.                 for(int i = 1; i <= len; ++i){
  28.                         for(int j = i-1; j >= 0; --j){
  29.                                 String temp = s.substring(j, i);.本文原创自1point3acres论坛
  30.                                 if(dpMap.containsKey(temp)){
  31.                                         dp[j][i] = dpMap.get(temp).length();. 牛人云集,一亩三分地
  32.                                         continue;
  33.                                 }. more info on 1point3acres
  34.                                 String ans = temp;
  35.                                 for(int k = j+1; k <= i; ++k){
  36.                                         String leftStr = s.substring(j, k);-google 1point3acres
  37.                                         String rightStr = s.substring(k, i);
  38.                                         if(dp[j][i] > dp[j][k] + dp[k][i]){
  39.                                                 dp[j][i] = dp[j][k] + dp[k][i];. visit 1point3acres for more.
  40.                                                 ans = dpMap.get(leftStr) + dpMap.get(rightStr);
  41.                                         }.1point3acres网
  42.                                         if( checkRepeating(s, j, k, k, i)
  43.                                                 && ( 2 + getLength(k-j, i-j) + dp[j][k] < dp[j][i]) ){
  44.                                                 dp[j][i] = 2 + getLength(k-j, i-j) + dp[j][k];
  45.                                                 ans = String.valueOf((i-j)/(k-j)) +"["+ dpMap.get(leftStr) +"]";
  46.                                         }
  47.                                 }
  48.                                 dpMap.put(temp,ans);
  49.                         }. 一亩-三分-地,独家发布
  50.                 }. from: 1point3acres
  51.                 return dpMap.get(s);. 留学申请论坛-一亩三分地
  52.         } 来源一亩.三分地论坛.
  53. . 1point3acres
  54.         public static void main(String[] arg){
  55.                 System.out.println( sortestEncodeString(arg[0]) );
  56.         }
  57. }
复制代码
回复 支持 1 反对 0

使用道具 举报

我的人缘0
yydcool 发表于 2016-11-15 11:03:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
scoi2003原题
回复 支持 1 反对 0

使用道具 举报

我的人缘0
qiuxuxing007 发表于 2016-11-13 02:07:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
为何会fail, 你第一问做出来了吗?
回复 支持 反对

使用道具 举报

我的人缘0
神罗天征 发表于 2016-11-13 02:14:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同求第二问解法……感觉考了第一题,必有follow up
回复 支持 反对

使用道具 举报

我的人缘0
sccnju 发表于 2016-11-13 02:39:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
搬个板凳等待大神解答第二问。。。
回复 支持 反对

使用道具 举报

我的人缘0
mikeyangh1992 发表于 2016-11-13 02:43:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
前排同关注一下follow-up
回复 支持 反对

使用道具 举报

我的人缘0
slarkzz 发表于 2016-11-13 03:02:56 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同求第二题解法
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
helloc93 发表于 2016-11-13 03:32:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
关注下第二题的解法
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sunnyroom 发表于 2016-11-13 03:45:43 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
qiuxuxing007 发表于 2016-11-13 02:07
为何会fail, 你第一问做出来了吗?

第一问做出来,第二问,真的不会
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sunnyroom 发表于 2016-11-13 03:46:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
aaabcbc 压缩成 3[a]2[bc] 这个例子举的不好,压缩后比压缩前还长,这种情况就不用压缩了,所以,好难好难
回复 支持 反对

使用道具 举报

我的人缘0
hmy0823 发表于 2016-11-13 04:47:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同求follow up问题的解决方法
回复 支持 反对

使用道具 举报

我的人缘0
jiongjiongyoush 发表于 2016-11-13 04:57:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同马克一下。。。。decode string以前刷g onsite面经有人遇到过
回复 支持 反对

使用道具 举报

我的人缘0
a529384424 发表于 2016-11-13 12:59:54 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
mark一下,坐等大神解答
回复 支持 反对

使用道具 举报

我的人缘0
cezheng2 发表于 2016-11-13 13:51:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
先寫一個不嵌套的encode的函數,然後不斷encode直到encode的output和input的字串相等可以嘛?
回复 支持 反对

使用道具 举报

我的人缘0
xiangminxufsu 发表于 2016-11-13 17:00:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
坐等大神来破解 =。=
回复 支持 反对

使用道具 举报

我的人缘0
NotAfraid2009 发表于 2016-11-14 03:04:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
感觉这样应该可行。. 牛人云集,一亩三分地
1: 从一个没折叠的位置开始,从长度为1,一直找到剩下长度的一半,找能折叠的最长的长度
2: 对能折叠的pattern进行递归,继续折叠。
. 留学申请论坛-一亩三分地3: 从下一个没有折叠的位置开始。
感觉写起来也挺麻烦的。
回复 支持 反对

使用道具 举报

我的人缘0
NotAfraid2009 发表于 2016-11-14 04:39:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
    public String encode(String str) {
        if (str == null || str.length() == 0) {
            return "";
        }
        
        int i = 0;
        int j = 0;. 围观我们@1point 3 acres
        String pattern = null;
        StringBuilder builder = new StringBuilder();
        while (i < str.length()) {
            j = 0;
            for (int len = 1; len <= (str.length() - i) / 2 && i + len <= str.length(); len++) {. more info on 1point3acres
                String p = str.substring(i, i + len);
                int cur = i + len;. 1point 3acres 论坛
                while (cur + len <= str.length()) {
                    if (p.equals(str.substring(cur, cur + len))) {
                        if (cur + len > j) {
                            j = cur + len;. from: 1point3acres
                            pattern = str.substring(cur, cur + len);
                        }
                        cur = cur + len;
                    } else {
                        break;
                    }. 留学申请论坛-一亩三分地
                }
            }
            if (j == 0) {. 1point3acres
                builder.append(str.substring(i, i + 1));
                i = i + 1;
            } else {
                int count = (j - i) / pattern.length();
                if (count == 1) {
                    builder.append(encode(pattern));. 1point 3acres 论坛
                } else {
                    builder.append(count).append('[').append(encode(pattern)).append(']');
                }
                i = j;
            }
        }
跟之前说的算法的一样,i表示需要encode的字符串的起始位置,j表示结束位置。
当j大于之前最远的位置(有点贪心的意思),记录找到的pattern。
最后根据j的位置判断如何折叠,如果j的位置为0,遍历过所有长度,说明没有可以折叠的串,i + 1;如果不为0, 就递归当前找到的pattern。
这个作为follow up如果还让完全写出代码,有点过分了,时间肯定不够 =。=
回复 支持 反对

使用道具 举报

我的人缘0
nycowboy 发表于 2016-11-14 04:47:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第二题可以用一个stack就解决了吧,不停地尝试和stack顶部的元素合并
回复 支持 反对

使用道具 举报

头像被屏蔽
我的人缘0
simonwoo 发表于 2016-11-14 12:59:15 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

我的人缘0
Aron930130 发表于 2016-11-15 06:23:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
NotAfraid2009 发表于 2016-11-14 04:39
public String encode(String str) {. visit 1point3acres for more.
        if (str == null || str.length() == 0) {
            ...

这个输入如果是axxxxaxxxxaxxxx,输出的答案不对吧?
回复 支持 反对

使用道具 举报

我的人缘0
Aron930130 发表于 2016-11-15 06:26:32 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Aron930130 发表于 2016-11-15 06:23
这个输入如果是axxxxaxxxxaxxxx,输出的答案不对吧?

哦哦,是我自己看错了...无视我
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-22 19:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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