DoorDash计算机科学面试真题

职位分类
全部
数据科学
数据分析
计算机科学
人工智能
产品经理
BQ
面试题
全部(64)
Coding(18)
System Design(7)
Algorithm(30)
Ood(0)
高频题(1)
全部(64)
Coding(18)
System Design(7)
Algorithm(30)
Ood(0)
高频题(1)
1.K-anagram
2.Nested transaction design
3.Serialize and deserialize a binary tree
4.Min time from top left to bottom right
5.Return all timestamp
6.Design donation system
7.Max job profit
8.Min number of operations to update menu
9.Remove smallest peaks in order
10.Leetcode 875
11.Leetcode 209
12.Leetcode 778
13.Leetcode 286
14.Leetcode 1235
15.Opening and closing time for a restaurant
16.Circuit breaker design
17.Number of requests dropped
18.Max profit for cooking
19.Balls left after collision
20.Number of drop in a gateway
21.Leetcode 224
22.Update menu
23.Similar restaurants
24.Find min path to all shops
25.API delimiter
26.Delivery Schedule
27.Asteroid Collision
28.消消乐
29.Similar restaurants
30.Design sonating system
31.Possible Bipartition
32.LeetCode 23
33.LeetCode 24
34. LeetCode 82
35.LeetCode 83
36.LeetCode 102
37.LeetCode 107
38.LeetCode 199
39.LeetCode 314
40.LeetCode 235
41.LeetCode 84
42.LeetCode 854
43.LeetCode 859
44.design tweet search
45.LeetCode826
46.find the length of the longest path that has the same values
47.LeetCode 124 变形题
48.LeetCode 838
49.LeetCode 1347
50.LeetCode 588
51.LeetCode 32
52.打印元素
53.两个数组的重合区域
54.设计slack
55.LeetCode 859
56.设计trie tree file system
57.设计用户评论系统
58.leetcode317
59.设计donation app
60.leetcode2360
61.leetcode2385
62.leetcode1268
63.leetcode36
64.leetcode37
1. K-anagram
k-anagram,换位置(swap)(最多换两个)和换字母(change)各一道
2. Nested transaction design
开放式问题,要求设计一个类似于redis的db api可以支持get、put和nested transaction。
3. Serialize and deserialize a binary tree
serialize and deserialize a binary treetree - left, right, val
4. Min time from top left to bottom right
路径问题,给你个matrix MxN, 每个entry (i,j) 所含的数字t表示当时间大于等于t的时候可以通过这个位置,左上角t永远为1,求最早可以到右下角的时间
5. Return all timestamp
第一步需要从input中提取 start and end timstamp。input 又一个gap。 然后返回一个list 包含 所有的时间节点 from start 到end。
 比如 start : 1 end :10 gap: 3,返回 1, 4, 7, 1‍‍‌‌‌‌‍‌‍‍‍‍‍‍‍‍‍‌‌‍0
