Leetcode 347: Find k most frequent numbers in the array - C# solution

July 28, 2016

Find k most frequent numbers in the array

Problem:

  // nums = [5, 3, 1, 1, 1, 3, 73, 1]

  // k = 1

  // return [1]

  // k = 2

  // return [1, 3]

  // k = 3

  // return [1, 3, 5]

 C# solution using Dictionary<int,int> and language Integrate Query (LINQ):

First, go through the array once, and keep the count for every distinct value:

We can use Language Integrated Query (LINQ) to call order by and then get Top k values.

Write a solution using C# first, post code here.

1. First practice, using LINQ, OrderByDescending, Take

https://gist.github.com/jianminchen/1941a6b82525feefe15a2c477e0a0a0b

LINQ reference:

http://stackoverflow.com/questions/5344805/linq-orderby-descending-query

http://stackoverflow.com/questions/192203/whats-the-linq-to-sql-equivalent-to-top-or-limit-offset

Actionable Item:

Write one solution using bucket sort to get k most frequent numbers in the array. 

Binary Tree Path Sum - two with same value checking

July 28, 2016

Problem:

Write a function that given a tree, returns true if at least 2 paths down the tree have the same sum. A path is a series of nodes from the root to the leaf. 

// ex1:
//     2
//   / \
//   4   5
//  / 
// 1
// returns true // 2+4+1 = 2+5
// ex2:
//     3
//   /
//   4
//  / \
// 1   1
// returns true //3+4+1 = 3+4+1
// ex3:
//   1
//  / \
// 3   4
// returns false // 1+3 != 1+4

Write code for binary tree path sum - two with same value checking:


Julia's first writing using C# language: Code is here. 

checklist of code style and design issues:

C# practice is here. 

2.1. if statement is minimum - avoid using if statement.
 Tips: let it fall through base case.
2.2. code style:
   Readable code
   Clean code
2.3. use LINQ to code select clause like SQL statement
2.4. Avoid early return when the duplicate path sum is added. (line 147 - line 154)
2.5. Let main function to take care of discussion of two path sum with same value  (line 123 - 128)
2.6  It is part of the design, one path sum is added to the dictionary twice; so if there are two path sum with same value, the value of dictionary >=4 instead >=2. 

Questions and answers:
1. Which blogs helps you to shape the idea to solve the problem quickly? 
When Julia worked on lowest common ancestor, she used this blog to write a version as well. 

Lowest common ancestor binary tree on geeksforgeek.org, link is here. 

One of Julia's practice documented in the bog is here. 

2. What is most important lessons learned through the practice?

Julia tried to avoid if statement when she designed the solution. Let base case take care of if statement only. Make the code simple as possible, therefore, design of the recursive function is void. line 143 - 162, function pathSumTracking.

Follow up

June 14, 2017
Write C# code to improve a few things. C# practice code is here.

Work on Leetcode 112 - Path sum.

Lintcode 79: longest common substring

July 26 2016

Work on lintcode: longest common substring.

Problem statement:

Given two strings, find the longest common substring.

Return the length of it.

Note

The characters in substring should occur continiously in original string. This is different with subsequnce.

Algorithm Study

Study the blog - longest common substring (60 minutes reading first time/ 20 minutes review every 6 months) written by a facebook engineer, Ider Zheng. Julia likes the article written in Chinese, it is a well-written and very good thinking process about the problem solving.

Julia likes to repeat the process here in her own words.

1. Brute force solution -> from O(n⁴) to O(n³), great analysis in the above blog:

Good thinking addes value to your coding practice:

Warmup with a brute force solution:

Time complexity - O(n⁴)

For example, a string s1 = "abcdefg",

One way to think about brute force:

The length of string is 7.

How many substring in s1? Guess?

Substring - start position and end position, two variables. Each one has O( n ) choices. Total is O(n²) choices.

More detail, start position can be any i from 0 to 6, and then end position starts from i to n-1. The variation formula, Sum = (n - 1) + ( n - 2) + ... + 1 = (n-1) n / 2, so the total is O(n²);

