Julia's coding blog - Practice makes perfect

From January 2015, she started to practice leetcode questions; she trains herself to stay focus, develops "muscle" memory when she practices those questions one by one. 2015年初, Julia开始参与做Leetcode, 开通自己第一个博客. 刷Leet code的题目, 她看了很多的代码, 每个人那学一点, 也开通Github, 发表自己的代码, 尝试写自己的一些体会. She learns from her favorite sports – tennis, 10,000 serves practice builds up good memory for a great serve. Just keep going. Hard work beats talent when talent fails to work hard.

Showing posts sorted by date for query leetcode 126. Sort by relevance Show all posts

Tuesday, May 10, 2022

Leetcode discuss: 957. Prison Cells After N Days

Here is the link.

C# | Quick learner | Bit manipulation warmup | Avoid TLE error

May 10, 2022
I am warmup algorithms to prepare for Google phone screen in 2022. I like to learn and learn quickly.

Introduction
To be a quick learner, I always like to read at least three solutions, and also write C# solutions based one Leetcode discuss post.

Analysis | Intuition | votrubac
Based on the following constraints given in problem statement, we can easily to discuss the scope of problem based on n in range of 2^9, cells.Length = 8.

Constraints:

cells.length == 8
cells[i] is either 0 or 1.
1 <= n <= 10^9

If cells's length is 8, in other words, there are 8 cells, since each cell is either 0 or 1, so the number of all the possible state combinations is 2^8 = 256. This means when N > 256, cells will have the same state as its orignal 256 states. So we expedite the search, avoid time out, reduce calculatuion of next state from n to [loop size] + n % [loop size]. It is challenge task to determine how to take minimum calculation approach in design stage.

For example, given n = 1,000,000, cells is an integer array with size 8, so the total steps to calculate is reduced from n to 256 + n %256, which is at most 512. Reduction from 1,000,000 to 512 is big success to solve this problem without TLE problem.

Using 2^8 vs HashSet | Random state
Since integer array cells's length - denoted as L determines at most 2^L states, it is random process to determine next state, so we can not determine how many states to end the cycle, therefore, we need to store all possible states and use HashSet to determine if it is seen in previous steps.

Of course, it is a good practice to write a solution using bit manipulation. I will try it as well.

Complexity Analysis
Runtime: O(2 ^ n), where n is the number of cells (not days). For 8 cells, we can have 64 different states.

Memory: O(n). We need to remember a single state of all cells for the loop detection. For 8 cells, the complexity is O(1).

The following C# code passes online judge.

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

namespace _957_prison_state_after_N_days___bit
{
    class Program
    {
        static void Main(string[] args)
        {
            //Input: cells = [0,1,0,1,1,0,0,1], n = 7
            //Output: [0,0,1,1,0,0,0,0]
            var test = new Program();
            var result = PrisonAfterNDays(new int[] { 0, 1, 0, 1, 1, 0, 0, 1 }, 7);
            Debug.Assert(String.Join(",", result).CompareTo("0,0,1,1,0,0,0,0") == 0);
        }

