차례[숨다][보여 주다]
- 1. 배열을 어떻게 정의합니까?
- 2. 동적 배열: 무엇입니까? 기본 어레이와 다른 점은 무엇입니까?
- 3. 배열과 사전은 서로 어떻게 다릅니까?
- 4. 배열의 몇 가지 장점과 단점을 나열하십시오.
- 5. "스파스 배열"이란 무엇을 의미합니까?
- 6. 언제 배열보다 연결된 목록을 선택하시겠습니까?
- 7. 인덱스 배열과 연관 배열의 차이점은 무엇입니까?
- 8. Heap은 정렬된 배열에 비해 어떤 이점이 있습니까?
- 9. 배열의 크기를 음수로 정의할 수 있습니까?
- 10. 1~100개 요소 배열에서 누락된 정수를 어떻게 찾습니까?
- 11. 배열에서 요소의 인덱스를 어떻게 찾습니까?
- 12. 배열에서 특정 요소를 어떻게 제거할 수 있습니까?
- 13. 두 어레이의 동일성을 어떻게 확인할 수 있습니까?
- 14. 배열에 대해 이야기할 때 "Dimension"과 "Subscript"라는 문구는 무엇을 의미합니까?
- 코딩 인터뷰 질문
- 15. 지정된 합계가 있는 배열에서 쌍을 찾습니다.
- 16. 선형 시간으로 이진 배열 정렬
- 17. 배열에서 가장 큰 XNUMX-int 제품을 찾습니다.
- 18. 배열의 모든 XNUMX을 끝으로 이동하는 방법
- 19. 한 번의 작업으로 전환되는 두 개의 항목이 있는 배열을 정렬하는 방법.
- 20. 두 개의 정렬된 배열을 제자리에 결합하는 방법.
- 21. 높은 위치와 낮은 위치를 번갈아 가며 항목 배열을 재정렬하는 방법은 무엇입니까?
- 22. 배열의 각 요소의 곱으로 나눗셈 연산자를 사용하지 않고 배열의 각 요소를 대체하는 방법은 무엇입니까?
- 23. 대수 시간으로 배열에서 가장 이상한 요소 찾기
- 24. 원형 배열의 각 요소에 대한 후속 더 큰 요소를 얻는 방법은 무엇입니까?
- 25. 어레이의 반전 횟수를 찾으십니까?
- 26. 빗물 갇힘 문제는 무엇입니까?
- 결론
코딩 인터뷰에는 일련의 DSA 질문이 포함되어 있습니다. 곧 있을 FAANG 또는 다른 Tier-1 기술 비즈니스와의 기술 인터뷰를 준비하고 있다면 어레이에 능숙해야 합니다.
대부분의 코딩 인터뷰에서 Strings에 이어 XNUMX위를 차지합니다. 배열은 메모리에서 서로 근접하게 유지되는 관련 데이터 요소의 그룹입니다.
C, C++, Java, Python, Perl, Ruby 등 모든 프로그래밍 언어와 연결되어 있기 때문에 어디에나 있습니다. 몇 가지 연습 코딩 문제와 어레이를 기반으로 한 인터뷰 질문 및 답변에 대해 계속 읽으십시오.
Python은 사용하기 쉽고 이해하기 쉬우며 우리 대부분에게 친숙해야 하기 때문에 코딩 문제를 해결하기 위해 이 게시물에서 사용될 것입니다.
의 시작하자.
1. 배열을 어떻게 정의합니까?
- 관련 데이터 유형의 그룹은 배열입니다.
- 배열은 항상 고정되어 있습니다.
- 동일한 종류의 변수가 배열 개체에 의해 여러 위치에 저장됩니다.
- 기본 유형과 개체 참조는 모두 호환됩니다.
2. 동적 배열: 무엇입니까? 기본 어레이와 다른 점은 무엇입니까?
동적 배열(자바에서 확장 가능한 배열, 크기 조정 가능한 배열, 변경 가능한 배열 또는 ArrayList라고도 함)이 제공하는 자동 크기 조정은 상당한 이점입니다.
배열은 크기가 고정되어 있으므로 미리 배열에 저장할 요소 수를 항상 알고 있어야 합니다. 반면에 동적 배열은 추가 구성원을 추가함에 따라 크기가 커지므로 사전에 정확한 크기를 알 필요가 없습니다.
3. 배열과 사전은 서로 어떻게 다릅니까?
이것은 정기적으로 묻는 인터뷰 질문의 기본 기반 배열입니다. 다음은 배열과 사전의 주요 차이점입니다.
- 배열은 유사한 항목의 정렬된 목록입니다. 반면 사전에는 키-값 쌍이 있습니다.
- 배열 크기는 동적으로 변경될 수 있습니다. 이러한 역동적인 아이디어는 사전에 존재하지 않습니다.
- 배열을 사용하기 전에 크기를 지정해야 합니다. 사전 크기는 사용자 지정할 필요가 없습니다.
- 배열의 크기를 확장하려면 Redim 문을 사용하십시오. 사전에서는 선언 없이 요소를 추가할 수 있습니다.
4. 배열의 몇 가지 장점과 단점을 나열하십시오.
장점:
- 배열은 여러 요소를 동시에 정렬할 수 있습니다.
- 기타 데이터 구조, 스택, 큐, 연결 목록, 트리, 그래프 등과 같이 배열로 구현할 수 있습니다.
- 인덱스를 사용하여 배열의 요소에 도달할 수 있습니다.
단점 :
- 배열의 크기는 미리 선언해야 합니다. 그러나 배열을 선언하는 순간에 필요한 크기를 인식하지 못할 수 있습니다.
- 배열의 구조는 정적입니다. 이는 배열 크기가 항상 고정되어 있고 메모리 할당을 늘리거나 줄일 수 없음을 의미합니다.
5. "스파스 배열"이란 무엇을 의미합니까?
희소 배열은 값이 XNUMX인 항목이 많은 데이터 배열입니다. 반대로 조밀한 배열에는 XNUMX이 아닌 값을 가진 대부분의 항목이 포함됩니다. 숫자를 객체로 변환하는 희소 배열의 인덱스에는 간격이 포함될 수 있습니다. HashMap에 비해 메모리 효율적입니다.
6. 언제 배열보다 연결된 목록을 선택하시겠습니까?
배열 대신 연결된 목록을 사용하는 경우 다음을 고려하십시오.
- 임의 액세스를 위해 요소가 필요하지 않습니다.
- 시간적 예측 가능성이 필수적인 경우 목록에서 일정 시간 삽입 및 제거가 필요합니다.
- 우선 순위 대기열을 만들려면 항목을 목록 중앙에 배치해야 할 수 있습니다.
- 목록이 얼마나 길어질지 알 수 없습니다. 배열 크기가 커지면 단순 배열과 마찬가지로 메모리를 다시 선언하고 복제해야 합니다.
7. 인덱스 배열과 연관 배열의 차이점은 무엇입니까?
연관 배열과 인덱싱된 배열 간의 주요 차이점은 다음 표에 나열되어 있습니다.
- 텍스트 또는 숫자 형식의 키-값 쌍은 연관 배열을 정렬하는 데 사용됩니다. 인덱스 배열의 키는 모두 숫자이며 각 키는 고유한 값에 연결됩니다.
- 연관 배열에서 키는 문자열일 수 있습니다. 0부터 시작하는 정수 키가 있는 인덱스 배열.
- XNUMX열 테이블은 연관 배열의 동작을 모방합니다. 단일 열 테이블과 유사한 것은 인덱스 배열입니다.
- 맵은 연관 배열 유형입니다. 인덱스 배열은 맵이 아닙니다.
8. Heap은 정렬된 배열에 비해 어떤 이점이 있습니까?
정렬된 배열보다 힙을 활용하는 시간 효율성이 주요 이점입니다. 힙 작업이 더 빠르지만 배열을 정렬하려면 많은 시간이 필요합니다. 힙은 배열을 정렬할 수 있는 것보다 훨씬 더 빠르게 가장 작은 요소를 발견할 수 있습니다.
주어진 숫자 모음은 정렬된 배열을 사용하여 두 가지 방법 중 하나로 배열할 수 있습니다. 반면에 주어진 숫자 모음에 대해 하나 이상의 잠재적인 힙이 있을 수 있습니다.
9. 배열의 크기를 음수로 정의할 수 있습니까?
아니요, 음의 정수를 배열 크기로 정의할 수 없습니다. 선언하면 컴파일 타임 오류가 발생하지 않습니다. 그러나 런타임에 NegativeArraySizeException이 발생합니다.
10. 1~100개 요소 배열에서 누락된 정수를 어떻게 찾습니까?
시리즈의 합계는 다음 함수를 적용하여 계산할 수 있습니다. n(n + 1) / 2
배열에 중복 항목이 없거나 하나 이상의 정수가 누락된 경우에만 이 기능이 작동합니다. 배열에 중복 요소가 있는지 여부에 관계없이 배열을 정렬하여 동일한 요소가 있는지 확인할 수 있습니다.
11. 배열에서 요소의 인덱스를 어떻게 찾습니까?
선형 또는 이진 검색을 통해 요소의 인덱스를 찾을 수 있습니다. 필요한 요소의 일치 항목을 찾을 때까지 선형 검색 기능은 배열의 모든 요소를 반복합니다. 일치하는 요소를 찾으면 인덱스를 반환합니다. 따라서 선형탐색의 시간복잡도는 O.(n)이다. 정렬된 배열과 정렬되지 않은 배열 모두 선형 검색을 사용할 수 있습니다.
간격의 중앙값이 필요한 요소와 일치하고 색인을 제공할 때까지 배열을 계속해서 반으로 나누는 이진 검색을 사용하면 배열이 정렬된 경우 요소의 색인을 얻을 수 있습니다. 결과적으로 이진탐색의 시간복잡도는 O.(log n)이다.
12. 배열에서 특정 요소를 어떻게 제거할 수 있습니까?
정의된 크기의 고정 세트이기 때문에 원래 배열에서 요소를 단순히 삭제할 수 없기 때문에 면접관은 다른 접근 방식을 제안하고 질문이 제기하는 문제를 처리하기를 원합니다. 가장 좋은 조치는 요소를 삭제하기 위해 새 배열을 만드는 것입니다. 이 배열의 첫 번째 배열에서 요소를 복제하고 삭제할 요소만 포함할 수 있습니다.
또 다른 전략은 배열에서 대상 요소를 찾은 다음 대상 요소 오른쪽에 있는 모든 항목의 순서를 반대로 바꾸는 것입니다.
13. 두 어레이의 동일성을 어떻게 확인할 수 있습니까?
먼저 제공된 두 배열의 길이를 확인해야 합니다. 두 배열의 일치하는 항목은 길이가 같을 때 비교됩니다. 두 배열은 동일한 것으로 간주됩니다. 모든 대응에서 각 구성 요소 쌍이 동일한 경우. 이 접근 방식은 시간이 많이 걸리므로 어레이 크기가 큰 경우 두 어레이의 동등성을 확인하는 데 권장되지 않습니다. Arrays 클래스에 포함된 equals() 메서드를 사용할 수도 있지만 면접관이 내장 메서드를 사용하지 않고 두 배열을 비교하도록 요청하는 경우 이 방법이 유용할 것입니다.
14. 배열에 대해 이야기할 때 "Dimension"과 "Subscript"라는 문구는 무엇을 의미합니까?
배열의 "차원"은 각 개별 구성원을 식별하는 데 필요한 인덱스 또는 첨자의 수입니다. 아래 첨자 및 치수가 명확하지 않을 수 있습니다. 차원은 허용된 키 범위에 대한 설명인 반면 아래 첨자는 숫자입니다. 각 배열 차원에는 하나의 첨자만 필요합니다.
예를 들어 arr[10][5] 배열은 10차원입니다. 하나는 5, 다른 하나는 0 크기입니다. 해당 구성 요소를 지정하려면 두 개의 첨자가 필요합니다. 둘 다 4에서 0 사이입니다. 9에서 XNUMX 사이의 값입니다.
코딩 인터뷰 질문
15. 지정된 합계가 있는 배열에서 쌍을 찾습니다.
예를 들어,
입력:
- 숫자 = [8, 7, 2, 5, 3, 1]
- 목표 = 10
출력:
- 쌍 발견 (8, 2)
- Or
- 쌍 발견 (7, 3)
입력:
- 숫자 = [5, 2, 6, 8, 1, 9]
- 목표 = 12
출력:
- 쌍을 찾을 수 없음
16. 선형 시간으로 이진 배열 정렬
선형 시간과 고정 영역에서 이진 배열을 정렬합니다. 출력은 먼저 모두 XNUMX을 표시한 다음 모두 XNUMX을 표시해야 합니다.
예를 들어,
- 입력: { 1, 0, 1, 0, 1, 0, 0, 1 }
- 출력: { 0, 0, 0, 0, 1, 1, 1, 1 }
간단한 접근 방식은 배열의 총 0 수, 예를 들어 k를 계산한 다음 배열의 첫 번째 k 인덱스를 0으로 채우고 나머지 인덱스를 1로 채우는 것입니다. 대안으로 배열 k에서 총 1의 수를 계산하고 배열의 마지막 k 인덱스를 1로 채우고 나머지 인덱스는 0으로 채울 수 있습니다.
주어진 접근 방식은 O(n) 시간 복잡도를 가지며 추가 스토리지를 사용하지 않습니다. 여기서 n은 입력 크기입니다.
17. 배열에서 가장 큰 XNUMX-int 제품을 찾습니다.
정수 배열에서 두 숫자의 가장 큰 곱을 찾습니다.
배열 10 3 5 6 2를 예로 생각해 보십시오. (-10, -3) 또는 (5, 6) 쌍이 가장 높은 곱입니다.
모든 요소 조합에 대해 생각하고 제품을 파악하는 것은 어리석은 접근 방식입니다. 현재 쌍의 제품이 지금까지 얻은 최대 제품보다 크면 최대 제품을 업데이트하십시오. 최종 제품의 구성 요소를 마지막으로 인쇄합니다.
n이 입력량인 위의 솔루션은 O(n2)의 시간 복잡도를 가지며 더 이상 공간을 차지하지 않습니다.
18. 배열의 모든 XNUMX을 끝으로 이동하는 방법
정수 배열의 모든 XNUMX을 끝으로 이동합니다. 대답은 일정한 공간을 사용하지 않고 배열 구성 요소의 상대적인 순서를 유지해야 합니다.
입력 : {1,2,3,0,8,0,4,7}
출력은 {1,2,3,8,4,7,0,0}입니다.
현재 요소가 0이 아닌 경우 배열의 다음 사용 가능한 위치에 요소를 배치합니다. 배열의 항목이 모두 처리되면 나머지 모든 인덱스를 XNUMX으로 채웁니다.
이전 솔루션은 O(n) 시간 복잡도를 가지며 여기서 n은 입력 크기입니다.
19. 한 번의 작업으로 전환되는 두 개의 항목이 있는 배열을 정렬하는 방법.
두 개의 교체된 항목과 모든 요소가 오름차순으로 정렬된 배열이 주어지면 선형 시간으로 배열을 정렬합니다. 배열에 중복이 없다고 가정합니다.
입력:= [1,9,3,4,7,2] 또는 [9,3,7,2,1,4] 또는 [2,4,1,7,3,9]
출력: = [1,2,3,4,7,9]
배열의 두 번째 요소부터 시작하여 목표는 각 요소를 이전 요소와 비교하는 것입니다. 분쟁의 위치는 두 개의 포인터 x와 y를 취하여 저장됩니다.
전자가 후자보다 큰 경우 x를 이전 요소의 인덱스로 업데이트하고 y를 현재 요소의 인덱스로 업데이트합니다. 이전 요소가 현재 요소보다 큰 것으로 판명되면 y를 현재 요소의 인덱스로 업데이트합니다.
마지막으로 인접한 각 요소 쌍 처리가 완료되면 인덱스 x와 y의 요소를 전환합니다.
앞서 언급한 방법은 크기 n의 입력 배열을 한 번만 스캔하기 때문에 시간 복잡도는 O(n)입니다. 솔루션을 위한 추가 공간이 필요하지 않습니다.
20. 두 개의 정렬된 배열을 제자리에 결합하는 방법.
정렬된 순서를 유지하여, 즉 X[]를 첫 번째 m개의 가장 작은 요소로 채우고 Y[]를 나머지 요소.
배열 X[]의 요소가 이미 올바른 위치(즉, 나머지 요소 중에서 가장 작은 요소)에 있는 경우 이를 무시합니다. 그렇지 않으면 Y[]의 첫 번째 멤버이기도 한 가장 작은 요소로 바꿉니다. 교체 후 정렬된 순서를 유지하려면 요소(현재 Y[0])를 Y[]의 적절한 위치로 전송합니다.
첫 번째 배열의 크기는 m이고 두 번째 배열의 크기는 n이며 시간 복잡도는 O(mn)입니다.
21. 높은 위치와 낮은 위치를 번갈아 가며 항목 배열을 재정렬하는 방법은 무엇입니까?
각 후속 멤버가 이전 및 다음 요소보다 크도록 정수 배열을 재정렬합니다. 배열에 중복 요소가 포함되어 있지 않다고 가정합니다.
어레이를 정렬하거나 추가 공간을 활용하는 것은 효과적인 접근 방식에 필요하지 않습니다. 우선 계획은 배열의 두 번째 구성원이며 각 루프 반복에 대해 XNUMX씩 증가합니다.
마지막 요소가 첫 번째 요소를 초과하면 구성 요소를 교체하십시오. 비슷한 맥락에서 다음 요소가 현재 요소보다 크면 두 항목을 전환합니다. 루프가 끝날 때 지정된 제한 사항을 준수하는 원하는 배열을 얻습니다.
22. 배열의 각 요소의 곱으로 나눗셈 연산자를 사용하지 않고 배열의 각 요소를 대체하는 방법은 무엇입니까?
나누기 연산자를 사용하지 않고 정수 배열의 각 요소를 다른 모든 요소의 곱으로 바꿉니다.
선형 시간과 상수 공간에서 재귀를 활용하여 이 문제를 해결할 수 있습니다. 오른쪽 하위 배열의 각 요소의 곱을 재귀적으로 계산하고 왼쪽 하위 배열 곱을 함수 매개 변수로 전달하는 것이 개념입니다.
시간 복잡도는 O(n)입니다.
23. 대수 시간으로 배열에서 가장 이상한 요소 찾기
하나를 제외한 모든 멤버의 발생 횟수가 짝수인 정수 배열이 주어지면 문제는 이 하나의 요소가 나타나는 횟수를 결정하는 것입니다. 배열에서 동일한 요소가 쌍으로 발생하고 한 행에 주어진 요소의 인스턴스가 두 개 이상 존재할 수 없는 경우 로그 시간 및 상수 공간에서 홀수 발생 요소를 찾습니다.
XOR 연산을 통해 선형 시간으로 이 문제를 해결할 수 있습니다. 목표는 배열의 모든 요소를 XOR하는 것입니다. 짝수 발생 요소가 서로 상쇄된 후 홀수 발생 요소만 남습니다.
이 문제는 O(log(n)) 시간에 해결할 수도 있습니다.
24. 원형 배열의 각 요소에 대한 후속 더 큰 요소를 얻는 방법은 무엇입니까?
순환 정수 배열의 각 요소에 대해 다음으로 큰 요소를 찾아야 합니다. 배열에서 요소 x 다음의 첫 번째 더 큰 정수는 해당 요소의 후속 더 큰 요소입니다.
오른쪽에서 왼쪽으로 배열 항목에 대해 작업할 수 있습니다. 목표는 스택이 비어 있거나 그 위에 더 높은 요소가 있을 때까지 각 요소 x에 대해 반복하는 것입니다. 그럴 때 스택 맨 위에 나타나도록 x의 다음으로 큰 요소를 설정합니다.
25. 어레이의 반전 횟수를 찾으십니까?
배열의 총 반전 수를 찾으십시오. 쌍 I j)는 I j)와 (A[i] > A[j])인 경우 배열 A의 반전이라고 합니다. 배열에 있는 이들의 모든 쌍을 계산해야 합니다.
오른쪽에 있는 것보다 적은 모든 배열 구성원을 세고 그 결과를 출력에 추가하는 것은 간단한 접근 방식입니다.
이 솔루션은 O(n2) 복잡도를 가지며 여기서 n은 입력 크기입니다.
26. 빗물 갇힘 문제는 무엇입니까?
폭이 각각 XNUMX단위인 주어진 막대 세트에 가둘 수 있는 가장 많은 물을 찾는 것은 "강우 가두기" 문제로 알려져 있습니다.
목표는 각 막대의 왼쪽과 오른쪽에 배치할 수 있는 가장 높은 막대를 결정하는 것입니다. 현재 막대의 높이보다 작은 왼쪽 및 오른쪽 선행 막대의 최소값은 각 막대 위에 저장된 물의 양입니다.
결론
다른 데이터 구조 항목과 비교할 때 배열은 더 간단합니다. 어레이 인터뷰 질문을 잘하기 위해서는 어레이에 대한 근본적인 이해가 필요합니다.
배열 작업(배열 선언/생성에서 배열 항목 액세스/수정까지)을 포함한 배열의 기초와 루프, 재귀 및 기본 연산자와 같은 프로그래밍 개념을 광범위하게 검토하여 배열 인터뷰 질문에 성공적으로 답해야 합니다. 문제를 완전히 인식하십시오.
질문이 있는 경우 설명을 구해야 합니다. 문제를 보다 관리하기 쉬운 부분으로 나누는 것을 고려하십시오. 프로그래밍을 시작하기 전에 알고리즘을 염두에 두어야 합니다. 그것을 적거나 흐름도에서 시각화하십시오. 그런 다음 코드 작성을 시작합니다.
댓글을 남겨주세요.