hash table

*HashMap.java

1. Separate chaining
 linked lists of values
  * search time complexity: logn

2. Open addressing
 Insert(k): Keep probing until an empty slot is found. Once an empty slot is found, insert k.
 Search(k): Keep probing until slot’s key doesn’t become equal to k or an empty slot is reached.
  *  linear probing
 


               Seperate Chaining	                                   Open Addressing
1.	Simpler to implement.	                                       equires more computation.
2.	never fills up, always add more elements to chain 	          table may become full.
3.	Less sensitive to the hash function or load factors 	        equires extra care for to avoid clustering and load factor.
4.	used when it is unknown how many and how frequently          used when the frequency and number of keys is known.
   keys may be inserted or deleted.	  
5.	Cache performance of chaining is not good as keys            better cache performance as everything is stored in the same table.
   are stored using linked list 	
6.	Wastage of Space                                             a slot can be used even if an input doesn’t map to it
   (Some Parts of hash table in chaining are never used).	 
7.	extra space for links 	                                      No links in Open addressing

HashMap<Integer, String> map = new HashMap<Integer, String>();
map.put(0, "a");
map.containsKey(-1);  // false
map.get(0); //"a"
map.keySet() // [0]
map.values() // ["a"]
map.size(); //1
map.clear(); //

Counter.py

266. Palindrome Permutation
https://leetcode.com/problems/palindrome-permutation/description/
Input: "aab"
Output: true
Input: "carerac"
Output: true
class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        counter = collections.Counter(s)
        cnt = 0
        for c in counter.values():
            cnt += c%2
        return cnt < 2  

242. Valid Anagram
https://leetcode.com/problems/valid-anagram/description/
Input: s = "anagram", t = "nagaram"
Output: true
class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return collections.Counter(s)==collections.Counter(t)
    
409. Longest Palindrome
https://leetcode.com/problems/longest-palindrome/description/    
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        counter= collections.Counter(s)
        nums= counter.values()
        odd = sum(num%2 for num in nums)
        return sum(nums) - odd + (odd>0)    
    
387. First Unique Character in a String
https://leetcode.com/problems/first-unique-character-in-a-string/description/
class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        #runtime complexity O(nlogn + n)  space complexity O(n)
        counter = collections.Counter(s)
        for i, c in enumerate(s):
            if counter[c]== 1:  return i
            
        return -1
825. Friends Of Appropriate Ages
https://leetcode.com/problems/friends-of-appropriate-ages/description/
Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person. 

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100
Otherwise, A will friend request B.

class Solution(object):
    def numFriendRequests(self, ages):
        """
        :type ages: List[int]
        :rtype: int
        """
        count = collections.Counter(ages)

        ans = 0
        for ageA, countA in count.items():
            for ageB, countB in  count.items():
                if ageA * 0.5 + 7 >= ageB or ageA < ageB or ageA < 100 < ageB: continue
                #countA * (countA - 1)
                ans += countA * countB
                if ageA == ageB: ans -= countA
        return ans

Distinct Characters.py

340. Longest Substring with At Most K Distinct Characters
https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
Given a string, find the length of the longest substring T that contains at most k distinct characters.
Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.
Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.
  
class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        # O(n)
        d= {}
        low= 0
        ans= 0
        for i, v in enumerate(s):
            d[v]= i
            if len(d) > k:
                low= min( d.values() )
                del d[ s[low] ]
                low += 1
            ans= max(ans, i-low+1)
        
        return ans

hash table collisions

time complexity 

* separate chaining

insert O(n)
search O(n)
delete O(n)


* open addressing 
insert O(n)
search O(n)
delete O(n)

sort by values.java

451. Sort Characters By Frequency
https://leetcode.com/problems/sort-characters-by-frequency/description/
public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
						
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        pq.addAll(map.entrySet());
				
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Map.Entry e = pq.poll();
            for (int i = 0; i < (int)e.getValue(); i++) 
                sb.append(e.getKey());
        }
        return sb.toString();
    }
}

sum.py

1. Two Sum
https://leetcode.com/problems/two-sum/description/
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # rumtime complexity: O(N) N=len(nums)  space complexity  O(N)
        d = {}
        for i, num in enumerate(nums):
            if target-num in d:
                return [i, d[target-num]]
            d[num] = i