Duolingo 2025 Research intern Karat 面经

• 1 min 自我介绍

• 15 min 3 道简答题，可以口头回答

• 评价算法是否可行：需求是从一个file里随机选一行, 要求每行选到的概率相同. 

做法 -- 随机挑选一个byte offset, 并在该offset前后找第一个

1. \n

复制代码

• 时间空间复杂度

def function(int x):
          res = 0
         while x > 0:
            if x % 10 == 7:
              res += 1
            x /= 10
          return res

• 对比两个算法, 求时间复杂度,  Followup： 并给出什么情况下使用哪种算法，解释为什么？

- 需求: 给定两个排好序的数组, 问第一个的数组的元素是否全部包含在第二个里
算法1: 把一个数组做成set, 遍历另一个数组, 在set里找.
算法2: 遍历数组1, 在数组2进行binary search.
        A size n, b size m

• 45min Coding 题， 在之前地里出现过， BFS解掉。

there is a 2 x 2 square moving diagonally through the screen.
Every time the square hits a side of the screen, it bounces at the same angle and keeps going. For example, if the screensaver hits the top of the screen at a certain angle, it would be bounced at the same angle it was received to a perceived perpendicular line.
   -------------------------
0              *
1             *|*
2            * | *
3           *  |  *
4          *   |   *
5         *    |    *
6        *     |     *
You are given the screen size, the starting direction, and the starting position of the top-left corner of the square.
Write a function to calculate the minimum amount of steps required for the square to reach any of the corners of the screen. If it never reaches a corner, return null or -1.
   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
--------------------------------------------------------
0 | -  -  -  -  *  *  -  -  -  -  -  -  *  *  -  -  -  - |   
1 | -  -  -  *  *  *  *  -  -  -  -  *  *  *  *  -  -  - |   
2 | -  -  *  *  *  *  *  *  -  -  *  *  *  *  *  *  -  - |   
3 | -  X  X  *  -  -  *  *  *  *  *  *  -  -  *  *  *  - |
4 | -  X  X  -  -  -  -  *  *  *  *  -  -  -  -  *  *  * |   
5 | -  -  -  -  -  -  -  -  *  *  -  - 

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

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

size_2, pos_2_4, "up-left")      ==> 10
screensaver(size_3, pos_3_1, "up-left")      ==> 0
screensaver(size_3, pos_3_2, "down-left")    ==> 0
screensaver(size_3, pos_3_3, "up-right")     ==> 0
screensaver(size_4, pos_4_1, "up-left")      ==> 1
screensaver(size_4, pos_4_2, "down-right")   ==> 0
screensaver(size_5, pos_5_1,  "up-right" )   ==> -1
screensaver(size_5, pos_5_2, "down-right")   ==> 3
screensaver(size_6, pos_6_1, "up-left")      ==> 2304
----------------------------------------------
Complexity variables:
R = number of rows in the screen
C = number of columns in the screen
up right (1, 1) -> down right.  0th row
up left (1, -1) -> down left.  0th row
down right (-1, 1) -> up right. last row
down left (-1, -1) -> up left.  last row
stops at 0th col or last col