回复: 15
收起左侧

Datadog Senior SDE Onsite 面(挂)经 求米

本楼:   👍  0
0%
0%
0   👎
全局:   0
0%
0%
0

2024(10-12月) 码农类General 硕士 全职@Datadog - 猎头 - 视频面试  | 😐 Neutral 😣 HardFail | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

回馈地里加求米


Datadog 视频Onsite 一共面了5轮  今天接到email,挂,但不知道是挂在哪一轮,还是都挂


Design
Coding I
Coding II
Values
Experience

  • System Design: 之前地里出现的类似于mint.com
  • Coding:    FileSystem , 地里出现过

                  给出了API
                  list(string path) 返回STRING列表,每一个可以代表DIR,也可以是一个FILE
                   isDirectory(String path)
                   delete(String path) 如果是文件会返回true,如果是空目录,返回true, 如果不为空,则返回false


      让实现一个新的DELETE(String path),可以删除本目录以及子目录,如果是文件,直接删除


      递归实现


       follow up question:  系统运行后,发现OOM, 怎么FIX     
                                   
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
ing tag, int windowSize), 返回某一个tag, 在给定的WINDOW SIZE内, value的SUM
4。 Value: 比较类似于BQ ,问一些做过的项目,担任的ROLE,怎么沟通等。
           
5。 Experience: 讲一个自己做过的PROJECT。  画了architect图,讲了一些设计的选择等。。

评分

参与人数 2大米 +6 收起 理由
清道神君 + 5 欢迎分享你知道的情况,会给更多大米奖励!
小亩xoapid2204 + 1 给你点个赞!

查看全部评分


