Data Structures & Algorithms

​

10X Training

Why data structures & algorithms?

Agenda

• Array & linked list
• Stack & queue
• Hash table
• Tree
• Graph

• Communication
• Java Implementations
• Performance
• Algorithms
• Puzzles

Array & linked list

What’s an array?

• Which is better: array or linked list?
• Definition
• What properties?
• Performance
• What are the functions?
• What are the fastest functions?
• What are the slowest functions?
• Ideal use case
• Example? Example at Sentifi?
• Draw
• How do you explain visually?
• Real world analogy
• How do you explain to your grand mother?

What’s an array?

• Definition
• Finite size
• Contiguous
• Equally spaced
• Performance
• ❓add(E): Big O?
• ❓ Amortized constant time
• Don’t care for best/worst case
• get(i)
• remove(i)
• Ideal use case
• Finite list of items
• All publishers to be scored �this week

​

What’s a linked list?

• Definition
• What properties?
• Performance
• What are the functions?
• What are the fastest functions?
• What are the slowest functions?
• Ideal use case
• Example? Example at Sentifi?
• Draw
• How do you explain visually?
• Real world analogy
• How do you explain to your grand mother?

​

What’s a linked list?

• Definition
• Nodes, head, tail, next pointer
• Expandable
• Sparse
• Performance
• add(E)
• get(i)
• remove(i)
• Ideal use case
• Growing list of items
• User’s portfolios

Reverse a linked list

​

Given pointer to the head node of a linked list, the task is to reverse the linked list.

​

Input : Head of following linked list

1->2->3->4->NULL

Output : Linked list should be changed to,

4->3->2->1->NULL

How are arrays & lists implemented in Java?

• Native array
• ❓ List VS Set
• Both Interfaces
• Order
• Allow duplicate
• ❓ ArrayList VS LinkedList
• AL = Resizable array
• LL = Doubly linked list
• ❓ Vector
• V = Same as AL but synchronized

34

How many data structures classes/interfaces in JDK 1.8?

queue & stack

What’s a queue?

• Definition
• What properties?
• Performance
• What are the functions?
• What are the fastest functions?
• What are the slowest functions?
• Ideal use case
• Example? Example at Sentifi?
• Draw
• How do you explain visually?
• Real world analogy
• How do you explain to your grand mother?

​

What’s a queue?

• Definition
• Front & back
• FIFO
• Performance
• enqueue()
• dequeue()
• Ideal use case
• FIFO ordering
• Raw messages waiting� to be processed

What’s a stack?

• Definition
• What properties?
• Performance
• What are the functions?
• What are the fastest functions?
• What are the slowest functions?
• Ideal use case
• Example? Example at Sentifi?
• Draw
• How do you explain visually?
• Real world analogy
• How do you explain to your grand mother?

What’s a stack?

• Definition
• Top
• LIFO
• Performance
• pop()
• push()
• Ideal use case
• Navigation history
• Browser back button

MinStack

​

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

​

push(x) – Push element x onto stack.

pop() – Removes the element on top of the stack.

top() – Get the top element.

getMin() – Retrieve the minimum element in the stack.

​

​

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); // Returns -3.

minStack.pop();

minStack.peek(); // Returns 0.

minStack.getMin(); // Returns -2.

hashtable & tree

What’s a hash table?

• Definition
• What properties?
• Performance
• What are the functions?
• What are the fastest functions?
• What are the slowest functions?
• Ideal use case
• Example? Example at Sentifi?
• Draw
• How do you explain visually?
• Real world analogy
• How do you explain to your grand mother?

What’s a hash table?

• Definition
• Associative array
• Buckets /slots
• Hash function, collision
• Performance
• get()
• put()
• Ordering
• Ideal use case
• Indexing
• Lookup Person by full name

​

Fast LRU Cache

​

Implement an LRU cache.

​

LruCache cache = new LruCache();

cache.put(k, v); // O(1)

cache.get(k); // O(1)

How are hash tables implemented in Java?

• ❓ What’s the Java interface?
• Map
• ❓ HashMap VS HashSet VS HashTable
• HashMap = Map, one null key, not synchronized
• HashSet = Set, backed by actual hash table (HashMap)
• Hashtable = null not allowed, synchronized - DON’T USE
• ❓ LinkedHashSet
• Set with order
• Backed by DLL
• ❓ ConcurrentHashMap
• Thread Safe
• Replacement for Hashtable
• Python dict

tree

What’s a tree?