6. Design donation system
考的是捐款系统,非常考验inject certain failure后系统还能handle traffic。
7. Max job profit
考的是start end time 里maximum job profit
8. Min number of operations to update menu
具体就是有两个menu, 都是用treeNode (里面存key value pair)表示, 来区别从previous menu 变到existing menu 要多少步操作
9. Remove smallest peaks in order
Remove Smallest Peaks in Order(https://binarysearch.com/problems/Remove-Smallest-Peaks-in-Order)
10. Leetcode 875
珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。
 
 珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。  
 
 珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。
 
 返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

11. Leetcode 209
给定一个含有n个正整数的数组和一个正整数target。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[nums 1, nums 1+1, ..., nums r-1, nums r],
并返回其长度。如果不存在符合条件的子数组,返回 0 。
12. Leetcode 778
在一个 n x n 的整数矩阵 grid 中,每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。
 
 当开始下雨时,在时间为 t 时,水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台,但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离,也就是默认在方格内部游动是不耗时的。当然,在你游泳的时候你必须待在坐标方格里面。
 
 你从坐标方格的左上平台 (0,0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。
13. Leetcode 286
给定一个矩阵,有门,有空房,有障碍物。求出每个空房到离它最近的门的距离。如果到不了,就用INF表示。
14. Leetcode 1235
你打算利用空闲时间来做兼职工作赚些零花钱。
 
 这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]。
 
 给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大报酬。
 
 注意,时间上出现重叠的 2 份工作不能同时进行。
 
 如果你选择的工作在时间 X 结束,那么你可以立刻进行在时间 X 开始的下一份工作。
15. Opening and closing time for a restaurant
饭店都有开门时间和关门时间,要写一个function,输入是开门和关门的时间,字符串, 12小时制 例如 ['mon 11:22 am', 'mon 12:14 pm'] 给出这个时间段中所有的以5min为间隔的时间点, 时间点必须能被5整除,格式是 第一位是 1-7 代表周一到周日,后面4位是24小时制的时间,对于前面例子的输入,输出是 [11125, 11130, 11135, 11140, 11145, 11150, 11155, 11200, 11205, 11210]注意点就是后面两位是60进1,‍‍‌‌‌‌‍‌‍‍‍‍‍‍‍‍‍‌‌‍中间两位是24进一,edge case 12am 在24小时制里是00:00, 代表星期的第一位超过7要重新回到1(星期日晚上开门,星期一凌晨关门的情况)
16. Circuit breaker design
大概就是一个circuit breaker有Open和Closed两个状态,实现Open和Closed的转化 (open到close可以是手动人工操作)需要设计函数然后测试
17. Number of requests dropped
给一个request time数组例如【1,1,1,1,2,2,2,3,3,3】,数组里的数代表request到达的时间,有一个rate limit rule,1秒内请求不能多于三个,多的request会被drop,10秒内不能多于20个,60秒内不能多于60个,求一共有多少request被drop,重复drop的request算一个。
18. Max profit for cooking
Round 1
 
 给三个list (料理难度,料理利润,厨师技能)
 
 一个厨师只能煮难度比他技术还低(或相等)的菜 (每个厨师只煮一道)
 
 返回 所有厨师的最大利润
 
 难度 = [2,4,6,8,10]
 
 $ = [20, 30, 40, 50, 60]
 
 技术 = [4, 5, 6, 7]
 
 返回 140 (30 + 30 + 40 + 40)
 
 Round 2
 
 给一个2维的String array, 每一个项目里面存了{餐厅名字,价格,相关性,种类}
 
 sort条件, 每一页显示多少间餐厅, 第几页
 
 按照imput 要求sort完
 
 返回指定页数的所有餐厅名称
 
 Follow up: 如果单一页面只‍‍‌‌‌‌‍‌‍‍‍‍‍‍‍‍‍‌‌‍能显示同一种类一次 重复的要等到下一页 才能显示
19. Balls left after collision
输入:几个球在一直线上运动,两个长度相同的Array,一个代表方向[1, 1, 1, -1], 1 向右走,-1向左,一个代表强度[5, 2, 1, 3],碰撞后强度大的剩下,相同强度两个球都损坏,问最后剩下哪几个球(返回index list)。
20. Number of drop in a gateway
有个gateway,如下规则:input是排序号的request时间戳,比如【1,1,1,1,2,3,4,5】
 
 如下规则:
 
 1. 1秒不能超过3个请求
 
 2. 10秒内不能超过20个请求
 
 3. 60秒内不能超过60个请求
 
 如果超过任意一个规则,那这个request会被drop。求drop的总数。
 
 比如上面的input,答案就是1,因为时间戳为1的请求有4个,第4个会被drop。
21. Leetcode 224
给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
 
 注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。
22. Update menu
菜单更换
 
 树节点包含key, value, children=list<Node>
 
 给两个菜单求update次数
 
 要求
 
 1. key相同value不同算一次update
 
 2. key不同算delete该‍‍‌‌‌‌‍‌‍‍‍‍‍‍‍‍‍‌‌‍节点以及所有children
 
 3. 新增节点算add
 
 4. 减少节点算delete
23. Similar restaurants
1. Definition: Similar restaurants
 
Two restaurants R1 and R2 are similar if we can swap a maximum of two letters (in different positions) of R1, so that it equals R2.
 
For example, "pot" and "top" are similar (swapping at positions 0 and 2).
 
Input: "hotpot", ["hottop", "hotopt", "hotpit", "httoop", "hptoot"]
 
Output: ["hottop", "hotopt", "hptoot"]
 
Follow-up
 
Given a restaurant name, find other restaurants in the list that are k-anagrams with each other. A name is a k-anagram with another name if both the conditions below are true:
 
 The names contain the same number of characters.
 
The names can be turned into anagrams by changing at most k characters in the string
 
name = “omega grill”, k = 2 and list = [“jmega frill”], “omega grill” is k-anagram with “jm‍‍‌‌‌‌‍‌‍‍‍‍‍‍‍‍‍‌‌‍ega frill” since they contain same number of characters and you can change ‘o’ to ‘j’ and ‘g’ to ‘f’
24. Find min path to all shops
大概就是一个二维数组表示的二维平面有一些炸弹,然后有些商店,有一些空地,问找出某个空地到所有商店距离和最短
25. API delimiter
类似API delimiter
 
要求每10s内最多call某个API 10次,每30s内最多call API 20次,每60s内最多call API 50次(具体数字忘了,编的)。超过限制的APIcall直接被拒绝
 
 然后给一个stream,问这个stream,会call API的共有多少个
26. Delivery Schedule
At DoorDash, many deliveries are scheduled well in advance. To improve our assignment rate, we want to enable dashers to claim these scheduled deliveries early. However, we noticed that certain dashers perform better, and want to reward them with a better selection. As a simple solution, we will introduce open windows for when deliveries will appear for a particular dasher. Below are the following requirements.
 
1。 deliveries scheduled two days or further into the future should never be available
 
2。 high tier dashers can see all of next day deliveries if the current time is 18:00 or later
 
3。 all dashers can see all of next day deliveries if the current time is 19:00 or later
 
4。 all dashers can see same day deliveries anytime
 
Follow up one:
A store could have a preferred list of dashers, which could see all of next day deliveries if the current time is 17:00 or later
 
Follow up two:
Some deliveries prefer bike vs car, which adds several more requirements:
 
1。 No dasher with a car should see a delivery that only allows bike
 
2。 No dasher with a bike could see a delivery that only allows car
 
3。 I‍‍f a dasher on bike, they could see all deliveries of the next day if the current time is 16:00pm
 
4。 If a dasher on car, for deliveries that allow both car and bike, the dasher could only see them after 19:00
27. Asteroid Collision
We are given an array asteroids of integers representing asteroids in a row.
 
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
 
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
 
 Example 1:
 
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:
 
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Example 3:
 
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
 
 
Constraints:
 2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
28. 消消乐
example1: [5, 10, -5], output: [5, 10] example2: [5, 10, -15], output: [-15]
 
正数代表向右走,负数代表向左走,如果撞击,小的那个消失, 如果两个数一样, 都消失,输出最后结果
 
Follow up: 如果有0代表是另一个方向, 怎么改代码
 
example1: [5, 0, 10, 0, -5], output: [0, 0, 5, 10] ,因为5 和 10是向右走,越过了0
 
example2: [5, 0, -10, 0, 5, -2, 0], output: [-10, 0, 0, 5], -10向左走,越过了0
29. Similar restaurants
Similar restaurants, 输入 name: hotpot, array = ["hptoot", "hoptot"]
最多有一对character可以换,求输出l‍‍‌‌‌‌‍‍‍‍‍‌‌‌‌‍‍‌‍‌ist of string of similar restaurants
30. Design sonating system
Donating system, especially concern at scale
31. Possible Bipartition
We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.
Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Example 1:
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4] and group2 [2,3].
 
