2020 May 23 Problems
54 views
Skip to first unread message
mohan kumar
May 23, 2020, 3:00:11 PM5/23/20
to leetcod...@googlegroups.com
class LFUCache {
Map<Integer, Integer> vals;
Map<Integer, Integer> counts;
Map<Integer, LinkedHashSet> lists;
int capacity;
int min;
public LFUCache(int capacity) {
vals = new HashMap<>();
counts = new HashMap<>();
lists = new HashMap<>();
this.capacity = capacity;
min = -1;
lists.put(1, new LinkedHashSet<>());
}
public int get(int key) {
if(!vals.containsKey(key))
return -1;
int count = counts.get(key);
counts.put(key, count+1);
lists.get(count).remove(key);
if(count==min && lists.get(count).size()==0)
min++;
if(!lists.containsKey(count+1))
lists.put(count+1, new LinkedHashSet<>());
lists.get(count+1).add(key);
return vals.get(key);
}
public void put(int key, int value) {
if(capacity<=0)
return;
if(vals.containsKey(key)) {
vals.put(key, value);
get(key);
return;
}
if(vals.size() >= capacity) {
int evit = (int)lists.get(min).iterator().next();
lists.get(min).remove(evit);
vals.remove(evit);
}
vals.put(key, value);
counts.put(key, 1);
min = 1;
lists.get(1).add(key);
}
}
Map<Integer, Integer> vals;
Map<Integer, Integer> counts;
Map<Integer, LinkedHashSet> lists;
int capacity;
int min;
public LFUCache(int capacity) {
vals = new HashMap<>();
counts = new HashMap<>();
lists = new HashMap<>();
this.capacity = capacity;
min = -1;
lists.put(1, new LinkedHashSet<>());
}
public int get(int key) {
if(!vals.containsKey(key))
return -1;
int count = counts.get(key);
counts.put(key, count+1);
lists.get(count).remove(key);
if(count==min && lists.get(count).size()==0)
min++;
if(!lists.containsKey(count+1))
lists.put(count+1, new LinkedHashSet<>());
lists.get(count+1).add(key);
return vals.get(key);
}
public void put(int key, int value) {
if(capacity<=0)
return;
if(vals.containsKey(key)) {
vals.put(key, value);
get(key);
return;
}
if(vals.size() >= capacity) {
int evit = (int)lists.get(min).iterator().next();
lists.get(min).remove(evit);
vals.remove(evit);
}
vals.put(key, value);
counts.put(key, 1);
min = 1;
lists.get(1).add(key);
}
}
--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
https://www.techbayarea.us/
whatsapp group : https://chat.whatsapp.com/GxL7anhP9swEWgAsntkrm8
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/9a374064-1e10-4557-8ccb-5121cf7cc74c%40googlegroups.com.
Tarini Pattanaik
May 23, 2020, 9:01:12 PM5/23/20
to leetcod...@googlegroups.com
819. Most Common Word
Runtime: 15 ms, faster than 37.58% of Java online submissions for Most Common Word.
public String mostCommonWord(String paragraph, String[] banned) {
LinkedList<String> bannedList = new LinkedList<String>();
for (String bannedWord: banned) {
bannedList.add(bannedWord);
}
paragraph = paragraph.replaceAll("[^a-zA-Z0-9]", " ");
paragraph = paragraph.toLowerCase();
paragraph = paragraph.trim();
String[] wordArray = paragraph.split(" ");
Map<String, Integer> map = new HashMap<String, Integer>();
int maxCount = 0;
String result = "";
for (String word: wordArray) {
String lowerWord = word.trim();
if (lowerWord.length() > 0 && !bannedList.contains(lowerWord)) {
int count = map.getOrDefault(lowerWord, 0);
count = count + 1;
if (count > maxCount) {
maxCount = count;
result = lowerWord;
}
if (lowerWord.length() > 0) {
map.put(lowerWord, count);
}
}
}
return result;
}
LinkedList<String> bannedList = new LinkedList<String>();
for (String bannedWord: banned) {
bannedList.add(bannedWord);
}
paragraph = paragraph.replaceAll("[^a-zA-Z0-9]", " ");
paragraph = paragraph.toLowerCase();
paragraph = paragraph.trim();
String[] wordArray = paragraph.split(" ");
Map<String, Integer> map = new HashMap<String, Integer>();
int maxCount = 0;
String result = "";
for (String word: wordArray) {
String lowerWord = word.trim();
if (lowerWord.length() > 0 && !bannedList.contains(lowerWord)) {
int count = map.getOrDefault(lowerWord, 0);
count = count + 1;
if (count > maxCount) {
maxCount = count;
result = lowerWord;
}
if (lowerWord.length() > 0) {
map.put(lowerWord, count);
}
}
}
return result;
}
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/CAFdrHHV2c%2Bmm2YtbbEKRF5_v_EPUz3stho-coSC9ezC7dN%3D2pw%40mail.gmail.com.
Tarini Pattanaik
May 24, 2020, 2:43:25 AM5/24/20
to leetcod...@googlegroups.com
863. All Nodes Distance K in Binary Tree
Runtime: 10 ms, faster than 87.02% of Java online submissions for All Nodes Distance K in Binary Tree.
======
Map<TreeNode, TreeNode> map;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> list = new LinkedList<Integer>();
map = new HashMap<TreeNode, TreeNode>();
traverse(root, null);
Queue<TreeNode> queue = new LinkedList<TreeNode>();
Set<TreeNode> visited = new HashSet<TreeNode>();
queue.add(target);
visited.add(target);
while(queue.size() > 0 && K >= 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode current = queue.poll();
if (K == 0)
list.add(current.val);
if (current.left != null && visited.add(current.left))
queue.add(current.left);
if (current.right != null && visited.add(current.right))
queue.add(current.right);
//add parent of the current node to the queue
if ( (map.get(current) != null) && visited.add(map.get(current)))
queue.add(map.get(current));
}
K--;
}
return list;
}
void traverse(TreeNode root, TreeNode parent) {
if (root == null)
return;
map.put(root, parent);
traverse(root.left, root);
traverse(root.right, root);
}
}
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> list = new LinkedList<Integer>();
map = new HashMap<TreeNode, TreeNode>();
traverse(root, null);
Queue<TreeNode> queue = new LinkedList<TreeNode>();
Set<TreeNode> visited = new HashSet<TreeNode>();
queue.add(target);
visited.add(target);
while(queue.size() > 0 && K >= 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode current = queue.poll();
if (K == 0)
list.add(current.val);
if (current.left != null && visited.add(current.left))
queue.add(current.left);
if (current.right != null && visited.add(current.right))
queue.add(current.right);
//add parent of the current node to the queue
if ( (map.get(current) != null) && visited.add(map.get(current)))
queue.add(map.get(current));
}
K--;
}
return list;
}
void traverse(TreeNode root, TreeNode parent) {
if (root == null)
return;
map.put(root, parent);
traverse(root.left, root);
traverse(root.right, root);
}
}
Rudy Talukder
May 24, 2020, 4:49:47 PM5/24/20
to leetcod...@googlegroups.com
Runtime: 36 ms, faster than 55.43% of Python3 online submissions for Most Common Word.
Memory Usage: 13.7 MB, less than 5.88% of Python3 online submissions for Most Common Word.
O(Time) = N
O(Space) = N
class Solution:
def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
paralow = paragraph.lower()
paralow = re.sub(',|\.|!|\?|;|\'',' ',paralow)
parastrlist = paralow.split()
wordlist=[]
worddict = {}
for i in parastrlist:
wordlist.append(i)
for i in wordlist:
if i in worddict.keys():
worddict[i] += 1
else:
worddict[i] = 1
maxval = 0
maxkey = None
for key in worddict.keys():
if ( (worddict[key] > maxval) and (key not in banned) ):
maxval = worddict[key]
maxkey = key
return maxkey
FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/CANQx_ARgsqE7eG5UvW_iaFv6V2D%3DwXkqC7bOP%2BLTiOxf9kmaCQ%40mail.gmail.com.
Abhishek Kaukuntla
May 26, 2020, 11:45:05 PM5/26/20
to leetcode-meetup
| 819 | Most Common Word | 44.2% | Easy |
class Solution {
/*
Approach:
1. Split the paragraph into an array of words by punctuation marks/whitespace.
2. Store the count of each occurrence of word in a map
3. Remove the banned words from the map
3. Find the most frequently occurring word from the map
Runtime: 17 ms, faster than 29.46% of Java online submissions for Most Common Word.
Memory Usage: 40.1 MB, less than 5.05% of Java online submissions for Most Common Word.
Time complexity: O(P + B) where P is the length of paragraph and B is the size of banned words
Space complexity: O(P)
*/
public String mostCommonWord(String paragraph, String[] banned) {
// Create an array of words from the paragraph
String[] words = paragraph.toLowerCase().split("[!?',;.\\s]");
// Store the count of word occurrences in a map
Map<String, Integer> wordCount = new HashMap<String, Integer>();
for (String word: words) {
word = word.trim();
if (word.isEmpty()) {
continue;
}
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
// Remove the banned words
for (String bannedWord: banned) {
if (wordCount.containsKey(bannedWord)) {
wordCount.remove(bannedWord);
}
}
// Find the max count
int maxCount = 0;
String maxWord = "";
Set<String> keys = wordCount.keySet();
for (String key: keys) {
int count = wordCount.get(key);
if (count > maxCount) {
maxCount = count;
maxWord = key;
}
}
return maxWord;
mohan kumar
May 27, 2020, 1:22:46 AM5/27/20
to leetcod...@googlegroups.com
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
Map<TreeNode, TreeNode> parents = new HashMap<>();
dfs(root, null, parents);
List<Integer> result = new ArrayList<>();
if(K == 0){
result.add(target.val);
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
Set<TreeNode> visited = new HashSet<>();
queue.offer(target);
visited.add(target);
int distance = 0;
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0; i<size; i++){
TreeNode curr = queue.poll();
if(curr.left!= null){
if(!visited.contains(curr.left)){
queue.offer(curr.left);
visited.add(curr.left);
}
}
if(curr.right!= null){
if(!visited.contains(curr.right)){
queue.offer(curr.right);
visited.add(curr.right);
}
}
if(parents.get(curr) != null){
if(!visited.contains(parents.get(curr))){
queue.offer(parents.get(curr));
visited.add(parents.get(curr));
}
}
}
distance++;
if(distance == K){
while(!queue.isEmpty()){
result.add(queue.poll().val);
}
return result;
}
}
return result;
}
private void dfs(TreeNode root, TreeNode parent, Map<TreeNode, TreeNode> parents){
if(root == null) return;
parents.put(root, parent);
dfs(root.left, root, parents);
dfs(root.right, root, parents);
}
}
dfs(root, null, parents);
List<Integer> result = new ArrayList<>();
if(K == 0){
result.add(target.val);
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
Set<TreeNode> visited = new HashSet<>();
queue.offer(target);
visited.add(target);
int distance = 0;
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0; i<size; i++){
TreeNode curr = queue.poll();
if(curr.left!= null){
if(!visited.contains(curr.left)){
queue.offer(curr.left);
visited.add(curr.left);
}
}
if(curr.right!= null){
if(!visited.contains(curr.right)){
queue.offer(curr.right);
visited.add(curr.right);
}
}
if(parents.get(curr) != null){
if(!visited.contains(parents.get(curr))){
queue.offer(parents.get(curr));
visited.add(parents.get(curr));
}
}
}
distance++;
if(distance == K){
while(!queue.isEmpty()){
result.add(queue.poll().val);
}
return result;
}
}
return result;
}
private void dfs(TreeNode root, TreeNode parent, Map<TreeNode, TreeNode> parents){
if(root == null) return;
parents.put(root, parent);
dfs(root.left, root, parents);
dfs(root.right, root, parents);
}
}
--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
https://www.techbayarea.us/
FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/4c55850d-f33f-4bc0-bc95-c240a94e02df%40googlegroups.com.
Daryl Wang
May 30, 2020, 11:52:26 AM5/30/20
to leetcode-meetup
| 819 | Most Common Word | 44.2% | Easy |
A basic dictionary problem. Use a dictionary to store the counts of all the words, then go through all the words to find the word with highest count and isn't in the banned list.
The most difficult part of the problem is dealing with capitalization and punctuation. The easiest way to deal with capitalization is to turn everything into lower case. For punctuation I've replaced the punctuation characters with empty space so I can use Python's split method, but if you're iterating through the string character by character to find words then punctuation characters become word break points along with white space.
O(n) space
O(n) space
O(n^2) time. Strictly speaking checking whether a word is banned ends up taking O(n^2) time, but since there are at most 100 banned words this is not a huge issue in practice.
class Solution:
def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
paragraph = paragraph.lower()
for punc in "!?',;.":
paragraph = paragraph.replace(punc, ' ')
words = paragraph.split()
counts = collections.Counter(words)
max_count = 0
ans = ""
for word in counts:
if word not in banned and counts[word] > max_count:
max_count = counts[word]
ans = word
return ans
On Saturday, May 23, 2020 at 9:22:56 AM UTC-7, Daryl Wang wrote:
Daryl Wang
May 30, 2020, 12:24:06 PM5/30/20
to leetcode-meetup
| 863 | All Nodes Distance K in Binary Tree | 54.1% | Medium |
This problem is simple when the target and root node are the same: it is just breadth first search for all nodes at depth K.
The tricky part is when is the target is not the root. The approach is to do a depth search to find the path to the target node. Once we have that path, we can then do a bunch of breadth first searches from the nodes in the path to find all nodes K distance away from the target. There are three types of nodes in the path:
1) The target node itself. We do a BFS for depth K from this node.
2) A path node that is itself K distance away from the target. We add this node to the results.
3) A path node that is less than K distance away from the target. We want to run BFS on the path node's child that is not on the path, so we can get result nodes that are above the target node. We choose the child that is not in the path so we avoid double counting nodes. The depth for this BFS is (K - target_depth + i), where target depth is the distance from the target to the root and i is the depth of the path node.
O(n) time. One pass over all the nodes to find the target node, a second pass to run all the BFS getting the results.
O(n) space
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:
result = []
if not root:
return []
if root == target:
# A basic breadth-first search that returns all of the values at depth K.
result = []
level = [root]
count = 0
while level:
if count == K:
return [n.val for n in level]
next_level = []
for node in level:
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
count += 1
level = next_level
return []
def path_to_root(node):
"""A helper function to find the target node.ArithmeticError
Return a list of
"""
if node == target:
return [node]
left = path_to_root(node.left) if node.left else None
if left:
return [node] + left
right = path_to_root(node.right) if node.right else None
if right:
return [node] + right
return []
path = path_to_root(root)
target_depth = len(path)
for i, subroot in enumerate(path):
if subroot == target:
result += self.distanceK(target, target, K)
elif i == target_depth - K - 1:
result += [subroot.val]
else:
# Check the subtree that does not contain the target node for nodes that are K - target_depth + i distance away.
other_tree = subroot.right if subroot.left == path[i + 1] else subroot.left
result += self.distanceK(other_tree, other_tree, K - target_depth + i)
return result
On Saturday, May 23, 2020 at 9:22:56 AM UTC-7, Daryl Wang wrote:
Daryl Wang
May 30, 2020, 12:58:51 PM5/30/20
to leetcode-meetup
| 460 | LFU Cache | 33.4% | Hard |
The basic idea is to use a dictionary for the cache, and a linked list to manage the ordering where the least frequently used item is the head of the list. To update nodes in the linked list easily, we keep a pointer from a key to its linked list node. The main difficulty in this problem is dealing with all the edge conditions for keeping the linked list in least frequent and then least recent order.
When an existing node is used for the (n + 1)th time, we need to move it further back in the list. How far back? We want it to be the last of all the (n + 1) nodes in the linked list. We can walk through the linked list until we get past all the nodes with usage counts of n or (n + 1), but we can reduce this to O(1) if we have a mapping of {usage count: linked list node}. The requirement that we evict the least recent item if there is a tie for the least frequent item means that we have to do more work to keep the list in recency order as well, which is where most of the edge conditions come from.
Once we have an updated linked list, we can find the LFU item easily by looking at the head of list. When we hit capacity and need to evict an key, we can delete the key at the head of the list.
O(1) time
O(n) space
class LFULinkedList:
def __init__(self, key=None, frequency=0):
self.key = key
self.frequency = frequency
self.next = None
self.prev = None
def __str__(self):
return ("LFULinkedList Node with key %s and freq %d,"
" prev %s, next %s" % (self.key, self.frequency,
self.prev.key if self.prev else None,
self.next.key if self.next else None))
def linkNext(self, nextNode):
"""
Links nextNode to the current node.
Sets this node's next pointer to nextNode, and sets nextNode's prev pointer to this node so that the nextNode follows this node.
Overwrites any existing connections to this node's follower and nextNode's predecessor.
"""
self.next = nextNode
nextNode.prev = self
def insertIntoList(self, insertionNode):
"""
Insert the given node into the linked list, following insertionNode.
"""
nextNode = insertionNode.next
insertionNode.linkNext(self)
self.linkNext(nextNode)
def cutFromList(self):
"""
Cuts this node from any linked list it is part of.
Sets this node's neighbors to point to each other, and set this node's next and prev pointers to None.
Does not assume that linked list has sentinel head and tail nodes.
"""
prevNode = self.prev
nextNode = self.next
if prevNode:
prevNode.next = nextNode
if nextNode:
nextNode.prev = prevNode
self.next = None
self.prev = None
class LFULinkedListSentinel(LFULinkedList):
def __init__(self):
super().__init__(key=None, frequency=-1)
def __str__(self):
return "LFU Linked List Sentinel"
class LFUCache:
def __init__(self, capacity: int):
self.maxCapacity = capacity
self.capacity = 0
self.cache = {}
self.nodeMap = {}
self.mostRecentPerCount = {}
# Pointer to head of a linked list, which is the least frequntly used key
self.headSentinel = LFULinkedListSentinel()
self.tailSentinel = LFULinkedListSentinel()
self.headSentinel.linkNext(self.tailSentinel)
self.leastFrequent = None
def leastFrequentNode(self):
return self.headSentinel.next
def leastFrequentCount(self):
return self.leastFrequentNode().frequency if self.leastFrequentNode() else -1
def updateMostRecentPerCount(self, node):
"""
Takes a node and updates the mostRecentPerCount if node is the most recent node for its frequency. If there are other nodes with the same frequency then the mostRecentPerCount will point to the most recent of those other nodes. Otherwise, deletes the mostRecentPerCount entry for node's frequency.
Does nothing if node is not the most recent for its frequency.
This function MUST be called while node is still part of the linked list and before its frequency is changed. If node's prev pointer is not set this function will fail.
"""
oldPrev = node.prev
if node == self.mostRecentPerCount[node.frequency]:
if oldPrev and oldPrev.frequency == node.frequency:
self.mostRecentPerCount[node.frequency] = oldPrev
else:
del self.mostRecentPerCount[node.frequency]
def incrementCount(self, key):
assert key in self.nodeMap, "Incrementing count for non-existent key"
node = self.nodeMap[key]
# Special case where node is the most recent of its frequency and there are no nodes with frequency + 1. In this case there are no changes to the linked list order.
if node == self.mostRecentPerCount.get(node.frequency, None) and (node.frequency + 1) not in self.mostRecentPerCount:
self.updateMostRecentPerCount(node)
node.frequency += 1
self.mostRecentPerCount[node.frequency] = node
return
self.updateMostRecentPerCount(node)
oldPrev = node.prev
oldNext = node.next
oldPrev.linkNext(oldNext)
# Increment frequency
node.frequency += 1
# Add node back into its new place
# Three cases for where we add the node after incrementing it's frequency to from f to f + 1. We choose, in order of descending priority:
# 1: There are already other keys with frequency f + 1. Add the node after the most recent of those nodes.
# 2: There are other keys with frequency f. Add the node after the most recent of those nodes. The most recent node with freq f is calculated after this node has been removed.
# 3: Add node after its original prev node. This is covered in the special case earlier
newPrev = self.mostRecentPerCount.get(node.frequency, None) or self.mostRecentPerCount.get(node.frequency - 1, None)
newNext = newPrev.next
newPrev.linkNext(node)
node.linkNext(newNext)
self.mostRecentPerCount[node.frequency] = node
def diagList(self):
"""
Debug function to print out the state of the linked list of cache keys.
"""
node = self.headSentinel
string = ["Diag List "]
while node:
if node.key is not None:
string.append(str(node))
node = node.next
def get(self, key: int) -> int:
# Update frequency
if key in self.nodeMap:
self.incrementCount(key)
return self.cache.get(key, -1)
def put(self, key: int, value: int) -> None:
if self.maxCapacity == 0:
return
if key in self.nodeMap:
self.incrementCount(key)
self.cache[key] = value
else:
if self.capacity == self.maxCapacity:
evicted = self.leastFrequentNode()
self.updateMostRecentPerCount(evicted)
evicted.cutFromList()
del self.cache[evicted.key]
del self.nodeMap[evicted.key]
self.capacity -= 1
self.cache[key] = value
newNode = LFULinkedList(key)
self.nodeMap[key] = newNode
precNode = self.mostRecentPerCount[self.leastFrequentCount()] if self.leastFrequentCount() == 0 else self.headSentinel
newNode.insertIntoList(precNode)
self.mostRecentPerCount[0] = newNode
self.capacity += 1
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
On Saturday, May 23, 2020 at 9:22:56 AM UTC-7, Daryl Wang wrote:
Reply all
Reply to author
Forward
0 new messages