- Linked List Cycle II (leetcode 142)
- Longest Palindromic Substring(leetcode 5)
- Binary Tree Maximum Path Sum(leetcode 124)
- Binary Tree Zigzag Level Order Traversal(leetcode 103)
- Change in a Foreign Currency
Optional:
- Minimizing Permutations
- 3 Way Quick Sort
Quest 1: Linked List Cycle Start Node.
/*
* Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
* There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
* Do not modify the linked list.
*
* Example 1:
* Input: head = [3,2,0,-4], pos = 1
* 3 -> 2 -> 0 -> -4 -> index(1)
* Output: tail connects to node index 1
* Explanation: There is a cycle in the linked list, where tail connects to the second node.
* Example 2:
* Input: head = [1,2], pos = 0
* 1 -> 2 -> index(0)
* Output: tail connects to node index 0
* Explanation: There is a cycle in the linked list, where tail connects to the first node.
*/
using System;
public class Solution
{
static void Main(string[] args)
{
ListNode n0 = new ListNode(3);
ListNode n1 = new ListNode(2);
ListNode n2 = new ListNode(0);
ListNode n3 = new ListNode(-4);
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n1; // linked to circle, index(1)
}
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public static ListNode DetectCycle(ListNode head) {
return head;
}
}
Quest 2: Longest Palindromic Substring.
/*
* Given a string s, return the longest palindromic substring in s.
*
* Example 1:
* Input: s = "babad"
* Output: "bab"
* Explanation: "aba" is also a valid answer.
* Example 2:
* Input: s = "cbbd"
* Output: "bb"
*
* Constraints:
* 1 <= s.length <= 1000
* s consist of only digits and English letters.
*/
using System;
public class Solution
{
static void Main(string[] args)
{
string s = "babad";
}
public string LongestPalindrome(string s) {
return s;
}
}Quest 3: Binary Tree Maximum Path Sum
/*
* A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
* The path sum of a path is the sum of the node's values in the path.
* Given the root of a binary tree, return the maximum path sum of any non-empty path.
*
* Example 1:
* 1
* / \
* 2 3
* Input: root = [1,2,3]
* Output: 6
* Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
* Example 2:
* -10
* / \
* 9 20
* / \
* 15 7
* Input: root = [-10,9,20,null,null,15,7]
* Output: 42
* Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
*
* Constraints:
* The number of nodes in the tree is in the range [1, 3 * 104].
* -1000 <= Node.val <= 1000
*/
using System;
public class Solution
{
static void Main(string[] args)
{
Node l11 = new Node(15);
Node l12 = new Node(7);
Node l21 = new Node(20);
l21.left = l11;
l21.right = l12;
Node l22 = new Node(9);
Node root = new Node(-10);
root.left = l22;
root.right = l21;
}
public class TreeNode
{
public int data;
public TreeNode left, right;
public TreeNode(int d, Node l = null, Node r = null)
{
data = d;
left = l;
right = r;
}
}
public int MaxPathSum(TreeNode root)
{
}
}Quest 4: Binary Tree Zigzag Level Order Traversal
/*
* Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
*
* Example 1:
* 3
* / \
* 9 20
* / \
* 15 7
* Input: root = [3,9,20,null,null,15,7]
* Output: [[3],[20,9],[15,7]]
* Example 2:
* Input: root = [1]
* Output: [[1]]
*
* Constraints:
* The number of nodes in the tree is in the range [0, 2000].
* -100 <= Node.val <= 100
*/
using System;
public class Solution
{
static void Main(string[] args)
{
Node l11 = new Node(15);
Node l12 = new Node(7);
Node l21 = new Node(20);
l21.left = l11;
l21.right = l12;
Node l22 = new Node(9);
Node root = new Node(3);
root.left = l22;
root.right = l21;
}
public class TreeNode
{
public int data;
public TreeNode left, right;
public TreeNode(int d, Node l = null, Node r = null)
{
data = d;
left = l;
right = r;
}
}
public static IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
}
}Question 5: Change in a Foreign Currency
/*
* You likely know that different currencies have coins and bills of different denominations. In some currencies, it's actually impossible to receive change for a given amount of money. For example, Canada has given up the 1-cent penny. If you're owed 94 cents in Canada, a shopkeeper will graciously supply you with 95 cents instead since there exists a 5-cent coin.
* Given a list of the available denominations, determine if it's possible to receive exact change for an amount of money targetMoney. Both the denominations and target amount will be given in generic units of that currency.
* Signature
* boolean canGetExactChange(int targetMoney, int[] denominations)
* Input
* 1 ≤ |denominations| ≤ 100
* 1 ≤ denominations[i] ≤ 10,000
* 1 ≤ targetMoney ≤ 1,000,000
* Output
* Return true if it's possible to receive exactly targetMoney given the available denominations, and false if not.
*
* Example 1
* denominations = [5, 10, 25, 100, 200]
* targetMoney = 94
* output = false
* Every denomination is a multiple of 5, so you can't receive exactly 94 units of money in this currency.
* Example 2
* denominations = [4, 17, 29]
* targetMoney = 75
* output = true
* You can make 75 units with the denominations [17, 29, 29].
*/
using System;
public class Solution
{
static void Main(string[] args)
{
int[] denominations = { 5, 10, 25, 100, 200 };
int targetMoney = 94;
}
private static bool canGetExactChange(int targetMoney, int[] denominations)
{
return true;
}
}Optional Question 1: Minimizing Permutations
/*
* In this problem, you are given an integer N, and a permutation, P of the integers from 1 to N, denoted as (a_1, a_2, ..., a_N). You want to rearrange the elements of the permutation into increasing order, repeatedly making the following operation:
* Select a sub-portion of the permutation, (a_i, ..., a_j), and reverse its order.
* Your goal is to compute the minimum number of such operations required to return the permutation to increasing order.
* Signature
* int minOperations(int[] arr)
* Input
* Array arr is a permutation of all integers from 1 to N, N is between 1 and 8
* Output
* An integer denoting the minimum number of operations required to arrange the permutation in increasing order
*
* Example 1
* arr = [3, 1, 2]
* output = 2
* Example 2
* arr = [2, 1, 3]
* output = 1
*/
using System;
public class Solution
{
static void Main(string[] args)
{
int[] arr = { 3, 1, 2 };
}
private static int minOperations(int[] arr)
{
return arr[0];
}
}Optional Question 2: 3 Way Quick Sort
/*
* Complete a 3 way quick sort function.
*
* Signature
* int[] quickSort3Way(int[] arr)
* Input
* -10000000 ≤ arr[i] ≤ 10000000
* Output
* A sorted array
* Example 1
* arr = [6, 3, 5, 7, 1, 4, 2]
* output = [1, 2, 3, 4, 5, 6, 7]
* Example 2
* arr = [-54, 35, 5, 87, 12, -4, 24, 765, -314, 53, -9087, -13245, 6364]
* output = [-13245, -9087, -314, -54, -4, 5, 12, 24, 35, 53, 87, 765, 6364]
*/
using System;
public class Solution
{
static void Main(string[] args)
{
int[] arr = { -54, 35, 5, 87, 12, -4, 24, 765, -314, 53, -9087, -13245, 6364 };
}
private static int[] quickSort3Way(int[] arr)
{
return arr;
}
}