오늘 개발자 위치에 대해 인터뷰를했는데 그 답변을 모른다는 흥미로운 techincal 질문을 받았습니다. 누군가 내 호기심에 대한 해결책을 제공 할 수 있는지 여기에서 질문 할 것입니다.링크 된 목록에서 손상 찾기
1) 100 개 요소 (정수 및 다음 노드에 대한 포인터)가있는 단일 링크 목록이 제공되고 링크 된 부분의 중간에 끊기 또는 손상이 있는지 감지하는 방법을 찾습니다. 명부? 연결된 목록으로 무엇이든 할 수 있습니다. 목록에서 반복 수행 중이므로 목록에서이 작업을 수행해야하며 목록에 문제가 있다는 것을 알기 전에 확인 작업을 수행해야합니다.
연결 목록의 중단 부분이 50 번째 요소라고 가정하면 정수 또는 심지어 다음 노드 (51 번째 요소)에 대한 포인터가 잘못된 주소가 아닌 쓰레기 값을 가리킬 수도 있습니다.
2) 연결된 목록이 손상된 경우 어떻게 데이터 손실을 최소화 할 수 있습니까?
"손상된"정수를 테스트하려면 유효 값의 범위가 무엇인지 알아야합니다. 그렇지 않으면, 주어진 (부호가있는) 정수의 값이 유효하지 않음을 판별 할 수있는 방법이 없습니다. 따라서 int에 대한 유효성 테스트가 있다고 가정하면 다음 요소를 반복하기 전에 항상 해당 값을 확인합니다.
손상된 포인터에 대한 테스트가 까다 롭습니다. 처음에는 참조 해제하기 전에 다음 요소에 대한 포인터 값을 확인하고 올바른 힙 주소인지 확인해야합니다. 세그먼트 화 오류를 피할 수 있습니다. 다음은 포인터가 가리키는 점이 실제로 유효한 연결 목록 노드 요소인지 확인하는 것입니다. 이것은 약간 까다 롭습니다. 아마도 포인터를 목록 요소 클래스/구조체로 참조 해제하고 int 및 "next"포인터의 유효성을 테스트합니다. 또한 포인터가 좋으면 이전 노드도 좋았을 것입니다.
에서 2) 손상된 노드를 발견 한 경우 [다음 포인터가 손상된 경우] 이전 노드의 "다음 포인터"를 즉시 NULL로 설정하고 해당 노드의 끝으로 표시합니다. 목록을 작성하고 오류 등을 기록하십시오.손상이 정수 값에 있지만 "다음"요소 포인터가 아니라면 목록에서 해당 요소를 제거하고 이전 및 다음 노드를 함께 연결해야합니다. 나머지 목록을 버릴 필요가 없으므로 그럴 경우!
주소가 유효한 힙 주소인지 어떻게 확인할 수 있습니까? – Vijay
@peter를 사용하면 segfault 핸들러를 설치하고 포인터에서 읽기를 시도 할 수 있습니다. segfault를 얻지 못하면 적어도 읽을 수있는 지점을 가리 킵니다. –
목록에 루프가있는 "손상"문제를 테스트하는 것도 중요합니다. 당신이 절대적으로 크기 (100)를 알고 있다면 그것은 사소한 것이지만 내 생각에 그 한계가 제거되어 후속 질문이 될 것입니다. 트릭을 안다면 In-place loop detection 역시 어렵지 않습니다. – samkass
손상이 중요한 문제가 될 수 있음을 디자인 타임에 알게되면 노드 데이터 구조에 필드로 "마법 값"을 추가하여 일부 데이터가 노드가 될 가능성이 있는지 여부를 식별 할 수 있습니다 . 또는 노드를 검색하는 메모리를 통해 실행하는 경우도 있습니다.
또는 몇 가지 링크 정보를 두 번 즉, 각 노드의 다음 노드 다음에 노드의 주소를 저장하여 하나의 링크가 손상된 경우 복구 할 수 있습니다.
유일한 문제는 세그먼트 화 오류를 방지해야한다는 것입니다.
요소 수 (100)가 알려져 있기 때문에 100 번째 노드에는 널 포인터가 있어야합니다. 만약 그렇다면, 좋은 확률을 가진 목록이 유효합니다 (예를 들어, 99 번째 노드가 손상되어 모든 0이있는 일부 메모리 위치를 가리키는 경우에는이를 보장 할 수 없습니다). 그렇지 않으면 몇 가지 문제점이 있습니다 (사실로 반환 될 수 있음).
UPD : 또한, 포인터가 주어진다면 delete 사용되는 일부 구조를 보면, 모든 단계에 가능할 수 있지만 delete을 사용하기 때문에 그 자체가 어떤 의미에서 안전하지 않다,이 구현 될 것입니다 -특유한.
이렇게 많은 수준에서 잘못되었습니다. 중간에 손상된 노드는 어때? 당신은 메모리가 정말로 쓰레기 일 때처럼 내일을 기억하지 못하는 것처럼 기억을 돌아 다니기 만하면됩니다. 당신이 기억할 수있는 운명에 의해서만 액세스 할 수 있습니다. 100 회 반복 한 후에 당신은 값 0을 가질 것입니다. 바늘. 이것은 완전히 실패합니다. – SimpleVar
부정확 한 해결책, 중간에 잘못된 포인터가있는 경우 어떻게 끝까지 탐색 할 수 있습니까? – DhruvPathak
@Yorye Nathan 글쎄, 당신이 예외를 잡아 내고 "그 문제는 BEFORE"라고 말할 수있는 기억을 남겨 두는 순간. 완벽하게 괜찮아. 100 번째 요소 앞에 널 포인터가있는 경우에도 마찬가지입니다. –
첫 번째 부분은 - 새 연산자를 오버로드하십시오. 새로운 노드가 할당 될 때 노드 앞뒤에 추가 공간을 할당하고 거기에 알려진 값을 입력하십시오. 트래버스에서 각 노드는 알려진 값 사이에 있는지 점검 할 수 있습니다.
링크 된 목록에 무엇이든 할 수 있다면, 각 요소의 체크섬을 계산하여 요소 자체에 저장하는 것입니다. 이 방법을 사용하면 요소의 단일 비트 오류 일지라도 손상을 감지 할 수 있습니다.
데이터 손실을 최소화하기 위해 이전 요소에 nextPtr을 저장하는 것을 고려할 수 있습니다. 즉, 현재 요소가 손상된 경우 이전 요소에서 다음 요소의 위치를 항상 찾을 수 있습니다.
이 모든 종류의 해답은 모든 시간 또는 범위 또는 둘 다로 돌아가서 검색을 쉽게하기 위해 목록을 구성하거나 내용을 제한하려고 시도한다는 것입니다. 질문의 하위 집합에 대한 모든 유효한 대답이 있지만 문제와 관련이있는 것은 없습니다. –
사실입니다. 목록이 작성되기 전에 수행 할 수 있습니다. – tytchong
이것은 쉬운 질문이며 몇 가지 가능한 대답이 있습니다. 각각은 효율성과 견고성을 교환합니다. 증가 된 견고성은 질문의 전제 조건이기 때문에 시간 (삽입 속도 및 노드 삭제 속도뿐만 아니라 탐색 속도의 목록 표시) 또는 공간 (각 노드에 저장된 추가 정보)을 모두 희생시키는 솔루션을 사용할 수 있습니다. 이제는 이것이 길이가 100 인 고정 목록이며 링크 된 목록의 데이터 구조가 가장 부적절하다는 문제점이 지적되었습니다. 왜 퍼즐을 조금 더 도전적으로 만들지 말고리스트의 크기가 선험적으로 알려지지 않았습니까?
"잘못된 주소 일 필요는 없습니다"C# 또는 Java의 잘못된 주소에 대한 포인터는 어떻게 C?의 안전하지 않은 키워드 또는 일부 기본 상호 운용성 (P/Invoke, JNI)을 금지합니까? –
먼저 "손상"을 정의해야합니다. – SimpleVar
이 태그를 C# 및 Java로 태그 지정하는 것이 정말로 맞습니까? 그들은 포인터가 없습니다 (안전하지 않은 C# 코드를 작성하지 않는 한) 및 참조가 잘못된 주소를 가리킬 수 없습니다. 질문은 C 또는 C++에서 더 적합합니다. –