Duolingo Karat面经（汇总3道coding+6道简答题）

duolingo实习第一轮vo（karat）面经，这里汇总一下地里面出现过的三道coding题（我面到的其中第二题），以及六道简答题（我面到的后三道）。求米！
（以下来源地里今年和去年的面经 + 我和朋友的面经）


Coding 1:

You are reading a Build Your Own Story book. It is like a normal book except that choices on some pages affect the story, sending you to one of two options for your next page.
The choices are provided in a list, sorted by the page containing the choice, and each choice has two options of pages to go to next. In this example, you are on page 3, where there is a choice. Option 1 goes to page 14 and option 2 goes to page 2.
choices = [[3, 14, 2]] => [current_page, first_choice, second_choice]
You start reading at page 1 and read forward one page at a time unless you reach a choice or an ending.
You really love this book and so you decide to read all possible story sequences. You notice that you are reading some pages more than others, so you want to find out which page you have read the most often when you read every storyline that leads to an ending.
You set some rules for your reading to avoid repeating pages too often. These rules are:
1) All storylines start at page 1.
2) Within any one storyline, you will never make the same choice twice (you may choose the other option)
3) If you reach a choice where you've already made both choices, you will not reach an ending, so this is not a valid storyline.
Given a list of endings and a list of choices with their destinations, return the page which was read the most often, as well as the number of times it was read. If multiple pages were read the same number of times, you may return any of them. If there are no valid storylines, return -1.
Example:
endings1 = [5, 10]
choices1_1 = [[3, 7, 9], [9, 10, 8]]
1 -> 2 -> 3(choice) -> 7 -> 8 -> 9(choice) -> 10(ending)
          |                      |
          |                      8 -> 9(choice, can't repeat 8) -> 10
          9(choice) -> 10(ending)
          |
          8 -> 9(choice, can't repeat 8) -> 10
All Storylines:
1->2->3->7->8->9->10
1->2->3->7->8-&

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

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

sightseeing(trails2, attractions2_1) => True
sightseeing(trails2, attractions2_2) => False
sightseeing(trails2, attractions2_3) => True
sightseeing(trails2, attractions2_4) => True
Complexity Variable:
n = number of trails


Duolingo的karat都是原题，准备下就好了，全部是dfs+backtracking解决。我抽到第二题，test case就只有底下列出来的两个，只要能过就行。我朋友抽到的第三题，test case也是只有列出来的那7个。


简答题6道：

1. 评价算法是否可行：需求是从一个file里随机选一行, 要求每行选到的概率相同. 做法 -- 随机挑选一个byte offset, 并在该offset前后找第一个 `\n`
2. 求算法复杂度：
需求: 求一个int里有多少个7
def function(int x):
          res = 0
         while x > 0:
            if x % 10 == 7:
              res += 1
            x /= 10
          return res
3. 对比两个算法, 求时间复杂度, 并给出什么情况下使用哪种算法(没说考虑空间复杂度)
- 需求: 给定两个排好序的数组, 问第一个的数组的元素是否全部包含在第二个里
算法1: 把一个数组做成set, 遍历另一个数组, 在set里找.
算法2: 遍历数组1, 在数组2进行binary search.

4. 评价算法是否可行：需求是reverse array in-place，方法 - loop through array，将每个element和它的mirror element做swap，例如第一个和最后一个，第二个和倒数第二个
5. 问以下需求改用什么算法解决：
一共有P个人，还有一个作为target的人，给你一个function x可以返回任意两个人互相喜欢的概率，且它为O(1)
需求是得到和target互相喜欢概率最大的N个人，且按照概率从大到小排序。
需给出数据结构，算法，时间空间复杂度
6. 求以下方法的复杂度：具体code这里不写了，就是一个简单的binary tree preorder traversal


总体面试体验很好，抽到一个白人大哥（可能是俄罗斯）面试，全程反馈很好，没什么口音。朋友抽到印度人，口音非常重。
流程是1分钟自我介绍，10分钟3道简答题，剩下时间coding+how to optimize+time/space complexity，一共一小时

请问coding 2的思路~

匿名用户 发表于 2022-11-12 21:40
三题都是dfs就可以了

okok，不过时间复杂度怎么分析呢，感觉有点复杂。。

匿名用户 发表于 2022-11-12 21:27
请问可以分享下三道coding的思路吗

三题都是dfs就可以了

谢谢分享！zszszszs

楼主面的SDE还是Research Intern?

cuirx 发表于 2022-10-03 09:23:41
楼主面的SDE还是Research Intern?

sde intern

他們似乎是有個題庫，總體解法差不多（dfs），三道小問題的知識點也差不多，雖然我的題不在樓主這個範圍裡面，但是感覺總的來說解法都是一樣的，樓主的整理很有參考價值～

感谢楼主分享！！

请问可以分享下三道coding的思路吗