Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its minimum depth = 2. Solution: Recursion /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; int left = minDepth(root.

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

Count Number of Substrings With K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters. Example 1 Input: s = "eceba", k = 2 Output: 5 Explanation: "ec", "ce", "eb", "ba" and "ece" k distinct characters. Example 2 Input: s = "aa", k = 1 Output: 2 Explanation: "a" and "aa" have k distinct characters. import java.util.Arrays; public class CountKSubStr { // Function to count number of substrings // with exactly k unique characters int countkDist(String str, int k) { // Initialize result int res = 0; int n = str.

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

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Solution 1 Time: O(n) Space: O(1) class Solution { public int trap(int[] height) { int n = height.

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

Container With Most Water

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note You may not slant the container and n is at least 2. The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].

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

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.

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

String to Integer Atoi

Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

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

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “". Example 1 Input: ["flower","flow","flight"] Output: "fl" Example 2 Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. Note All given inputs are in lowercase letters a-z. Note # Time: O(n*l), l: number of strings class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs or len(strs) == 0: return "" res = strs[0] for s in strs: # string.

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

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1 Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2 Input: "cbbd" Output: "bb" Solution Dynamic Programming # https://leetcode.com/problems/longest-palindromic-substring/discuss/157861/Python3-DP-Solution-with-Lots-of-Comments # time: O(n^2) # space: O(n^2) class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ str_len = len(s) if str_len == 0: return "" # Initialize DP table (dimensions: str_len x str_len) memo = [[False for i in range(str_len)] for j in range(str_len)] start = 0 # Starting index of the longest palindrome max_len = 1 # Length of the longest palindrome # Fill DP table for single char palindromes for i in range(str_len): memo[i][i] = True # Fill DP table for 2 char long palindromes for i in range(str_len - 1): j = i + 1 if s[i] == s[j]: memo[i][j] = True start = i max_len = 2 # Fill DP table for palindromes of every other length # starting from 3 for length in range(3, str_len + 1): for i in range(str_len - length + 1): j = i + (length - 1) if s[i] == s[j] and memo[i+1][j-1]: memo[i][j] = True start = i max_len = length return s[start: start + max_len] # time: O(n^2) # space: O(1) class Solution(object): def __init__(self): self.

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

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

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

Nvidia Cuda Architecture

Fundamental concepts/components in the CUDA architecture: thread: core/kernel: Block: a collection of parallel threads. Grid: a collection of parallel thread blocks. warp: a set of threads (commonly 32) that get executed simultaneously. Thread blocks are executed as smaller groups of threads known as “warps” in sequence. streaming multiprocessor: the number of blocks per grid is limited by SM. Waprs are scheduled to execute in SMs. Streaming Multiprocessor has a Shared Memory.

by lek tin in "computer-architecture" access_time 2-min read