Example 2:
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
 
Example 3:
Input: n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false
 
 
Constraints:
1 <= n <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= dislikes[i][j] <= n
ai < bi
 
All the pairs of dislikes are unique.
32. LeetCode 23
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
33. LeetCode 24
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

 

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

 

Constraints:

  • The number of nodes in the list is in the range [0, 100].
  • 0 <= Node.val <= 100
34.  LeetCode 82
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

 

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

 

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.
35. LeetCode 83
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

 

Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

 

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.
36. LeetCode 102
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
37. LeetCode 107
Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
38. LeetCode 199
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

 

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
39. LeetCode 314
Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

 

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Example 2:


Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]
Example 3:


Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]
 

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
40. LeetCode 235
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

 

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.
41. LeetCode 84
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

 

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

 

Constraints:

  • 1 <= heights.length <= 105
  • 0 <= heights[i] <= 104
42. LeetCode 854
Strings s1 and s2 are k-similar (for some non-negative integer k) if we can swap the positions of two letters in s1 exactly k times so that the resulting string equals s2.

Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.

 

Example 1:

Input: s1 = "ab", s2 = "ba"
Output: 1

Example 2:

Input: s1 = "abc", s2 = "bca"
Output: 2

 

Constraints:

  • 1 <= s1.length <= 20
  • s2.length == s1.length
  • s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.
  • s2 is an anagram of s1.
43. LeetCode 859
Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

  • For example, swapping at indices 0 and 2 in "abcd" results in "cbad".
 

Example 1:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

Example 2:

Input: s = "ab", goal = "ab"
Output: false
Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.

