@violangreg/

HashTable practice

JavaScript

No description

fork
loading
main.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//Google Question
//Given an array = [2,5,1,2,3,5,1,2,4]:
//It should return 2

//Given an array = [2,1,1,2,3,5,1,2,4]:
//It should return 1

//Given an array = [2,3,4,5]:
//It should return undefined

class HashTable {
  constructor(size){
    this.data = new Array(size);
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++){
        hash = (hash + key.charCodeAt(i) * i) % this.data.length
    }
    return hash;
  }

  set(key) {
    let address = this._hash(key);
    
    if(!this.data[address]){
      this.data[address] = new Array();
    }

    let bucket = {
      key: key
    };

    this.data[address].push(bucket);
  }

  get(key) {
    const buckets = this.data[this._hash(key)];
    for(var i in buckets)
    {
      if(buckets[i].key == key)
        return buckets[i].key;
    }
  }
}

function firstRecurringCharacter(input) {
  let myHashTable = new HashTable(input.length);
  
  for(var i in input){
    if(myHashTable.get(input[i]) != undefined)
      return myHashTable.get(input[i]);
    myHashTable.set(input[i]);
  }
}

function firstRecurringCharacter2(input) {
  let map = {};
  
  for(var i in input){
    if(map[input[i]] != undefined)
      return input[i];
    else map[input[i]] = 0;
  }
}
  
firstRecurringCharacter2([2,5,5,2,3,5,1,2,4])

//Bonus... What if we had this:
// [2,5,5,2,3,5,1,2,4]
// return 5 because the pairs are before 2,2
Native Browser JavaScript