Leetcode 18: 4 Sum

May 17, 2016

Introduction

Julia likes to write some code after she reads the blog:

http://www.cnblogs.com/TenosDoIt/p/3649607.html

Write her own practice using C#. 

Will come back. 

January 31, 2017

Study C++ code first. 

Code review study here. 

Follow up

Dec. 29, 2017

It feels good to read the blog written 18 months ago. At that time, I was shy and do not write too much how I feel to learn 4 sum algorithm. At that time, I do not know that I can use Leetcode 18 discussion to find all the solutions. It is so interesting to know the person who I was 18 months ago. The code I liked at that time usually is searched from Google.

I like to review the blog written by TenosDolt, and then copy and paste the analysis of Leetcode 18: 4 Sum in Chinese here.

算法 2： 
O(n²)的算法，和前面相当，都是先对数组排序。

哈希map预处理

我们先枚举出所有二个数的和存放在哈希map中，其中map的key对应的是二个数的和，因为多对元素求和可能是相同的值，故哈希map的value是一个链表(下面的代码中用数组代替)，链表每个节点存的是这两个数在数组的下标；这个预处理的时间复杂度是O(n²

枚举第一个和第二个元素方法

接着和算法1类似，枚举第一个和第二个元素，假设分别为v1, v2, 然后在哈希map中查找和为target - v1 - v2的所有二元对（在对应的链表中），查找的时间为O（1），为了保证不重复计算，我们只保留两个数下标都大于 V2 的二元对（其实我们在前面3sum问题中所求得的三个数在排序后的数组中下标都是递增的），即使是这样也有可能重复。

Example study

比如排好序后数组为[-9, -4, -2, 0, 2, 4, 4]，target = 0，当第一个和第二个元素分别是-4，-2时，我们要得到和为0 -(-2) -(-4) = 6的二元对，这样的二元对有两个, 都是(2,4)，且他们在数组中的下标都大于-4和-2，如果都加入结果，则(-4,-2,2,4)会出现两次，因此在加入二元对时，要判断是否和已经加入的二元对重复. 

由于过早二元对之前数组已经排过序，所以两个元素都相同的二元对可以保证在链表中是相邻的，链表不会出现(2,4)->(1,5)->(2,4)的情况，因此只要判断新加入的二元对和上一个加入的二元对是否重复即可.

因为同一个链表中的二元对两个元素的和都是相同的，因此只要二元对的一个元素不同，则这个二元对就不同。我们可以认为哈希map中key对应的链表长度为常数，那么算法总的复杂度为O(n²).

Also, I will study the code written in Java and then write a C# version. First, let me save the java code in a gist first. 

One thing I like to read the blog written by TenosDolt is that he recommended a blog related to K sum algorithm in general.

Leetcode 15: 3 Sum

May 17, 2016

problem statement:

https://leetcode.com/problems/3sum/

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

Julia likes to write some code after she reads the blog:

http://www.cnblogs.com/TenosDoIt/p/3649607.html

Write her own practice using C#: 

https://gist.github.com/jianminchen/9ca3f9982c1011ed4a658f83ca203549

https://github.com/jianminchen/Leetcode_C-/blob/master/15_3Sum.cs

Pass Leetcode online Judge

Line 62, Change the variable name from newTarget to twoSumTarget, since newTarget is not so clear, confusing. 

https://gist.github.com/jianminchen/61c848a30b1e10364359d2d73c0338fe

Question and Answer:

1. How is your practice?

Answer: Julia tried to practice guidelines from "Clean Code", she learned a few things:
name a list variable to avoid using "list", HashSet variable does not call "set", force her to think about meaningful name. 
For example, line 47 - keys, variable is declared as HashSet<string>. 

 1.  She tried to put "two sum target" function (line 62 - line 103) as a while loop instead of standalone function; 

 2.  Confused with target - 3 sum target with 2 sum target, two variables - naming change:

     newTarget -> twoSumTarget (line 62)

 3. 3 variables are replaced by an array: line 58, trialTriplet

 4. line 71 twoSumValue variable is named to explicitly tell the sum of 2 values, not 3 values.

2. Fun time?

2.1 Julia spent more than 45 minutes to go over C# Array class and all API,

Array.Sum(), use C# Array.Sum() instead of writing yourself.

2.2. 3 variables related to target value, 

target, twoSumTarget, twoSumValue

Good time to read the blog: (10 - 20 minutes)

http://www.sigmainfy.com/blog/summary-of-ksum-problems.html

3. Can you improve the code to get rid of using HashSet to check duplicate? 
Answer: 
Read the blog: 
http://fisherlei.blogspot.ca/2013/01/leetcode-3-sum-solution.html 

line 21, 22: quick solution to avoid duplicate set: 

while(start<end && num[start] == num[start-1]) start++;   

while(start<end && num[end] == num[end+1]) end--; 

System Design

May 17, 2016

System Design:

http://blog.gainlo.co/index.php/category/system-design-interview-questions/

tiny URL system design:
http://blog.gainlo.co/index.php/2016/03/08/system-design-interview-question-create-tinyurl-system/

Amazon dynamo: 
http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

Julia loves this article talking about cache system design; once she does some code review on basic LRU, she starts to enjoy the computer science, she just loves the engineering, good ideas to solve problems.

http://goo.gl/pL5ee4

classical reader/ writer problem / lock / multiple shards/ commit logs/ memcached

Reference:
1. LRU - C# practice

http://juliachencoding.blogspot.ca/2016/04/leetcode-146-lru-cache_26.html 

Leetcode 16 - 3 sum closest

May 17, 2016

Julia likes to write some code after she reads the blog:

http://www.cnblogs.com/TenosDoIt/p/3649607.html

Write C# practice on Leetcode 16 - 3 sum closest solution:

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

First practice on Leetcode 16 - 3 sum closest solution on 

https://github.com/jianminchen/Leetcode_C-/blob/master/3sumCloset.cs

Previous blog:

http://juliachencoding.blogspot.ca/2016/01/leetcode-1-15-15-two-sum-3-sum-3-sum.html

Question and Answer:

1. What do you learn through the practice this time?

Julia learns the importance to do static analysis on the code. Do not rush, make sure every variable/ name is making sense, every line of code is best she can present, every executable path should be examined. Every scope of variable is close to minimum as possible. Walk through the examination steps loudly. 

2. What common steps Julia likes to build a ritual after her first writing - C# code - after she failed to present a two sum algorithm on May 4, 2016? 

Answer:

1. Julia likes to examine every line of code, see if she can improve the presentation; 

2. Check every variable, scope, meaningful name

3. Check every executable path, make sure that no bug

4. What test case will be executed on the line. 

5. Avoid early return error, other common errors. 

6. Read the code, speak out what she is doing on reviewing of each line, each variable. Talk about the change she likes to make, thing found needs to be taken care of.   

3. What is most important to solve the problem? 

Using two sum problem solving technique, extend the method to solve the 3 sum closest one. 

The idea is most important and also know how to do time complexity analysis - O(n^2) solution - best one. 

Since O(n^2) is the best time complexity we can solve the problem, sorting takes less than O(n^2); certainly, array can be sorted first. 

So, here is the analysis Julia does for the problem - 3 sum closest. 

Idea:

* 1. Sorting takes O(nlogn) for an array

* 2. And then, choose (i, j, k), assuming i<j<k, iterate on variable i,

*   we need to find two sum problem for each i, new target = target - nums[i]

*   since the array is sorted, two pointer solution can be used. One is the beginning

*   of array, another one is the end of the array.

*

*   So, this step 2 process takes O(n^2) time

*

* Overall, the algorithm will take O(n^2) time complexity

*

*

*   read the C# Array API - 10 minutes

*   https://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx

Human resource analytical articles

May 17, 2016

As a software programmer, Julia likes every effort she put in to help her grow, and also every company she had chance to explore, get educated by reading, talking.

One of her interest is about human resource analytics. Her favorite reading blogs.

One of articles - plotting your career path.

She likes to explore more in the city of Vancouver.

web technology - a short research in Vancouver technology industry

May 16, 2016

  As a software programmer, Julia noticed that she was out of date from 2010 - 2015. She started to do a little research here and there, try to catch up small details. 10 - 20 minutes a time,  "What is hot in Vancouver area - IT skills".

  Starting from August 2015, she started to learn OO principle: S.O.L.I.D.. She came cross the topic by a small talk with a manager from Microsoft in 2015. She started to follow the principles and write a lot of small classes and functions. She also feels less stressful to handle frequent code change in live website.

  She noticed that in the city of Vancouver, the principle is also very popular this year 2016.

 1.  Hootsuite - May 16 - 2016  Junior Software Developer

• Automated testing using tools like Casper.js, Nightwatch.js or Selenium
• Javascript, CSS & HTML
• JS libraries and frameworks like jQuery, Backbone, Angular, React, Underscore
• CSS pre-processor(s) like Sass, Less, etc...
• PHP
• Using relational (MySQL) or NoSQL (Mongo) data stores
• Working with REST APIs
• Agile philosophies and continuous delivery

 Julia, you are learning MVC, Angular JS, also, check out REST APIs. 

 2. Simba - May 16, 2016 Senior C++ software developer 
 superlative code, top quality code reviews, and comprehensive automated tests. 
 BI tools: Tableau, Microsoft power BI and Lumira  - Limira? 
 using C++ memory management and performance analysis tools - what tools? Google it!
 Visual Studio and Xcode - (Julia's comment: Xcode? )
 3+ years of C++, STL, smart pointers, RAII, and concurrent (multi-threaded) programming

3. Global Relay - automation developer 
 Automated testing frameworks
 REST and JSON
 GIT and SVN
 Scrum and Kanban
 Build tools: Maven 
 Continuous integration system: Bamboo 
 Network protocols: HTTP, TLS and TCP
 Jbehave and Selenium Web Driver 
 Thrift API
Julia, can you name 2 service oriented architectures? REST and JSON

Connect nodes at the same level in a binary tree

May 16, 2016 

Connect nodes at the same level in a binary tree  

http://www.geeksforgeeks.org/connect-nodes-at-same-level/   (? bug)

better one:
http://javabypatel.blogspot.ca/2015/08/connect-nodes-at-same-level-in-binary-tree-using-constant-extra-space.html

Using Queue - 
http://javabypatel.blogspot.ca/2015/08/connect-nodes-at-same-level-in-binary-tree.html

Question and answer:

1. How long do you study the problem? What do you learn? 

Julia spent more than 1 hour to study the blogs above. She will write down her own notes about the test case, analysis and solution, and post them in the blog. Encourage herself to write, to share and to improve her confidence on problem solving. 

Will come back soon. 

Leetcode 215: Find kth largest element in the array

May 15, 2016

 Problem statement:
 https://leetcode.com/problems/kth-largest-element-in-an-array/

 Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

 Read some blogs about this problem:

 http://www.jianshu.com/p/f52a88550588

 Julia likes to spend 10 - 20 minutes to review "Quick Select" - the idea, similar to Quick Sort, most important part is to partition.

 Time complexity: O(nlogn) in quicksort, but O(n) in quick select.

 1. Quick sort: Time complexity: O(nlogn)

 2. Use Heap sort, O(klogN)
Java Solution, using priority queue, code to study:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/215.kth-largest-element-in-an-array.java

Spend 20 minutes to read the blog:  4:23pm - 4:43 pm
1. http://www.cnblogs.com/yuzhangcmu/p/4164807.html

2. https://en.wikipedia.org/wiki/Introselect (read 10 minutes - 4:30pm - 4:40pm)

3. http://stackoverflow.com/questions/7559608/median-of-three-values-strategy

4. http://www.quora.com/What-is-the-most-efficient-algorithm-to-find-the-kth-smallest-element-in-an-array-having-n-elements

5. http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/ (4:50pm - 5:20pm)

30 minutes to review the solutions, write down short notes:
6 methods:
1. Use bubble k times - O(nk)
Modify bubble sort to run the outer loop at most k times
Like bubble sort, other sorting algorithms like selection sort can also be modified to get the k largest element.

2. Use temporary array
Time complexity: O((n-k)*k)

3. Use sorting
1. Sort the elements in descending order in O(nlogn)
4. Print the first k numbers of the sorted array O(k)
Time complexity: O(nlogn)

4. Use Max Heap
1. Build a Max Heap tree in O(n)
2. Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)
Time complexity: O(n+klogn)

5. Use order statistics:
1) use order statistics algorithm to find the kth largest element.
Julia, take some time to review the article: see the topic selection in worst-case linear time O(n). (10 - 15 minutes)
Write down main ideas using your own words:
Use a deterministic algorithm that runs in O(n) in the worst case.

