Find minimum required parentheses - discussion

Find minimum required parentheses

/**
* Get the minimum required parentheses from the given parentheses such that their original 
order is still preserved. Note that it should also remove invalid parentheses.

(((()))) => ()
)))() => ()
()(()()) => ()(()())

))))() ))) => ()

*/

public static string GetMinimumRequireParentheses(char[] text)
{
  if(text == null || text.Length == 0)   
      return "";
  
  var length = text.Length; 
  int openBracket = 0;
  int unmatchedBracket = 0; 
  var minimumString = new StringBulider(); 
    
  char previous = '';
  for(int index = 0; index < length; index++)
  {
      var current = text[index]; 
      var isOpen = current == '('; 
      
      if(isOpen)
      {
          openBracket++; 
          // add (
          if(openBracket == 1)
          {
              minimumString.Append("("); 
          }
      }
      else 
      {
          if(openBracket > 0)
          {
              // add - previous char ), I have to special handling , add ()
              // missing open bracket somewhere before 
              if(previous == '(')
              {
                  minimumString.Append("()"); // 
              }
              else 
              {  // 1. (()) -> no need to add - extra )
                 // 2. ()()) -> need to add extra big parenthese ->  
                  minimumString.Append(")"); // but I missed one open bracket at the beginng
              }
              
              openBracket--; 
          }         
      }
      
      var previous = current; 
  }
    
    var stringMayInclude = minimumString.ToString();
  // edge case
    if(openBracket > 0)
    {
        // remove one ( from minimum string 
        //last one
        stringMayInclude.Replace('(', ''); // last one in the string, 
    }
    
  return minimumString.ToString(); 
}

/*
* For example: ")(((())())((" -> "(()())"
* For example: "((()))" -> "()"
*/
/*
keywords:

parentheses () not  {}[]
invalid parentheses
(()) -> (), 
how many remove here?
outer one is removed since they are extra, 

x -> 

constrain: preserve orginal order 
)))() => () -> do not have open one to match them 

()(()()) -> () ((x)(y)), the outer one is also valid? group x and y together

Ask: 
get the minimum required parentheses.
    
1) Invalid Parentheses - openBracket, unmatched bracket (removed right away) -> finish the string 
(((() - remove extra open bracket -> 3, so then you have to remove 3 extra open bracket
O(n) -> scan 3 open bracket unmatched 
when it is good time for remove
   find pair () first, 
    
2) Optimise them (Remove all the extra parentheses).
*/

You are working for a company where they sell millions of products online. 
Each product is represented by a unique Id. 
Their analytics systems works in a way that on each product click, 
the corresponding product id will be reported to you. 
Given this stream of data, you have to generate the recommendation of top “k” clicked products.

public interface RecommendationContract {
	void initialise(int k);
	void onProductClicked(String productId);
	List<String> getTopProducts() ;
}
// top k
// million of products online -> top k from millions -> top k -> k = 10, million 

// unique id is presented 
public class Product
{
    public int UniqueId {get; set;}
    public int CountClicked {get; set;}
    
}

Declare an array - dynamic increasing data structure 
Dictionary<string, click> -> look up dictionary, add click increment on, 
add new entry to dictionary
For any moment, I have to work on this dictionary, generate topKProducts
Brute force -> not need to sort unique - nlogn - n million 

top K -> 
    K - element 
    MaxHeap
    MinHeap
    
    new product come in, should current > minimumOne -> remove minimum -> add current one -> minimumHea[
        already in top K
        stay top K -> adjust heap
        
    time complexity: logK 
    query minimum number in heap -> O(1)  * n  
    it is in heap, maintain the heap , O(lgk) * n
    above time complexity:  n * O(lgK)
        ONProductionCliked:
          dictionary-> O(1)
          heap time -> < minimum value O(1)
          in the heap -> maintain the heap -> heapify O(logk)
         overall O(logk)
        
        getTopKProducts
        {
           K - O(1), O(lgk)
           k * lgk -> maximum heap size -> k, k - 1, ..., 1 -> 0
           
           time complexity klgk
        }        
    }