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

  1. median of two sorted array
  2. Group Shifted Strings
  3. Flatten a Multilevel Doubly Linked List
  4. Redundant connection II
  5. Bulls and Cows
  6. Guess the word
  7. 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

  1. Binary Tree Maximum Path Sum
  2. Combination I & II
  3. Valid Palindrome II & III
  4. Subarray Sum Equals K
  5. Product of Array Except Self
  6. 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

  1. Trapping Rain Water
  2. Regular expression matching
  3. Word search II
  4. Maximum Width of Binary Tree
  5. 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:

  1. Facebook | Operation research scientist | Onsite reject
  2. Stripe | new grad | Onsite reject
  3. 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.

  1. 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.

  2. 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).

  3. 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)

  4. 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.

  5. 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

googlefacebook offermicrosoft


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

My notes - I like to review those algorithms quickly:

  1. median of two sorted array
  2. Group Shifted Strings
  3. Flatten a Multilevel Doubly Linked List
  4. Redundant connection II
  5. Bulls and Cows
  6. Guess the word
  7. Recover Binary Search Tree
  1. Binary Tree Maximum Path Sum
  2. Combination I & II
  3. Valid Palindrome II & III
  4. Subarray Sum Equals K
  5. Product of Array Except Self
  6. Next Permutation
  1. Trapping Rain Water
  2. Regular expression matching
  3. Word search II
  4. Maximum Width of Binary Tree
  5. 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. 

Leetcode: Jianmin Chen | Last 12 months submission | Comparison to Dr. Lai

 Jianmin Chen



Dr. Lai  https://leetcode.com/justyy/

Day 500 streak on daily challenge

around 3yrs - I did it every day for the past THREE years.

https://leetcode.com/justyy/

Take 30-60 minutes per day to do coding, stick to it and you will definitely see you improve yourself when you reach 100 days, 200 days and so on..

I started leetcoding in 2018 when I was looking for new opportunities, and soon i love the feeling of solving questions especially when you get the green "AC".

I become addicted to leetcoding, and my programming skills improve over time. It becomes a habit and just like we need to brush the teeth every day - if i don't do it, i feel uncomformable.

I soon got a job at General Electric, 13 months later I joined AWS and then 18 months later, here I am at Microsoft Research Cambridge (MSRC) - I had 10 interviews at MSRC.

One tip: you can solve problems by the categories, companies - the most frequent questions by companies help a lot. For the first few rounds of interview, the Leetcode mocking is very helpful to get familiar with solving problems under time pressure.

Also, by teaching, you learn quicker and understand better. Writing code on whiteboard helps but become less important as after COVID, all interviews are conducted online, so a decent keyboard is more necessary than practicing coding on whiteboard.

Feel free to AMA. Thank you.


Follow up 

March 25, 2022

I just could not believe that I have chance to prepare for another Meta onsite in April 2022. I think that it is more challenge this year since I only practice Leetcode algorithms less than 3 months, with less than 200 submissions, less than 40 additional algorithms solved. 


Leetcode profile: HelloACM.com | From 600 beyond I like to find talent people on Linkedin.com

March 9, 2022

Search profiles

I started to review my post From 600 beyond, and then I like to find some profiles with a lot of submissions in 2021. I did find this profile, and his discussion post, and then I came cross HelloACM.com.

HelloACM.Com

I like to go over this Leetcode profile:  

https://leetcode.com/justyy/

TWO years NO days off (actually more than two years, I started to do Leetcode programming in 2018 while I was looking for jobs) - I am still learning. I am considering myself still a newbie (maybe better than Noob).
Another reason that I practice coding is that I can teach my sons (aged 6 and 8) programming - as I teach them and upload them here: https://github.com/DoctorLai/Teaching-Kids-Programming/blob/main/README.md



Leetcode: Alex Wice | Profile, solutions

 March 9, 2022

I like to explore a few Leetcode profiles. Here is the link of Alex Wice. 

