Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one. Example 1 Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Given two binary strings, return their sum (also a binary string). The input strings are both non-empty and contains only characters 1 or 0. Example 1 Input: a = "11", b = "1" Output: "100" Example 2 Input: a = "1010", b = "1011" Output: "10101" Solution class Solution: def addBinary(self, a, b): """ :type a: str :type b: str :rtype: str """ result = [] carry = 0 i = len(a)-1 j = len(b)-1 while carry or i >= 0 or j >= 0: total = carry if i >= 0: total += int(a[i]) i -= 1 if j >= 0: total += int(b[j]) j -= 1 result.
Validate if a given string can be interpreted as a decimal number. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true " -90e3 " => true " 1e" => false "e3" => false " 6e-1" => true " 99e2.5 " => false "53.5e93" => true " --6 " => false "-+3" => false "95a54e53" => false Note It is intended for the problem statement to be ambiguous.
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note Although the above answer is in lexicographical order, your answer could be in any order you want.
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note The solution set must not contain duplicate quadruplets. Example: Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
In react, sometimes we need to render a component based on some flag, for example, we need to display a different set of information to the admin users than the normal users. We have a prop called isAdmin render () { const { isAdmin } = this.props return ( <div> { isAdmin ? <CustomeComponent {...propSetA} / > : <CustomeComponent {...propSetB} / > } </div> ) } Looks good right, but there is one problem.
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 Solution: Idea #1 - Brute force with sorting first: Time complexity : O(NlogN) Space complexity : O(N) Idea #2 - Compare head nodes one by one: Time complexity : O(kN) Space complexity : O(N) - creating a new linked list or O(1) in-place Idea #3 - Merge lists one by one:
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1 Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Example 2 Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10]. Solution # Definition for an interval. # class Interval: # def __init__(self, s=0, e=0): # self.
Given a collection of intervals, merge all overlapping intervals. Example 1 Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2 Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. Solution # Definition for an interval. # class Interval: # def __init__(self, s=0, e=0): # self.start = s # self.end = e class Solution: def merge(self, intervals): """ :type intervals: List[Interval] :rtype: List[Interval] """ intervals.
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Example 1 Given nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.