Try to reduce brute force variation from O(n²) to O(n), instead of letting start position and end position
both varies, just work on start position only.

Small improvement based on brute force solution

Time complexity - O(n³)

Second way to think about using brute force:
The start position of substring is from 0 to n-1, so considering the start position, start a new search.

So, the total of search is O(n).

 Longest common substring - start from start-position, and then  compare both of chars are equal, if yes, continue, record length and compare to maximum length, else then break the search.

1. C++ code:

Code is from the blog written by a facebook engineer.

The time complexity is O( n³ ). There is duplicated calculation.

Will write C# practice very soon.

Dynamic programming - optimal time complexity O(n²)

2. Use Dynamic programming, in the above blog, the analysis is very helpful.

Work on dynamic programming, improve time complexity from O(n⁴) or O(n³) to O(n²), using memorization, space O(n²), bottom up approach.

The idea is to find the formula of DP - dynamic programming.

table T(i, j) - common substrings, using end position as a variable.


one is in s1, ending at position s1[i];
one is in s2, ending at position s2[j].

We know that if T(i, j) >0, then, s1[i] = s2[j];
if(s1[i+1] == s2[j+1]), then, T[i+1, j+1] = T[i,j]+1,
otherwise, T[i+1,j+1] = 0.

Will think about to put together a graph here to explain the idea as well.

2. C++ code:


From blog: C++ code
DP solution, time complexity O(nm), space O(nm)


3. further improvement: C++ code
DP solution, time complexity O(nm), space O(nm) -> O(n+m) -> O(1)
because the recurrence formula tells us that the current position only relies on diagonal position - left-up corner ( i - 1, j - 1)
https://gist.github.com/jianminchen/0061dcf562bd0bdb091301241c38730f

From blog

Julia's practice:
1. brute force solution C#
A. first writing, static analysis catching 1 bug, left 2 bugs for debugging. (not so good!)

B. fix all bugs - final presentation: C#

2. Dynamic programming solution using C#:


Highlights of code writing and execution:

1. static analysis - find bugs
change made: line 56 - 61, if the longest common substring is with length 1 and also start from row 0 or col 0.

line 67 - 72

2. Test case failed on line longestCommonSubstring("abc1def","1ghijkl") - should be "1",

change made: move end1 variable to line 49, and set variable from line 56 - 61, line 67 - line 72

2nd version: add comments


3. DP solution with space reduction: O( nm ) -> O( n+m )  -> O( 1 )

practice later.

* Design issues:
         *
         * 4 variables - memo, longest, end1, searchFirstRowCol
         * 1. memorization using two dimension array - memo
         * 2. variable int longest - get maximum length
         * 3. variable int end1    - string s1 - end position - s1's substring end position
         * 4. variable bool searchFirstRowCol - check first row and first col to update maximum length

DP problems:

Follow up after 8 months

March 17, 2017

1. Read code review on longest common substring algorithm.
2. Read wiki article about "Algorithm Implementation/Strings/Longest common substring"
3. Blog formatting to make it more readable. 
4. Code review:

Ashton and String Hackerrank

Coding practice is like sports - I don't feel fear when I am on court. That's where I feel at home.

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

Factorial - facebook code lab

July 25, 2016

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Example :

n = 5
n! = 120 
Number of trailing zeros = 1
So, return 1

Plan to work on the problem.

Blogs to read:
1. Find maximum length snake sequence:

http://www.geeksforgeeks.org/find-maximum-length-snake-sequence/

2. Root to leaf path sum equal to a given number
http://www.geeksforgeeks.org/root-to-leaf-path-sum-equal-to-a-given-number/

Blog to read:
1. How to construct a blog in 10 minutes? Using github and jekyII?

http://cenalulu.github.io/jekyll/how-to-build-a-blog-using-jekyll-markdown/

