HackerRank: Two string - thinking in Java

March 25, 2016

Read other people's ideas. Understand other people by reading their code. Julia likes to read some Java programming language code for 1-2 hours, she came cross people's code, amazed by ideas from people working in Facebook, Amazon, and amazed that people have GOLD prize on HackerRank.

Julia likes to be able to write very readable, most understandable code with shortest time as possible.

problem statement:

https://www.hackerrank.com/challenges/two-strings

Here are a few Java solution she likes:

Solution 1:
https://gist.github.com/jianminchen/6f029bb909ed7d85c012

Solution 2:
source code reference: 
https://www.hackerrank.com/winger

People like to use bit operation, most likely they are expert and then have some Gold in HackerRank. 

bit operation
https://gist.github.com/jianminchen/3d2acf64725cd73c79db


use one integer to store 26 characters, 1 bit one char from a to z.

private static int f(String a) {
        int r = 0;
        for (char c : a.toCharArray()) {
            r |= 1 << (c - 'a');    // Julia's comment: 1 left shift (c-'a') times 

        }
        return r;
    }

Solution 3:

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

Solution 4:

It is interesting to read InputStream, need to warm up on Java class

https://gist.github.com/jianminchen/21ffc64093fd5952647c

Solution 5:
use HashSet, Set, Character, String classes
https://gist.github.com/jianminchen/1eb02a940f7fa4b6a3f7

Leetcode 33: Search in sorted rotated array

March 23, 2016

understand the algorithm - good analysis graph in the following blog:
http://fisherlei.blogspot.ca/2013/01/leetcode-search-in-rotated-sorted-array.html


using this analysis in the blog:
First, Julia, you have to find out which half is sorted; only one of them;
Second, use sorted half to determine if the search is in the sorted half or not;
Then, you go to sorted half/ unsorted half.

Code can be optimized, if it is in sorted half, then, go to normal binary search
otherwise, go to unsorted - modified binary search - use recursive to write a solution first.

http://bangbingsyb.blogspot.ca/2014/11/leetcode-search-in-rotated-sorted-array.html


Julia, in your practice, you discuss that the middle point is a peak element/ valley element or not; and then, both halves are sorted, which is the special case.

Lesson learned:

1. In your analysis, you have to make the test case as simple as possible, as you see in the above blog:
use 0 -7,
原数组：0 1 2 4 5 6 7
情况1：  6 7 0 1 2 4 5    起始元素0在中间元素的左边
情况2：  2 4 5 6 7 0 1    起始元素0在中间元素的右边

2. And then, you have to be careful, how many cases are then discussed. The above, two cases, using 0 as search element

3. 两种情况都有半边是完全sorted的。根据这半边，当target != A[mid]时，可以分情况判断：
Actually, you should add one more restriction, search half is sorted in ascending order. 

because the half of 6 7 0 1, 6 > 1, in the descending half, it must include going up and then going down. but, 
in the ascending half, 1 2 4 5, just pure ascending. <- you can argue that, it is a fact! 

HackerRank: Two string - thinking in C++ over 15 ways

March 24, 2016

Julia likes to get idea how to write modern C++, she started to read at least 50 C++ solutions a week.

Always look for brilliant ideas to solve a simple problem. Take time to read other people's code, and then, find really excellent ideas.

Algorithm problem solving -> More ideas -> Good thinker -> Confidence.

Julia, think in C++ - solve problems using the following:
1. bit operation
2. array int[26]
3. class set
4. class unordered_set, functions: reserve, insert, count
5. class bitset, size_t
5. cin vs gets, pointer - some calculation

Problem statement is here.


Solution 1:
Here it is, namespace std, >>, string class, set<char>, auto, &x, for(auto &x: A), modern C++ style

C++ code is here. 


Solution 2: using bit operation - beautiful code, genius!
source code reference:

https://problemsolvingnotes.wordpress.com/page/2/
https://www.hackerrank.com/MarioYC
ACM ICPC World Finalist 2012, 2013
count - reference:
http://www.cplusplus.com/reference/algorithm/count/