上一篇:分享个 SOTI Senior Software Developer (C#.NET) 面经,OA题目 + HR一面分享
下一篇:Oracle NG挂经
地里匿名用户
匿名用户-0QDLR  2024-12-9 07:25:37 来自APP
本楼:   👍  1
100%
0%
0   👎
春暖花开NUIO 发表于 2024-12-1 15:49
Follow Up:
不清楚怎么修改原贴,所以加在这里

楼主觉得这个怎么样?


```python
from collections import deque
from typing import Dict, Tuple

class TimeSeriesDB:
    def __init__(self, window_size: int):
        self.window_size = window_size
        # Dictionary mapping tags to their respective deques
        # Each deque maintains timestamps and values in chronological order
        # Example: {"env:prod": deque([(1, 10), (2, 20), (3, 30)])}
        self.buffers: Dict[str, deque] = {}
        # Dictionary tracking running sums for O(1) query time
        # Example: {"env:prod": 60} (sum of 10 + 20 + 30)
        self.running_sums: Dict[str, int] = {}
        
    def add_point(self, tag: str, timestamp: int, value: int) -> None:
        """
        Add a new point maintaining chronological order
        Time complexity: O(n) due to insertion
        """
        # Initialize new tag if needed
        if tag not in self.buffers:
            self.buffers[tag] = deque()
            self.running_sums[tag] = 0
            
        buffer = self.buffers[tag]
        
        # Remove outdated points (outside window)
        while buffer and buffer[0][0] <= timestamp - self.window_size:
            self.running_sums[tag] -= buffer[0][1]
            buffer.popleft()
            
        # Find correct position to maintain chronological order
        insert_pos = 0
        for i, (ts, _) in enumerate(buffer):
            if timestamp < ts:
                insert_pos = i
                break
            insert_pos = i + 1
            
        # Insert at correct chronological position
        buffer.insert(insert_pos, (timestamp, value))
        self.running_sums[tag] += value
        
    def query(self, tag: str) -> int:
        """
        Query sum for window with O(1) complexity
        Returns sum of values within window_size of most recent timestamp
        """
        return self.running_sums.get(tag, 0)

# Example usage demonstrating out-of-order inserts
db = TimeSeriesDB(window_size=5)

# Insert out of order
db.add_point("env:dev", 3, 30)  # Third timestamp first
db.add_point("env:dev", 1, 10)  # First timestamp second
db.add_point("env:dev", 2, 20)  # Second timestamp last

# Points are now stored in order: [(1, 10), (2, 20), (3, 30)]
print(db.query("env:dev"))  # Returns 60 (sum of all points within last 5 time units)

# Add a point that will make the first point expire
db.add_point("env:dev", 7, 40)  # Point at timestamp 1 will be removed
# Points are now: [(2, 20), (3, 30), (7, 40)]
print(db.query("env:dev"))  # Returns 90
```

Time Complexity:
- Initialization: O(1)
- add_point(): O(n) where n is current points in window
  * Finding insert position: O(n) - linear search through buffer
  * Insertion in deque: O(n) - shifting elements
  * Removing outdated points: O(k) where k is points to remove
  * Updating running sum: O(1)

- query(): O(1)
  * Simply returns running sum
  * No calculation needed as window is maintained in add_point()

Space Complexity: O(n * m) where:
- n is window_size (max points per tag)
- m is number of unique tags
- We store:
  * buffers: O(n * m) for deques
  * running_sums: O(m) for sums per tag

补充内容 (2024-12-09 23:57 +08:00):

```python
from collections import deque
from typing import Dict


class TimeSeriesDB:
    def __init__(self, max_window_size: int):
        self.max_window_size = max_window_size
        # Dictionary mapping tags to their respective deques
        # Each deque maintains timestamps and values in chronological order
        # Example: {"env:prod": deque([(1, 10), (2, 20), (3, 30)])}
        self.buffers: Dict[str, deque] = {}
        
    def add_point(self, tag: str, timestamp: int, value: int) -> None:
        """
        Add a new point while maintaining chronological order and
        removing points outside the max_window_size.
        """
        if tag not in self.buffers:
            self.buffers[tag] = deque()
            
        buffer = self.buffers[tag]
        
        # Remove outdated points based on max_window_size
        while buffer and buffer[0][0] <= timestamp - self.max_window_size:
            buffer.popleft()
            
        # Insert at correct chronological position
        insert_pos = 0
        for i, (ts, _) in enumerate(buffer):
            if timestamp < ts:
                insert_pos = i
                break
            insert_pos = i + 1
            
        buffer.insert(insert_pos, (timestamp, value))
        
    def query(self, tag: str, window_size: int) -> int:
        """
        Query the sum of values for the given tag within the specified window size.
        If window_size exceeds max_window_size, it defaults to max_window_size.
        """
        if tag not in self.buffers or not self.buffers[tag]:
            return 0
        
        # Ensure requested window size does not exceed max_window_size
        window_size = min(window_size, self.max_window_size)
        
        buffer = self.buffers[tag]
        max_timestamp = buffer[-1][0]
        window_start = max_timestamp - window_size
        
        total = 0
        # Iterate backwards through the buffer (which is sorted by timestamp)
        for (ts, val) in reversed(buffer):
            if ts >= window_start:
                total += val
            else:
                # Since buffer is sorted, once we hit a timestamp < window_start, we can stop
                break
        
        return total


# Example usage:
db = TimeSeriesDB(max_window_size=10)
# Process each point in the input
for point in input_points:
    db.add_point(
        tag=point["tag"],
        timestamp=point["timestamp"],
        value=point["value"]
    )


# Query with window_size=5
# max_timestamp = 6, window_start = 6-5 = 1
# Points in [1,6]: (3,200), (6,300) = 500
print(db.query("env:dev", 5))  # Output: 500


# Query with window_size=15, capped at max_window_size=10
# window_start = 6-10=-4
# Points in [-4,6]: (0,100), (3,200), (6,300) = 600
print(db.query("env:dev", 15)) # Output: 600
```
回复

使用道具 举报

jjtylerho 2024-11-17 07:53:52 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   5
100%
0%
0
coding 2 = prefix sum?
回复

使用道具 举报

jjtylerho 2024-11-17 00:05:32 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   5
100%
0%
0
FileSystem 是 包括 create path? did you use trie structure?
回复

使用道具 举报

地里匿名用户
匿名用户-PJBCJ  2024-11-17 00:25:38
本楼:   👍  0
0%
0%
0   👎
lz几年经验,没有downlevel到sde2这个选项吗?
回复

使用道具 举报

 楼主| 春暖花开NUIO 2024-11-19 07:19:01 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   0
0%
0%
0
jjtylerho 发表于 2024-11-16 11:05
FileSystem 是 包括 create path? did you use trie structure?

不包括 create path,

trie structure 好象不适合

list() 会返回一个List<String>, 如果递归调用有可能太多的path返回来,造成OOM
回复

使用道具 举报

 楼主| 春暖花开NUIO 2024-11-19 07:19:52 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   0
0%
0%
0
匿名用户 发表于 2024-11-16 11:25
lz几年经验,没有downlevel到sde2这个选项吗?
15年
没给这个项,
也没有给别的FEED BACK,所以,不清楚是挂在某一轮,还是全挂了
回复

使用道具 举报

 楼主| 春暖花开NUIO 2024-11-19 07:22:54 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   0
0%
0%
0

prefix sum?应该也是可以的,
我当时用的是sliding window,
因为是一次返回特定size的sum .
比如
3,4,3,4,3,4     如果window size 是2
那就要求返回: 7,7,7,7,7

评分

参与人数 1大米 +15 收起 理由
bryanjhy + 15 给你点个赞!

查看全部评分

回复

使用道具 举报

 楼主| 春暖花开NUIO 2024-12-1 23:49:15 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   0
0%
0%
0
Follow Up:
不清楚怎么修改原贴,所以加在这里

后来联系HR,讨论interview feedback,
说是挂在了第二轮 coding 2:给出, 无序的list of point  (tags, timestamp, int value)
        理由是,我用的算法(sliding window)效率不算高,虽然实现了,但coding时间有些长
        

        对于数据,是需要按照time来排序的, 因为是动态添加,个人以为 要么是priority queue,要么是tree, 抑或是binary index tree(如果时间夸度不是特别大)。
        有同学觉的这题目可以在O(n) time space来实现吗?
回复

使用道具 举报

本楼:   👍  0
0%
0%
0   👎
全局:   0
0%
0%
0
春暖花开NUIO 发表于 2024-12-1 10:49
Follow Up:
不清楚怎么修改原贴,所以加在这里

这题我电面时候遇到了 不过因为是电面我就直接sort+sliding window了
回复

使用道具 举报

地里匿名用户
匿名用户-0QDLR  2024-12-9 06:55:19
本楼:   👍  0
0%
0%
0   👎
本帖最后由 匿名 于 2024-12-8 23:25 编辑

字字叔叔
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

Advertisement
>
快速回复 返回顶部 返回列表