2)

Leetcode 4: Median of two sorted array - a warmup practice

May 15, 2015

Review the leetcode 4: Median of two sorted array, warm up the algorithm.

Here is the last practice:

https://github.com/jianminchen/Leetcode_C-/blob/master/4MedianOfTwoSortedArrays.cs

Step 1: 
Read the last practice 10 - 20 minutes on May 15, 2016
-- write down the ideas: 
1. Brute force solution: O(nlogn)
2. Linear solution: O(n) 

3. Transform to the kth element problem first, and then: 
Try to get rid of k/2 elements once, so the algorithm will go to logk, k = (m+n)/2 

Some analysis and reasoning: 
Assuming that A and B both arrays are with length > k/2, and then, compare A[k/2-1] and B[k/2-1]. 

Read the blog again:
http://blog.csdn.net/yutianzuijin/article/details/11499917

http://blog.csdn.net/zxzxy1988/article/details/8587244

Step 2: 
Spend 30 minutes to read and then write some code. 

Related to Leetcode 215: Find kth largest element in the array. 


Question and Answer:

1. Write down what you learn through this practice.
Answer: The algorithm is very well defined, is a special case of find kth element in two sorted arrays.

2. Algorithms learning and important thing to learn:

Answer:
1. Always know how to solve the problem using naive solution, brute force one first.

