Java - 요소가 무작위 화 된 후에 목록의 원래 순서를 복구하십시오.

Question

제목 자체적으로 설명하고 있습니다. 이것은 인터뷰 질문이었습니다. Java에서 List는 인터페이스입니다. 그래서 그것은 어떤 컬렉션에 의해 초기화되어야합니다.

나는 이것이 혼란스러운 까다로운 질문이라고 생각합니다. 내가 맞았나요? 이 질문에 대답하는 방법?

Answer 1

원래 목록의 복사본이없고 무작위 알고리즘이 정말로 무작위라고 가정하면 원래 목록을 복원 할 수 없습니다.

이 유형의 질문에 대한 설명은 대답보다 훨씬 중요합니다. 이를 완전히 설명하려면 함수 및 맵 (Java 클래스 정의가 아님)의 수학적 정의를 사용하여 설명해야합니다.

함수는 한 도메인의 요소를 다른 도메인으로 맵핑 한 것입니다. 이 예에서 첫 번째 도메인은 첫 번째 목록의 "주문"이고 두 번째 도메인은 두 번째 목록의 "주문"입니다. 첫 번째 도메인에서 두 번째 도메인으로 이동할 수있는 방법은 첫 번째 도메인의 각 요소가 두 번째 도메인의 요소 중 하나로 이동하는 함수입니다.

원하는 것은 역 함수가 있는지 또는 두 번째 도메인의 요소를 첫 번째 도메인의 요소로 "백 맵핑"할 수있는 해당 함수인지 여부를 확인하는 것입니다. 두 번째 도메인의 한 요소가 첫 번째 도메인의 여러 요소에 매핑되거나 다시 매핑되지 않을 수도 있기 때문에 일부 함수 (숫자를 제곱하거나 F (x) = x * x)를 되돌릴 수 없습니다. 9 이후

9 maps to 3 
144 maps to 12 
121 maps to -11 
9 maps to -3 

3과 -3에 매핑해야하며,지도마다 단 하나의 목적을 가지고 있어야 곳은 역 기능을 시도하는 숫자, 예를

F(x) = x * x 
F(3) = 9  or ( 3 -> 9) 
F(12) = 144 or (12 -> 144) 
F(-11) = 121 or (-11 -> 121) 
F(-3) = 9 or (-3 -> 9) 

제곱, 우리는 기능이 필요합니다 x * x의 역함수를 만드는 것은 불가능합니다. 이것이 수학자들이 제곱근 연산자를 퍼지하고 (+ 또는 -) 말하는 이유입니다.

Google 임의 목록에 돌아갑니다. 맵이 정말로 랜덤하다는 것을 안다면 출력 값이 입력 값과 완전히 독립적이라는 것을 알 수 있습니다. 따라서 역함수를 만들려고한다면, 델림 마를 실행하게됩니다. 함수가 무작위라는 사실은 출력에서 ​​입력을 계산할 수 없다는 것을 알려주므로 함수를 "알았더라도"출력이 있더라도 입력에 대해 어떤 가정도 할 수 없습니다.

의사 랜덤 인 경우 (무작위로 보이는 경우가 아니라면) 이제는 사실이 아닌 임의의 기능을 되돌릴 수있는 충분한 정보를 수집 할 수 있습니다.

Answer 2

외부 주문 정보 (고스트 사본이 포함 된 JVM 속임수 포함)를 보관하지 않고 항목이 암시 적으로 주문되지 않은 경우 원래 주문을 복구 할 수 없습니다.

정보가 손실되면 정보가 손실됩니다. 목록의 구조가 원하는 순서를 기록하는 유일한 장소이고 그 순서를 어지럽 혀지면 좋은쪽으로 사라집니다.

Answer 3

사용자보기가 있으며 내부가 있습니다. 이해할 수있는 질문과 해석 될 수있는 질문이 있습니다.

사용자가보기에 목록 항목은 메모리 블록이며 다음 항목에 대한 포인터는이 메모리 내부의 (4 → 8? 숫자를 계속 변경하는 :) 바이트 집합입니다. 따라서 목록이 무작위로 지정되고 다음 항목에 대한 포인터가 변경되면 해당 메모리 영역이 오버라이드되어 복구 할 수 없습니다.

이해되는 질문은 무작위 화 된 후에 목록이 제공된다는 것입니다.

내부 - 나는 Java 또는 OS 사람이 아니지만 프로세스가 실행되는 방식이 순진한보기와 다른 경우를 조사해야합니다. Java는 모든 셀을 복사하여 목록을 무작위화할 수 있으므로 이전 목록은 여전히 ​​어딘가에 메모리에 보관됩니까? 어쩌면 포인터의 백업 값을 유지할 수 있습니까? 어쩌면 포인터가 외부 테이블에 보관되어 목록과 분리되어 재구성 될 수 있습니까? 아마도. 내부.

이해 - 누가 무작위로 분류되기 전에 목록에 액세스 할 수 없다고 말하는가? 너는 방금 그것을 인쇄 할 수 있었다! 아니면 그 실행의 흔적을 가지고 있습니까? 또는 누가 Java의 목록을 사용하고 있다고 말했습니까? 아마도 자신의 버전 제어 목록을 사용하고 있습니까? 아니면 자신의 reversable-randomize 방법을 사용하고 있습니까?

에드윈 벅의 대답은 훌륭하지만 모든 것이 면접관이 무엇을 찾고 있었는지에 달려 있습니다.