Handshakes That Dont Cross

You are given an even number of people num_people that stand around a circle and each person shakes hands with someone else, so that there are num_people / 2 handshakes total. Return the number of ways these handshakes could occur such that none of the handshakes cross. Since this number could be very big, return the answer mod 10^9 + 7 Example 1 Input: num_people = 2 Output: 1 Example 2 Input: num_people = 4 Output: 2 Explanation: There are two ways to do it, the first way is [(1,2),(3,4)] and the second one is [(2,3),(4,1)].

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

Report Contiguous Dates

Table: Failed +--------------+---------+ | Column Name | Type | +--------------+---------+ | fail_date | date | +--------------+---------+ Primary key for this table is fail_date. Failed table contains the days of failed tasks. Table: Succeeded +--------------+---------+ | Column Name | Type | +--------------+---------+ | success_date | date | +--------------+---------+ Primary key for this table is success_date. Succeeded table contains the days of succeeded tasks. A system is running one task every day. Every task is independent of the previous tasks.

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

Maximum Product of Splitted Binary Tree

Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized. Since the answer may be too large, return it modulo 10e9 + 7. Example 1 Input: root = [1,2,3,4,5,6] Output: 110 Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10) Example 2 Input: root = [1,null,2,3,4,null,null,5,6] Output: 90 Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.

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

Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string. You can swap the characters at any pair of indices in the given pairs any number of times. Return the lexicographically smallest string that s can be changed to after using the swaps. Example 1 Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd" Example 2 Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]] Output: "abcd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[0] and s[2], s = "acbd" Swap s[1] and s[2], s = "abcd" Example 3 Input: s = "cba", pairs = [[0,1],[1,2]] Output: "abc" Explaination: Swap s[0] and s[1], s = "bca" Swap s[1] and s[2], s = "bac" Swap s[0] and s[1], s = "abc" Constraints 1 <= s.

by lek tin in "algorithm" access_time 3-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

Android Unlock Patterns

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys. Rules for a valid pattern: Each pattern must connect at least m keys and at most n keys. All the keys must be distinct. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern.

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

Human Traffic of Stadium

X city built a new stadium, each day many people visit it and the stats are saved as these columns: id, visit_date, people Please write a query to display the records which have 3 or more consecutive rows and the amount of people more than 100(inclusive). For example, the table stadium: +------+------------+-----------+ | id | visit_date | people | +------+------------+-----------+ | 1 | 2017-01-01 | 10 | | 2 | 2017-01-02 | 109 | | 3 | 2017-01-03 | 150 | | 4 | 2017-01-04 | 99 | | 5 | 2017-01-05 | 145 | | 6 | 2017-01-06 | 1455 | | 7 | 2017-01-07 | 199 | | 8 | 2017-01-08 | 188 | +------+------------+-----------+ For the sample data above, the output is:

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

Consecutive Available Seats

Several friends at a cinema ticket office would like to reserve consecutive available seats. Can you help to query all the consecutive available seats order by the seat_id using the following cinema table? | seat_id | free | |---------|------| | 1 | 1 | | 2 | 0 | | 3 | 1 | | 4 | 1 | | 5 | 1 | Your query should return the following result for the sample case above.

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

Active Businesses

Table: Events +---------------+---------+ | Column Name | Type | +---------------+---------+ | business_id | int | | event_type | varchar | | occurences | int | +---------------+---------+ (business_id, event_type) is the primary key of this table. Each row in the table logs the info that an event of some type occured at some business for a number of times. Write an SQL query to find all active businesses. An active business is a business that has more than one event type with occurences greater than the average occurences of that event type among all businesses.

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

Bitwise and of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. Example 1 Input: [5,7] Output: 4 Example 2 Input: [0,1] Output: 0 Solution «««< HEAD Java class Solution { public int rangeBitwiseAnd(int m, int n) { int shift = 0; while (m < n) { m >>= 1; n >>= 1; shift++; // System.out.println("m: " + String.

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