推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1366|回复: 16
收起左侧

刚刚 阅后即焚 电面

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

2016(10-12月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
好想去snapchat。。。面的时候有点紧张了。。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
一个ABC的妹子吧应该,之前在linkedin查是standford cs的。。。第一题 BigInt 做multiply,暗自窃喜。半个小时结束了之后 噩梦开始:
第二题就是有向图 有没有cycle。。。楼主之前面经看到这道题,但不太熟,之前又geekfor上面的代码 差不多搞懂了吧,然后这题好像不用写代码,就讨论,然后就怎么也讨论不出来啊。。。妹子continue 不懂我在说什么。。我好像也不太懂我在说什么,我就根据http://www.geeksforgeeks.org/detect-cycle-in-a-graph/上的代码:。妹子一直质疑为什么要用两个数组,我觉得一个就可以,就一直讨论讨论讨论,她也不知道我再说什么。。我也找不出一个反例反驳她。。然后都一个多小时 还在讨论。。。最后就草草问了两个问题 就结束了。。估计是挂了。。。. From 1point 3acres bbs
-google 1point3acres
不过哪位大神来给我解答解答 这有向图,到底是咋个回事。。。不能只用一个数组吗?只用recur? 到后面我也找不到反例。。。只能说 好吧,看来可以用一个。。。但心里是不服气的啊,这geek上的代码还能错了?。。。。

哎 攒攒rp吧。。。patpat。。。
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
    if(visited[v] == false)
    {
        // Mark the current node as visited and part of recursion stack. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        visited[v] = true;
        recStack[v] = true;

        // Recur for all the vertices adjacent to this vertex
        list<int>::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
                return true;
            else if (recStack[*i])
                return true;
        }

    }
    recStack[v] = false;  // remove the vertex from recursion stack
    return false;
}

// Returns true if the graph contains a cycle, else false.
// This function is a variation of DFS() in [color=rgb(0, 130, 0) !important][size=1em]http://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclic(). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
{
    // Mark all the vertices as not visited and not part of recursion
    // stack
    bool *visited = new bool[V];. more info on 1point3acres.com
    bool *recStack = new bool[V];. more info on 1point3acres.com
    for(int i = 0; i < V; i++)
    {. 1point 3acres 璁哄潧
        visited = false;
        recStack = false;
    }
.鐣欏璁哄潧-涓浜-涓夊垎鍦
    // Call the recursive helper function to detect cycle in different
    // DFS trees
    for(int i = 0; i < V; i++)
        if (isCyclicUtil(i, visited, recStack))
            return true;

    return false; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.



补充内容 (2016-11-5 08:02):
刚收到on-site 消息了。。。。这也太快了。。。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

灰溜溜溜溜 发表于 2016-11-5 07:21:44 | 显示全部楼层
用一个int数组就行吧
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-11-5 07:32:03 | 显示全部楼层
哈。楼主的妹子跟我面试的时候一个妹子~。
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-11-5 07:53:28 | 显示全部楼层
leixiang5 发表于 2016-11-5 07:32
哈。楼主的妹子跟我面试的时候一个妹子~。
.1point3acres缃
妹子怎么样啊。。。。&#128514;&#128514;。。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-11-5 07:54:40 | 显示全部楼层
wwtwxlwjh 发表于 2016-11-5 07:53
妹子怎么样啊。。。。&amp;#128514;&amp;#128514;。。。
. visit 1point3acres.com for more.
什么怎么样呀。multiply没debug出来。挂了。名字k开头的吧~
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-11-5 07:56:49 | 显示全部楼层
leixiang5 发表于 2016-11-5 07:54
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷什么怎么样呀。multiply没debug出来。挂了。名字k开头的吧~

表情竟然显示不出来。。。。我开始押题就押bigint。。。结果竟然还有一道。。。。
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-11-5 07:57:40 | 显示全部楼层
灰溜溜溜溜 发表于 2016-11-5 07:21. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
用一个int数组就行吧

找到的代码都用两个数组的。。。哪位大神用一个数组 辛苦po上来 学习学习 O(∩_∩)O~~
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-11-5 07:59:28 | 显示全部楼层
wwtwxlwjh 发表于 2016-11-5 07:56
表情竟然显示不出来。。。。我开始押题就押bigint。。。结果竟然还有一道。。。。

你做太快了吧。所以再给你出了一道
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-11-5 08:02:13 | 显示全部楼层
leixiang5 发表于 2016-11-5 07:59
你做太快了吧。所以再给你出了一道

竟然过了。。。。。
回复 支持 反对

使用道具 举报

灰溜溜溜溜 发表于 2016-11-5 08:17:25 | 显示全部楼层
wwtwxlwjh 发表于 2016-11-5 08:02
竟然过了。。。。。

卧槽 半小时出结果?
回复 支持 反对

使用道具 举报

Toby 发表于 2016-11-5 08:27:52 | 显示全部楼层
有向图查环肯定用topological sort。DFS也行,比较麻烦
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-11-5 08:44:12 | 显示全部楼层
灰溜溜溜溜 发表于 2016-11-5 08:17
卧槽 半小时出结果?
. 1point 3acres 璁哄潧
可能不到半小时。。。。
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-11-5 08:44:40 | 显示全部楼层
Toby 发表于 2016-11-5 08:27
有向图查环肯定用topological sort。DFS也行,比较麻烦

哎 有环问题 搞不懂啊。。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-11-5 09:00:58 | 显示全部楼层
wwtwxlwjh 发表于 2016-11-5 08:44
可能不到半小时。。。。
. From 1point 3acres bbs
妹子速度快。一面完了就submit feedback
回复 支持 反对

使用道具 举报

剪时光 发表于 2016-11-5 10:06:09 | 显示全部楼层
请问lz  big int multiply是指 lc 43. Multiply Strings 吗? 谢谢分享!
回复 支持 反对

使用道具 举报

 楼主| wwtwxlwjh 发表于 2016-11-5 10:13:29 | 显示全部楼层
剪时光 发表于 2016-11-5 10:06
请问lz  big int multiply是指 lc 43. Multiply Strings 吗? 谢谢分享!
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
对。。。
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-11-5 11:06:06 | 显示全部楼层
查环 第一个visit数组是为了节省时间用的,遍历过了可以不用再遍历,其实你就用Instack 然后恢复现场就可以了。。只是这样比较慢,
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-21 05:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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