OpenAI Coding的一道新题讨论

最近面OpenAI挂在一道coding题目上，之前在某论坛里没看到过。特此分享出来跟大家讨论一下。

题目

题目要求实现一个类似vector的数据结构。这种数据结构先写后读。也就是说，一开始只写入，不读取。经过一系列写入之后，会切换成只读模式，后续就不会再有写入了。另外，一开始无法知晓总共需要插入的数据的数量。

这个数据结构要支持随机插入，即向任意一个下标插入数据，如果所在下标已经有数据，则它之后的所有数据都需要后移一个位置。

值得一提的是，面试官一开始没跟我说一个重要的特性，那就是，插入的下标可以是任意数字，不必小于当前数据的长度。比如一开始没有数据的时候，可以直接向下标为100的位置插入数据。这一点跟JavaScript的Array相似，它中间是可以有洞的。这个让我一开始的实现方向有点偏差，后来就没时间了。

大致的接口定义如下

class SpecialVector:
    def __init__(self):
        pass

    def insert(self, index: int, data: str):
        """
        Insert data at index, shifting all subsequent elements by one position.
        """
        pass

    def get(self, index: int) -> str:
        """
        Read data at index.
        """
        pass

    def switch_to_read_only(self):
        """
        Optional function to implement logic for switching to read-only mode.
        """"
        pass

讨论

跟面试官一番讨论以后，明确了大方向。插入可以做到O(1), 把计算负担转移到读取的时候。写入的时候用一个Map结构来存储所有插入的操作，比如index => data, 但是不真正进行插入。读取的时候计算该下标前面的插入操作的数量，来决定有多少次shift发生，然后算出当前下标最终的数据。同时可以把这个数据缓存起来，后续重复读取相同的下标可以不用再次计算。

面试官大致认可了这个思路，不过写得乱七八糟的，后来时间也不够了，没写完。测试样例也没写几个，基本上就是挂在这一轮了。

改天有空我来让ChatGPT写一份，估计挺啰嗦的。各位有什么高见请在评论区分享。