O(nlogn) -> O(n) -> O(log(m+n)/2)

2. And then, discuss the improvement.

Roger Federer's Top 10 Rules For Success

May 14, 2016

  Julia had some bad behavior one time on tennis court in 2014, she hit the tennis racket on the net when she made the mistake on the court. The opponent told her that it was just a game, relax and enjoy it. Now, she is getting better, she learnes to celebrate when she wins a point instead of showing disappointment when she loses a point. Power fist is her favorite.

 https://www.youtube.com/watch?v=rAdn_JGq5bQ

1. Question yourself

2. Work on your strengths

3. Enjoy what you're doing

4. Have structured goals
Short term goal
Long term goal - without goal and target, cannot compete totally.
Do it the Roger Federer Way

Question yourself.

5. Build a great team
Have a team, good friends around you. Some people question me, really care about me.

6. Be prepared

7. Learn from your mistakes
Do not smash rackets, do not complain. No more commentary on his own points. Mental focus.

8. Separate work from life

9. Chase your dreams

10. Have fun

Roger Federer CNN Talk Asia 2013 Interview Part 1

https://www.youtube.com/watch?v=ixesWSqfJx0&feature=youtu.be

"Enjoy yourself. Train hard, no regrets, all I can do is to do my best. No matter the outcome. Be honest. Losing is fine. Everything about win is a bonus."

