Say you have an array for which the $i^{th}$ element is the price of a given stock on day $i$. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Solution: public class Solution { public int maxProfit(int k, int[] prices) { /*

Say you have an array for which the $i^{th}$ element is the price of a given stock on day $i$. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Solution 1: DP, $O(n)$ time and $O(n)$ space. public class Solution { public int maxProfit(int[] prices) { if(prices.length==0) return 0; int min = prices[0]; int[] preProfit = new int[prices.length]; for(int i=1; i<prices.length; i++){ min = Math.min(min, prices[i]); preProfit[i] = Math.max(preProfit[i-1], prices[i]-min); } int max = prices[prices.length-1]; int[] posProfit = new int[prices.length]; for(int i=prices.length-2; i>=0; i--){ max = Math.max(max, prices[i]); posProfit[i] = Math.max(posProfit[i+1], max-prices[i]); } int maxProfit = 0; for(int i=0; i<prices.length; i++) maxProfit=Math.max(maxProfit, preProfit[i]+posProfit[i]); return maxProfit; } } Solution 2: DP, $O(n)$ time and $O(1)$ space.

Say you have an array for which the $i^{th}$ element is the price of a given stock on day $i$. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) Example 2: Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e.

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode dummy = new ListNode(0); ListNode scan = dummy; if(lists.length==0) return dummy.next; PriorityQueue<ListNode> pq =

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively. Pay attention to comparison change due to backward scaning. Solution: public class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int s1 = m - 1; int s2 = n - 1; int s = m + n - 1; while(s>=0){ if(s1==-1) while(s>=0) nums1[s--] = nums2[s2--]; else if(s2==-1) while(s>=0) nums1[s--] = nums1[s1--]; /* pay attention to comparison change due to backward scaning */ else nums1[s--] = nums1[s1]>nums2[s2] ?

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: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Solution 1: straightforward solution, add “()” to every possible position and use Set to check uniqueness. public class Solution { public List<String> generateParenthesis(int n) { if(n==0) return new ArrayList<String>(); List<String> ans = new ArrayList<>(); ans.add("()"); for(int i=1; i<n; i++){ Set<String> set = new HashSet<>(); for(String s : ans){ for(int j=0; j<s.length(); j++){ set.add(s.substring(0,j)+"()"+s.substring(j)); } } ans = new ArrayList<>(set); } return ans; } } Solution 2: recursive.

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy

Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. Solution: public class Solution { public int[] searchRange(int[] nums, int target) { int

Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. Try to do this in one pass. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; *