一亩三分地论坛

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

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

TripAdvisor电面面经

[复制链接] |试试Instant~ |关注本帖
lishusha 发表于 2015-11-5 10:17:30 | 显示全部楼层 |阅读模式

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

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

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

x
感觉这tripadvisor越来越不靠谱了。我几年前还面过他家的daodao组的。最后因为各种原因没去。。。这次猎头再次推荐,本来约了早上9点,等了块半小时没打来。跟猎头问了一下。说reschedule到中午12点。结果11点多的时候猎头打电话又说12点不行,问可不可以下午4点再面。。。。
是一个engineer skype过来直接video call。
先是一些很general的问题。比如,什么是树,什么是二叉树,什么是BST。问BIG-O。还给了一个小trick说如果一个有序数组,从第一个数开始是节点,接下来见的是一个什么样的结构的书。我刚开始理解为要我怎么减一个BST,就说要怎么换root。结果他说不换root,root就是第一个,直接建树。然后我就说只有做子树。他再问这是不是binary tree。我想当然就说不是,这更像是一个linked list。。。。。后来反应过来解释说,也是BT啦,只是不balanced。然后接着问怎么balance这个tree......鐣欏璁哄潧-涓浜-涓夊垎鍦
tree完了又开始问hashtable。什么是好的hash function。BIG-O当然省不了啊。
然后又问stack的基本function, big-o。
然后又问sort的算法我知道什么。各个算法的big-o.我非常囧的说quick sort和merge sort worst case都是O(N^2).结果被鄙视了说merge sort worst case 也是O(nlgn)>..<
接着才进入正题开始敲代码
1. 判断一个string,可不可以变成palindrome string。就是可以任意调换里面的字符,只要能组成一个palindrome string,就return true.
比如: axxba -> true,因为可以变成axbxa
            aaxb-> false
2.给一个节点 class Node{ int value; List<Node> childNodes;}, 计算这个树所有节点的和。
延伸:计算这个树的avg
颜色:计算这个数的 standard diviation(???).给了个公式 sd = sqrt(sum(avg-value)^2)/(count-1)-google 1point3acres
当然也要问BIG-O是什么的。



.鏈枃鍘熷垱鑷1point3acres璁哄潧
. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

1

查看全部评分

6zy 发表于 2015-11-6 12:47:33 | 显示全部楼层
oneshot 发表于 2015-11-6 09:59
请问楼主第一道题判断palindrome的string是如何做的啊? 我只想到了分长度是奇数或者偶数考虑,先把string ...

可以直接用hashset吧,如果set里有这个char就remove,没有就加进去,最后set里面有一个char(对应奇数)或没有char(对应偶数)都算是palindrome。
回复 支持 1 反对 0

使用道具 举报

oneshot 发表于 2015-11-6 09:59:16 | 显示全部楼层
请问楼主第一道题判断palindrome的string是如何做的啊? 我只想到了分长度是奇数或者偶数考虑,先把string专程chars[], 然后排序,是偶数的话,就如果相邻两个不同的话返回false; 是奇数的话,又用了一个hashmap记录出现次数,才判断出是否palindrome。
回复 支持 反对

使用道具 举报

 楼主| lishusha 发表于 2015-11-6 20:37:49 来自手机 | 显示全部楼层
因为我用的c#,所有我是用的dictionay来记每个char的count,然后看奇数count不能超过一个。ls的做法更好更简单些
回复 支持 反对

使用道具 举报

oneshot 发表于 2015-11-6 23:16:28 | 显示全部楼层
6zy 发表于 2015-11-6 12:47
可以直接用hashset吧,如果set里有这个char就remove,没有就加进去,最后set里面有一个char(对应奇数) ...

好方法,我后来也想到了也可以直接用HashMap, Key是出现的字母,Value是出现的次数,最后遍历一遍map中的value,除以2余数为1的个数为0或者1的话就可以变成palindrome。 感觉还是用HashSet更好一些。
回复 支持 反对

使用道具 举报

sevenyunan 发表于 2015-12-21 00:29:47 | 显示全部楼层
你好同学 我想问下那个计算所以节点的合我只知道下面这个version的 但是不知道你那种定义treenode的解法 能不能简略解释下你是怎么解的

public class TreeNode {.1point3acres缃
        int val;. 1point 3acres 璁哄潧
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
                val = x;
        }
}
回复 支持 反对

使用道具 举报

null_point_exc 发表于 2016-11-2 22:51:12 | 显示全部楼层
char[26] map = new char[26]; //O(n). more info on 1point3acres.com

//Hamming Weight Algorithm O(1)
https://en.wikipedia.org/wiki/Hamming_weight  .鏈枃鍘熷垱鑷1point3acres璁哄潧
. more info on 1point3acres.com

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 20:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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