        /// <summary>
        /// study code
        /// https://leetcode.com/problems/prison-cells-after-n-days/discuss/1769581/C-bitwise-op
        /// </summary>
        /// <param name="cells"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int[] PrisonAfterNDays(int[] cells, int n)
        {
            // using 8 bits integer to reprenst each cell in given cells array
            var bits = 0;
            
            for (int i = 0; i < cells.Length; i++)
            {
                // left shift i bits - each cell maps to one bit from left to right
                // | - or operator
                bits |= (cells[i] << i);  
            }

            var map = new Dictionary<int, int>();
            int step = 0;  
            int state = bits;  

            while (!map.ContainsKey(state))  
            {
                map.Add(state, step); 
                step++;

                //01111110 - 8 bits - first bit and last bit will not change 
                //01111110 - 8 bits - integer 126 = 2 ^7 - 1 - 1 = 128 - 1 - 1 = 126
                // if it is easy to understand the above calcuation, then go ahead to read the code

                // shift k left and right to get the next state
                // left shift one bit - 
                var leftShift = (state) << 1;
                var rightShift = (state) >> 1;
                // XOR operator ^, 1 ^ 1 = 0, 1 ^ 0 = 1, 0 ^ 0 = 0

                // Bitwise Complement Operator (~ tilde)
                // the bitwise complement operator is a unary operator 
                // (works on only one operand). It takes one number and 
                // inverts all bits of it. When bitwise operator is applied on bits then, 
                // all the 1’s become 0’s and vice versa. The operator for the bitwise complement is ~ (Tilde).
                // 
                state = ~(leftShift ^ rightShift) & 126;                
            }

            int entryStep = map[state];    
            int L = step - entryStep;

            // avoid TLE error 
            if (n >= entryStep)
            {
                n = (n - entryStep) % L + entryStep;   
            }

            state = bits;
            for (int i = 0; i < n; i++)   // walk n steps from oringal state
            {
                state = ~((state >> 1) ^ (state << 1)) & 126;
            }

            var result = new int[8];
            for (int i = 0; i < cells.Length; i++)  
            {
                // left shift >> i, and determine if it is 0 or 1
                result[i] = (state >> i) & 1;  
            }

            return result;
        }
    }
}

Wednesday, March 9, 2022

Algorithms to study: FB | Google | Amazon | More | 2020 New graduate looking for FANG jobs

March 9, 2022

Here is the link.

Offers from Google L4 | Facebook E3 | Microsoft L60 | Amazon SDE1 (Experience)

Last Edit: April 1, 2020 4:48 AM

42.3K VIEWS

I would like to share my experience interviewing with Google, Facebook, Microsoft, Apple. I had a return offer from Amazon (SDE1). In the last 2 months, I took 6 phone screen, 4 onsites and got offers from Google (L4), Facebook (E3), Microsoft (L60). The TC information is at the end. I am also including my internship interview experience with Amazon.

I will try to add the equivalent leetcode questions (as many as I can remember).
Hope this will be helpful.

Profile:
MS in computer science (graduating in May 2020)
YOE : 2 before masters
Others: 1 internship at Amazon
Leetcode : 754 (E : 177, M : 451, H : 126)

Google | SDE L4 | Mountain View | March 2020 | (Accepted)

Application:
Contacted by recruiter. The position was for people with at least 2 YOE. The level will be decided by interview performance.

phone screen (45 min):
1 easy (string) , 1 hard (binary search, divide conquer) , 1 medium (string)
All 3 questions were LC questions, can be found in google's list in LC.
I felt the focus was more on basic understanding and approach towards the problem (rather than optimal solution). Bugs, incorrect syntax is totally fine as long as you can recognise them and fix it. One small note, practising coding on Google Doc can be a make or break factor. You don't want to get caught balancing braces during a LC hard.

virtual onsite:
4 technical rounds (45 min each), 1 behavioral round (45 min).
technical round 1 : 1 medium (linked list, recursion, multiple followups)
technical round 2 : 1 medium (string), 1 hard (graph)
technical round 3: 1 medium (Queue, follow-up on concurrency), 1 hard (binary search tree)
technical round 4: 1 easy (string), 1 hard (ad-hoc, minimax)
behavioral: Standard Googlyness questions (can be found online)

All questions were exact or slight variation of LC questions, more specifically from Google's list. Focus was more on optimal solution.

Leetode equvalent questions

median of two sorted array
Group Shifted Strings
Flatten a Multilevel Doubly Linked List
Redundant connection II
Bulls and Cows
Guess the word
Recover Binary Search Tree

Decision Process:
Google has a lengthy process following onsite: hiring committee approval, team matching, executive committee approval. The time required to complete this steps depends on recruiter, other deadlines, interview performance. Mine was completed in 10 days (onsite to receiving offer letter).
For compensation negotiation, levels.fyi is very helpful. It's always best to go to them asking for way more than you expect. They generally do not take that as a negative.

Overall experience was awesome.

Facebook | SDE E3 | Mountain View | March 2020 | (Offered)

