Push vs PullPros and cons of push and pull modelPush: broker pushes messages to the consumer;(broker in charge)Pro: Optimized for latency: broker can send out message immediately ;Pro: client(consumer) logic is lightweight -> only send message and don't track message status ;Pro: load balancing among competing consumers ;Con: flow control-> need to send fast or slow depends on the consumption speed;Con: due to this flow control, the broker logic is more complex.Pull: consumer pull data from broker;(consumer in charge)Con: polling a tight loop: consumer needs to check often ;Con: client logic i ...继续阅读 (13)

LogMemory vs DiskLog segmentMessage position(offset)For broker, keeping message in memory makes gets and puts fast; but thememory are limited.When there is spike(producer sendmore messages), or message is toobigorconsumers gets slower. -> we need to drop the failed messages or store them somewhere else.If some of the messages are kept in memory, when it crashes or quit, messages are lost.RabbitMQ and ActiveMQ keep messages in both memory and disk, while Kafka store memory solely on disk.Log: (like a queue in memory): a file in the disk and append only; messages have id and append to the file. ...继续阅读 (14)

The importance of queues in distributed systemQueueBounded and unbounded queuesCircular buffer and it's applicationsMessage can be stored in disk and memoryUsequeue: FIFOunbounded queue: use as much memory as it canBounded queue: limited size queue, the size is specified at creation.Implementation: data structure support ordering, insert and delete in constant time;Linklist : a pointer on the tail and head;Arrat : add is easy, but remove will shift all the elements ahead, so the operation is O(n)In the array case, the deletion is slow, so we can think of some way to avoid the shifts->(space ex ...继续阅读 (13)

QuestionA phrase is apalindromeif, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.Given a strings, returntrueif it is apalindrome, orfalseotherwise.Example 1:Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.Example 2:Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.Example 3:Input: s = " " Output: true Explanation: s is an empty string "" after removi ...继续阅读 (14)