Bigtable in action (Google Cloud Next '17)

 March 9, 2022

Daily routine video | Start a day | BigTable | NoSQL

Here is the link. 

  • Introduction
  • Cloud Bigtable
  • Data model
  • Schema design
  • Customer Service Density
  • Partner Geomesa/ CCRI
  • Wrap-up



Tuesday, March 8, 2022

【大大讀書】《一流的人如何保持顛峰》(說書人:謝文憲)

 March 8, 2022

Here is the link. 

【大大讀書】:一年訂閱100本影音說書,每週會更新2本。 馬上訂閱,再加贈200本影音說書,讓你十倍速快速升級! 快去看看:http://bit.ly/2OrOcY7

為什麼拚命做的人不是先升遷?真正厲害的人懂得如何休息跟練習 |《一流的人如何保持顛峰》心得

 March 8, 2022

Here is the link. 

《一流的人如何保持顛峰》是我喜歡的一本書,裡面的道理或許看起來簡短,但實則長期影響一個人的工作表現,或是人生滿意度。這支影片我會分享裡面得到的心得。​ -​ 📕支持著作:https://reurl.cc/ONA6R 🎥 訂閱頻道:https://goo.gl/VsQgD2 📚更多學習成長影片:https://goo.gl/Ce7e3T -​ 📘我的Facebook:https://fb.com/richfriend.fans ⏺我的Instagram:https://www.instagram.com/alvin701 💰我的理財筆記:http://blog.17rich.com/ -​ 影片目錄​ 01:40 本書作者背景​ 02:53 成長公式::壓力 + 休息​ = 成長 03:46 第1部分》成長公式的運用​ 06:31 第2部分》過度壓力的傷害​ 08:58 第3部分》一流的人懂休息​ 10:42 總結​ -​ #如何休息 #閱讀心得 #艾讀​ --------------------------------------------------------------------------------​ ★這些人氣影片也別錯過★​ -------------------------------------------------------------------------------- ​ ‣‣10年沒上班,我活過來了!​ https://youtu.be/9SOt8_hbfQc ‣‣成功者每天都在做什麼?他們都有的高效習慣​ https://goo.gl/WQprfL ‣‣5個超好用的說話技巧,聊到對方心坎裡!​ https://youtu.be/Q9HQSoFChGU ‣‣R90睡眠法,頂級運動員都在用​ https://youtu.be/POzU_gjS60s ‣‣只要3小時,勝過別人一天的工作量​ https://goo.gl/AKo2CP ‣‣10本可以改變人生的書!​ https://goo.gl/nkPvNJ ‣‣為什麼有錢人會這樣做?5個加快財務自由的方法​ https://youtu.be/kh38NbLyZs8 ‣‣這本書影響我15年,快樂是自己能決定的事!​ https://youtu.be/cjpsKkbD5MU ‣‣作者花20年,發現富人變有錢的真正方法​ https://youtu.be/snUfe9eX9HA

Stephen Duneier

 From Wikipedia, the free encyclopedia

Jump to navigationJump to search
Stephen Duneier
Stephen Duneier, CEO Bija Advisors.png
BornJuly 1967 (age 54)
Brooklyn, New York[1]
EducationMBA in finance and economics
Alma materNew York University, Stern School of Business
OccupationFounder and CEO of Bija Advisors LLC, Lecturer at University of California, Artist, Author
Known forIncorporating Cognitive Science with Investment Management,[2] Yarnbombing in the Wilderness,[3] Extreme Goal Achievement
Spouse(s)Barbara
Websiteyarnbomber.com, thelpe.com

Stephen Duneier is an American professional investment manager, strategy consultant, speaker, lecturer, author, artist and Guinness World Record holder.

Education[edit]

Duneier attended the University of Florida from 1985 to 1987 before leaving to pursue a career in financial management with Drexel Burnham Lambert and then Prudential-Bache. He finished his undergraduate education at Florida Atlantic University with a BBA in finance and economics and received an MBA in finance and economics from New York University's Stern School of Business.[4]

Career in finance[edit]

While still attending graduate school at NYU, Duneier worked as a foreign exchange option trader specializing in exotic derivatives at Credit Suisse in New York City. He was later hired by Bank of America to expand their foreign exchange business into European crosses and Emerging Markets and eventually promoted to Global Head of Currency Option Trading. Soon after Bank of America merged with Nations Bank, Duneier moved to AIG International where he was eventually named managing director in charge of Emerging Markets trading and based out of London, England. In 2002, Duneier launched a proprietary trading portfolio known as "TIP" for AIG International.[5] Shortly after the firm merged with Banque AIG, Duneier became a global macro portfolio manager at London Diversified Fund Management in London and later at Peloton Partners in Santa Barbara, California.[6] In 2008, he was one of the founding partners at Grant Capital Partners[7] which grew to $1.25 billion in assets under management.[8] He left in 2012 to launch Bija Capital Management and eventually Bija Advisors LLC, a consulting firm which advises experienced hedge fund managers, CIO's and asset allocators. Through Bija Advisors, he speaks on and publishes a subscription based newsletter covering topics on economics,[9][10] cognitive science,[11] and investment management.[12][13] Duneier's book, AlphaBrain is released in March 2019 (Wiley & Sons).

Career as a cognitive science practitioner[edit]

In 2001, Duneier began to apply his approach to decision making, which he calls "Bija", to his personal life, leading to a long string of eccentric goals and resolutions being set and achieved.[14] In 2012, it reached fever pitch when he embarked upon 12 for 2012,[15] a New Year's resolution which included 12 Learning Resolutions and 12 Giving Resolutions.[16] As part of his resolutions, he has performed at comedy clubs; learned to fly a helicopter; climbed iced waterfalls; raced cars; had root canal without anesthetic; learned to speak German; read 50 books in 52 weeks;[17] participated in the Pier to Peak half marathon; learned to unicycle; used jumping stilts to hike; fostered a pit bull; built homes for families in Arizona; learned ballroom dancing, how to drum, slackline, parkour, skydive; and flown planes aerobatically.[18]

He set the Guinness World Record for the largest crocheted granny square. It is 1,311 square feet, incorporates more than 30 miles of yarn and weighs over 60 pounds. It took 2 years, 7 months and 17 days to create, and required more than 500,000 double crochet stitches.[19][20][21][22]

Duneier now speaks[23] and writes about his experience and how others can take what we have learned from research conducted in the field of cognitive science in order to make better decisions and achieve bigger goals.[24]

Career as a lecturer[edit]

Duneier teaches undergraduate and graduate level courses on Decision Analysis in the College of Engineering at the University of California in Santa Barbara.[25]

How to Achieve Your Most Ambitious Goals | Stephen Duneier | TEDxTucson

March 8, 2022

Here is the link. 

How you define Stephen Duneier depends on how you came to know him. Some define him as an expert institutional investor, while others know him as a large scale installation artist, avid outdoorsman, professor, decision strategist, coach, business leader, mindfulness extremist, author, speaker, daredevil or Guinness world record holder. In his talk, Stephen explains that what truly defines him aren't titles, but an approach to decision making that transformed him from someone who struggled with simple tasks to a guy who is continuously achieving even his most ambitious dreams. For thirty years, he has applied cognitive science to investing, business and life. The result has been the turnaround of numerous institutional businesses, career best returns for managers who have adopted his methods, the development of a $1.25 billion dollar hedge fund and a rapidly shrinking bucket list. Mr. Duneier teaches graduate courses on Decision Analysis in UCSB’s College of Engineering. His book, AlphaBrain is due for release in early 2017 from Wiley & Sons. Through Bija Advisors, he helps business leaders improve performance by applying proven, proprietary decision-making methods to their own processes. His artwork has been featured around the world and is represented by the Sullivan Goss Gallery. As Commissioner of the League of Professional Educators, Duneier is using cognitive science to alter the landscape of American education. He is the former Head of Currency Option Trading at Bank of America and Emerging Markets at AIG International. This talk was given at a TEDx event using the TED conference format but independently organized by a local community. Learn more at http://ted.com/tedx



Leetcode algorithm: Copy his idea in terms of writing posts

 https://leetcode.com/issac3/

Stay tuned, I will write more in detail later. 

I created a backtracking algorithm list on Leetcode.com, and I will practice one algorithm called Leetcode 131. Palindrome Partitioning


Be Ambitious: How To Be A Powerful Woman

March 8, 2022

Here is the link. 

Self-belief and ambition... The UK's most powerful women share their experiences, advice and philosophy for a successful working life. Find out more about the Woman's Hour Power List: http://www.bbc.in/whpowerlist

10 things I did last 12 months to help me a lot

March 8, 2022

Introduction

It takes some wisdom to make good choice last 12 months. I like to put together 10 things I did last 12 months, and see if I can learn better, live better and enjoy my wealth and stay healthy. 

10 things I did 

  1. I spent time to learn how to ski, attended snowing school four times in a month - February, 2022;
  2. I paid Google premium youtube.com
  3. I paid Roger monthly plan first time in last 12 years. I understand that it is important to stay connected to family and friends. I chose to use Roger pay as you go, and then I limited myself so many ways in my daily life. 
  4. I paid Microsoft small business office monthly subscription in my home office. 
  5. I bought Michael Kors handbag first time in my life. I like to learn better how Michael Kors and their stock performance during pandemic, people still purchase expensive brand name bags. 
  6. I uploaded a lot of videos on instagram.com, so that I can learn and play and entertain myself with interesting content. Small videos and other content written by myself, I record video more often using my Google 5g 4a phone. 
  7. I chose to continue to run weekly, I run 5K every Saturday around deerlake. 
  8. Weight control, now my weight is below 200 lb, around 195lb. 
  9. I learn how to deal with my frozen shoulder much better. Less pain and recovery is in progress. 
  10. I learn how to go through high pollen index season more carefully. 

Google interview preparation guide

Here is the article from mtu.edu. 

How to succeed: 

At Google, we believe in collaboration and sharing ideas. Most importantly, you'll need more information from the interviewer to analyze & answer the question to its full extent. 

  • * It’s OK to question your interviewer. 
  • * When asked to provide a solution, first define and frame the problem as you see it. 
  • * If you don't understand - ask for help or clarification. *
  •  If you need to assume something - verbally check it’s a correct assumption! 
  • * Describe how you want to tackle solving each part of the question. 
  • * Always let your interviewer know what you are thinking as he/she will be as interested in your process of thought as your solution. Also, if you're stuck, they may provide hints if they know what you're doing. 
  • * Finally, listen - don't miss a hint if your interviewer is trying to assist you! 


5) What is Google looking for?: 

