Note: Condition was given that n will always be valid.
Approach: Use two pointers.
Implementation in C#:
public void RemoveNthFromEnd(int n)
{
LinkedListNode first = this.Head, second = this.Head;
for (int i = 1; i <= n; ++i)
{
second = second.Next;
if (second == null)
{
this.Head = this.Head.Next;
return;
}
}
while (second.Next != null)
{
first = first.Next;
second = second.Next;
}
first.Next = first.Next.Next;
}
Complexity: O(n)
Problem: Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
The matching should cover the entire input string (not partial).
Example:
Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Approach: Use DP. Have a table [s.Length + 1][p.Length + 1] where table[i][j] indicates s(0..i-1) is a match of pattern p(0...j-1). Once we fill this we need to return table[s.Length][p.Length]. Here is how to fill this table -
Implementation in C#:
public bool IsRegexMatch(string s, string p)
{
bool[,] lookup = new bool[s.Length + 1, p.Length + 1];
lookup[0, 0] = true;
for (int i = 1; i <= p.Length; ++i)
{
if (p[i - 1] == '*')
{
lookup[0, i] = i - 2 >= 0 ? lookup[0, i - 2] :false;
}
}
for (int i = 1; i <= s.Length; ++i)
{
for (int j = 1; j <= p.Length; ++j)
{
if (p[j - 1] == '*')
{
lookup[i, j] = lookup[i, j - 2];
if (p[j - 2] == '.' || p[j - 2] == s[i - 1])
{
lookup[i, j] = lookup[i, j - 2] || lookup[i - 1, j];
}
}
else if (p[j - 1] == '.' || s[i - 1] == p[j - 1])
{
lookup[i, j] = lookup[i - 1, j - 1];
}
else
{
lookup[i, j] = false;
}
}
}
return lookup[s.Length, p.Length];
}
Complexity: O(m * n)
Approach: The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.
To generate odd length palindrome, Fix a centre and expand in both directions for longer palindromes, i.e. fix i (index) as center and two indices as i1 = i+1 and i2 = i-1
Compare i1 and i2 if equal then decrease i2 and increase i1 and find the maximum length.
Use a similar technique to find the even length palindrome.
Take two indices i1 = i and i2 = i-1 and compare characters at i1 and i2 and find the maximum length till all pair of compared characters are equal and store the maximum length.
public string LongestPalindromicSubString(string str)
{
if(string.IsNullOrEmpty(str))
{
return string.Empty;
}
int maxLength = 1;
int start = 0;
for (int i = 1; i < str.Length; ++i)
{
// Find the longest even length palindrome with center points as i-1 and i.
int low = i - 1;
int high = i;
while(low >= 0 && high < str.Length && str[low] == str[high])
{
if (high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}
// Find the longest odd length palindrome with center point as i
low = i - 1;
high = i + 1;
while(low >= 0 && high <str.Length && str[low] == str[high])
{
if (high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}
}
return str.Substring(start, maxLength);
}
Complexity: O(n^2)
Problem: Given a string s, find the length of the longest substring without repeating characters.
Example:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
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.
Approach: Clearly it's a sliding window problem. Like in any other sliding window problem we will maintain start and end indices of current window. We can have a hash map but we can use hash set here as the occurrence of every character in substring can't be more than one. We will keep incrementing end by 1 and for each index 'end', there could be 2 cases:
Implementation in C#:
Complexity: O(n)
Example: Input : ar1[] = {-5, 3, 6, 12, 15}
ar2[] = {-12, -10, -6, -3, 4, 10}
The merged array is :
ar3[] = {-12, -10, -6, -5 , -3,
3, 4, 6, 10, 12, 15}
Output : The median is 3.
Solution: Start partitioning the two arrays into two groups of halves. The first half contains some first elements from the first and the second arrays, and the second half contains the rest elements form both arrays. Reach a condition such that, every element in the first half is less than or equal to every element in the second half.
public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
if (nums1 == null && nums2 == null)
{
return -1;
}
if (nums1.Length == 0 && nums2.Length == 0)
{
return -1;
}
if (nums1.Length <= nums2.Length)
{
return this.FindMedianSortedArraysInternal(nums1, nums2);
}
else
{
return this.FindMedianSortedArraysInternal(nums2, nums1);
}
}
private double FindMedianSortedArraysInternal(int[] nums1, int[] nums2)
{
int minIndex = 0, maxIndex = nums1.Length, nums1Index = 0, nums2Index = 0;
double median = 0;
while (minIndex <= maxIndex)
{
nums1Index = (minIndex + maxIndex) / 2;
nums2Index = ((nums1.Length + nums2.Length + 1) / 2) - nums1Index;
if (nums2Index < 0)
{
maxIndex = nums1Index - 1;
continue;
}
// if num1Index = num1.Length, it means that elements from num1 in the second half is an
// empty set. and if num2Index = 0, it means that elements from num2 in the first half is an
// empty set. so it is necessary to check that, because we compare elements from these two
// groups. Searching on right
if (nums1Index < nums1.Length && nums2Index > 0 && nums2[nums2Index - 1] > nums1[nums1Index])
{
minIndex = nums1Index + 1;
}
// if num1Index = 0, it means that Elements from num1 in the first half is an empty set and if
// num2Index = num2.Length, it means that Elements from num2 in the second half is an
// empty set. so it is necessary to check that, because we compare elements from these two
// groups. searching on left
else if (nums1Index > 0 && nums2Index < nums2.Length && nums2[nums2Index] < nums1[nums1Index - 1])
{
maxIndex = nums1Index - 1;
}
// Found the desired halves
else
{
// this condition happens when we don't have any elements in the first half from num1 so
// we returning the last element in num2 from the first half.
if (nums1Index == 0)
{
median = nums2[nums2Index - 1];
}
// this condition happens when we don't have any elements in the first half from num2 so
// we returning the last element in num1 from the first half.
else if (nums2Index == 0)
{
median = nums1[nums1Index - 1];
}
else
{
median = Math.Max(nums1[nums1Index - 1], nums2[nums2Index - 1]);
}
break;
}
}
// If number of elements is odd there is one middle element.
if ((nums1.Length + nums2.Length) % 2 == 1)
{
return median;
}
// Elements from nums1 in the second half is an empty set.
if (nums1Index == nums1.Length)
{
return (median + nums2[nums2Index]) / 2;
}
// Elements from nums2 in the second half is an empty set.
if (nums2Index == nums2.Length)
{
return (median + nums1[nums1Index]) / 2;
}
return (median + Math.Min(nums1[nums1Index], nums2[nums2Index])) / 2;
}