2. Buy a domain, buy a Alibaba cloud virtual computer, Nginx + WordPress - set up youownsite.com
http://storypku.com/2014/05/%E5%88%9B%E7%AB%99%E8%AE%B0/

Pascal's triangle - facebook code lab

July 25, 2016

Given numRows, generate the first numRows of Pascal’s triangle.

Pascal’s triangle : To generate A[C] in row R, sum up A’[C] and A’[C-1] from previous row R - 1.

Example:

Given numRows = 5,

Return

[
     [1],
     [1,1],
     [1,2,1],
     [1,3,3,1],
     [1,4,6,4,1]
]

Plan to work on the problem.

Blogs to read:

1. http://cenalulu.github.io/linux/all-about-cpu-cache/

2. http://cenalulu.github.io/mysql/how-i-become-a-facebook-dba/

3. http://cenalulu.github.io/python/online-programming-test/

4. http://cenalulu.github.io/python/euler-project-experience/

substring - facebook code lab - Leetcode 30

July 25, 2016

You are given a string, S, and a list of words, L, that are all of the same length.

Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

Example :

S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Plan to work on the problem

Get Java, C++ code:

1. C++ solution: 
study C++ code:
https://gist.github.com/jianminchen/1eb3d40f6173f07c7db90d39c1c71edf

from blog:
https://yujia.io/blog/2015/11/17/LeetCode-30-Substring-with-Concatenation-of-All-Words/

2. sliding windows method - introduction - great idea - ... 
study Java code:
https://gist.github.com/jianminchen/c1f4d4f0b53cd197e3cfaa968a76f62e

from the blog:  http://yuanhsh.iteye.com/blog/2187543

Review sliding window blog:
http://juliachencoding.blogspot.ca/2015/07/leetcode-longest-substring-without.html

Longest common prefix - LCP - facebook code lab

July 25, 2016

Write a function to find the longest common prefix string amongst an array of strings.

Longest common prefix for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2.

As an example, longest common prefix of "abcdefgh" and "abcefgh" is "abc".

Given the array of strings, you need to find the longest S which is the prefix of ALL the strings in the array.

Example:

Given the array as:

[

  "abcdefgh",

  "aefghijk",

  "abcefgh"
]

The answer would be “a”.

Plan to work on the problem

Blog reading:

1. Talk about CMU computer science - network security course in 2015 - good to know the college - computing teaching
http://article.heron.me/2015/05/cmu-nctu-final.html

course project:
https://github.com/heronyang/youtube_fake_view/blob/master/doc/paper.pdf

2. Four algorithm questions to review
http://codechen.blogspot.ca/search/label/interview

Inspired by the above blog, write code for binary tree path sum - two with same value checking:
https://gist.github.com/jianminchen/b5aa95fb574fcb6f4135f88a4b47d5f8

checklist of code style and design issues:
https://gist.github.com/jianminchen/b5aa95fb574fcb6f4135f88a4b47d5f8
2.1. if statement is minimum - avoid using if statement, tips: let it fall through base case.
2.2. code style:
   Readable code
   Clean code
2.3. use LINQ to code select clause like SQL statement
2.4. Avoid early return when the duplicate path sum is added.
2.5. Let main function to take care of discussion of two path sum with same value

3. Find k most frequent numbers in the array
Problem:
  // nums = [5, 3, 1, 1, 1, 3, 73, 1]
  // k = 1
  // return [1]
 
  // k = 2
  // return [1, 3]
 
  // k = 3

  // return [1, 3, 5]


First, go through the array once, and keep the count for every distinct value:

We can use LINK to call order by and then get Top k values.


But, in the analysis of the top k values in the array -

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


1. sorting the array   O(nlogn)
2. use selection sort O(nk)
3. use sorting
4. use min heap
5. use max heap
6. use temporary array
7. use order statistics

7A. randomized selection algorithm - a dertministic algorithm that runs in O(n) in the worst case

 http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf
