Heap & Graph & HashMap

No11视频 2:01:12

Summary:

Approach to solve tree problem: Recursion -->

classical recursion(bottom up) / carry on recursion(up to bottom)

  • 用O(n)时间，把n size 的问题变成一个n/2的问题

    • TC: O(n) --> quick selection

  • 用O(1)时间， 把n size的问题变成两个n/2的问题

    • TC: O(n) --> merge sort

Heap -->size + comparator(priority)

  • Priority Queue is one type of implementation of Heap

  • Heap的逻辑结构 is a tree

  • 存储结构是个unsorted array

  1. heap order: Min Heap / Max Heap minimum / maximum上下有序

  2. heap is always a complete binary tree

  3. only access the top node when you use it

  4. insert(push/offer/add) pop(poll/delete/remove) get update/put

    1. nitialize heapify

    2. heapify: O(n) convert an unsorted array to tree

    3. insert() O(logn)

    4. delete() O(logn) --> remove()

    5. update()O(logn) --> delete() insert()

  5. Given an element with index x in the unsorted array

  • Queue<Student> heap = new PriorityQueue<>()

    • by default it is a min Heap with primitive

Q1 L215 Kth Smallest to Largest Element in an Unsorted Array

  • need to clarify: from small to largest kth

  • no more space and time C

S1: Sort and return kth element, TC: nlogn SC: O(1) use quick sort(random pick 5 pivots and then pick the median) or count/bucket sort

S2: Quick Selection / QuickSort Partition + Binary Search

  1. find pivot

S3: MinHeap -> Size n

  1. nlogn one by one --> heapify the whole input array O(n)

  2. keep pop out k time O(klogn)

  3. TC: O(n+klog) SC:O(n)

  4. may be streaming flow or very large

  5. 结果是升序排列

S4: MaxHeap --> Size k

  1. heapify the first k elements from input array O(k)

  2. loop the remaining elements, if value of the element x is smaller than the heap top, delete and insert x into the heap

  3. TC: O(k +(n-k)logk) SC: O(k) 当k接近于n，S4 better than S3

  4. 需要从maxHeap里poll 出来，降序

S5: TreeSet/TreeMap

左右有序的数据结构

Q2 Top K Frequency words in an Dictionary

S1: HashMap + minHeap + Element

<key = word, value = frequency>

  • Element{word, frequency}

  • class Element{

    • String word;

    • int Frequency

    }

  • heap PriorityQueue<Element>

  • new comparator, return ele1.frequency - ele2.frequency(minHeap)

  • return ele2.freq- ele1.freq(maxHeap)

  • @Override

  • int compare(Element ele1, Element ele2){

  • }

  • for(Key key: map.keySet()) --> for(int num : nums) array, list, set, collection

  • for(Entry entry: map/entrySet(()) 遍历key value pair

S2: HashMap + TreeMap<Element>

S3: 如果内存放不下 could use Trie(26 个 char)

can only store space as 26^49, based on the first character, do 26 partition, to 26 different partition, then 26^49 could be dealled by 26 machines

S4:Distributed System Memory / Partition input / virtual vs physical

input too big, can't be store.单机放不下，多机进行

  • virtual vs physical, physical is about 16G, but for program, the space is about 160G, so we need machine to coordinate协调 the virtual address to transfer to which machine, which memory, which physical address.

    • For example: we opened some things which takes too many space, we have to move those not frequently used things to my hard disk, this hardware, for my memory system, is virtual .

S5: Big Data, MapReduce, 代替hashmap，to do the word count

HashMap --> tell your <Key, Value> pair

  1. why can get(key) byO(1)

    1. we could we have hash code.

  2. hash function hashcode

    1. 对k 取％ or ／；it is not consistent --> consistent hashing --> rehashing(耗时)

    2. MD5, SHA-1, SHA-2, hash编码方式

  3. avoid collision --> load factor ＝ 1

    1. separate chaining, like a single linked list

    2. open addressing, find the next available bucket

      1. linear proving: linear detect

  • HashTable: 线程安全（Thread safety); how to implement -->

    • 锁机制 --> 锁的key value pair

  • HashMap: 手写锁来保证thread safe

    • high performance, no time cost

  • HashSet :add(key) output return boolean, if addable return true, if noe addable return false

Hash is concrete class

Set:

  • set is a interface

  • set only store key, by <E>

  • 进行查重去重，de duplicate

  • set.contains(key)key是否存在

  • set.add(key) ➕得进去返回true，

  • set.remove(key)

  • keys are unique and TC:O(1)

Map: TC:O(1)

  • <key, value> 范型定义，不接受private

  • 基于key进行查重

  • 基于key value pair 产生的对应关系

    • key and value could be null

    • key is unique, but value could not be unique

  • 单向一一对应关系

    • how to 双向？use two hashMaps

  • map.contains(key)

  • map.get(key) --> getOrDefault()

  • map.put(key,value)新的值覆盖旧的值，如果刚create, return null

  • map.remove(key)

  • 实现限时即焚

    • put(key,value), get(key)

    • <key(string, expiredTime)>

  • 延时即焚

    • put(key,value), get(key)

  • 阅后即焚

    • get(key), + remove

String Hash

Q2 L268 Missing Number

clarify: sorted? 是否是等差数列吗？是nums, or string, or character?

  • S1: Sort -->one pass --> check arr[fast] - arr[fast-1] ==2, return fast/arr[fast]-1;

  • S2: Sort --> one pass --> check value with index, index can be implemented with counter initialized with 0;

  • S3: Sort --> binary search, check index and value

  • S4: unsorted --> HashMap<key = value of element, value = count>

    • two pass: build hashmap + check with counter ++

  • S5: HashSet<key = value of element>

    • tow passO(n)

    • build hashSet + check with counter ++

  • S6: Math

    • res + sum = (0 + n) * (n+1)/2

  • S7: XOR

Q2.1每个出现两次， find有且只有一个出现一次

  • arr[i] = i / 2;

Q2.2 每个出现m次，找出出现n次的

Q3 Given two array array1[n],array2[m], find the common elements

  • clarify data type: 查相等是hashSet, && sorted? && any duplicate common

  • S1:sort the array1 and array2

    • 1 3 5 8 10 11

    • i

    • 2 4 7 8 9 11

    • j

    • pointer(i j, move the smaller one)

    • TC:O(logn + m logm + m+ n)

  • S2: HashSet

    • add the whole array 1 into hashSetO(n)

    • loop all elements from the other array, check duplicateO(m)

    • time:O(m+n) Space O(n)

  • S3: sorted --> Binary Search TC: mlogn -->m(1 + n/m)

  • if the size of array has large difference, use Binary Search, otherwise ,use S1

Graph

  1. nodes edges

  2. connected or disconnected (union find)

  3. directed or non-directed

  4. cycle (most difference with tree), de-duplicated

  5. weight权重

  6. degree度，入度（多少指向我），出度（多少指向其他node）

class GraphNode{
    int value;
    ArrayList<GraphNode> neibours; HashMap<GraphNode, Weight>
    
    GraphNode(int x){
        value = x;
        Neighbours = new ArrayList<GraphNode>()
    }
}

Tree is a DAG(Directed Acyclic Graph)

  1. use Matrix to represent there is an edge or not

    1. if have edge with other node, input 1

    2. shortage: waste space since we don't care where is marked as '0'

  2. Adjacent List

    1. save SC

    2. shortage:

PreviousBinary (Search) Tree & Divide ConquerNext数据结构相互实现（A.K.A）

Last updated

Was this helpful?