Generate Parentheses Link to original Problem on LeetCode
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
Company: Microsoft, Facebook
Solution (Backtracking and Recursion):
Time Complexity: Space Complexity:
class Solution(object): def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ result = [] self.generateParenthesisHelper(n, n, "", result) return result def generateParenthesisHelper(self, left, right, path, result): if left > right: return if left == 0 and right == 0: result.
Reverse String Link to original Problem on LeetCode
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1:
Input: [“h”,“e”,“l”,“l”,“o”] Output: [“o”,“l”,“l”,“e”,“h”]
Example 2:
Input: [“H”,“a”,“n”,“n”,“a”,“h”] Output: [“h”,“a”,“n”,“n”,“a”,“H”]
Permutations Link to original Problem on LeetCode
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
Company: Microsoft, Adobe, Google
Solution (Backtracking and Recursion):
Time Complexity: Space Complexity:
class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ result = [] self.permuteHelper(nums, [], result) return result def permuteHelper(self, nums, path, result): if not nums: result.append(path) for i in range(len(nums)): self.
3Sum Link to original Problem on LeetCode
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Missing Number Link to original Problem on LeetCode
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Example 1:
Input: [3,0,1] Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1] Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Company: Amazon, Google
Solution 1 (Using XOR):
class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ # We know XOR of same number is 0 # We also know that len(nums) is present in the list # iff it is not the number which is absent # So we keep len(nums) in result result = len(nums) # Then we loop through each number # and XOR the result with index and number for i, num in enumerate(nums): result ^= i result ^= num # By the end the absent number will be present in result return result Solution 2 (Using Sum):
Maximum Subarray Link to original Problem on LeetCode
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Company: Facebook, Paypal, Yahoo, Microsoft, LinkedIn, Amazon, Goldman Sachs