Les Brown's motivation talk

May 14, 2016

 Julia likes the motivation speech and she found a favorite talk. She likes the talk from Les Brown.

 Let Julia start to write this blog using one of sentences in the talk:

 "Some people know what is happening, some people make things happen, some people do not know what is happening."

Julia likes to make things happen, work on building confidence, and she thinks that Les Brown can be a great motivation for her.

  https://www.youtube.com/watch?v=5zEJGsvXhxg

 1. Believe in yourself

 2. Amaze your customers

 3. Take full responsibility for your life

 4. Stand up to yourself

 5. Go all out
 Mind likes garden. Weeds can grow everywhere, but exotic flower has to be grown in certain conditions.

 6. Stay busy
Sometimes life is in slump, continue to execute, stay busy.

 7. Give more than you are paid for
Courage to work on - Start to work early - Develop a habit to work for more than you are paid for.

Work on the path and leave a trail.

8. Someone's opinion is not your reality

9. You are different

10. Don't stop running towards your dream

Top 10 strategies Work Hard for Entrepreneurs

May 14, 2016

 Watch the video:
 https://www.youtube.com/watch?v=pkH5EwEI_LU

 Here are some notes about work hard:
1. Donald Trump: He heard the meaningful way  from golf player: about work hard and luck.

Great golf player: Gary player, "The hard you work, the lucky you get.", all I have to know that I am working very hard, the hard you work, the lucky you get.

