During programming, it's important to design and use right data structures.
Here is a list of problems that we can use to improve our data structure design skills.
Design an in-memory search engine
How to index and store in memory
How to support free text queries, phrase queries
Map<String, List<Document>>
List<Document> is sorted
Document: docId, List<Long> positionIds
List<Long> is sorted
How to save to files
How to merge small files into big files
-- When save to file, make it sorted by word
-- Use merge sort to merge multiple fields
How to make it scalable - how solr cloud works
Google – Manager Peer Problem
1. setManager(A, B) sets A as a direct manager of B
2. setPeer(A, B) sets A as a colleague of B. After that, A and B will have the same direct Manager.
3. query(A, B) returns if A is in the management chain of B.
Tree + HashMap
Map<Integer, TNode> nodeMap
TNode: value, parent, neighbors
Design an Excel sheet’s Data structure
http://codeinterviews.com/Uber-Design-Excel/
You need to perform operations like addition. The excel sheet is very sparse and is used to store numbers in the range 1-65K. Index for a cell is known.
Sparse table: Map<Integer, Map<Integer, String>> data
Follow-up question: In excel, one cell can refer to other cells, if I update one cell, how do you update all the dependent cells？
--Topological sort
- Use multiple data structures
Design a data structure that supports insert, delete, search and getRandom in constant time
private List<String> list = new ArrayList<String>();
Map<String,Integer> indexes = new HashMap<String,Integer>();
-- When remove key, swap the old element in list with the last element, and change the last element index to its new location
Follow up
- What if the value may be duplicated?
- How to test getRandom()?
-- Implement addItem - O(1), getTop10Items
-- Implement HashTable with get,set,delete,getRandom functions in O(1).
Implement Get and Insert for TimeTravelingHashTable
- insert(key, value, timestamp)
- get(key, timestamp)
- get(key) // returns value associated with key at latest time.
Map<K, TreeMap<Float, V>> keyToBSTMap = new HashMap<>();
public V get(K k, Float time){
if(keyToBSTMap.containsKey(k) == false) return null;
if(keyToBSTMap.get(k).containsKey(time))
return keyToBSTMap.get(k).get(time);
else
return keyToBSTMap.get(k).lowerEntry(time).getValue();
}
Stack supports getMin or getMax
Stack<Integer> main = new Stack<>();
Stack<Integer> minStack = new Stack<>();
Design a stack with operations(findMiddle|deleteMiddle) on middle element
-- Use Double Linked List
LeetCode 311 - Sparse Matrix Multiplication
https://discuss.leetcode.com/topic/30631/my-java-solution
Map<Integer, HashMap<Integer, Integer>> tableA, tableB
Design SparseVector:
-- supports dot(SparseVector that)
Design SparseMatrix
-- supports plus(SparseMatrix that)
Google - remove alarm
https://reeestart.wordpress.com/2016/06/30/google-remove-alarm/
hash map - map priority to set of alarm id
max priority heap - PriorityQueue<Integer>
Recover a Quack Data Structure
Two Sum III - Data structure design
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
1. O(1) add, O(n) find
2. O(n) add, O(1) find
Add and Search Word
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
Shortest Word Distance II
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
Your method will be called repeatedly many times with different parameters.
Map<String, List<Integer>> map: word -< sorted index
Here is a list of problems that we can use to improve our data structure design skills.
Design an in-memory search engine
How to index and store in memory
How to support free text queries, phrase queries
Map<String, List<Document>>
List<Document> is sorted
Document: docId, List<Long> positionIds
List<Long> is sorted
How to save to files
How to merge small files into big files
-- When save to file, make it sorted by word
-- Use merge sort to merge multiple fields
How to make it scalable - how solr cloud works
Google – Manager Peer Problem
1. setManager(A, B) sets A as a direct manager of B
2. setPeer(A, B) sets A as a colleague of B. After that, A and B will have the same direct Manager.
3. query(A, B) returns if A is in the management chain of B.
Tree + HashMap
Map<Integer, TNode> nodeMap
TNode: value, parent, neighbors
Design an Excel sheet’s Data structure
http://codeinterviews.com/Uber-Design-Excel/
You need to perform operations like addition. The excel sheet is very sparse and is used to store numbers in the range 1-65K. Index for a cell is known.
Sparse table: Map<Integer, Map<Integer, String>> data
Follow-up question: In excel, one cell can refer to other cells, if I update one cell, how do you update all the dependent cells？
--Topological sort
- Use multiple data structures
Design a data structure that supports insert, delete, search and getRandom in constant time
private List<String> list = new ArrayList<String>();
Map<String,Integer> indexes = new HashMap<String,Integer>();
-- When remove key, swap the old element in list with the last element, and change the last element index to its new location
Follow up
- What if the value may be duplicated?
- How to test getRandom()?
-- Implement addItem - O(1), getTop10Items
-- Implement HashTable with get,set,delete,getRandom functions in O(1).
Implement Get and Insert for TimeTravelingHashTable
- insert(key, value, timestamp)
- get(key, timestamp)
- get(key) // returns value associated with key at latest time.
Map<K, TreeMap<Float, V>> keyToBSTMap = new HashMap<>();
public V get(K k, Float time){
if(keyToBSTMap.containsKey(k) == false) return null;
if(keyToBSTMap.get(k).containsKey(time))
return keyToBSTMap.get(k).get(time);
else
return keyToBSTMap.get(k).lowerEntry(time).getValue();
}
Stack supports getMin or getMax
Stack<Integer> main = new Stack<>();
Stack<Integer> minStack = new Stack<>();
Design a stack with operations(findMiddle|deleteMiddle) on middle element
-- Use Double Linked List
LeetCode 311 - Sparse Matrix Multiplication
https://discuss.leetcode.com/topic/30631/my-java-solution
Map<Integer, HashMap<Integer, Integer>> tableA, tableB
Design SparseVector:
-- supports dot(SparseVector that)
Design SparseMatrix
-- supports plus(SparseMatrix that)
Google - remove alarm
https://reeestart.wordpress.com/2016/06/30/google-remove-alarm/
hash map - map priority to set of alarm id
max priority heap - PriorityQueue<Integer>
Recover a Quack Data Structure
Copy its all elements in to an array
--it's pop()/peek() randomly remove or return first or last elementTwo Sum III - Data structure design
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
1. O(1) add, O(n) find
2. O(n) add, O(1) find
Add and Search Word
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
Shortest Word Distance II
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
Your method will be called repeatedly many times with different parameters.
Map<String, List<Integer>> map: word -< sorted index