Application:
Applied for new grad position. Standrad new grad application.

Phone Screen:
1 medium (string, followup: Dynamic programming)
1 medium(array, hashmap, followup : array, hashmap)
All questions were LC questions, can be found in facebook's list. The focus was on correctness, finding optimal solution.

Virtual Onsite
2 technical rounds, 1 behavioral + technical round
Technical round 1: 1 medium (binary search tree), 1 hard (DFS)
Technical round 2: 1 medium(string, not LC), 1 medium(backtracking, multiple followup: backtracking)
Technical + behavioral round: Standard facebook behavioral questions, 1 medium (not LC, backtracking, DP question)

All but 2 questions can be found in facebook's list. There was multiple followup in all questions. My last round did not go well (partly because of connection issues, and partly because I messed up).

Leetcode equivalent questions

Binary Tree Maximum Path Sum
Combination I & II
Valid Palindrome II & III
Subarray Sum Equals K
Product of Array Except Self
Next Permutation

decision process
It took them around 7 business days to make decision and another 2 days for paperwork.

Overall experience was great.

Microsoft | L60 | Redmond | March 2020 (Offered)

Application:
Contacted manager over linkedIn. This was a domain specific research SDE role and did not follow the standard new grad process. Manager worked with recruiter to setup everything.

Phone screen
1 medium (BFS).
Discussion on past project, experience and domain specific topics.

Onsite
5 technical rounds. Focus was on coding, domain knowledge, system design
Technical 1 : discussion on past publication, project, domain knowledge. No coding questions.
Technical 2 : 1 hard (Trie, BFS), 1 hard (string). 1 system design. domain specific case based questions.
Technical 3 : some behavioral, past experience, research related questions. case based questions
Technical 4: 1 hard (array), 1 medium(BFS).
Technical 5: Past experience, research related questions, case based questions.

All coding questions can be found in Microsoft's list in LC. System design question a standrad question found in Grkking the System design interview.
The domain specific questions were difficult and lot more focused on how handle scale.

Leetcode equivalent questions

Trapping Rain Water
Regular expression matching
Word search II
Maximum Width of Binary Tree
Shortest Path in Binary Matrix

Decision Process
They took 10 days to make a decision and sending an offer. This is strictly my personal opinion, but the negotiation process was not a great experience (lowballing with level, compensation, asking/hinting repetitively to sign).
Overall experience, mixed. (Team/engineers: great, recruiting process: not so much)

Apple | ML Engineer | Seattle | March 2020 (Passed)

Passed phone screens, Onsite was scheduled. But I had to cancel it.

Application
Contacted Manager over linkedIn.

Phone screen 1
1 medium (string), 1 medium (BFS). one ML case based question.
The coding questions can be found in Leetcode's top 100 questions.

Phone screen 2
This was focused around ML, no coding questions. ML questions were difficult and the interviewer went into details of each concept. Discussion around past experience, project, publication.

After 2 phone screen and another call with manager, they decided to schedule a onsite.
The overall experience was very very bad. Each phone screen was followed by a prolonged silence from recruiter. Because of that it took nearly 3.5 months to just complete 2 phone screens. Which is just ridiculous. I would have preferred to get rejected early on rather than continuing with this mess for so long.

I also, interviewed and got rejected from these companies/roles:

Facebook | Operation research scientist | Onsite reject
Stripe | new grad | Onsite reject
Bloomberg | new grad | Onsite reject

Stripe | new grad | Bay Area | October 2019 | Rejected
Application:
Applied through career page with referral.

Phone Screen:
1 extremely easy question related to custom sorting.

Onsite
3 Technical rounds, 1 behavioral round
Technical round 1 (Integration interview) : Use an HTTP library to implement some HTTP request testing. Clone a Git repo. It will contain couple of JSON files with HTTP request information, query information and expected response. Design the request and response functionality and check correctness of your implementation. I messed up in this round.
Behavioral round: Questions on past experience, projects, future goals. Standard behavioral questions.
Technical round 2 (Coding interview) : 1 easy question (similar to optimal account balancing, if you are not asked to do it optimally, i.e. the total number for transaction need not be minimum. Followup : optimal account balancing)
Technical round 3 (Bug squashing) : Clone a Git repo. It will have two/three bugs. You have to fix them. I fixed one and identified the source of the second bug but couldn't fix it.