Example 3:

Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.

 

Constraints:

  • 1 <= s.length, goal.length <= 2 * 104
  • s and goal consist of lowercase letters.
44. design tweet search
有stream flow 输入最新的tweet,100M tweets per our。需提供keyword search
45. LeetCode826
You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:

  • difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and
  • worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).
Every worker can be assigned at most one job, but one job can be completed multiple times.

  • For example, if three workers attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, their profit is $0.
Return the maximum profit we can achieve after assigning the workers to the jobs.

 

Example 1:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] 
and they get a profit of [20,20,30,30] separately.

Example 2:

Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0

 

Constraints:

  • n == difficulty.length
  • n == profit.length
  • m == worker.length
  • 1 <= n, m <= 104
  • 1 <= difficulty[i], profit[i], worker[i] <= 105
46. find the length of the longest path that has the same values
 Given an integer matrix, find the length of the longest path that have same values. The matrix has no boundary limits. (like, Google Maps )
 From each cell, you can either move to two directions: horizontal or vertical. You may NOT move diagonally or move outside of the boundary.
 nums = [
 [1,1],
 [5,5],
 [5,5]
 ]

47. LeetCode 124 变形题
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.
LeetCode 124变形:要求是起始点和终点必须为leaf node
Follow-up:树中的一些节点会被标记,要求是起始点和终点必须为这些被标记的节点
 

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 3 * 104].
  • -1000 <= Node.val <= 1000
48. LeetCode 838
There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left. Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

You are given a string dominoes representing the initial state where:

  • dominoes[i] = 'L', if the ith domino has been pushed to the left,
  • dominoes[i] = 'R', if the ith domino has been pushed to the right, and
  • dominoes[i] = '.', if the ith domino has not been pushed.
Return a string representing the final state.

 

Example 1:

Input: dominoes = "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Example 2:

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

 

Constraints:

  • n == dominoes.length
  • 1 <= n <= 105
  • dominoes[i] is either 'L', 'R', or '.'.
49. LeetCode 1347
You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.

Return the minimum number of steps to make t an anagram of s.

An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

 

Example 1:

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

Example 2:

Input: s = "leetcode", t = "practice"
Output: 5
Explanation: 
Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s.

Example 3:

Input: s = "anagram", t = "mangaar"
Output: 0
Explanation: "anagram" and "mangaar" are anagrams. 

 

Constraints:

  • 1 <= s.length <= 5 * 104
  • s.length == t.length
  • s and t consist of lowercase English letters only.
50. LeetCode 588
Design a data structure that simulates an in-memory file system.

Implement the FileSystem class:

  • FileSystem() Initializes the object of the system.
  • List<String> ls(String path)
    • If path is a file path, returns a list that only contains this file's name.
    • If path is a directory path, returns the list of file and directory names in this directory.
  • The answer should in lexicographic order.
  • void mkdir(String path) Makes a new directory according to the given path. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.
  • void addContentToFile(String filePath, String content)
    • If filePath does not exist, creates that file containing given content.
    • If filePath already exists, appends the given content to original content.
  • String readContentFromFile(String filePath) Returns the content in the file at filePath.
 

Example 1:

Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

 

Constraints:

  • 1 <= path.length, filePath.length <= 100
  • path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just "/".
  • You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
  • You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist.
  • 1 <= content.length <= 50
  • At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.
51. LeetCode 32
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

 

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

 

Constraints:

  • 0 <= s.length <= 3 * 104
  • s[i] is '(', or ')'.
52. 打印元素
一个数组,按大小打印元素,但元素要符合条件a[k-1]<a[k]>a[k+1],符合这种条件的按大小打印a[k].
53. 两个数组的重合区域
两人大小一样的二维数组,都是0或1,返回数组a是1的连续区域数量,而且相同的区域在b也是1。例如a={{1,1,0,1,0,1}},b={{1,1,1,0,0,1}},返回2。follow up是O(1)space。
54. 设计slack
设计slack
55. LeetCode 859
Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

  • For example, swapping at indices 0 and 2 in "abcd" results in "cbad".
 

Example 1:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

Example 2:

Input: s = "ab", goal = "ab"
Output: false
Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.

Example 3:

Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.

 

Constraints:

  • 1 <= s.length, goal.length <= 2 * 104
  • s and goal consist of lowercase letters.
56. 设计trie tree file system
trie tree file system .follow up watch func
57. 设计用户评论系统
用户评论饭店单品,其他用户可以给这个评论打分点赞,门冲根据用户点赞给评论作者返现