Daily Coding Problem을 구독하면 매일 한 개의 코딩 문제를 이메일로 받을 수 있다.

DCP #6

이 문제는 구글 면접에서 나온 문제입니다.

보통 이중 연결 리스트는 nextprev 두 개의 상태를 가지는 노드를 가지고 구현을 합니다. 하지만 보다 효율적으로 메모리를 사용하기 위해 두 개의 상태를 하나로 합쳐서 구현할 수 있는데 이를 XOR 연결 리스트라고 합니다. XOR 연결 리스트의 노드는 이전 노드와 다음 노드의 주소를 XOR한 값을
가지고 있는 both한 개의 상태만을 사용합니다.

25-1.png

그럼 지금부터 XOR 연결 리스트를 사용해서 리스트 끝에 노드를 추가하는 add(element)함수와 주어진 색인의 노드를 반환하는 get(index)함수를 구현해주세요.

파이썬과 같이 포인터가 없는 언어의 경우 노드의 주소를 반환하는 함수 get_pointer와 주소로 부터 다시 노드를 참조해주는 함수 dereference_pointer가 있다고 가정하여도 좋습니다.

원문 확인

코드

C언어 코드 보기

class Node
    attr_reader :val
    attr_accessor :npx

    def initialize data
        @val = data
        @npx = 0
    end
end

class XORLinkedList
    attr_reader :root, :tail, :nodes

    def initialize data
        @root = Node.new(data)
        @nodes = 1
    end

    def add element
        new_node = Node.new(element)

        if @root.npx == 0
            @root.npx = get_pointer(new_node)
            new_node.npx = get_pointer(@root)
        elsif
            curr_node = deref_pointer(@root.npx)
            prev_addr = get_pointer(@root)

            while curr_node.npx != prev_addr
                next_node = deref_pointer(curr_node.npx ^ prev_addr)
                prev_addr = get_pointer(curr_node)
                curr_node = next_node
            end

            new_node.npx = get_pointer(curr_node)
            curr_node.npx = prev_addr ^ get_pointer(new_node)
        end

        @nodes += 1
    end

    def get(index)
        if index == 0
            return @root.val
        end

        curr = deref_pointer(@root.npx)
        prev_addr = get_pointer(@root)

        for i in (1 ... index) do
            next_node = deref_pointer(prev_addr ^ curr.npx)   
            prev_addr = get_pointer(curr)
            curr = next_node
        end

        curr.val
    end
end

def get_pointer(node)
    node.object_id
end

def deref_pointer(node_addr)
    ObjectSpace._id2ref(node_addr)
end

list = XORLinkedList.new("A")
list.add("B")
list.add("C")
list.add("D")
list.add("E")

puts list.get(0)  # => A
puts list.get(1)  # => B
puts list.get(2)  # => C
puts list.get(3)  # => D
puts list.get(4)  # => E

GitHub: https://github.com/muicode/DCP
Blog : https://muicode.github.io