구 글 면접 문제 5 번 풀 기 (10 배)

구 글 면접 에피소드 에서 나 온 글 이 있어 요. 면접 문제.
문 제 는 이렇다.
만약 에 이것 이 각종 자모 로 구 성 된 문자열 이 있다 고 가정 하면 이것 은 또 다른 문자열 이 있 고 이 문자열 의 자모 수가 상대 적 으로 적다 고 가정 합 니 다.알고리즘 에 따 르 면 모든 작은 문자열 에 있 는 알파벳 이 큰 문자열 에 있 는 것 을 가장 빨리 찾 을 수 있 는 방법 은 무엇 입 니까?
예 를 들 어 다음 두 문자열 이 라면:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
정 답 은 true 입 니 다. string 2 에 있 는 모든 알파벳 string 1 도 있 습 니 다.다음 두 문자열 이 라면:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ
정 답 은 false 입 니 다. 두 번 째 문자열 의 Z 자 모 는 첫 번 째 문자열 에 없 기 때 문 입 니 다.
그 가 이 문 제 를 문 제 했 을 때, 과장 되 지 않 게 말 하면, 나 는 거의 입 에서 나 올 뻔 했다.사실 나 는 이 문제 에 대해 매우 자신 이 있다.(힌트: 내 가 제공 한 답 은 그 에 게 있어 서 최 악의 것 이 분명 하 다. 면접 에서 그의 수많은 사소한 표현 에서 알 수 있다.)
이런 조작 에 대해 유치 한 방법 은 두 번 째 문자열 의 모든 자 모 를 돌아 가면 서 첫 번 째 문자열 과 같은 지 확인 하 는 것 이다.알고리즘 에서 볼 때 이것 은 O (n * m) 차 조작 이 필요 합 니 다. 그 중에서 n 은 string 1 의 길이 이 고 m 는 string 2 의 길이 입 니 다.위의 예 를 들 어 최 악의 경우 16 * 8 = 128 번 의 조작 이 있 을 것 이다.
조금 더 좋 은 방안 은 이 두 문자열 의 자 모 를 정렬 한 다음 에 두 문자열 에 대해 순서대로 문의 하 는 것 이다.두 문자열 의 정렬 은 O (m log m) + O (n log n) 차 작업 이 필요 하 며, 이후 선형 스 캔 은 O (m + n) 차 작업 이 필요 합 니 다.마찬가지 로 위의 문자열 을 예 로 들 면 16 * 4 + 8 * 3 = 88 에 두 문자열 을 선형 으로 스 캔 하 는 16 + 8 = 24 의 조작 이 필요 합 니 다.(문자열 의 길이 가 증가 함 에 따라 이 알고리즘 의 효과 가 점점 좋아 질 것 이다)
결국, 나 는 그 에 게 가장 좋 은 알고리즘 을 알려 주 었 는데, O (n + m) 번 만 조작 하면 된다.방법 은 첫 번 째 문자열 에 대해 문의 하고 그 중의 모든 자 모 를 하나의 Hashtable 에 넣 는 것 이다 (원 가 는 O (n) 또는 16 번 조작).그리고 두 번 째 문자열 에 대해 물 어보 고 Hashtable 에서 모든 자 모 를 조회 하여 찾 을 수 있 는 지 확인 합 니 다.찾 지 못 하면 일치 하지 않 는 다 는 뜻 입 니 다.이것 은 8 번 의 조작 을 소모 할 것 이다. 이 두 가지 조작 을 합치 면 모두 24 번 밖 에 안 된다.좋 죠? 앞의 두 가지 방안 보다 좋 습 니 다.
가 이 는 움 직 이지 않 았 다."그 는 가죽 바지 가 부스럭 거 리 는 소 리 를 내 며 대답 했다."더 좋 은 것 은 없 습 니까?"라 고 그 가 물 었 다.
오 마 이 갓? 이 녀석 은 도대체 무엇 을 원 하 는 거 야? 나 는 화이트 보드 를 보고 그 에 게 로 돌 아 왔 다. "아니 야, O (n + m) 는 네가 얻 을 수 있 는 가장 좋 은 결과 야. 적어도 한 글자 에 한 번 은 방문 해 야 이 작업 을 완성 할 수 있다 는 거 야. 이 방안 은 마침 한 글자 에 한 번 만 접근 하 는 거 야. 내 가 옳다 고 확신 할 수록."
그 는 화이트 보드 앞으로 걸 어 갔다. "그렇다면? 만약 에 우리 가 일정한 수의 자모 로 문자열 을 구성한다 고 가정 하면 나 는 모든 자모 에 소 수 를 분배 하고 2 부터 뒤로 유추 할 것 이다.그러면 A 는 2, B 는 3, C 는 5, 등등.지금 나 는 첫 번 째 문자열 을 옮 겨 다 니 며 모든 자모 가 대표 하 는 소 수 를 곱 했다.너 는 결국 아주 큰 정 수 를 얻 게 될 거 야, 그렇지?그리고 두 번 째 문자열 을 알파벳 별로 나 누 어 물 어보 세 요.만약 제 거 된 결과 에 나머지 가 있다 면, 이것 은 일치 하지 않 는 자모 가 있다 는 것 을 설명 한다.만약 전체 과정 에서 나머지 가 없다 면, 너 는 그것 이 첫 번 째 문자열 이 적당 한 부분 집합 이라는 것 을 알 아야 한다.이러 면 안 돼 요?“
나 는 이 첫째 가 어떻게 소수 곱 하기 나 누 기 를 실 현 했 는 지 모 르 겠 지만, 나 로 서 는 실현 후 효과 가 크게 떨 어 졌 다.
1000000 회 순환 에 대해 서 는
checkStringInByHashMap: 203ms
checkStringInByPrime:        3357ms
10 배 차이 나 는 HashMap 으로 이 루어 지 는 것 은 간단 하고 빠르다.
그러나 HashMap 은 문자 가 포함 되 어 있 는 지 아 닌 지 를 조회 할 때마다 hash 와 찾 아야 하기 때문에 빠 르 지 않 습 니 다.
그래서 저 는 bitset 로 비트 로 고 를 표시 하 는 방법 을 실 현 했 습 니 다. 1000000 번 의 순환 은 11ms 만 필요 합 니 다.
결론: 황소 의 말 도 완전히 믿 을 수 없다. 모든 아름 다운 알고리즘 은 실제 테스트 결 과 를 기준 으로 해 야 한다.
bitset 소스 코드 구현:

	public boolean checkIfIn(MyBitSet set) {
		long tmp;
		if (this == set)
			return true;

		while (wordsInUse > set.wordsInUse)
			words[--wordsInUse] = 0;

		// Perform logical AND on words in common
		for (int i = 0; i < wordsInUse; i++) {
			tmp = words[i];
			tmp &= set.words[i];
			if (tmp != words[i]) {
				return false;
			}
		}
		return true;
	}

이상 은 큰 문자열 을 여러 번 사용 하 는 것 을 전제 로 합 니 다. 매번 다 르 면 간단 한 loop 이 가장 좋 은 방안 입 니 다. hashmap 를 만 드 는 비용 도 높 기 때 문 입 니 다.