hashmap:

Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string. Example 1: Input: s1 = "ab" s2 = "eidbaooo" Output: True Explanation: s2 contains one permutation of s1 ("ba"). Example 2: Input:s1= "ab" s2 = "eidboaoo" Output: False Constraints: The input strings only contain lower case letters.

by lek tin in "algorithm" access_time 1-min read

Sort Characters by Frequency

Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer. Example 2: Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together.

by lek tin in "algorithm" access_time 1-min read

Jewels and Stones

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels. The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

by lek tin in "algorithm" access_time 2-min read

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Example 1 Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: ^ | | o | o | o +-------------> 0 1 2 3 4 Example 2 Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Explanation: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6 NOTE: input types have been changed on April 15, 2019.

by lek tin in "algorithm" access_time 2-min read

LFU Cache

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item.

by lek tin in "algorithm" access_time 3-min read

Design Hashmap

Design a HashMap without using any built-in hash table libraries. To be specific, your design should include these functions: put(key, value): Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value. get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. remove(key): Remove the mapping for the value key if this map contains the mapping for the key.

by lek tin in "algorithm" access_time 2-min read

Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0. Example Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?

by lek tin in "algorithm" access_time 3-min read

Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome. Example 1 Input: "code" Output: false Example 2 Input: "aab" Output: true Example 3 Input: "carerac" Output: true Solution class Solution: def canPermutePalindrome(self, s: str) -> bool: lookup = set() for c in s: if c not in lookup: lookup.add(c) else: lookup.remove(c) return len(lookup) <= 1

by lek tin in "algorithm" access_time 1-min read

First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer. Example 1 Input: [1,2,0] Output: 3 Example 2 Input: [3,4,-1,1] Output: 2 Example 3 Input: [7,8,9,11,12] Output: 1 Solution (hashmap) Time: O(N) Space: O(N) from collections import Counter class Solution: def firstMissingPositive(self, nums: List[int]) -> int: counter = Counter(nums) curr = 1 while True: if curr not in counter: return curr curr += 1 Follow-up Your algorithm should run in O(n) time and uses constant extra space.

by lek tin in "algorithm" access_time 2-min read

Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values. For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1). Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

by lek tin in "algorithm" access_time 2-min read