Here is the link.
C# Understand difference between return all valid strings and any valid string
Oct. 5, 2020
301. Remove Invalid Parentheses
Introduction
It was my 10:00 PM mock interview on Oct. 4, 2020. I started to prepare Google phone screen, and I have 12 free mock interviews as interviewee on interviewing dot io website. I was asked to solve the similar algorithm as hard level 301 find all valid strings, except only return one valid string. The solution can be super simple and quick to solve using less than 15 minutes.
My approach
I did come out the idea using stack to find invalid paretheses by going through once, but I did not take the hint, and then went for breadth first search and start from removing one char until a valid string is found. The solution to find only one valid string is linear time, but the following breadth first search algorithm time complexity is O((m + 1)! n), m is total number of paretheses, and n is the length of string.
After the mock interview
I quickly modified my code and then submitted as the answer of hard level 301 algorithm. The code passes all test cases. I like to write down some lessons I learned through the practice.
Highlights of discussion in mock interview of my implementation:
- Time complexity, if the string is 10 of open paretheses, "((((((((((", and then each index position will have to be considered to be removed, 10 substrings will be added to queue, next round each string has length of 9, 9 subsring will be added to queue for each of them, so total is 10 * 9, therefore, the total of string is 10!. The interviewer corrected my estimation of time complexity: not O(m * n), should be O((m + 1)! * n), whereas m is total number of paretheses, n is length of string.
- Duplicate removal - inside while loop, the second for loop start index should be bigger than previous one - parent string. More detail not "j = 0", should be "j = item2" saved from Queue.
- Inside while loop, the second for loop, the string to enqueue should start from j, not j + 1, since j position's char is removed.
My performance on mock interview
I did some analysis based on a few simple test cases first, and then I told the interviewer that I like to write code to make sure those few simple test cases working at least.
// bfs -> VALID BRUTE FORCE
// ONCE - SHOULD BE Minimum number
// BFS ->
// ()() -> ok
// (() -> remove one, index 0 or 1 -> find valid (), remove open
// ()(( -> remove two,
// check not valid
// 0 )(( -> queue
// 1 (((
// 2 ()(
// 3 ()( -> queue
// ------------------------
// 0 )(( -> queue
// 1 (((
// 2 () -> valid string found!
// 3 ()( ->
()()))
--
)()))
Feedback I like to look into
It takes me long time to master this hard level algorithm: 301. Remove Invalid Parentheses. Without practice and help from interviewers, it will take me more time to understand my weakness. I like to work on my communication skills as well besides coding and analysis, requirement gathering.
Here are some feedbacks I like to think about after the mock interview:
Help your interviewee get better!
- The interviewee proposed a stack solution, which is in the right direction of the optimal solution, but she then dropped it and proposed a BFS solution. The BFS solution is sub-optimal as it would take more space.
- Once the interviewer explicitly mentioned the proposed solution makes sense and can go ahead with implementation, it would be better for the interviewee to jump into the implementation instead of spending extra time on explaining the idea more.
- During implementaion, the interviewee considered the edge cases, such as empty input and 0-length string.
- The actual implementation is sub-optimal in terms of time complexit.
- The code can be cleaner. The inconsistent indentation hurts the readability of the code.
- The interviewee proactively thought of more efficient optimization based on the original solution, though the improvement introduced bugs.
- The time and space complexity based on the implementation should be at the scale of factorial instead of polynomial.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _301_all_valid_paratheses
{
class Program
{
static void Main(string[] args)
{
var list = RemoveInvalidParentheses("(a)(b(a)");
}
/// <summary>
/// Oct. 5, 2020
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static IList<string> RemoveInvalidParentheses(string s)
{
if (s == null || s.Length == 0)
{
new string[] { "" }.ToList();
}
if(isValid(s))
{
return new String[]{s}.ToList() ;
}
var set = new HashSet<string>();
// queue - BFS - save index position of open or close parentheses
// index - int[], size - 2, index position - second - 0, close 1
// Tuple<string, int>
var queue = new Queue<Tuple<string, int>>();
queue.Enqueue(new Tuple<string,int>(s, 0));
// (a)b)
// ()((
// -
// ((((((( ->
// O(m * m * N * N) -
// m is how many strings (count of parenthese), n is size of string - 4
// space -> queue O(m! * n) - m is count of parent chars in string
// m + m*(m-1) + m(m-1)(m-2) + ... + m!
// m* m!= (m+1)! loosely upper bound
// 10 -> 10*9 -> 10*9*8
// 10 -> 10: 9 -> 90: 8
while(queue.Count > 0)
{
// BFS - every string will be check - O(m) count of parenthese < N
var count = queue.Count;
for(int i = 0; i < count; i++)
{
//(a)b)
var current = queue.Dequeue();
var item1 = current.Item1;
var item2 = current.Item2;
// O(N * N)
for(int j = item2; j < item1.Length; j++) // (
{
var c = item1[j];
var isPare = c == '(' || c== ')';
if(isPare)
{
var tmp = item1.Substring(0, j) + item1.Substring(j + 1, item1.Length - j - 1);
if(isValid(tmp))
{
set.Add(tmp);
}
else
{ // one char shorter
queue.Enqueue(new Tuple<string, int>(tmp, j));
}
}
}
}
if (set.Count > 0)
{
break;
}
}
return set.ToList();
}
// O(N) - N length of S
private static bool isValid(string s)
{
if(s == null || s.Length == 0)
return true;
int openCount = 0;
for(int i = 0; i < s.Length; i++)
{
var c = s[i];
if(c == '(')
{
openCount++;
}
else if(c == ')')
{
if(openCount == 0)
{
return false;
}
openCount--;
}
}
return openCount == 0;
}
}
}
