leetcode Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj% Si = 0.
If there are multiple solutions, return any subset is fine.
123 nums: [1,2,3]Result: [1,2] (of course, [1,3] will also be ok)
123 nums: [1,2,4,8]Result: [1,2,4,8]
leetcode Valid Perfect Square
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as
12 Input: 16Returns: True
12 Input: 14Returns: False
leetcode Water and Jug Problem
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
- Fill any of the jugs completely.
- Empty any of the jugs.
- Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
12 Input: x = 2, y = 6, z = 4Output: True
12 Input: x = 2, y = 6, z = 5Output: False
leetcode Count Numbers with Unique Digits
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding
leetcode Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Given num = 16, return true. Given num = 5, return false.
Follow up: Could you solve it without loops/recursion?
leetcode Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
num = 5you should return
- It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
- Space complexity should be O(n).
- Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
leetcode House Robber III
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
12345 3/ \2 3\ \3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
12345 3/ \4 5/ \ \1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
leetcode Self Crossing
You are given an array x of
npositive numbers. You start at point
xmetres to the north, then
xmetres to the west,
xmetres to the south,
xmetres to the east and so on. In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with
O(1)extra space to determine, if your path crosses itself, or not.
Given x =
[2, 1, 1, 2]
Given x =
[1, 2, 3, 4]
false(not self crossing)
Given x =
[1, 1, 1, 1]
leetcode Increasing Triplet Subsequence
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.Your algorithm should run in O(n) time complexity and O(1) space complexity.
[1, 2, 3, 4, 5],
[5, 4, 3, 2, 1],
leetcode Verify Preorder Serialization of a Binary Tree
One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as
1234567 _9_/ \3 2/ \ / \4 1 # 6/ \ / \ / \# # # # # #
For example, the above binary tree can be serialized to the string
#represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as