"We are not simply looking for engineers to solve the problems they already know the answers to; we are interested in engineers who can work out the answers to questions they had not come across before." 

Interviewers will be looking at the approach to questions as much as the answer: 

  • * Does the candidate listen carefully and comprehend the question? 
  • * Are the correct questions asked before proceeding? (important!) 
  • * Is brute force used to solve a problem? (not good!) 
  • * Are things assumed without first checking? (not good!) 
  • * Are hints heard and heeded? 
  • * Is the candidate slow to comprehend / solve problems? (not good!) 
  • * Does the candidate enjoy finding multiple solutions before choosing the best one? 
  • * Are new ideas and methods of tackling a problem sought? 
  • * Is the candidate inventive and flexible in their solutions and open to new ideas? 
  • * Can questioning move up to more complex problem solving? Google is keen to see really high quality, efficient, clear code without typing mistakes. Because all engineers (at every level) collaborate throughout the Google code base, with an efficient code review process, it’s essential that every engineer works at the same high standard.


30 hard level algorithms: google - Leetcode premium

 

30 hard level algorithms: google - Leetcode premium

 Dec. 7, 2020

Introduction

It is a tough project to work on. I am planning to go over the following 30 hard level algorithms provided by Leetcode premium. 

30 hard level algorithms

I like to go over those 30 hard level algorithms

  1. 727 Minimum windows subsequence - DP, sliding window
  2. 715 Range Module, Segment tree, ordered map
  3. 552 Student attendance record II, DP
  4. 465 Optimal account balancing 
  5. 1499 Max value of equation, Array, sliding window
  6. 753 Cracking the safe, math, DFS
  7. 1231 Divide Chocolate, Binary search, greedy
  8. 308 Range sum query 2D - Mutable, Binary indexed tree, segment tree
  9. 1293 Shortest path in a grid with obstacles elimination
  10. 1444 Number of ways of cutting a pizza, DP
  11. 527 Word abbreviation, string, Sort
  12. 1240 Tiling a rectangle with the fewest squares, DP, backtracking
  13. 315 Count of smaller numbers after self, Binary search, Divide and conquer, Sort, binary indexed tree, segment tree
  14. 460 LFU cache, design
  15. 1406 Stone game III
  16. 248 Strobogrammatic Number III
  17. 1610 Maximum number of visible points, Two pointers, Geometry
  18. 335 Self crossing, Math
  19. 420 Strong password checker
  20. 1345 Jump Game IV
  21. 679 24 Game
  22. 642 Design search autocomplete system
  23. 1377 Frog position after T seconds 
  24. 818 Race car
  25. 1255 Maximum score words formed by letters, bit manipulation
  26. 174 Dungeon game, binary search, DP
  27. 1125 Smallest sufficient team, DP, bit manipulation
  28. 68 Text justification, string
  29. 847 shortest path visiting all nodes, DP, BFS
  30. 732 My calendar III, segment tree, ordered map

