yokolet

[Top]

Others

• Divide Two Integers
• Find the Celeberity
• Integer to English Words
• Minimum Window Substring
• Number of Islands II
• Palindrome Pairs

yokolet

"""
Given two integers dividend and divisor, divide two integers without using
multiplication, division and mod operator. Return the quotient after dividing dividend
by divisor. The integer division should truncate toward zero.
- Both dividend and divisor will be 32-bit signed integers.
- The divisor will never be 0.
- Assume we are dealing with an environment which could only store integers within the
  32-bit signed integer range: [−2**31,  2**31 − 1]. For the purpose of this problem,
  assume that your function returns 2**31 − 1 when the division result overflows.

yokolet

"""
Implement a trie with insert, search, and startsWith methods.
- You may assume that all inputs are consist of lowercase letters a-z.
- All inputs are guaranteed to be non-empty strings.

Example:
trie = Trie()
trie.insert("apple")
trie.search("apple")   # returns True
trie.search("app")     # returns False

yokolet

"""
Description:
Given a stream of integers and a window size, calculate the moving average of all
integers in the sliding window.

Example:
m = MovingAverage(3)
m.next(1)   # 1
m.next(10)  # (1 + 10) / 2
m.next(3)   # (1 + 10 + 3) / 3

yokolet

"""
Description:
Design a hit counter which counts the number of hits received in the past 5 minutes.
Each function accepts a timestamp parameter (in seconds granularity) and you may assume
that calls are being made to the system in chronological order (ie, the timestamp is
monotonically increasing). You may assume that the earliest timestamp starts at 1. It
is possible that several hits arrive roughly at the same time.

Example:
counter = HitCounter()

yokolet

"""
Design a Tic-tac-toe game that is played between two players on a n x n grid. You may
assume the following rules:
- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves is allowed.
- A player who succeeds in placing n of their marks in a horizontal, vertical, or
  diagonal row wins the game.

Example:
Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

yokolet

"""
Description:
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.

Example:

yokolet

"""
Description:
Median is the middle value in an ordered integer list. If the size of the list is even,
there is no middle value. So the median is the mean of the two middle value. For example,
- [2,3,4], the median is 3
- [2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
- void addNum(int num) - Add a integer number from the data stream to the data structure.
- double findMedian() - Return the median of all elements so far.

yokolet

"""
Description:
Given two sparse matrices A and B, return the result of AB.
You may assume that A's column number is equal to B's row number.

Example:
Input:
A = [
  [ 1, 0, 0],
  [-1, 0, 3]

yokolet

"""
Description:
Design and implement a data structure for Least Recently Used (LRU) 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 reached its capacity, it should invalidate the least recently used
            item before inserting a new item.
You should make both operations to run in O(1) time complexity.