How to improve system performance with cachingDuplication cacheLocal vs external cacheAdding data to cache(explicitly, implicitly)Cache data eviction(size-based, time-based, explicit)Expiration vs refreshLocal(private)cache: same machine as the app itself. Google Guava Cache. Simple and fast but not scalable due to the size limit. And zero fault tolerance and durability.External (shared/remote) cache: external storage. Redis , Memecached. Scalable(all servers capacity, and fault tolerant and durable(if support replication)Hash table persists all things at one time until they are explicitly rem ...继续阅读 (9)

Fundamentals of reliable, scalable, and fast communicationSynchronous vs asynchronous communicationSynchronous and asynchronous request-response modelsAsynchronous messagingFor client communicate with server, we have two optionsThe client send requests to server directly, or the client send requests to a messaging systemRequest-response model can be in synchronous and asynchronous manner.Sync : client waits for the response to come back;Async: client does not wait for the response to come back.Messaging : the client sent message to the messaging system , and later the messaging system send the ...继续阅读 (10)

QuestionGiven a stringsand an integerk, returnthe length of the longestsubstringofsthat contains at mostkdistinctcharacters.Example 1:Input: s = "eceba", k = 2 Output: 3 Explanation: The substring is "ece" with length 3.Example 2:Input: s = "aa", k = 1 Output: 2 Explanation: The substring is "aa" with length 2.Constraints:1 <= s.length <= 5 * 1040 <= k <= 50ApproachSliding window when the question is asking something for substring;The logic is clearStart from left , if in the map then it will not affect the unique number count so we move forward ;If it's not in the map, then we put into map, b ...继续阅读 (10)

QuestionGiven a strings, find the length of thelongestsubstringwithout repeating characters.Example 1:Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.Example 2:Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.Example 3:Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.Constraints:0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.ApproachUse a map to record each character ...继续阅读 (10)

How to achieve certain system quantities with the help ofhardwareRegions, availability zones, data centers, racks, serversA example :US Start up -> a web application -> deploy a single general-purpose server in the garage; it accepts HTTP requests all over the world and store the data in the database (in the same machine);As the app grows and the data and request increase, you find single server are not enough to store data(CPU bound, memory bound and IO bound), a more powerful machine is pricy, so you bought another machine -> for database dedicated ;One day your dog accidentally turned off t ...继续阅读 (13)

QuestionGiven two stringssandtof lengthsmandnrespectively, returntheminimum windowsubstring*ofssuch that every character int(including duplicates) is included in the window. If there is no such substring, returnthe empty string*"".The testcases will be generated such that the answer isunique.Example 1:Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.Example 2:Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window.Example 3:Input: s = "a", t = "aa" Output: "" Explana ...继续阅读 (12)

QuestionGiven afileand assume that you can only read the file using a given methodread4, implement a methodreadto readncharacters. Your methodreadmay becalled multiple times.Method read4:The APIread4readsfour consecutive charactersfromfile, then writes those characters into the buffer arraybuf4.The return value is the number of actual characters read.Note thatread4()has its own file pointer, much likeFILE *fpin C.Definition of read4:Parameter: char[] buf4 Returns: int buf4[] is a destination, not a source. The results from read4 will be copied to buf4[].Below is a high-level example o ...继续阅读 (11)

QuestionRoman numerals are represented by seven different symbols:I,V,X,L,C,DandM.Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000For example,2is written asIIin Roman numeral, just two one's added together.12is written asXII, which is simplyX + II. The number27is written asXXVII, which isXX + V + II.Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is notIIII. Instead, the number four is written asIV. Because the one is before the five we subtract it ...继续阅读 (9)

QuestionRoman numerals are represented by seven different symbols:I,V,X,L,C,DandM.Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000For example,2is written asIIin Roman numeral, just two ones added together.12is written asXII, which is simplyX + II. The number27is written asXXVII, which isXX + V + II.Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is notIIII. Instead, the number four is written asIV. Because the one is before the five we subtract it ...继续阅读 (8)

Reinforce the understanding of frequently used system design concepts and to demonstrate how to apply them to solve problems.How to Define System RequirementsSystem RequirementsWhat a functional requirement and non-functional requirementsFunctional requirement: defines thebehavior, what a system us is supposed to do; e.g. the system must allow applications to exchange messagesNonfunctional requirements: defines thequalityof a system, how a system is supposed to be. e.g. scalable, highly available, fastWhy they are importantInterviewer tends to make the problems vague and wants to see how candi ...继续阅读 (11)

QuestionGiven a stringcolumnTitlethat represents the column title as appears in an Excel sheet, returnits corresponding column number.For example:A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...Example 1:Input: columnTitle = "A" Output: 1Example 2:Input: columnTitle = "AB" Output: 28Example 3:Input: columnTitle = "ZY" Output: 701Constraints:1 <= columnTitle.length <= 7columnTitleconsists only of uppercase English letters.columnTitleis in the range["A", "FXSHRXW"].ApproachSame idea with question 168 and this question is easier to implement.Each digit of column title string is the coeffic ...继续阅读 (11)

QuestionGiven an integercolumnNumber, returnits corresponding column title as it appears in an Excel sheet.For example:A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...Example 1:Input: columnNumber = 1 Output: "A"Example 2:Input: columnNumber = 28 Output: "AB"Example 3:Input: columnNumber = 701 Output: "ZY"Constraints:1 <= columnNumber <= 231 - 1ApproachFigure out how the column title and numbers are converted, it's can be regarded as a 26-based conversion;Then you will find that for each title appended it's the abcd...x;You don't have to create a map or array to store all the number to ...继续阅读 (9)

QuestionYou are given a 2D array of integersenvelopeswhereenvelopes[i] = [wi, hi]represents the width and the height of an envelope.One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.Returnthe maximum number of envelopes you can Russian doll (i.e., put one inside the other).Note:You cannot rotate an envelope.Example 1:Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).Example 2:Input: envelopes = [[1, ...继续阅读 (12)

QuestionGiven an integer arraynums, returnthe length of the longeststrictly increasingsubsequence**.Example 1:Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.Example 2:Input: nums = [0,1,0,3,2,3] Output: 4Example 3:Input: nums = [7,7,7,7,7,7,7] Output: 1Constraints:1 <= nums.length <= 2500-104 <= nums[i] <= 104ApproachUse dp, define dp[i] as the ith element, that so far it can be longest subsequence.The status transform equation is if the element nums[i] is larger than the previous element nums[j], thendp[i ...继续阅读 (10)

QuestionGiven an integer arraynums, reorder it such thatnums[0] <= nums[1] >= nums[2] <= nums[3]....You may assume the input array always has a valid answer.Example 1:Input: nums = [3,5,2,1,6,4] Output: [3,5,1,6,2,4] Explanation: [1,6,2,5,3,4] is also accepted.Example 2:Input: nums = [6,6,5,6,3,8] Output: [6,6,5,6,3,8]Constraints:1 <= nums.length <= 5 * 1040 <= nums[i] <= 104It is guaranteed that there will be an answer for the given inputnums.Follow up:Could you solve the problem inO(n)time complexity?AlgorithmTBH, I was inspired by the explanation of first exampleThe description of the quest ...继续阅读 (15)

QuestionAwiggle sequenceis a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.For example,[1, 7, 4, 9, 2, 5]is awiggle sequencebecause the differences(6, -3, 5, -7, 3)alternate between positive and negative.In contrast,[1, 4, 7, 2, 5]and[1, 7, 4, 5, 5]are not wiggle sequences. The first is not because its first two differences are positive, and the second is not b ...继续阅读 (12)

QuestionGiven an integer arraynums, move all0's to the end of it while maintaining the relative order of the non-zero elements.Notethat you must do this in-place without making a copy of the array.Example 1:Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]Follow upCould you minimize the total number of operations done?AlgorithmBasic solution is to leverage bubble sort and bubble the 0 to the end, this will have a O(n*n) time complexity;In the follow up, the algorithm is showed in the second code part, we maintain two pointers, one is normal index for looping, the other is the sorted or moved num ...继续阅读 (14)

QuestionGiven an arraynumswithnobjects colored red, white, or blue, sort themin-placeso that objects of the same color are adjacent, with the colors in the order red, white, and blue.We will use the integers0,1, and2to represent the color red, white, and blue, respectively.You must solve this problem without using the library's sort function.Example 1:Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]AlgorithmYou cannot assume the amount of 0, 1, 2 are the same.Basically the idea is to put the 0s at the left side and 2s at the right side, and the positions left in the middle are 1sThere should ...继续阅读 (12)

QuestionYou are given two integer arraysnums1andnums2, sorted innon-decreasing order, and two integersmandn, representing the number of elements innums1andnums2respectively.Mergenums1andnums2into a single array sorted innon-decreasing order.The final sorted array should not be returned by the function, but instead bestored inside the arraynums1. To accommodate this,nums1has a length ofm + n, where the firstmelements denote the elements that should be merged, and the lastnelements are set to0and should be ignored.nums2has a length ofn.Example 1:Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5, ...继续阅读 (13)

QuestionYou are given asorted uniqueinteger arraynums.Arange[a,b]is the set of all integers fromatob(inclusive).Returnthesmallest sortedlist of ranges thatcover all the numbers in the array exactly**. That is, each element ofnumsis covered by exactly one of the ranges, and there is no integerxsuch thatxis in one of the ranges but not innums.Each range[a,b]in the list should be output as:"a->b"ifa != b"a"ifa == bExample 1:Input: nums = [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: The ranges are: [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7"Example 2:Input: nums = [0,2,3,4,6,8,9] Out ...继续阅读 (16)

QuestionYou are given an inclusive range[lower, upper]and asorted uniqueinteger arraynums, where all elements are within the inclusive range.A numberxis consideredmissingifxis in the range[lower, upper]andxis not innums.Returntheshortest sortedlist of ranges thatexactly covers all the missing numbers**. That is, no element ofnumsis included in any of the ranges, and each missing number is covered by one of the ranges.Example 1:Input: nums = [0,1,3,50,75], lower = 0, upper = 99 Output: [[2,2],[4,49],[51,74],[76,99]] Explanation: The ranges are: [2,2] [4,49] [51,74] [76,99]Example 2:Input: nums ...继续阅读 (10)

QuestionGiven an integer arraynums, find a subarray that has the largest product, and returnthe product.The test cases are generated so that the answer will fit in a32-bitinteger.Example 1:Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.Example 2:Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.Constraints:1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10The product of any prefix or suffix ofnumsisguaranteedto fit in a32-bitinteger.AlgorithmThe Constrains is a little misleading, making me think it may leverag ...继续阅读 (11)

QuestionGiven an integer arraynumsand an integerk, returnthe maximum length of asubarraythat sums tok. If there is not one, return0instead.Example 1:Input: nums = [1,-1,5,-2,3], k = 3 Output: 4 Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.AlgorithmThis is a sub array question.Where is something likearray - sumyou can try to leverage pre-sum. In this question, we are also given a target. At the very beginning, I tried use two pointers but to doesn't work. The slight different of two pointers question and pre sum is obvious actually, preSum is used when the questions ref ...继续阅读 (10)

QuestionSuppose you are at a party withnpeople labeled from0ton - 1and among them, there may exist one celebrity. The definition of a celebrity is that all the othern - 1people know the celebrity, but the celebrity does not know any of them.Now you want to find out who the celebrity is or verify that there is not one. You are only allowed to ask questions like: "Hi, A. Do you know B?" to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).You are given a helper functionbool kno ...继续阅读 (11)

QuestionGiven an integer arraynums, returnan arrayanswersuch thatanswer[i]is equal to the product of all the elements ofnumsexceptnums[i].The product of any prefix or suffix ofnumsisguaranteedto fit in a32-bitinteger.You must write an algorithm that runs inO(n)time and without using the division operation.Example 1:Input: nums = [1,2,3,4] Output: [24,12,8,6]Example 2:Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]Constraints:2 <= nums.length <= 105-30 <= nums[i] <= 30The product of any prefix or suffix ofnumsisguaranteedto fit in a32-bitinteger.AlgorithmTypical array questions, use prefix prod ...继续阅读 (12)

QuestionYou are given an integer arrayheightof lengthn. There arenvertical lines drawn such that the two endpoints of theithline are(i, 0)and(i, height[i]).Find two lines that together with the x-axis form a container, such that the container contains the most water.Returnthe maximum amount of water a container can store.Noticethat you may not slant the container.Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.Example 2:Input: hei ...继续阅读 (11)