2. Bill Gates:   2 weeks in a year, work and think: think week. Think about things, reading book, do we have right priorities.

3. Oprah: Talk to girls, real work: Figure out where your power bases. Alignment of personality, gifts you have to give, work on yourself. Fulfill self up, keep your cup full.

    Do not afraid. Embrace the full of yourself. Honor yourself.

4. Sean Combs (American Rapper): Hard work

5. Jason Calacanis (Internet entrepreneur and blogger): Work 3 jobs to go to college, father did not pay tax, and then restaurant was taken.

6. Elon Musk: work on super hard. 7 days a week, programming all the time. Every waking hour. 50 hours/ week, you work 100 hours/ week.

7. Derek Jeter (baseball shortstop): never satisfied. Some one is better. You have to work hard than other people.

8. Grant Cardone: work ethics so high, unbelievable, know you work hard, therefore, you can be top 10 - 20%.
People know you because you have a good ethnics - He works, he produces, vibrate the level, tremendous work ethnics.
Ask you a question:
"Do people know you because of your unbelievable work ethics?" If you have to get top 10 percent.

How good your skills are. Discipline yourself even if you have billionaire dollars.

American way - work ethics.

9. Alex Morgan (soccer player): practice more than your opponent and teammate, mental prepare every day,  not sucking off, put a lot of hours. No secret why you are succeed.

10. Cristiano Ronaldo (football player): You have to work. Work every day.
Put in mind, body can be improved. Work, is Part of me, not the attitude of "I have to do the work". As an athlete, small detail like drills, conditioning helps.

Some algorithms to study

May 13, 2016

Introduction

Here are some algorithm problems Julia likes to review, what she did is to spend 2 hours to go over Glassdoor.com and go over the interview questions on companies (A, F, L, M, G) from 2016 backward to January 2015.

As a software programmer, Julia knows the value of good thinker in algorithm, problem solving; and write readable, clean code to implement the idea using Java, C++, C#, JavaScript, learn through simple problem solving every day.

Algorithms to review

Put problems in the groups to help study:

Array:

1. Leetcode 23 - Merge K sorted array 

http://www.geeksforgeeks.org/merge-k-sorted-arrays/

-- read stack, queue, priority queue - definition - May 13, 2016

https://msdn.microsoft.com/en-us/library/4ef4dae9.aspx

read through priority queue API document, and understand more if I can.

