OpenAI Coding的一道新题讨论

Question

最近面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发生，然后算出当前下标最终的数据。同时可以把这个数据缓存起来，后续重复读取相同的下标可以不用再次计算。

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

各位有什么高见请在评论区分享。

ZzzZachery · Answer

哇感谢大佬分享

都市传说 · Answer

以下是大语言模型给出的示例实现，大家可以参考一下。其实这题没有很难，而且估计还有后续的其他问题。

class SpecialVector:
    def __init__(self):
        # Store insertions as (index, data) pairs in order of insertion
        self.insertions = []
        self.read_only = False
    
    def insert(self, index: int, data: str):
        """
        Insert data at index, shifting all subsequent elements by one position.
        Time complexity: O(1)
        """
        if self.read_only:
            raise RuntimeError("Vector is in read-only mode")
        
        # Simply append the insertion operation - O(1)
        self.insertions.append((index, data))
    
    def get(self, index: int) -> str:
        """
        Read data at index.
        Time complexity: O(n) where n is number of insertions
        """
        if not self.read_only:
            raise RuntimeError("Vector must be in read-only mode to read")
        
        # Process insertions in reverse order to find what ends up at this index
        current_index = index
        
        # Work backwards through insertions to find the original position
        for insert_idx, data in reversed(self.insertions):
            if insert_idx <= current_index:
                # This insertion affects our position
                if insert_idx == current_index:
                    # Found the data that was inserted at this final position
                    return data
                else:
                    # This insertion shifted our target back by 1
                    current_index -= 1
        
        # No data found at this index (hole)
        return None
    
    def switch_to_read_only(self):
        """
        Switch to read-only mode.
        """
        self.read_only = True


# Example usage and test cases
if __name__ == "__main__":
    # Test case 1: Basic insertion and reading
    vec = SpecialVector()
    vec.insert(0, "A")
    vec.insert(1, "B")
    vec.insert(0, "C")  # This should shift A and B to the right
    vec.switch_to_read_only()
    
    print("Test 1:")
    print(f"Index 0: {vec.get(0)}")  # Should be "C"
    print(f"Index 1: {vec.get(1)}")  # Should be "A"
    print(f"Index 2: {vec.get(2)}")  # Should be "B"
    print(f"Index 3: {vec.get(3)}")  # Should be None
    print()
    
    # Test case 2: Insertion with holes
    vec2 = SpecialVector()
    vec2.insert(100, "X")
    vec2.insert(5, "Y")
    vec2.insert(50, "Z")
    vec2.switch_to_read_only()
    
    print("Test 2:")
    print(f"Index 5: {vec2.get(5)}")    # Should be "Y"
    print(f"Index 50: {vec2.get(50)}")  # Should be "Z"
    print(f"Index 100: {vec2.get(100)}")# Should be "X"
    print(f"Index 10: {vec2.get(10)}")  # Should be None (hole)
    print()
    
    # Test case 3: Multiple insertions at same index
    vec3 = SpecialVector()
    vec3.insert(0, "First")
    vec3.insert(0, "Second")
    vec3.insert(0, "Third")
    vec3.switch_to_read_only()
    
    print("Test 3:")
    print(f"Index 0: {vec3.get(0)}")  # Should be "Third"
    print(f"Index 1: {vec3.get(1)}")  # Should be "Second"
    print(f"Index 2: {vec3.get(2)}")  # Should be "First"
    print()
    
    # Test case 4: Complex shifting scenario
    vec4 = SpecialVector()
    vec4.insert(10, "A")
    vec4.insert(5, "B")
    vec4.insert(7, "C")  # This should shift A to position 11
    vec4.switch_to_read_only()
    
    print("Test 4:")
    print(f"Index 5: {vec4.get(5)}")   # Should be "B"
    print(f"Index 7: {vec4.get(7)}")   # Should be "C"
    print(f"Index 10: {vec4.get(10)}") # Should be None (hole)
    print(f"Index 11: {vec4.get(11)}") # Should be "A" (shifted from 10)

OpenAI Coding的一道新题讨论

题目

讨论

2 Answers