LintCode - Michael's Blog

Flatten 2D Vector

601. Flatten 2D Vector [https://www.lintcode.com/en/old/problem/flatten-2d-vector/] Implement an iterator to flatten a 2d vector. Example Given 2d vector = [ [1,2], [3], [4,5,6] ] By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,

LintCode

Sort Colors II

LintCode-143.Sort Colors II [http://www.lintcode.com/en/problem/sort-colors-ii/] Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k. Notice: You are not

LintCode

Consistent Hashing II

Consistent Hashing II [http://lintcode.com/en/problem/consistent-hashing-ii/] 在 Consistent Hashing I 中我们介绍了一个比较简单的一致性哈希算法，这个简单的版本有两个缺陷： 1. 增加一台机器之后，数据全部从其中一台机器过来，这一台机器的读负载过大，对正常的服务会造成影响。 2. 当增加到3台机器的时候，每台服务器的负载量不均衡，为1:1:2。为了解决这个问题，引入了 micro-shards 的概念，一个更好的算法是这样： 1. 将 360° 的区间分得更细。从 0~359 变为一个 0 ~ n-1 的区间，将这个区间首尾相接，连成一个圆。 2. 当加入一台新的机器的时候，随机选择在圆周中撒 k 个点，代表这台机器的

LintCode

Consistent Hashing

Consistent Hashing [http://www.lintcode.com/en/problem/consistent-hashing/] 一般的数据库进行horizontal shard的方法是指，把 id 对数据库服务器总数 n 取模，然后来得到他在哪台机器上。这种方法的缺点是，当数据继续增加，我们需要增加数据库服务器，将 n 变为 n+1 时，几乎所有的数据都要移动，这就造成了不 consistent。为了减少这种 naive 的 hash方法(%n) 带来的缺陷，出现了一种新的hash算法：一致性哈希的算法——Consistent Hashing。这种算法有很多种实现方式，这里我们来实现一种简单的 Consistent Hashing。 1. 将 id 对 360 取模，

LintCode

Topological Sorting

LintCode-127.Topological Sorting [http://www.lintcode.com/en/problem/topological-sorting/] Given an directed graph, a topological order of the graph nodes is defined as follow: For each directed edge A -> B in graph, A must before B in the order list. The first node in the order can be

LintCode

First Position of Target

LintCode-14.First Position of Target > For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. > If the target number does not exist in the array, return -1. > Example > If the array is [1, 2, 3, 3,

LintCode

Find Minimum in Rotated Sorted Array II

LintCode-160.Find Minimum in Rotated Sorted Array II [http://www.lintcode.com/en/problem/find-minimum-in-rotated-sorted-array-ii/] > Suppose a sorted array is rotated at some pivot unknown to you beforehand. > (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). > Find the minimum element.

LintCode

Remove Duplicates from Unsorted List

LintCode-217.Remove Duplicates from Unsorted List [http://www.lintcode.com/en/problem/remove-duplicates-from-unsorted-list/] > Write code to remove duplicates from an unsorted linked list. > Example > Given 1->3->2->1->4. > Return 1->3->2->4 > Challenge > (hard) How would you solve this problem if a temporary buffer is not allowed?

LintCode

Longest Words

LintCode-133.Longest Words [http://www.lintcode.com/en/problem/longest-words/] > Given a dictionary, find all of the longest words in the dictionary. > Example > Given { "dog", "google", "facebook", "internationalization", "blabla" } > the longest words are(is) ["internationalization"]. > Given { "like", "love", "hate", "yes" } > the longest words are ["like", "love", "hate"]. > Challenge > It's easy

LintCode

Rotate List

LintCode-170.Rotate List [http://www.lintcode.com/en/problem/rotate-list/] > Given a list, rotate the list to the right by k places, where k is non-negative. > Example > Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3. /** * Definition for singly-linked list. * public class ListNode { * int

LintCode

Triangle

LintCode-109. Triangle [http://www.lintcode.com/en/problem/triangle/] > Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. > Notice > Bonus point if you are able to do this using only O(n) extra space, where

LintCode

Climbing Stairs

LintCode-111.Climbing Stairs [http://www.lintcode.com/en/problem/climbing-stairs/] > You are climbing a stair case. It takes n steps to reach to the top. > Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? > Example > Given an example

LintCode

House Robber

LintCode-392.House Robber [http://www.lintcode.com/en/problem/house-robber/] > You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and

LintCode

Swap Two Nodes in Linked List

LintCode-511.Swap Two Nodes in Linked List [http://www.lintcode.com/en/problem/swap-two-nodes-in-linked-list/] > Given a linked list and two values v1 and v2. Swap the two nodes in the linked list with values v1 and v2. It's guaranteed there is no duplicate values in the linked list. If v1

LintCode

Max Points on a Line

LintCode-186.Max Points on a Line [http://www.lintcode.com/en/problem/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 > Given 4 points: (1,2), (3,6), (0,0), (1,3). > The maximum number is 3.

LintCode

Majority Number

LintCode-46. Majority Number [http://www.lintcode.com/en/problem/majority-number/] > Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it. > Example > Given [1, 1, 1, 1, 2, 2, 2], return 1 > Challenge > O(n) time and

LintCode

Subarray Sum

LintCode-138.Subarray Sum [http://www.lintcode.com/en/problem/subarray-sum/] > Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number. > Notice: There is at least one subarray that it's

LintCode

The Smallest Difference

LintCode-387.The Smallest Difference [http://www.lintcode.com/en/problem/the-smallest-difference/] > Given two array of integers(the first array is array A, the second array is array B), now we are going to find a element in array A which is A[i], and another element in array B which

LintCode

Interleaving Positive and Negative Numbers

LintCode-144.Interleaving Positive and Negative Numbers [http://www.lintcode.com/en/problem/interleaving-positive-and-negative-numbers/] > Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers. > Notice: You are not necessary to keep the original order of positive integers or negative integers. > Example: Given [-1, -2,

LintCode

Anagrams

LintCode-171.Anagrams [http://www.lintcode.com/en/problem/anagrams/] > Given an array of strings, return all groups of strings that are anagrams. > Notice: All inputs will be in lower-case. > Example > Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"]. > Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"

LintCode

Compare Strings

LintCode-55.Compare Strings [http://www.lintcode.com/en/problem/compare-strings] > Compare two strings A and B, determine whether A contains all of the characters in B. > The characters in string A and B are all Upper Case letters. > Notice: The characters of B in A are not necessary continuous or

LintCode

Two Strings Are Anagrams

LintCode-158.Two Strings Are Anagrams [http://www.lintcode.com/en/problem/two-strings-are-anagrams] > Write a method anagram(s,t) to decide if two strings are anagrams or not. > Clarification: What is Anagram? * Two strings are anagram if they can be the same after change the order of characters. > Example: Given s

LintCode

Binary Tree Path Sum

LintCode-376. Binary Tree Path Sum [http://www.lintcode.com/en/problem/binary-tree-path-sum/] > Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target. > A valid path is from root node to any of the leaf nodes. > Example: Given a binary

LintCode

Palindrome Partitioning

LintCode-136.Palindrome Partitioning [http://www.lintcode.com/en/problem/palindrome-partitioning/] > Given a string s, partition s such that every substring of the partition is a palindrome. > Return all possible palindrome partitioning of s. > Example: Given s = "aab", return: [ ["aa","b"], ["a","a","b"] ] public class Solution { /** * @param s: A string

LintCode

Maximum Subarray Difference

LintCode-45.Maximum Subarray Difference [http://www.lintcode.com/en/problem/maximum-subarray-difference/] > Given an array with integers. > Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest. > Return the largest difference. > Notice: The subarray should contain at least one number > Example: For [1, 2, -3,