Stripe is known for their unique interview process. I knew about the rounds and what kind question will be there, but still they caught me off guard. It's because there is no way to practice the integration and bug squash interview. The only weakness in their process is they don't have too many different questions and have limited number of tricks (but damn, they were good).

Amazon | SDE Intern | Seattle | March 2019 | Accepted
Application:
Carrer page with referral.

Online assessment:
Amazon sends 2 online assessments (OA) for internship. One OA includes 2 coding questions and another OA includes 6/7 debugging questions. To my knowledge, people solving more 4 debugging questions and 2 coding questions are safe.

Phone screen:
This is the final round for Amazon SDE intern role. Usually 1/2 questions. I was asked:
Number of islands
LRU cache

Decision Process:
I got result within 1 day. Generally, Amazon has a 5 business day response policy.

Interview process was pretty streamlined.
Amazon does not have the greatest recruiting team and it takes a while to get a response. Probably because they hire so many SDEs. Also, you generally don't have any control on team selection or project.

Preparation
I would love to share more of my experience and process. But, there is a lot of great preparation/experience posts on Leetcode, reddit and more importantly, I am too lazy to write. But, here's something I understood in this process.

Preparation is very subjective. Posts/guidelines are often not very helpful and unintentionally misleading. (yes, I see the irony here). If you are new to interviewing, it would be best to assume the first 2-3 interview you give will go horrendously bad (true story). But, that experience will allow you to finetune your process.
Most (or atleast FAANG) companies will ask questions from Leetcode or slight modification of a leetcode question( > 90% in my case). The only way to mitigate risk is to increase the number of question you know or have solved before. It's better to solve 800 LC questions than to trust your problem solving skill over phone in a 45 minutes window or in a cold conference room with a bunch of strangers staring at you. Company specific lists are a better option. Company specific lists can be found in section 'Companies' in Problem page (if you can afford leetcode premium, it's worth it).
Praticing interviewing over phone, virtual is important. So, something like Prmp can be very helpful. (Prmp offers free mocks). For onsite, if you have the luxury you can apply to 1/2 companies that you have no intention of joining or you know you won't get. This gave me a chance to adjust with travel, interviewing continuously for 3-4 hours (Note: May be considered unprofessional)
In most cases, luck is a make or break factor, your skill may not matter. In a FAANG internship interview, one guy was asked a single question : "Two sum", another guy was asked "AVL tree". This kind of messed up things happen all the time. I am pretty sure, if I am interviewed again I may or may not pass all the interviews. I just got lucky. The only way to deal with that is same as point 2.
If you need to use different languages for different interviews (in my case, ML interviews expected python and I prefer C++ for SDE interview) dedicate time to context switching. This might cause issues if you are not very comfortable with continous context switch.

TC information
TC includes base, stock (first year), sign-on bonus, performance bonus
Google L4 (MTV) : base 155K, TC : 325K
Facebook E3 (MTV): base 123K, TC 240K
Microsoft L60 (Redmond) : base 118K, TC 210K
Amazon L4 (Seattle): base 112K, TC 152K

March 19, 2022 - I like to take some time to prepare my own notes.

My notes - I like to review those algorithms quickly:

median of two sorted array
Group Shifted Strings
Flatten a Multilevel Doubly Linked List
Redundant connection II
Bulls and Cows
Guess the word
Recover Binary Search Tree

Binary Tree Maximum Path Sum
Combination I & II
Valid Palindrome II & III
Subarray Sum Equals K
Product of Array Except Self
Next Permutation

Trapping Rain Water
Regular expression matching
Word search II
Maximum Width of Binary Tree
Shortest Path in Binary Matrix

Create a public list on Leetcode.com using my account. I did like to review and code carefully the algorithm called Recover binary search tree, Leetcode 99.