一亩三分地论坛

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

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

刚刚 阅后即焚 电面

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

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

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

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

x
好想去snapchat。。。面的时候有点紧张了。。。
一个ABC的妹子吧应该,之前在linkedin查是standford cs的。。。第一题 BigInt 做multiply,暗自窃喜。半个小时结束了之后 噩梦开始:
第二题就是有向图 有没有cycle。。。楼主之前面经看到这道题,但不太熟,之前又geekfor上面的代码 差不多搞懂了吧,然后这题好像不用写代码,就讨论,然后就怎么也讨论不出来啊。。。妹子continue 不懂我在说什么。。我好像也不太懂我在说什么,我就根据http://www.geeksforgeeks.org/detect-cycle-in-a-graph/上的代码:。妹子一直质疑为什么要用两个数组,我觉得一个就可以,就一直讨论讨论讨论,她也不知道我再说什么。。我也找不出一个反例反驳她。。然后都一个多小时 还在讨论。。。最后就草草问了两个问题 就结束了。。估计是挂了。。。

不过哪位大神来给我解答解答 这有向图,到底是咋个回事。。。不能只用一个数组吗?只用recur? 到后面我也找不到反例。。。只能说 好吧,看来可以用一个。。。但心里是不服气的啊,这geek上的代码还能错了?。。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
.鏈枃鍘熷垱鑷1point3acres璁哄潧
哎 攒攒rp吧。。。patpat。。。
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{. 1point3acres.com/bbs
    if(visited[v] == false)
    {
        // Mark the current node as visited and part of recursion stack
        visited[v] = true;
        recStack[v] = true;. From 1point 3acres bbs

        // 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];. visit 1point3acres.com for more.
    bool *recStack = new bool[V];
    for(int i = 0; i < V; i++)
    {
        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))
. Waral 鍗氬鏈夋洿澶氭枃绔,            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
哈。楼主的妹子跟我面试的时候一个妹子~。

妹子怎么样啊。。。。&#128514;&#128514;。。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-11-5 07:54:40 | 显示全部楼层
wwtwxlwjh 发表于 2016-11-5 07:53
妹子怎么样啊。。。。&amp;#128514;&amp;#128514;。。。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
什么怎么样呀。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. 鍥磋鎴戜滑@1point 3 acres
你做太快了吧。所以再给你出了一道
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
竟然过了。。。。。
回复 支持 反对

使用道具 举报

灰溜溜溜溜 发表于 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.1point3acres缃
卧槽 半小时出结果?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
可能不到半小时。。。。
回复 支持 反对

使用道具 举报

 楼主| 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 然后恢复现场就可以了。。只是这样比较慢,
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 21:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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