설계 시험.우버 면접 문제 해결

나는 우연히 그가 구글에서 어떻게 일자리를 구할 수 있는지에 관한 수수께끼를 풀었다는 게시물을 보았다.이 글은 그가 이 문제를 해결하는 데 사용한 데이터 구조에 관한 것이다.
본문에서 우리는 다음과 같은 내용을 포함할 것이다.
1>나무가 뭐예요?
2> 왜 그리고 어떻게 사용하는지.
3>javascript에서 간단한 Trie를 실현하는 방법.
그래서 bisaclly는 이 난제를 해결하기 위해 트리/접두사 트리를 사용했는데,

트리가 뭐예요?

Tries는 트리 기반 데이터 구조로 문자열을 효율적으로 저장하는 데 사용된다.

그것들은 어떻게 사용합니까?

상상해 보세요. 당신의 임무는 미국의 모든 도시 이름을 저장하는 것입니다.
가장 간단한 방법은 모든 도시 이름을 가져와 하나의 그룹에 저장하는 것입니다. 그러나 닌자 개발자이기 때문에 모든 도시 이름을 저장하는 데 필요한 총 공간을 줄이는 데 도움이 될 수 있습니다.
다음은 모든 이름의 접두사가 "New"인 도시의 목록입니다.

 "New Albany"                          "New Bedford"
 "New Bern"                            "New Braunfels"
 "New Britain"                         "New Kensington"
 "New London"                          "New Madrid"
 "New Market"                          "New Martinsville"
 "New Mexico"                          "New Milford"
 "New Orleans"                         "New Paltz"
 "New Philadelphia"                    "New Rochelle"
 "New Smyrna Beach"                    "New Ulm"
 "New Windsor"                         "New York"
 "New York City"                       "New Brunswick"
 "New Castle"                          "New Glarus"
 "New Hampshire"                       "New Harmony"
 "New Haven"                           "New Hope"
 "New Iberia"                          "New Jersey"

따라서 매번 "New"를 반복하는 것보다 그것을 압축하는 것이 낫습니까?
"New"는 일반적인 접두사이기 때문에 모든 단어에서 "New"를 삭제하고 데이터 구조를 만들어 "New"를 상기 도시에 자동으로 추가할 수 있습니다. 예를 들어
예를 들어 4개 도시의 경우 다음과 같이 표시됩니다.

근데 앞으로 한 발짝 더 가는 게 어때요?
'뉴마드리','신시장','뉴마틴스빌'은 모두'뉴마'의 공통점이 있기 때문에 문자열을 더욱 압축합시다.
이렇게 함으로써 우리는 모든 도시에 도착했다.

재밌게 놀고 하나 만들자here
같은 공공 접두사를 가진 도시가 한데 묶여 있어 공간을 줄이는 데 도움이 된다.
더 많아!!!
어떻게 시도를 통해 검색 속도를 크게 가속화합니까?
trie와 array에 존재하는 검색을 시뮬레이션해 보겠습니다.

검색 속도가 매우 빠르다. 왜냐하면 우리는 수조에서 교체할 필요가 없고 6개 각도에서 결과를 얻을 수 있기 때문이다.
trie 및 배열에 없는 검색 문자열:

4개의 각도에서 검색 문자열이 존재하는지 확인할 수 있습니다.

적용:

Trie는 많은 곳에서 사용되고 있다. 예를 들어 자동 완성 기능(우리는 다음 블로그에서 구축할 것이다), 데이터 분석, Gnome 분석, 맞춤법 검사 등이다.
이제 우리는 트리가 무엇인지, 그리고 그것이 왜 유용한지 알게 되었다. 우리 하나를 구축하자!

Trie 구축

우리는 ['abc','abab','babc','cab'를 위해 트리를 구축할 것이다]
효율성을 높이기 위해 O(1) 검색을 이용하여 Trie를 구축하기 위해 객체를 사용합니다.

1단계

우리는 기본적으로 나무를 구축하고 있기 때문에, 트리에 대해서는 뿌리가 비어 있지만, 하위 대상에 대한 정보를 저장할 뿌리가 필요합니다.