2. Leetcode 215: Find the kth largest element in an array
http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

Tree problems:

1. Check if given binary tree is a mirror.  

2. Serialize and deserialize the tree

3. Get mirror image of a BST

4. Connect nodes at the same level in a binary tree  

    http://www.geeksforgeeks.org/connect-nodes-at-same-level/   (? bug)
   better one:
http://javabypatel.blogspot.ca/2015/08/connect-nodes-at-same-level-in-binary-tree-using-constant-extra-space.html


Leetcode:

1. Leetcode -- 3 sum 

2. Leetcode 215  - Kth largest elment in the array (quick select)

Linked List:

1. If we have a linked list, and if I give you a number n, then first n node of the linked list should get reversed next n node should as it is, next n should get reversed like wise.

For example, n=3 

String:

1. Given an array of strings,  need to check every string in the array is a palindrome or not.  If it is, we have to print it.  

http://codereview.stackexchange.com/questions/73542/hashtable-implementation

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

2. Write a function to determine the longest palindromic substring of a given string.  

3. Find the minimum number of palindromes in a string. 

Sorting:

1. Write a merge sort 

Hashtable:

1. How do you implement a hash table? 

Dynamic Programming:

1. optimal coins

2. Ladder of height 100, u can use jumps {1,2,3} how many different ways can u reach 100.

DFS/ BFS/ Search:

1. Transform a [1,0] matrix grid into matrix grid of manhattan distance between closest 1's  

2. Given a certain number of tasks with specific start and end times, find the maximum number of jobs that can be 

done   

Misc:

1. Check whether rectangle overlap

2. Reverse a matrix in a given sequence

http://iwillgetthatjobatgoogle.tumblr.com/post/11352414963/implement-a-hash-table

3. There is a 9 digit number, you need to rearrange the number and make just bigger number then this one

    pivot element - google to find a solution

4. There are 9 buckets,Each bucket contains some chocolates(number of chocolates labeled on the bucket), a kid is there, He takes 1 second to eat all the chocolates of 1 bucket and as puts the bucket back, bucket gets filled again with the half chocolate then the original bucket had. kid has n second, find a way in which he can eat max chocolate in n seconds.

5. Find the next largest number.  

6. Solving the jigsaw puzzle. Input is the pieces of the puzzle and a method taking two pieces as input and returning true if they fit.

Leetcode 17: Phone Number - Practice using DFS/ Stack and BFS/ Queue

May 12, 2016

 Write two more practice using Queue/ BFS and DFS/ stack on this leetcode question:

Using Queue/ BFS
https://gist.github.com/jianminchen/5691a3488a2ef4f0660194502ae15f68

Using Stack/ DFS
https://gist.github.com/jianminchen/872bf70039fa8c61ff208b34a591c8ec

Previous blogs about practice:

April 21, 2016 using recursive function, DFS
http://juliachencoding.blogspot.ca/2016/04/window-sum.html

January 24, 2016 using recursive function, DFS
http://juliachencoding.blogspot.ca/2016/01/leetcode-17-letter-combinations-of.html


Question and Answer:

1. What is the difference using Queue and Stack on space usage?

For example, using Queue/ BFS, source code line:

Line 31: IList<string> list = letterCombination("234"); // test result: "abc", "def", so 3x3 = 9 cases. If the string is "2345678", 7 digits string, then, when first string is added to the list, on line 86, the queue's count is around 3^7 = 9 * 9 * 9 * 3, more than 2000 records in the queue. However, using Stack/ DFS, source code line 31, the string is "2345678", when the first phone number is added to the list, the stack size is around 3*7 = 20, around 20 records in the stack. So, it takes more space to use queue/ BFS on this problem solving, not efficient on space usage.

2. Please look into string, stringBuilder on this problem solving.
Read more blogs on this discussion:

Algorithm: Rotate array by one element

May 11, 2016