Actionable Items

I only studied and learned the top nine hard level algorithms, still I have 21 algorithms to review. Now it is 11:34 PM. 

  1. 727 Minimum windows subsequence - DP, sliding window
  2. 715 Range Module, Segment tree, ordered map
  3. 552 Student attendance record II, DP
  4. 465 Optimal account balancing 
  5. 1499 Max value of equation, Array, sliding window
  6. 753 Cracking the safe, math, DFS
  7. 1231 Divide Chocolate, Binary search, greedy
  8. 308 Range sum query 2D - Mutable, Binary indexed tree, segment tree
  9. 1293 Shortest path in a grid with obstacles elimination
Life is tough. I should plan early and have more time for those 21 hard level algorithms. 

Leetcode discuss: 424. Longest Repeating Character Replacement

March 8, 2022

Here is the link. 


C# | Sliding window technique | Time complexity: O(N)

Feb. 28, 2022
Introduction
It is most important to get optimized time complexity, linear complexity. I continued to modify the code after my last practice.

Two changes | One is to get max ocurrence in O(1) time | Always move right pointer
For every sliding window, it takes O(1) time to get max occurrence. Just use one variable maxValue and a HashMap.

Always move right pointer in every iteration seen in while statement.

In theory | after careful review
It is not a problem to move left pointer in sliding window, even though it may affect maxValue variable which stands for maxium occurrence in sliding window.

