When you have a friend solved 900 algorithms

Oct. 20, 2019

Introduction

It is a small world, I had chance to meet engineers as an interviewer on interviewing.io, so I do not need to pay coach fee, I can work with best engineer in the world after mock interview. I worked with one two months ago, but I learn difference between us, he solves problems much more efficiently.

Two months later

I shared one of solutions on leetcode.com after I played weekly contest, and then I got comment around 10:00 PM. Here is the post.

I had chance to learn to write a better solution, since I found that he also posted an answer, I wrote C# code using same idea as well.

When you have a friend

I always work hard to push myself to meet top talent people. Sometimes I can not tell how good people are as an engineer, senior engineer, Ph.D. graduate, Microsoft engineer, Facebook engineer. I just learn from them by  working on mock interview as interviewer/ interviewee, and exchange ideas through Leetcode discuss.

Here is the post.

C# Code study: a solution can be written in two loops

I chose to study top voted solution which is converted to a different problem. I like to describe this way, it is to find all sliding windows containing above average number of chars in "QWER". The dictionary to store is whole string except current sliding window. Why? It is so simple to write to the code and it can be solved in less than 15 minutes. The solution link is here.

Here are shortcuts I learn from your code:

1. Define map using int as key, each char of "QWER" is the key which is ascii value; Avoid string IndexOf etc.
2. Work on sliding window, start and end, for each end position from 0 to length - 1, run a loop on start as long as the balance string is met.
3. Work on simplicity in design process and coding process. Right now there are less than 5 things to consider, map, ascii value, slide window, left, right, while loop

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace sliding_windows___study_code
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = BalancedString("QWER");
        }

        /// <summary>
        /// Oct. 19, 2019
        /// Leetcode 
        /// study code
        /// https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/JavaC%2B%2BPython-Sliding-Window
        /// It is to find all sliding windows containing above average number of chars in "QWER". 
        /// The dictionary to store is whole string except current sliding window. Why? It is so simple 
        /// to write to the code and it can be solved in less than 15 minutes.
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int BalancedString(string s)
        {
            var exclusiveSlidingWindow = new Dictionary<int, int>();
            var length = s.Length;
            var minLength = length; 

            for(int i = 0; i < length; i++)
            {
                int key = s[i];
                if(!exclusiveSlidingWindow.ContainsKey(key))
                {
                    exclusiveSlidingWindow.Add(key, 0);
                }

                exclusiveSlidingWindow[key]++; 
            }

            int left = 0; 
            int average = length/4; 

            // Find all sliding window containing each char of "QWER" above average
            for(int index = 0; index < length; index++)
            {
                exclusiveSlidingWindow[s[index]]--;

                while(left < length && 
                    (!exclusiveSlidingWindow.ContainsKey('Q') || exclusiveSlidingWindow['Q'] <= average) && 
                    (!exclusiveSlidingWindow.ContainsKey('W') || exclusiveSlidingWindow['W'] <=average)  && 
                    (!exclusiveSlidingWindow.ContainsKey('E') || exclusiveSlidingWindow['E'] <= average) && 
                    (!exclusiveSlidingWindow.ContainsKey('R') || exclusiveSlidingWindow['R'] <= average))
                {
                    minLength = Math.Min(minLength, index - left + 1); 
                    exclusiveSlidingWindow[s[left]] += 1; // not in the sliding window
                    left++; // caught by online judge
                }
            }

            return minLength == length? 0 : minLength; 
        }
    }
}

I checked C# code shared here, and I learn that I can break giant expression in my above code. There are two tips:



Declare exclusiveSlidingWindow hashmap using Dictionary class, and then use constructor to initiate four keys with initiate value 0;
While loop giant expression can be removed, four case of 'Q', 'W', 'E', 'R' can be replaced using one aggregate function Max.




I wrote comment on my own post on Oct. 20, 2019 10:53 AM. 

The C# code seen in my friend's post:
Idea 1: var freq = new Dictionary<char, int>() {{'Q', 0},{'W', 0}, {'E', 0},{'R', 0}};
Idea 2: freq.Values.Max()


var freq = new Dictionary<char, int>() {{'Q', 0},{'W', 0}, {'E', 0},{'R', 0}};
        int n = s.Length, res = n, i = 0;
        foreach(var ch in s)
            freq[ch]++;
        
        for (int j = 0; j < n; j++) 
        {
            freq[s[j]]--;
            while (i < n && freq.Values.Max() <= n / 4) 
            {
                res = Math.Min(res, j - i + 1);
                freq[s[i++]]++;
            }
        }
        
        return res;