Quickly find out the blogs related to "Rotate array by one element", look for optimal solution. Julia, it is not so important to show optimal solution, but  at least, never waste the opportunity to show that you are a hacker, willing to solve any problem.

Anything about rotate two dimensional array:

1.
http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array

2.
https://blogs.msdn.microsoft.com/oldnewthing/20080902-00/?p=21003

3.
http://geekswithblogs.net/cwilliams/archive/2008/06/16/122906.aspx

4. Matrix transpose
https://en.wikipedia.org/wiki/Transpose

Question and answer:
1. How many hours do you spend to work on this problem?
Reading 2 hours +. 

Leetcode 48: rotate image

May 11, 2016

Julia likes to study the algorithm: rotate image

http://fisherlei.blogspot.ca/2013/01/leetcode-rotate-image.html

http://shunrang.blogspot.ca/2015/10/rotate-image-and-spiral-matrix.html

Leetcode 239: sliding window maximum

May 11, 2016

Study two blogs. The first one is written in Chinese, link is here. And the second one is here.

Read the blog, link is here.

Julia, please write down your C# practice:

Question and Answer:
1. How long do you study the problem? What do you learn?

Julia spent over 30 minutes on this question. And she learns that deque is excellent data structure to achieve optimal time complexity and complete the task.

2. Can  you tell the concrete the example and show how to solve the problem?

Just think like a greedy algorithm. Make the special data structure like Java Deque data structure, every node is added to the deque once and also removed once. Keep the deque as small as possible, in other words, if the element cannot be the maximum of sliding window, then it should be removed from deque right away.

So, time complexity is O(N).

Also, make it greedy, inside the deque, all elements are sorted by descending order from left to right.

For example, windows size with 4, [1, 3, -1, 2], no matter what next numbers are, 1 and -1 are never going to be a maximal as the window moving. The queue should like [3,2].

So, to maintain the queue in order.
add node in queue from right side only; but remove nodes from both end, just before a node is added.

3. Time complexity analysis:
For those solutions - you can come out:
A. Use heap, or other solutions, time complexity can up to O(nlogn).
w - window size
n - array size
Building a heap, time complexity O(wlogW)
...
so, if w<<n, close to O(n), but if w = 3/n or 4/n, the running time goes up to O(nlogn).
B. ?

4. Learn Java Dequeue class, and C# linkedList:
   API:

   First:
   getFirst
   RemoveFirst
 
   Last:
   addLast
   getLast
   removeLast

   isEmpty

Leetcode 317 - shortest distance from all building - a warm up practice (Part 3)

May 11, 2016

Julia spent time to rewrite the algorithm on Leetcode 317.

Here is her last practice on January, 2016. The blog is top 3 most visited blog - 138 visit up to May 11, 2016. So, she is encouraged to rewrite the code.

Her practice after 4 months is here.

She likes to do more writing on this algorithm, try to figure out ways to improve the performance.

HackerRank – Connected Cell in a Grid - Warm up with Five Practices (V)

May 11, 2016

Being a software programmer, it is easy to spend hours to read and catch up technologies, work on new algorithm, but no coding, one day, or one week, even half month/ month. 

So, warm up like sports. Julia chose the algorithm - Connected Cell In a Grid to warm up for a few hours. 

Last time, less than 1 month ago, Julia did work on this algorithm – connected cell in a grid. And then, she started to warm up again.

Here is one of blogs last practice on April 16, 2016:

http://juliachencoding.blogspot.ca/2016/04/hackerrank-connected-cell-in-grid.html

Fifth practice, using stack instead of recursive function, implement the DFS algorithm:

https://gist.github.com/jianminchen/11725341e9474e0503950616c9ad1848

Question and Answer:

1. What do you like the approach - using stack, DFS algorithm? 

To write using stack is similar to using queue, but the search is DFS instead of BFS. Julia does not have time to build a test case to compare the order of visited nodes this time.