sync with stdio
http://www.cplusplus.com/reference/ios/ios_base/sync_with_stdio/

using | inclusive OR
http://www.cplusplus.com/doc/tutorial/operators/
solution in C++:
https://gist.github.com/jianminchen/a0724f1fbbe5c621cd63

using namespace std;

int main(){
    ios::sync_with_stdio(0);

    string A,B;

    int T;

    cin >> T;

    int cont[26];

    while(T--){
        cin >> A >> B;    
   
        memset(cont,0,sizeof cont);
   
        for(int i = 0;i < A.size();++i)
            cont[ A[i] - 'a'] |= 1;   // Julia's comment: set first bit as 1, using | - inclusive OR
   
        for(int i = 0;i < B.size();++i)
            cont[ B[i] - 'a'] |= 2;  //  Julia's comment: set second bit as 1, using | - inclusive OR
   
        if(count(cont,cont + 26,3) > 0) cout << "YES\n";
// check array cont - if there is any number is 3, if found, return true
        else cout << "NO\n";
    }

    return 0;
}

Solution 3:
https://gist.github.com/jianminchen/6b443714e61f1c8c1382

Solution 4:
https://gist.github.com/jianminchen/dcfc885d390939a08ae2

Solution 5:
https://gist.github.com/jianminchen/13c2d3832f1cbd53433c

Solution 6: set class, insert, find, end functions
read set class end function:
http://www.cplusplus.com/reference/set/set/find/
set class insert function:
http://www.cplusplus.com/reference/set/set/insert/

https://gist.github.com/jianminchen/1fd8c8e9acdc72f18d10

Solution 7:
https://gist.github.com/jianminchen/f4b6dcea9936347192e9

Solution 8: unordered_set class, reserved function, insert, count function
unordered_set class reserve function:  http://www.cplusplus.com/reference/unordered_set/unordered_set/reserve/

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

Solution 9: cin vs gets, scanf, pointer - calculation
warm up with some concepts:
C++ gets:
http://www.cplusplus.com/reference/cstdio/gets/

compare two solutions - difference
https://gist.github.com/jianminchen/f35171b0c2ddcd403c2b

code is better! - https://www.hackerrank.com/avolchek 24 Gold
https://gist.github.com/jianminchen/d9c0d7a25ca2e24ca17b

Solution 11:
warm up with std::fill function template:
http://www.cplusplus.com/reference/algorithm/fill/
very strong C++ coder:
https://www.hackerrank.com/Informatimukas
https://gist.github.com/jianminchen/ff3fd27b8c1245322adf

Solution 12: bitset, size_t
https://gist.github.com/jianminchen/765ba74888057b887cac

Solution 13: vector class template
https://gist.github.com/jianminchen/c0e3a44edc31b3804331

Solution 14: 
very readable - two functions
https://gist.github.com/jianminchen/43f23e82ee04076c7496

Pluralsight: C++ Advanced Topics

March 23, 2016

Pluralsight:
C++ Adavanced Topics
https://www.pluralsight.com/courses/adv-cpp

Avoid Manual Memory Management
Use Lambdas
Use Standard Containers
Use Standard Algorithms
Embrace Move Semantics
Follow Style Rules
Consider the Plmpl Idiom
Stop Writing C with Classes

Julia is still trying to figure out ways to know best teachers in C++/ C#. Where to find them? Julia, stay focus, find several articles from stackOverFlow about C++, related to Lambdas, Move semantics, have some serious reading, then, come back to the video.

Watch some videos:
https://www.youtube.com/playlist?list=PL_AKIMJc4roXG7rOmqsb_wDG1btCzhS8F

Pluralsight: C++ Core Guidelines and the Guideline Support Library

March 23, 2016 - 2 hours course

First Look: C++ Core Guidelines and the Guideline Support Library


Two hours lecture:
Great talk with code example:  "express the intent", "const", "null"

Tips Julia likes:
Install Nuget:
C++ Core Checker
https://www.nuget.org/packages/Microsoft.CppCoreCheck/

