一亩三分地论坛

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

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

Tripadvisor 电面

[复制链接] |试试Instant~ |关注本帖
zhouyoung1124 发表于 2015-12-8 23:29:30 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@TripAdvisor - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
这几天面的,问问大家tripadvisor电面多久出结果?谢拉谢拉!
一道题,火柴棍拼图数正方形拼图图片链接:http://matchstickpuzzles.blogspot.com/2011/06/55-4x4-square-how-many-squares.html
把垂直的棍子和水平的棍子抽象成两个二位数组 boolean[][] ver boolean hor[][],然后算两个dp数组 int[][]dpV(垂直方向) int[][]dpH(水平方向),其中每个值表示截至当下点有几根连续木棍,最后对dpH逐点验证是否能以该棍为左上角第一根水平棍构成长度为1~n的正方形。
面试过程中写的代码其实有几个小bug,不过我和面试官当下都没有发现,只是探讨了下看思路正确就没有深究,我后来下了自己重新测试了下,把代码改好然后发回给了面试官。
代码如下:
public int countSquare ( boolean[][] ver , boolean[][] hor ) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
    if ( ver == null || hor == null || ver.length == 0 || ver[0].length == 0 || hor.length == 0 || hor[0].length == 0 ){
        return 0;
    }
    int[][] dpV = new int[ ver.length ][ ver[0].length ];-google 1point3acres
    int[][] dpH = new int[ hor.length ][ hor[0].length ];
    int res = 0;
    for ( int j = 0; j < dpV[0].length; ++j  ) {
        for ( int i = 0; i < dpV.length; ++i ) {
            if ( ver[j] ) {
                dpV[j] = i == 0 ? 1 : (dpV[i - 1][j] + 1);
            } else {
                dpV[j] = 0;
            }
        }
    }
    for ( int i = 0; i < dpH.length; ++i  ) {
        for ( int j = 0; j < dpH[0].length; ++j ) {
            if ( hor[j] ) {
                dpH[j] = j == 0 ? 1 : (dpH[j - 1] + 1);
            } else {
                dpH[j] = 0;
            }. visit 1point3acres.com for more.
        }
    }

    for ( int i = 0; i < dpH.length; ++i ) {
        for ( int j = 0; j < dpH[0].length; ++j ) {
            for ( int l = 1; l <= Math.min(dpH[0].length - j , dpV.length - i ) ; ++l  ){
                if ( dpH[ l + j - 1 ] >= l && dpH[i + l][ l + j - 1 ] >= l && dpV[i + l - 1][j ] >= l && dpV[ i + l - 1 ][ l + j ] >= l ) {
                        ++res;
                }
                if ( !(dpH[ l + j - 1 ] >= l) ) {
                    break;
                }
             }
        }
    }
    return res;
}

若图形为n*n 则该算法时间复杂度O(n*n*n). From 1point 3acres bbs
总体比我想象的略难。这题虽然思路不是太难想到,但因为两个二位矩阵的input长宽一个是n*(n+1)一个是(n+1)*n所以稍微有点tricky
面过的大神记得说一下电面多久出结果哈!



. visit 1point3acres.com for more.

评分

1

查看全部评分

oneshot 发表于 2015-12-9 00:10:35 | 显示全部楼层
楼主是投的是哪个职位?是一个中国人面的吗?我电面也是给的这个题...
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-12-9 04:54:10 | 显示全部楼层
oneshot 发表于 2015-12-9 00:10. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主是投的是哪个职位?是一个中国人面的吗?我电面也是给的这个题...

对的,我记得好像姓胡。
你电面完多久给的回音?
回复 支持 反对

使用道具 举报

oneshot 发表于 2015-12-9 05:28:12 | 显示全部楼层
zhouyoung1124 发表于 2015-12-9 04:54
对的,我记得好像姓胡。. 1point 3acres 璁哄潧
你电面完多久给的回音?
-google 1point3acres
HR还没有回复, 感恩节前一周面的,估计是挂了,我是用DFS直接做的,而且建立的二维矩阵是maxtix[j] = 1 如果横竖的火柴棍有交点,matrix[j] = 0如果没有交点,然后输入做的DFS。

补充内容 (2015-12-9 06:17):
写错了,是设定matrix[j] = 1如果横竖的火柴棍有交点,matrix[j] = 0如果没有交点。然后对每一个等于1的位置(i, j), 找(i + xLen, j) , (i, j + yLen), (i + xLen, j + yLen)这三点是否值也是1。
回复 支持 反对

使用道具 举报

oneshot 发表于 2015-12-9 06:26:31 | 显示全部楼层
oneshot 发表于 2015-12-9 05:28
HR还没有回复, 感恩节前一周面的,估计是挂了,我是用DFS直接做的,而且建立的二维矩阵是maxtix[j] = 1  ...

matrix[j]
回复 支持 反对

使用道具 举报

gzwenyue 发表于 2015-12-11 05:54:36 | 显示全部楼层
楼主有消息了么?
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-12-12 02:56:28 | 显示全部楼层
gzwenyue 发表于 2015-12-11 05:54
楼主有消息了么?

电面后第三天给的feedback,下周onsite
回复 支持 反对

使用道具 举报

xuxinzhu0081 发表于 2015-12-12 14:22:30 | 显示全部楼层
直接onsite吗 我为什么还给了coding assignment?
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-12-13 10:02:05 | 显示全部楼层
xuxinzhu0081 发表于 2015-12-12 14:22
直接onsite吗 我为什么还给了coding assignment?

不晓得啊,可能因为我和他们说我想速度解决不像拖到年后,,,
回复 支持 反对

使用道具 举报

sevenyunan 发表于 2015-12-13 21:20:10 | 显示全部楼层
请问一下你申请的是什么职位 ?
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2015-12-14 00:41:26 | 显示全部楼层
我不知道是哪个组其实,好久以前做过一个OA...
回复 支持 反对

使用道具 举报

sjmrday 发表于 2016-1-30 14:06:08 | 显示全部楼层
楼主后来拿到offer了嘛?
回复 支持 反对

使用道具 举报

 楼主| zhouyoung1124 发表于 2016-2-1 09:40:27 | 显示全部楼层
sjmrday 发表于 2016-1-30 14:06
楼主后来拿到offer了嘛?

没有,去了onsite,面试体验和彼此的印象都不太好。
后来去了别家
回复 支持 反对

使用道具 举报

bbmbill 发表于 2016-10-10 01:06:58 | 显示全部楼层
问一下楼主这个火柴棍抽象成二维数组是如何抽象的啊 谢谢~
回复 支持 反对

使用道具 举报

liujiajunwin 发表于 2016-10-21 04:29:37 | 显示全部楼层
楼主能不能再详细介绍下onsite问的题目啊?马上也要去onsite了,求点经验~~
回复 支持 反对

使用道具 举报

bbmbill 发表于 2016-10-21 10:03:13 | 显示全部楼层
liujiajunwin 发表于 2016-10-21 04:29
楼主能不能再详细介绍下onsite问的题目啊?马上也要去onsite了,求点经验~~

楼上几号去onsite?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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