爱彼迎 Code challenge 20

两个题时间其实没有很难，但读题其实挺花时间的，如果没有一下子想到怎么做，可能时间会比较紧。
第一题还有顺序的问题，一开始我以为某个词序列乱了就把这个词挑出来加到结果里就好了，后来等我写完了测试，才发现一个词乱了后面的都认为是乱的。建议如果OA 要求不清楚的时候还是先跑几个test cases看看到底是什么情况再做。
吐槽一下第一个题，个人认为，这个description写的语法结构欠缺。出题人想把很多事情在一句话里面描述清楚。然而最后却把一句话的句式结构变得非常复杂，并不能让人很容易理解出题人想要表达的是什么。有些句子的甚至连主语和谓语的使用都有问题，需要多上两边才能明白在说什么。这种情况，如果人与人当面交流的话很容易通过提问来问清楚，但是OA的话有点浪费时间，不能最快的集中注意力去解决真正要解决的问题。
希望贴图能帮助有需要的小伙伴

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一题还是没看懂"i l chee" 算是"i like cheese"的subsequence吗？说的是elements of strings in same order，这和word有什么关系啊，出题的人真是脑子被驴踢了。

第一题的结果不唯一吧，比如“two three one two three” 和 “two three", 那么结果有”one two three“和”two three one“两种？

第二题有nlog(n)甚至linear的算法吗？目前我只想到了n^2的，感觉应该有更优的。。。

leizhao987 发表于 2018-12-28 18:03
第一题的结果不唯一吧，比如“two three one two three” 和 “two three", 那么结果有”one two three“和 ...

第二题是不是O(n^3)? 最多 nC₃ 的组合数结果，那么算法怎么写也得要n^3的复杂度啊

这是开始换新题了么？

我发了一个 DownSequence 问题的O(nlogn)的解法。希望对大家有帮助。求加米。

https://www.1point3acres.com/bbs/thread-468477-1-1.html

第二题有这么复杂么，题意不是说downsequence定长为3了么。如果不是定长，5321算什么呢。定长为3就好做了啊，就是线性的

补充内容 (2019-1-11 15:47):
确实是n2.。。

刚收到OA20，但是邮件里说的只有一题，地里关于20的都是两题，楼主有收到邮件说是只有一题吗？

Baymaxgo 发表于 2019-2-27 05:10
刚收到OA20，但是邮件里说的只有一题，地里关于20的都是两题，楼主有收到邮件说是只有一题吗？

What is the question?

https://www.1point3acres.com/bbs/thread-468477-1-1.html
看见这个帖子给了我很多的其实，看这个帖子的解法最后是维护了两个数组，
一个数组是描述左边比该元素小的元素的个数，另一个数组是描述右边比该元素大的元素的个数，
这句话是什么意思
x0, x1, x2, ..., xi, ...., xn
lessThanfromLeft[i]代表从0到i-1个元素当中，比元素i小的元素个数
同理，
moreThanfromRight[i]代表从i+1到n个元素中，比元素i大的元素个数
这样根据那个帖子里面遍历一遍这两个数组求一个两个数组乘积的sum
如果是这样的话，可以根据插入排序的方法分别求出这两个数组。
这种方法的时间复杂度还是nlgn，但是理解上来稍微简单一些，等分超过10分，我就写代码。lol