1. the idea is to divide n items into n/5 sets (denoting m sets), each contains 5 items. O(n)
2. Find the median of each of the m sets. O(n)
3. Take those m medians and put them in another array.  Use Dselection() to recurisively calculate the median of these medians. Call this x. T(n/5)
4. ...

7B. Use QuickSort partition algorithm to partition around the kth largest number O(n).

7C. Sort the k-1 elements (elements greater than the kth largest element) O(klogk). This step is needed only if sorted output is required.

longest palindrome - facebook code lab

July 25, 2016

Problem statement:

Given a string S, find the longest palindromic substring in S.

Substring of string S:

S[i...j] where 0 <= i <= j < len(S)

Palindrome string:

A string which reads the same backwards. More formally, S is palindrome ifreverse(S) = S.

Incase of conflict, return the substring which occurs first ( with the least starting index ).

Example :

Input : "aaaabaaa"
Output : "aaabaaa"

Plan to work on java coding in short future. 

Hint:
Brute force: 
How many substrings? - start position and end position, O(N^2) variables, and each substring needs one palindrome check, so time complexity is O(N^3). 


Facebook code lab editorial hint: 

A simpler approach, O(N^2) time and O(1) space:

In fact, we could solve it in O(N^2) time without any extra space.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2N-1 such centers.

You might be asking why there are 2N-1 but not N centers?

The reason is that the center of a palindrome can be in between two letters.

Such palindromes have even number of letters (such as “abba”) and their center are between the two ‘b’s.

Since expanding a palindrome around its center could take O(N) time, the overall complexity is O(N^2).

1. first practice:  (in Java)

highlights: 

1. String - compile error: string, Java String class, not string. Different from C#
2. String.substring(int beginIndex, endIndex), endIndex is exclusive <- understand exclusive meaning here: line 66, line 90
3. Java String [] operator - compiler error, using charAt() function
4 . line 33 - 36 bug removal - use extra boolean update, since line 35 - update maxLength, so line 36 update boolean should not be used. Saved status 
5. Two for loops can be merged into one loop 
6. Design concern, use start pos and end pos, substring has O(n^2), but if only consider the center position of palindrome, only O(n) case.

2. 2nd practice - merge two for loops

Blogs to read:

https://segmentfault.com/a/1190000006059081?utm_source=weekly&utm_medium=email&utm_campaign=email_weekly

http://blog.iderzheng.com/coding-is-not-everything/

http://code.iderzheng.com/leetcode/

http://blog.iderzheng.com/i-like-interview/

Excellent analysis - brute force O(n^4) -> O(n^3)

http://blog.iderzheng.com/longest-common-substring-problem-optimization/

Follow up 

January 11, 2017

Longest palindrome string - best review - no raw loop.

Build a palindrome - HackerRank world codesprint #5

July 25, 2016

Read the problem statement more than 30 minutes:

Build a palindrome - problem statement is here. 

Try to come out the idea to solve the problem first. (Advanced problem) - Learning starts from reading the analysis. Prepare for advanced level challenges from HackerRank, one by one.

Read the editorial notes:

editorial notes

Here are a list terms to review:

1. Consider that >= (L+1)/2 characters are present in the first string.

2. string hashing/ a palindromic tree

3. Iterate on each index i of the given string a and consider the longest palindrome starting from i as a part of your solution to find the maximum length possible, L, for string s.

4. Suffix array

5. LCP - largest common prefix array

Required Knowledge: Suffix Array, Palindromic Tree, String Hashing, Implementation

one selected code to study - Just use it as an example to motivate herself to work hard one by one on small topic, and then, one day in the future, build complicated stuff like this challenge. 

C# code to study

Java code to study

C++ code to study

Previous blog about suffix array

Follow up after 6 months

March 26, 2017

Format the style of the blog, clean up web links and make the web links readable.

Balanced forest - HackerRank - world codesprint #5

July 25, 2016

Spent more than 30 minutes to read the problem statement:

https://www.hackerrank.com/contests/world-codesprint-5/challenges/balanced-forest

Try to come out the idea to solve the problem.

Will come back later.