非科班出生，面鹅厂暑期实习生

[alphaG]

面微信支付，一面还行，二面上来就问整型无序双向链表能不能转排序二叉树，我是真不会呀，暑期实习这么难吗,有没有鹅厂大佬，求推荐适合小弟的岗位

[easylee]

数据结构必须会，其中链表和树是最常考的。

话说非科班还拿到了面试机会，看来简历挺漂亮啊！

[lhx2008]

一面过了就行，过多一段时间有其他组捞你，至于问不问算法，问多难这个看运气了，WXG 是最难的

[rapiz]

面你这个算很简单的了。我一面就被扔了四道算法题，时间空间紧到我一般认为不可行。

[ekuso]

wxg 的要求更高吧

[alphaG]

@easylee 末流 211 小硕一枚，菜到扣脚，我简直自不量力

[alphaG]

@rapiz 看来我一面真的走了狗屎运

[alphaG]

@lhx2008 谢谢，我还要加把劲

[xupefei]

这面试题不是很难，lz 估计没刷题。
首先进行链表 inplace 排序，比如用 quick sort 。
然后是构建二叉树。首先用快慢指针找到中间节点，然后递归左半边和右半边。

两道题都是 leetcode 原题。

[alphaG]

@xupefei 我就刷过 20 道牛客，leetcode 真还没刷过，感谢提醒

[JerryCha]

？不懂就问，能不能直接一个一个从链表里读构建一个 BST

[hhyvs111]

微信这个操作正常，以前面了三轮，每一面都是上来三道编程题，半小时昨晚

[alphaG]

@hhyvs111 你们都太强了 8

[DevRoss]

WXG 的校招更难，面完部门还有几轮面委会。真正的过五关斩六将。🐶

[alphaG]

@DevRoss 层主已经进 WXG 了吗，好强啊，膜拜一下

[coer]

有序双向链表可以构造成排序二叉树，就是一个递归，leetcode 原题，不过无序链表首先得排序，链表的排序比如用自低向上的归并。

[xupefei]

@JerryCha 可以，从小到大一个一个挑出来，构造一个非常不平衡的二叉树。复杂度 n^n 。

[fzz]

本科非科班连续挂了两次 我是真的菜。

[lihongming]

为何要先排序？又没要求平衡二叉树，直接用第一个节点做 root，然后逐个上树不就好了？时间复杂度 O(NlogN)

当初学 BST 的时候，老师就说可以用于排序。

[CismonX]

楼主的简历应该是比较优秀了。我是本科非科班，春招和秋招都没拿到鹅厂的笔试机会，而且我觉得如果我是读了研的非科班应该更没机会😥

[DamienS]

@lihongming worst case 不是 nlogn 吧。假设这链子已经从小到大 sort 好了，你不是一直往树右边加么，那不 n^2 了。