优步面试经历（2018-19年校园实习）

第一轮：

第一轮是在线编码轮，由3个编码问题组成，在90分钟内进行尝试。

问题1：-

在办公室安排的会议持续时间为t，开始时间为0。在两次会议之间，有n个演示文稿的开始和结束时间是给定的，即第i个演示文稿从s[i]开始，在e[i]-1结束。这些演示文稿彼此不重叠。您将获得k，即您可以重新安排的演示文稿的最大数量，保持原始顺序不变。请注意，演示文稿的持续时间不能更改。只能更改开始和结束时间。你的任务是最大限度地延长会议期间没有安排演讲的最长时间。

限制条件：-

1<=t<=100000000

0<=k<=n

1<=n<=100000

e[i]<=s[i+1]，0<=i

s[i]

问题2：-

您将得到一个由0和1组成的nx m网格。值为1表示可以输入该单元格，0表示不允许输入该单元格。从网格的左上角（1，1）开始，必须到达右下角（n，m），这样才能从每个单元格向右或向下移动。你的任务是计算达到目标的方式总数。

限制条件：-

1<=n，m<=10000

问题3：-

给你一个图中的边列表，对于每一对由边连接的顶点，它们之间有两条边，一条曲线边和一条直线边，即元组（x，y，w1，w2）意味着在顶点x和y之间，有一条权重为w1的直线边和一条权重为w2的曲线边。给定两个顶点a和b，必须从a到b穿过一系列边，这样在整个路径中最多可以使用一条曲线边。您的任务是找到满足上述条件的从a到b的最短路径。

第二轮：

这是一个技术回合，持续了大约一个小时。我被要求设计一个蛇和梯子游戏，并用我选择的语言编写相同的代码。我用随机数设计了棋盘，然后我被要求在两个玩家之间玩游戏，我对游戏进行了同样的编码。他给这个问题引入了一个窍门，让我给董事会的难度打分。我认为从开始到结束的最短路径（广度优先搜索），但他说更好的方法是计算从一开始达到特定数字的概率。因此，我使用动态规划来计算达到某个特定数量的概率，其中1<=x<=宣布平局的移动次数的最大上限。然后他问我，他不想要一场只需15步就能结束的比赛，因为这会让比赛变得无聊。所以我被要求计算游戏在15到100步中结束的概率。最后，他让我通过观察球员的位置来判断当时谁处于获胜的位置。他对我的回答感到满意。

第三轮：

这是一个解决问题的回合，持续了75分钟。他问了我一个很复杂的问题。就这样…

有3个整数a，b，w。

有两个方程式——

1. w+a=b
2. a（按位和）b=0；

我得到了w的值，他让我计算出满足这两个方程的对数（a，b）。假设没有溢出。我使用递归+位操作来解决这个问题，他似乎对我的方法很满意，尽管我也需要他的帮助。

附言：3小时后，我接到了一个报价电话。