• Definition
• What properties?
• Performance
• What are the functions?
• What are the fastest functions?
• What are the slowest functions?
• Ideal use case
• Example? Example at Sentifi?
• Draw
• How do you explain visually?
• Real world analogy
• How do you explain to your grand mother?

What’s a tree?

• Definition
• Root, leaf
• Parent/children/sibling
• Depth, path
• Performance
• insert()
• search()
• remove()
• Ideal use case
• Hierarchical data
• Sentifi categories, world locations
• ❓Use in database
• Indexing for range search
• Find all users created in the past 30 days

112

What type of trees do you know?�How Pages in category "Trees (data structures)" on Wikipedia?

What’s a BST?

• Binary Search Tree
• ❓Properties
• Only 2 children
• Left subtree < right subtree
• Ordered
• In-order traversal is very efficient
• ❓Algorithm
• Depth first search

What’s a red-black tree?

• Binary Search Tree
• ❓What’s wrong with the blue tree? ---------->
• Degenerate tree
• Self balancing
• ❓Why
• Search performance

Breadth first search

​

​

What’s a trie?

• Tries - YouTube
• ❓Usage at Sentifi?
• Keyword matching for Ads
• ❓Benefit over HT for lookups?
• Space
• ❓Ideal use case over HT?
• Prefix-related queries
• Autocomplete

What’s a heap?

• ❓Properties
• Parent > Children (max heap)
• Parent < Children (min heap)
• Balanced
• Priority queue
• Backed by Heap
• ❓Why?
• insert()
• findMax()
• ❓Ideal use case
• Stream out of order events
• Task/job queue with priorities

How are trees implemented in Java?

• ❓new java.util.BinaryTree()?
• None
• ❓Why not?
• Scope? Easy to implement?
• ❓SortedSet, SortedMap
• Order is maintained (backed by tree)
• No DS tree in java...
• ...but some Collections are backed by trees
• ❓TreeSet, TreeMap
• Not trees but Set/Map interfaces!
• Backed by Red-Black tree

What’s a graph?

• ❓Properties?
• Tree with a cycle
• Directed VS Undirected
• Edge, vertices
• ❓Ideal use case
• Social network
• ❓How to store graph state in memory?
• Adjacency list, adjacency matrix

NY Metro

Given a square matrix representing the intersections of streets in a BIG city (like New York City) where each element of the matrix contains either 1 or 0 (meaning that there is or is not a stairwell to a subway at that location respectively)

​

Produce a new matrix of the same size where each element is the distance to the nearest subway stair well from that street intersection.

​

Example:

​

0 0 1 0

0 0 0 0

1 0 0 0

0 0 0 0

​

2 1 0 1

1 2 1 2

0 1 2 3

1 2 3 4

​

No

Is there a graph data structure in JDK 1.9?

concurrency

❓ How does concurrency affect DS?

• ❓Name some thread safe collections
• BlockingXXX: BlockingQueue
• ConcurrentXXX: ConcurrentHashMap
• ❓How to achieve thread safety?
• ❓Mutex. In Java?
• synchronized
• ❓Immutability. In Java?
• final
• ❓Copy the data. In Java?
• ...

❓ What are iterators?

• ❓ Have you ever used one?
• Yes. Enhanced for loop = syntactic shortcut
• ❓ Use cases for iterators?�while (iterator.hasNext()) {� iterator.remove(); �}
• Types of iterators?
• Fail fast = ConcurrentModificationException
• Collection is modified structurally �while one thread is iterating over it
• Weakly consistent = �Copy (with some synchronization)
• Snapshot = Copy (one time)

What’s CopyOnWriteArrayList?

• Snapshot iterator
• Snapshot when iterator is created
• ❓Performance impact?
• Slowwwwww
• ❓Use case?
• # traversal >>>>>> # mutations
• Lots of reads, few writes

Any other Java Data Structures?

• Guava
• ImmutableCollections: 100% thread-safe collections
• MultiSet, SortedMultiSet: Easily count number of occurrences of a specific element in a set
• Multimap: unlabeled directed graph
• bidirectional map: map in which both keys and values are unique and both should be usable as keys to search values
• CollectionUtilities: like java.util.Collections
• Apache Commons Collections
• MapIterator
• Bags
• Nobody really use it anymore

What have we learned?

What have we learned?

What have we learned?

What have we learned?

What have we learned?

What have we learned?

Thank you

​

​

Homework�Implement NY Metro�Homework2.nearestStairwell([][])�B+tree VS B-tree

Next�10X - Clean code