code analysis: <- check warnings
Extra Clang Tools 3.8 documentation
http://clang.llvm.org/extra/clang-tidy/checks/list.html
clang-Tidy Checks

Most guidelines can't be checked by a tool
Those that can are gathered into profiles

At least two tools exist today to check your code against profiles:
CppCoreCheck for Visual Studio
Clang-tidy

Keep learning is much fun to use www.pluralsight.com. - 2016 Julia Chen

http://www.gregcons.com/kateblog/

Plan to watch courses provided by Kate Gregory - Julia's favorite C++ teacher:
C++ Advanced Topics
C++ Fundamentals and Part 2
Using StackOverflow and Other StackExchange Sites
Play by Play: Modernizing C++ Code with Kate Gregory

Reference: 
http://juliachencoding.blogspot.ca/2015/12/cpp-core-guidelines.html

Learning JavaScript

March 23, 2016

Favorite book in 2015:  JavaScript and some PHP. 
Book:  JavaScript and PHP  

2/10/2015 - 3/27/2015 

https://github.com/jianminchen/JavaScriptAndPHP

Need to go back to review the practice again, review what Julia learned in 2015.

Learning AngularJS - developer org document

March 23, 2016

  Spend more than 20 hours already to learn AngularJS. Julia started to read the developer document, and play with some code.

  Spent time to read the document first:
https://docs.angularjs.org/guide/introduction
https://docs.angularjs.org/guide/directive

plan to watch AngularJS video from Microsoft:
https://mva.microsoft.com/en-US/training-courses/introduction-to-angularjs-8682?l=qJ8KNLH1_1804984382

Pluralsight: Play by Play: Modernizing C++ Code with Kate Gregory

March 23 ,2016

 Another 2 hours to work on the course: 

Play by Play: Modernizing C++ Code with Kate Gregory

Julia learned a few things. 

1. For loop - code review and concern, comparison to foreach range and for

2. While loop 

3. Using the nullptr keyword 

4. 

5. 

6. 

7. 

8. 

9. 

10. 

AngularJs fundamentals

March 22, 2016

Angular one hour video

http://weblogs.asp.net/dwahlin/video-tutorial-angularjs-fundamentals-in-60-ish-minutes

Spent hours to read code examples.

Pluralsight: Angular Fundamentals

March 22, 2016

 Spent hours to watch course "Angular Fundamentals". 6 hours video. Be patient, and take some notes.

https://app.pluralsight.com/library/courses/angularjs-fundamentals/table-of-contents


Introduction to Angular - 25m 20s

Angular Controller & Markup - 83 minutes

Creating and Using Angular Services - 83 minutes

Angular Routing - 51 minutes - March 22

Creating Custom Angular Directives - 76 minutes

Test Angular - 89 minutes

Leetcode 238； Product of Array except itself

March 21, 2016

Worked on the algorithm LeetCode 238:

Product of an array
http://juliachencoding.blogspot.ca/2015/07/two-algorithms-questions.html

http://fisherlei.blogspot.ca/2015/10/leetcode-product-of-array-except-self.html

Julia likes to share some tips about writing the code, assuming that you know the optimal solution is using dynamic programming (DP), and extra space is O(N).

For example,

Array: [1, 2, 3 ,4], denoted as arr[].