class Trie{
    constructor(){
         this.root = {}
    }
}

2단계:

이제 그룹 ['abc','abab','ba','cab'의 모든 문자열을 훑어보고 트리를 만듭니다.
먼저 "abc":
우리는 트리에'a'가 있는지 확인합니다. 뿌리가 비어 있기 때문에 존재하지 않기 때문에'a'를 트리에 추가한 다음'b'를 추가한 다음'c'를 추가합니다.기왕 우리가trie의 끝에 도달했으니, 우리는 단어'abc'를 저장하여'예'를 표시하고,'abc'는 효과적인 단어이다.
우리는 여기서 끝난다:
두 번째'abab'.
우리는 같은 과정을 반복한다. 우리는 "a"가 존재하는지 검사한다. 왜냐하면 이것은 존재하기 때문이다. 우리는 새로운 노드를 만들지 않고 "a"노드로 돌아간다. 그리고 우리는 "b"가 존재하는지, "a"노드에 연결되어 있는지 검사한다. 그러므로 "a"노드가 "b"노드에 연결되어 있지 않기 때문에 우리는 새로운 "a"노드를 만들어서 "b"노드에 연결하고 계속 반복한다.
따라서 문자열을 Trie에 삽입하면 세 가지 기본 단계로 귀결됩니다.
1> 역할이 노드에 연결되지 않으면 새 노드를 생성하고 변환합니다.
2> 역할이 노드에 연결되어 있으면 변환합니다.
3 > 문자열의 끝인 경우 현재 하위 트리의 잎에 문자열을 추가합니다.
시각화:

코드로 번역해 보겠습니다.

  insert(word) {
    let node = this.root;                            
    for (let c of word) {
      if (node[c] == null) node[c] = {};             //if {c} not present, create one
      node = node[c];                                // travese{c} 
    }
    node.isWord = true;                              // add word.
  }

따라서 모든 문자열에 대해 루트와travese부터 시작합니다.
모든 문자 c에 대해 대상을 만들었는지 확인하고, 만들지 않으면 그것을 만들고 반복합니다.
마지막으로, 우리는'abc'를true로 설정하여'네,'abc'문자열을 사용할 수 있습니다.
따라서 ["abc", "abab"] 우리의 실제 trie는 다음과 같다.

let root = {
  "a":{
    "b":{
      "c":{
        isWord:true
      },
      isWord:false,
      "a":{
        "b":{
          "isWord":true
        },
        isWord:false
      },
      isWord:false
    },
    isWord:false
  },
  isWord: false
}

console.log(root.a);
console.log(root.a.b);
console.log(root.a.b.c);
console.log(root.a.b.c.isWord);
console.log(root.a.b.a);
console.log(root.a.b.a.b);
console.log(root.a.b.a.b.isWord);
console.log(root.a.b.isWord);
console.log(root.a.b.f == null);

이제 삽입과 유사한 함수를 만듭니다.

 traverse(word) {
    let node = this.root;
    for (let c of word) {
      node = node[c];
      if (node == null) return null;
    }
    return node;
  }

검색을 위해 문자열을 훑어보고 "isWord"가true로 설정되었는지 확인합니다.

  search(word) {
    const node = this.traverse(word);
    return node != null && node.isWord === true;
  }

요컨대

class Trie {
  constructor() {
    this.root = {};
  }

  insert(word) {
    let node = this.root;
    for (let c of word) {
      if (node[c] == null) node[c] = {};
      node = node[c];
    }
    node.isWord = true;
  }

  traverse(word) {
    let node = this.root;
    for (let c of word) {
      node = node[c];
      if (node == null) return null;
    }
    return node;
  }

  search(word) {
    const node = this.traverse(word);
    return node != null && node.isWord === true;
  }
}

나는 이 문장이 충분하다고 생각한다. 다음 문장은 트리에 기반한 검색을 자동으로 만드는 방법을 소개할 것이다.
github:https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/DataStructures/Trie.js