What if max frequent letters are more than one, the one recorded is not the same one removed. But it should still work, I should find a few test cases to explain in detail later if I have time.

Follow up
March 1, 2022
If the left pointer in sliding window increments one, the string in sliding window is a substring of previous sliding window, therefore there is no need to check max occurrence. In other words, right pointer can increment one as well. So inside while loop, every iteration the right pointer can increment one.

The following C# code passes online judge.

public class Solution {
    public int CharacterReplacement(string s, int k)
        {
            if (s == null || s.Length == 0 || k < 0)
                return 0;

            var length = s.Length;
            var left = 0;
            var right = 0;

            var map = new Dictionary<char, int>();
            var maxValue = 0; 
            var maxLength = 0;            

            while (left <= right && right < length)
            {                
                var current = s[right];

                if (!map.ContainsKey(current))
                {
                    map.Add(current, 0);
                }

                map[current]++;         

                /* the following two statements: Time complexity: O(NlogN)
                var values = map.Values.ToList();
                var maxValue = values.Max();
                */
                maxValue = map[current] > maxValue? map[current] : maxValue;

                var width = right - left + 1;
                var widthCheck = width - maxValue <= k;
                if (widthCheck)
                {
                    maxLength = width > maxLength ? width : maxLength;
                   // right++;
                }
                else
                {
                    var removed = s[left];
                    map[removed]--;
                    if (map[removed] == 0)
                    {
                        map.Remove(removed);
                    }

                    left++;
                }

                // always move right pointer
                right++;
            }

            return maxLength;
        }
}