for each i, i = 0 to 3,
product of i, denoted as P[i],
leftP[i]   = arr[0] *arr[1]*...arr[i-1] = leftP[i-1]*arr[i-1].
rightP[i] = ...
P[i[ = leftP[i] * rightP[i]

write C# code:

1  public static int[] getProduct(int[] arr)   // not A, match description: arr  <- complaint 1, style
2 {
3      if(arr== null || arr.Length ==0) return null;
4
5     int n = arr.Length;
6     int[] res = new int[n];
7
8   int tmp =1;
9    for(int i=0; i< n; i++)
10   {
11       if( i ==0)         // <- complaint 2: 
12            res[0] = 1; // <-  complaint 2: not necessary, remove if clause

}

So, write again starting from line 9. Remember the analysis, only thing you have to do, one multiplication, one extra variable to store previous result - tmp.

Code should match the analysis <-  Julia learned the lesson. 

8    int tmp = 1; 
9    for(int i=0; i< n; i++)
10   {
11       res[i] = tmp;   // it works when i = 0; 
12       tmp *= arr[i];
13   }

    that is the code for leftP[i].

Next practice:
https://www.hackerrank.com/challenges/computing-the-correlation

https://www.hackerrank.com/challenges/unbounded-knapsack

Reading time: blogs

March 20, 2016

Blogs to read in next week:
The 80/20 rule basically states that it will take you 20% of a project’s time to achieve 80% of the desired effect, and then the remaining 80% of time to just get the last 20% right.
https://medium.com/@maebert/9-things-i-learned-as-a-software-engineer-c2c9f76c9266#.xhxvsis00

How to work smart in the office, share space, avoid interrruption etc.?
https://www.facebook.com/notes/will-hughes/how-to-level-up-as-a-developer/10153879894028632

War for tech talent - unbelievable high salary, benefits.
http://www.andiamogo.com/war-for-tech-talent


http://blog.alinelerner.com/

http://www.interviewing.io/

http://www.gainlo.co/#!/

http://blog.gainlo.co/

BootStrap CSS framework: Building Responsive UI with Bootstrap 6-hours - Full Sample code

March 20, 2016

Plan to spend 6 hours to watch this course: (Spent time from 10:00am - 4:00pm)

https://mva.microsoft.com/en-us/training-courses/building-responsive-ui-with-bootstrap-8378?l=BDfMAHIz_3004984382

One hour on March 20, 2016

Go over bootswatch.com

https://mobirise.com/bootstrap-carousel/

http://getbootstrap.com/javascript/#carousel

Julia likes to find the bootstrap carousel multiple frames at once -
http://stackoverflow.com/questions/20007610/bootstrap-3-carousel-multiple-frames-at-once

http://www.bootply.com/92514

HackerRank: Two string - thinking in JavaScript over 10 ways

March 19, 2016

Introduction 

 A new drill to learn JavaScript is not to read a book, instead of thinking in JavaScript and study how people use the language to solve a simple string algorithm.

  It is the excellence learning experience to read JavaScript 14 submissions.

  First step is to go over each solution, and learn from others how to solve problem using JavaScript.

  Julia used to spend months to read definitive JavaScript guide book, but she noticed that learning was slow and less motivated. She likes to learn JavaScript in much more fun ways.

Problem Statement link is here.

Over 10 JavaScript Solutions

 JavaScript solutions she chooses to read, the submission link filtered by JavaScript language is here.


Solution 1:

study code 1 is here.


Review Array.shift function, link on w3schools.com is here. 

JavaScript Array.splice method on w3schools.com is here. 

indexof is here. 

process.stdin - try to figure out what it is on stackoverflow.com. 

The link is here - how to work with process stdin-on

The link is here - how to detect an empty stdin stream 


Solution 2:

Study code 2 is here. 



Solution 3:

https://gist.github.com/jianminchen/25edcfe155c8859a922c

(continued on March 21, 2016)

Solution 4:

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

Solution 5:

Structured code, using prototype, simulated class function, new/ this etc., two sliding pointers, make me laugh

https://gist.github.com/jianminchen/8f1d0a7d1765ba5cdc83

read one more article to entertain the idea of using new/ this in JavaScript:

http://stackoverflow.com/questions/5224295/javascript-the-good-parts-how-to-not-use-new-at-all

Solution 6: 

JavaScript, things I like: using j== first.length to determine YES/ NO, the big problem of coding - repeat same code in if/ else code.
https://gist.github.com/jianminchen/8899cb7587b0389e6ff6

line 6 - line 26 - Julia likes to swap two strings to ensure str1.length <  str2.length

Solution 7: 

swap two string if need. 
https://gist.github.com/jianminchen/10f5cfa5c1ab22070922           

Solution 8: 

write a function to add unique chars into the array - Julia likes the function. 

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

object literal {} - act like a hashmap
search function time complexity O(N^2) - not efficient

A discussion on object literal -
http://stackoverflow.com/questions/17486854/how-to-create-a-method-in-object-literal-notation

Solution 9:

use jagged array - good practice
https://gist.github.com/jianminchen/8dca6d1fd8fe96b7323c

Solution 10: 

using object literal - creating a hashtable, and then, first string goes into as Hashtable - add it if not in; second string, add one on existing one.
https://gist.github.com/jianminchen/ee9fbf9612c8ada8ccae
code can be refactored, early return line 23,  not wait until on line 30.

Solution 11:

Array.prototype.ForEach
https://gist.github.com/jianminchen/69119913341c9bea8b0c
https://gist.github.com/jianminchen/bfe92a2556aab268d250

read this blog to understand the function:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach
https://msdn.microsoft.com/en-us/library/ff679980(v=vs.94).aspx

still concern about value, index, array arguments in ForEach function.

spent 10 minutes to go over the topic:
http://neversaw.us/2011/01/16/not-your-fathers-javascript/

Good article, stopped here: (continue later)

http://neversaw.us/2011/01/16/not-your-fathers-javascript/#binding-is-great

Array iteration:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array#Iteration_methods (20 minutes reading)

Too much detail, just 5 minutes reading:

http://andrewdupont.net/2006/05/18/javascript-associative-arrays-considered-harmful/
http://www.less-broken.com/blog/2010/12/lightweight-javascript-dictionaries.html

Solution 12:

Using string to contain 26 characters, then look up each one in two string, use Array.indexOf method

Study code is here. 

Solution 13:

Use RegExp expression

Study code using RegExp is here.


Solution 14:

Use Binary search

Code submission is here.


Statistics: Hour spent: 8 hours

Follow up 

April 4, 2016

Julia needs to warm up JavaScript every week, she likes the drill; After 8 hours practice using the drill, she noticed that the code she wrote before was so bad, immediately, she spent 2 days to rewrite some of them, in middle of March.

Hacker Rank: Two Strings - thinking in C# 15+ ways

March 18, 2016

Problem statement is here.

Introduction

Julia likes to try a new way to train herself to expand C#, C++ , Java, and JavaScript languages, by reading the solutions first, followed up with a study to feed curiosity, make learning more fun.

Read other people's code! It may be big surprise. Julia is out-of-date to catch up C# skills, when she read those lamba function and LINQ code, she was shocked how concise it is. 

Writing this blog is to help herself to advance her skills in language C#, the more she writes about her learning process, the more she involves with the community, she gets much smart every day. You do not believe it? -:)

Julia's C# implementation is here.

Thinking in all languages

Let us go over some submissions and then write down what players do to solve the problem.

Julia reads 5 different languages at least 10 solution each, total more than 50 solutions.  To learn C#, C++, Java, JavaScript, she likes to have this extensive reading on algorithm code submissions, and then build up her daily routine as a software programmer. Read code is most challenging and exciting work to build up a good programmer. 

A list for each language in her arsenal:

C#    - Read first, then write

C++  - Read more C++ code, prepare to write any time

Java  - Read more

JavaScript - Julia tries to read more JavaScript code, focus on reading for next 2 months

Thinking in C# 15+ ways

How to think about 15+ ways in C#? Enumerate the class and API you like to solve the algorithm two strings. Are you ready for this?

She also likes the following C# solution by other submissions:

Here is the link to go over all C# solution on two string algorithm on Hackerrank.com, called two string C# solutions.

Do it yourself before code tour

Before you read the solution, can you think about using C# Hashset, Dictionary, String.Contains, Hashset.Overlap method, string.indexOf, Hashtable, string.Intersect etc. solve the problem?

Dictionary

Hashset

  Hashset.Overlap 

Hashtable

String 

  String.Contains

  string.indexOf 

  string.Intersect

Using two pointer to solve the problem

Code tour

20 code submissions are listed to study. C# classes are used in the following orders:

Array
Dictionary
Enumerable
HashSet
HashTable
IEnumerable
String
StringBuilder

APIs are most important things to learn in coding. 

1. Hashset

use hashset - more efficient, code is here. 

read hashset constructor on Microsoft website. Excellent, Julia is learning to write new C# code

2. ToList

Read Enumerable.ToList<Source> method on Microsoft site first. Link is here.

Read Enumerable.ToAny<Source> method on Micrsoft site, link is here.

3. string.intersect API

Code submission is here to study. 

4. using C#, var, foreach, Any method - interesting to read

Code is here to study. 

5. IEnumerable - interesting to read the code

Code is here to study. 

Read IEnumberable:  C++ analog - duck typing, a question on stackoverflow.com. Link is here.

IEnumberable - Java analog

stackoverflow question is here.

6.  Two hashsets

Code is here to study

7. Hashset - overlaps method - code is readable

Code is here to study. 

Hashset overlap API

MSDN document is here.

8. Array, Array.BinarySearch method - it is not time efficient solution - but code is reusable.

Code is here to study.

9. Declare new struct data, use byte type, and code is beautiful, succinct.

Code is here to study.

10. use two pointers, move forward if need separately - can be reused.

Code is here to study.

11. Two things Julia likes:

'z'-'a' in array declaration,

second one is to use one array int[26], not 2; second one is char array

Code is here.

 bool[] founded = new bool['z' - 'a' + 1];

 char[] secondWord = Console.ReadLine().ToCharArray();

12. Use Hashtable

Code is here.

13. Use string.Contains() method

Code is here. 

14. Use Dictionary class

Code is here. 

Dictionary<int, char>

Dictionary<int,char> dex = new Dictionary<int,char>();

Dictionary method ContainsValue()

15. string.ToCharArray(), Distinct() of Char Array, ToList(), ToArray(), string.IndexOf methods

Code is here. 

16. Use string.Contains, two dimension array

Code is here. 

17. use Dictionary<char, bool>

Code is here.

18. use StringBuilder to concatenate output

Code is here. 

Read the discussion StringBuilder vs string to concatenation
a question on stackoverflow.com, the article is here to read. 

One more article to read:

https://support.microsoft.com/en-us/kb/306822 

19. use " " to concatenate two input strings and then .Split them

Code is here. 

Last one, 20:

IEnumerable -  Code is here. 

StringBuilder

Read StringBuilder article on support.microsoft.com. Here is the article link. 

Take some notes here:

1. the benefits of using the StringBuilder class over traditional concatenation techniques

2. C/C++ strcat() - to allocate a large character array as a buffer and copy string data into the buffer.

3. In .NET framework, a string is immutable; it cannot be modified in place. <- immutable explanation!

4. The C# + concatenation operator builds a new string and causes reduced performance when it concatenates large amounts of text. 

5. .NET framework, a StringBuilder class is optimized for string concatenation. 

same as using a character array in C/C++, as well as automatically growing the buffer size (if needed) and tracking the length for you. 

6. Reuse existing StringBuilder class rather than reallocate each time you need one. This limits the growth of the heap and reduces garbage collection. StringBuilder makes more efficient use of the heap than using the + operator. 

Statistics

More than 3 hours to work on this study, thinking in C#.

Future master of C# programmers

  

It is the big world since millions programmers are working right now. How to advance the skills to compete? 

The idea of training on hackerrank is simple,  easy to access, and the resource is good since the code passes all test cases on hackerrank, and it is free. 

The study of thinking in 15+ ways are a good start for Julia to master C# programming language. First Julia has to reach out to the community to see how other people think in C#, and then document the study, and then understand the thinking process in all the ways. 

Julia likes to be the master of C# programming language, and also a good problem solver. Every idea counts. 

Follow up 

May 5, 2017

Spent more than 2 hours to clean up the blog, make it more readable, fix issues on styles like font color, size, layout, subheading etc. 

Practice those C# solution. 

Compare hackerrank code submissions study with other choices, such as taking courses or reading a book on C#.