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 relevance for query alien dictionary. Sort by date Show all posts

Thursday, June 16, 2016

Leetcode 269 - Alien Dictionary - Practice 2 more times

June 16, 2016

Try to find a small topic to start to do some research every day at least 20 minutes, and then build up more later on.

Today topic is about writing algorithm code - problem solving, 1st writing (study other's code and understand) vs 1st writing (with simple test case with a diagram, more focus, a small problem):

Here is the cycle Julia goes through for Leetcode 269 - Alien Dictionary:

Coding process ->
choose an algorithm to code ->
study 4 or 5 solution from over 10 solutions ->
cannot learn an algorithm just by reading, stop reading ->
write C# code based on one of them (Java, or C++) ->
add comment, make code readable, debugging ->
code works ->
wait 10 - 20 minutes ->
draw a diagram to work on a simple test case ->
rewrite the code 2nd time->
big difference, a new story to write - it takes close to one hour ->
interesting experience. ->
3rd rewrite ->
document the difference

First blog of Leetcode 269 Alien Dictionary:

http://juliachencoding.blogspot.ca/2016/06/leetcode-269-alien-dictionary.html

1st good writing in C#:
https://gist.github.com/jianminchen/85129ed50ce597f896b0f0c5a2fa5586

Afterwards, work out a simple test case, and then, write down the graph with detail data structure and data, write code based on the picture. New ideas come out naturally to improve:

1st writing focusing on the above diagram: C# implementation
https://gist.github.com/jianminchen/58d80aa86a027af7a3e52277d15c3733

3rd writing using C# code:
https://gist.github.com/jianminchen/8d4c1f601bae0ca7ef27e470dfe1e636

Highlight the differences 3rd time:
1. line 26, base case is updated: words.Length <= 1 instead of <1
2. Add comments what to find in the function alienOrder
1. spell error topological -> topoligical
2. add nodes variable as part of graph
3. getNodes function -
look into string.ToList() -> List<char>
study HashSet.UnionWith() input argument and its type IEnumerable<T>
4. rewrite graphSetup function tasks from line 62 - 79
explain very clearly to find an edge if there is one;
what to construct in the graph.
add precondition for the function.
5. rewrite the function comment for topologicalSort
6. missing line 163 - 164, run time error - array access - out-of-index

statistics:
Time spent: 3rd practice - more than 40 minutes

Quick tip:
{"wrt", "wrf", "er", "ett", "rftt"}

first char, comparison (all five words) => w -> e -> r
third char comparison (first two words - "wrt","wrf") => t->f
second char comparison (third, fourth words -"er","ett") => r-> t

So, the order is "wertf"

Comparison:
alienOrder - two things noticed documented in comment.

3rd writing - take some time to look up HashSet.UnionWith argument type: IEnumerable<T>, good time to learn something here.

Practice to write down what to do, in order to write good code, also need to explain what to do first. Good writing right side! Bravo!

Find a bug, 2nd version, left side, no edge case: return; should be continue; line 89

https://gist.github.com/jianminchen/58d80aa86a027af7a3e52277d15c3733

Also, write down tasks before writing code, good habit to train to focus on tasks when writing.

Use node in neighbors to make code more readable.

One algorithm a time. Take your time to master an algorithm.

Everyone asks me what’s next. I’m here to stay, taking it one game at a time.#CreateYourMark pic.twitter.com/CzDq5CIGMA
— Angelique Kerber (@AngeliqueKerber) May 21, 2016

Sunday, March 11, 2018

Leetcode 269: Alien Dictionary

March 11, 2018

Introduction

It is time for me to review graph algorithm called topological sort. Here are a few blogs I documented my practice more than 2 years ago, in 2016.

Course schedule, here is the blog.
Alien dictionary, here is the blog one; here is the second blog.

Algorithm practice

It is so interesting to read the blog I wrote more than 2 years ago. I like to laugh about it, the writing style is kind of different, but I am so glad to know that I can trace what my thought process and learning process after 2 years. It is so sweet to read what I did write and draw. I felt so good to enjoy my own work, review the learning process again.

What I like to do is to write a C# version, and also find 3 ideas in discussion panel and write a C# version for each idea.

Also I like to post a question on code review website. I need to learn better this time.

Actionable Item

Plan to review the old algorithm related in Leetcode. Leetcode 133: clone graph, Course Schedule and course schedule II.

May 3, 2018

I had a mock interview with the friend. And he told me to work on the alien dictionary algorithm. I do not need to write the code, but please tell him how to work on the solution.

I remembered that I worked on the algorithm before, a few years ago. And then he asked me what kind of graph algorithm I can apply. I said that it may be topological sorting. It is a graph algorithm. But I do not remember too much detail any more.

Saturday, July 21, 2018

Leetcode 269: Alien Dictionary

July 21, 2018

Introduction

It is time for me to review the algorithm called Alien Dictionary. I do not know what I should do in order to get best benefit, I like to give it 30 minute study.

Alien dictionary

I like to learn something from my favorite blog called brandyang. I created a gist for his blog.

Also I found another better one in Chinese, so I created a gist for myself to study again. Here is the gist.

Wednesday, June 15, 2016

Leetcode 269: Alien Dictionary

June 15, 2016

Leetcode 269 Alien dictionary

Choose to work on a graph problem - using Topological Sorting:

Study C++ solution:
http://www.cnblogs.com/jcliBlogger/p/4758761.html

Discussion about the problem description:
https://leetcode.com/discuss/53997/the-description-is-wrong

Study C++ solution:

https://leetcode.com/discuss/54024/straightforward-c-solution?show=54024#q54024

Java solution to study:

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/269.alien-dictionary.java

http://www.cnblogs.com/yrbbest/p/5023584.html

Julia worked on C# code:
https://gist.github.com/jianminchen/07546625d828f63e762ba03b463fe8aa
line 75, 76, after queue.peek() is called, need to call dequeue. (dead loop)

https://gist.github.com/jianminchen/a49496ea21cadcbdda7c1669216c05a5

Add more comment, where to be careful, to avoid bugs:
https://gist.github.com/jianminchen/47f516b54686080c3a68bc8c3f1d04cb

More comment, variable name refactor:
https://gist.github.com/jianminchen/85129ed50ce597f896b0f0c5a2fa5586

Read blogs:
http://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/

Comparison between 2 versions:
variable name change: graph -> dependencyList, more meaningful. The graph has nodes, dependency list, inDegree array.

Change function name: getCharSet -> getNodes

Love those comment, so helpful to get start to coding...

Left side first implementation:

for(int j=0; j < shortLength; j++)

{

...

break;

}

confusing, not very easy to follow. line 154 - line 176, 22 lines of code. The big scope to handle.

Also, this for loop is nested loop, too many lines of code inside.

Replacement of while loop is short, only 3 lines of code.

graphSetup -> what we can tell here? ... later!

Question and answer:
1. Can you work on a simple example to explain the idea of your solution?

Here is the warm up for topological sorting using two strings {"wrt","wrf"}:

Review previous blog:

http://juliachencoding.blogspot.ca/2016/04/leetcode-208-course-schedule.html

Warmup practice:
statistics: 1 bug, more than 60 minute to write. Totally new program
https://gist.github.com/jianminchen/58d80aa86a027af7a3e52277d15c3733
a few changes to highlight:
1. line 24 - 26 add comment what to do about graph
2. line 49 - 65 motivation talk - help to design the function
using the graph above {"wrt","wrf"}, help to write code
3. line 72 - 74 special case words length is 1
4. line 81 - line 85 use one pointer to slide forward <- more flat code
5. line 87 add comment - no edge -> very good comment
6. line 91 - 94 first writing with a bug - prev, curr, but prev twice

Here is the comparison file:
https://github.com/jianminchen/Leetcode_C-/blob/master/Leetcode269FirstAndSecondPractice.pdf

Statistics:
time spent: 3hours +

I don't feel fear when I am on court. That's where I feel at home #CreateYourMark #RG16 @adidastennis @adidasFR pic.twitter.com/ZVNcZvWZE0
— Kristina Mladenovic (@KikiMladenovic) May 20, 2016

Saturday, June 11, 2016

Algorithms to study

June 11, 2016

Prepare to write some code. Find algorithms to work on.

1. Leetcode 76: Minimum Window Substring
Study the code:
http://blog.csdn.net/sunnyyoona/article/details/43925035

2. Leetcode 91: Decode the ways
https://github.com/jianminchen/puzzles/blob/master/decode_ways.cc

2D. Leetcode 128: Longest Consecutive Sequence in Array

2E. Leetcode 139, 140, Word break

2F. Leetcode 150 Evaluate Reverse Polish Notation

3A. Leetcode 289: Game of Life
3B. Leetcode 298: Longest Consecutive Sequence in BT

4. LeetCode 351 - Android Unlock Patterns

Study the code:
http://massivealgorithms.blogspot.ca/2016/06/leetcode-351-android-unlock-patterns.html

5. Read project Euler website:

https://projecteuler.net/archives

6. Strobogrammatic number I, II, III (246, 247, 248)

Study code:
http://buttercola.blogspot.ca/2015/08/leetcode-strobogrammatic-number.html

https://tonycao.gitbooks.io/leetcode-locked/content/LeetCode%20Locked/c1.5.html

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/246.strobogrammatic-number.java

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/247.strobogrammatic-number-ii.java

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/248.strobogrammatic-number-iii.java

7. One minute call 60 times at most

Leaky bucket algorithm
https://en.wikipedia.org/wiki/Leaky_bucket

8. Stock Maximization
https://www.hackerrank.com/challenges/stockmax

9.

http://www.careercup.com/question?id=5840928073842688

11. Leetcode: shortest word distance I, II, III
https://segmentfault.com/a/1190000003906667

study Leetcode solution:
https://github.com/MaskRay/LeetCode

12. Leetcode 53: Maximum Subarray
https://github.com/jianminchen/Leetcode_C-/blob/master/53MaximumSubArray1.cs
https://github.com/jianminchen/Leetcode_C-/blob/master/53MaximumSubArray2.cs

http://juliachencoding.blogspot.ca/2015/07/dp-problem-kadanes-algorithm-maximum.html

13. Leetcode 352 - Data Stream as Disjoint Intervals (Hard - 34% passing rate)
http://www.cnblogs.com/grandyang/p/5548284.html

14. Leetcode 174 Dungeon game

15. Leetcode 247 H-index

16. Leetcode 269 Alien dictionary

17. Leetcode 142 Linked List Cycle II

17B. Leetcode 286 Walls and Gates

18. Leetcode 329 Longest increasing path in matrix
19. Leetcode 345 Reverse Vowels of a string
20. Leetcode 354 Russian Doll Envelopes

Flatten Linked List
http://www.geeksforgeeks.org/flattening-a-linked-list/

Blogs: Learn system design:
https://www.quora.com/How-should-I-prepare-for-my-Google-interview-if-I-have-1-month-left

80 questions to think about:
https://www.educative.io/collection/5642554087309312/5679846214598656

有O(N*M)的算法，思路是转换成直方图然后维护一个栈。

一个矩阵里，里面元素是0或者1，要你找一个面积最大的全1的子矩阵。

如果不要求是矩形只要求是一块任意形状的区域的话，可以使用FloodFill,O(N*M). 然后这里是矩阵，然后我们转换。

brute force:

枚举左上和右下两个点，然后判断是否全1，这样是 O(N*N*M*M)的算法，因为判断是否全1可以用sum数组来减一下，O(1)就够了。
(detail discussion: https://zhuanlan.zhihu.com/p/19873823?refer=qinchao)

http://poj.org/problem?id=3494
FloodFill
https://en.wikipedia.org/wiki/Flood_fill

blog:
Leetcode 269
C++ solution:
http://www.cnblogs.com/jcliBlogger/p/4758761.html

Discussion about the problem description:
https://leetcode.com/discuss/53997/the-description-is-wrong

C++ solution:

https://leetcode.com/discuss/54024/straightforward-c-solution?show=54024#q54024

Java solution to study:

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/269.alien-dictionary.java

http://www.cnblogs.com/yrbbest/p/5023584.html

study C# code:
https://gist.github.com/jianminchen/07546625d828f63e762ba03b463fe8aa

Leetcode 329:
http://gaocegege.com/Blog/algorithm/leetcode329

http://blog.csdn.net/sbitswc/article/details/50707203

http://basics.sjtu.edu.cn/~xiaojuan/algo16/

June 20, C# practice:
https://gist.github.com/jianminchen/b984ccba8dabbb0bb78160c6e5c6e8b4

Sunday, February 13, 2022

【干货】刷题这样上手面试必备的10个算法 | LeetCode清单 | 100小时+刷题经验分享 [上]

Feb. 13, 2022

Here is the link.

做这个视频距离我上次刷题已经快两年了我也是学了就忘那种所以总结复习和写文案都花了10个小时以上的时间而且融合了我上百小时的刷题心血！！而且我也不是擅长给讲题的那种所以拍下来真的好累啊感觉好多东西我也不知道我有没有说清楚哈哈哈哈反正我脑汁已经没了希望大家一定要点赞订阅！！祝大家刷题加油找工作顺利都能拿到自己心仪的offer！ ================================================== 以下是我说的 10 个算法和数据结构和他们的 Leet Code 经典题！功课都给你总结好了还不来抄！ 1. Recursion / Backtracking a. 39. Combination Sum https://leetcode.com/problems/combina... b. 40. Combination Sum II https://leetcode.com/problems/combina... c. 78. Subsets https://leetcode.com/problems/subsets/ d. 90. Subsets II https://leetcode.com/problems/subsets... e. 46. Permutations https://leetcode.com/problems/permuta... f. 47. Permutations II https://leetcode.com/problems/permuta... 2. Graph Traversal - DFS, BFS, Topological Sorting a. 133. Clone Graph https://leetcode.com/problems/clone-g... BFS / DFS b. 127. Word Ladder https://leetcode.com/problems/word-la... BFS c. 490. The Maze https://leetcode.com/problems/the-maze/ d. 210. Course Schedule II https://leetcode.com/problems/course-... (Topological Sorting) e. 269. Alien Dictionary https://leetcode.com/problems/alien-d... (Topological Sorting) 3. Binary Tree / Binary Search Tree (BST) a. 94. Binary Tree Inorder Traversal https://leetcode.com/problems/binary-... b. 236. Lowest Common Ancestor of a Binary Tree https://leetcode.com/problems/lowest-... c. 297. Serialize and Deserialize Binary Tree https://leetcode.com/problems/seriali... d. 98. Validate Binary Search Tree https://leetcode.com/problems/validat... e. 102. Binary Tree Level Order Traversal https://leetcode.com/problems/binary-... (BFS) 4. Binary Search a. 34. Find First and Last Position of Element in Sorted Array https://leetcode.com/problems/find-fi... b. 162. Find Peak Element https://leetcode.com/problems/find-pe... c. 69. Sqrt(x) https://leetcode.com/problems/sqrtx/ 5. Data Structure a. 242. Valid Anagram https://leetcode.com/problems/valid-a... (Hash Table) b. 133. Clone Graph https://leetcode.com/problems/clone-g... (Hash Table) c. 127. Word Ladder https://leetcode.com/problems/word-la... (Hash Table) d. 155. Min Stack https://leetcode.com/problems/min-stack/ (Stack) e. 225. Implement Stack using Queues https://leetcode.com/problems/impleme... (Stack / Queue) f. 215. Kth Largest Element in an Array https://leetcode.com/problems/kth-lar... (PriorityQueue) g. 23. Merge k Sorted Lists https://leetcode.com/problems/merge-k... (PriorityQueue) 6. Linked List Manipulation a. 237. Delete Node in a Linked List https://leetcode.com/problems/delete-... b. 92. Reverse Linked List II https://leetcode.com/problems/reverse... c. 876. Middle of the Linked List https://leetcode.com/problems/middle-... d. 143. Reorder List https://leetcode.com/problems/reorder...

Saturday, July 13, 2019

269 Alien dictionary

It is a hard level locked algorithm on Leetcode.com. I plan to study the algorithm on this web page.

Friday, April 26, 2019

Case study: online code assessment preparation

April 26, 2019

Introduction

It is so challenging for me to prepare online code assessment. I have to push myself hard to prepare, one idea is to work on mock interview on Leetcode.com.

My preparation

Here are the algorithms I worked on from April 18 to April 22, 2019. I worked on a few random set algorithms, one mock interview I solved two algorithm, second one I did not solve any of those two. I was so surprised to learn the fact that I need to work hard and quickly master those basic algorithms again.

I chose to use those mock interview algorithms to test my problem solving status. I had chance to use those 38 algorithms to help me prepare for online assessment.

Total random set number is 28. I exhausted all random set algorithm in the first two categories, online assessment and phone interview.

13 easy 22 medium 3 hard

Easy level

20. Valid Parentheses

66. Plus One

101. Symmetric Tree

125. Valid Palindrome

155. Min Stack

160. Intersection of Two Linked Lists

171. Excel Sheet Column Number

206. Reverse Linked List

242. Valid Anagram

387. First Unique Character in a String

680. Valid Palindrome II

953. Verifying an Alien Dictionary

977. Squares of a Sorted Array

Medium level

15. 3Sum

17. Letter Combinations of a Phone Number

31. Next Permutation

33. Search in Rotated Sorted Array

43. Multiply Strings

49. Group Anagrams

56. Merge Intervals

75. Sort Colors

79. Word Search

102. Binary Tree Level Order Traversal

139. Word Break

165. Compare Version Numbers

199. Binary Tree Right Side View

223. Rectangle Area

235. Lowest Common Ancestor of a Binary Search Tree

322. Coin Change

402. Remove K Digits

540. Single Element in a Sorted Array

567. Permutation in String

791. Custom Sort String

833. Find And Replace in String

909. Snakes and Ladders

Hard level

140. Word Break II

282. Expression Add Operators

895. Maximum Frequency Stack

Actionable Items

In order to prepare Microsoft online code assessment on April 23, I went over over 20 random set mock interview algorithms on Leetcode.com. I stuck on a few algorithms, easy medium and hard level.

The preparation is also helpful for me to improve my weekly contest performance.

I do not have time to write code for every algorithm. I just choose to spend 5 to 10 minutes and see if I can come out the idea how to solve the problem. And then I terminate the interview and quickly look up the algorithm and solution on Leetcode.com

I put together a github page called online assessment preparation.

Here are the random set with algorithms I worked on.

I use over 15 set algorithms to prepare myself to work on various algorithms.

Wednesday, October 21, 2020

Hard level algorithms - six hard level algorithms

Hard level algorithms:

630 course schedule
269 Alien dictionary
759 Employee free time
632 smallest range covering elements from k lists
sequence reconstruction

I plan to work on those 5 hard level algorithms in next few days.

Thursday, May 3, 2018

Leetcode 269: Alien dictionary

May 3, 2018

Introduction

Plan to spend time to review the algorithm again. I like to make the algorithm my favorite graph algorithm in May, 2018.

I know that it takes a lot of sacrifice from a friend who coached me through mock interview, how to pay attention to detail. I like to write the blog to express my thankfulness to those people. Like my hitting partner on tennis court, those algorithm practice trains me to think harder, work harder.

One day I wish I can use my mathematics training over years and be able to use some of them in the work. First I have to learn how to be a good software programmer first, my crafting skills has to be improved first.

Learn how to talk in Chinese about the algorithm

It is interesting to learn how to express the algorithm in Chinese first. I did 10 minutes study and made a gist based one a blog. Here is the gist. The algorithm with some improvement is here.

Plan to write a C# solution based on the above Java code.

Past practice

Here is my past practice. I need to warm up and write a solution. It is such great warmup to review code written more than 2 years ago, here is code I reviewed and wrote this time.

Thursday, March 10, 2022

Topic wise problems for Beginners

Last Edit: February 3, 2021 3:06 PM

Here is the link. Leetcode profile is here.

39.0K VIEWS

I have started my Leetcode journey from 3 months, and I have solved few problems along the way. I had to manage my college courses and prepping up Algorithms and Data Structures, so I wasn't able to grind as much problems as I would have liked to.

Prepping up Data Structures and Algorithms

I used another platform for reviewing basic data structures and algorithms. I never really prepared algorithms seriously, so I decided to review all basic algorithms and ds. I started coding basic data structures and reviewed basic algorithm paradigms and solved first 7-10 problems from each topic. This helped me in warming up with the topic and I was aware of basic tricks associated with basic problems.

Learning Collections / STL library

Start learning STL/Collections library if you haven't heard of it. Even though we can code up basic sorting, simple data structures such as stack/queue, we don't always have to code them while solving problems, we can always use them to fast track solving problems, so we can spend time in solving our problem, rather than coding the repititive algorithms and data structures.
More Info.

List of Problems topic wise

Finally, here is a list of problems that I solved topic wise and wasn't able to solve them in the first chance. I used solutions / discuss to check the approach of solving problems. Few are some which are worth revisiting. Finally, I have solved around 137 problems, so that should suffice for a beginner to onboard with the process of leetcode grind.