Leetcode 317: Shortest distance from all buildings (part 2)

January 19, 2016

Problem statement:

 You want to build a house on an empty land which reaches all buildings in the shortest amount

  of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2,

  where:

        Each 0 marks an empty land which you can pass by freely.

        Each 1 marks a building which you cannot pass through.

        Each 2 marks an obstacle which you cannot pass through.

        For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

    1 - 0 - 2 - 0 - 1

    |   |   |   |   |

    0 - 0 - 0 - 0 - 0

    |   |   |   |   |

    0 - 0 - 1 - 0 - 0

     *

     * The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is

     * minimal. So return 7.

     *

Practice using C#

Julia chose this Java code implementation to study first, and then she wrote one using C#.

She spent more than 2 hours from 9pm - 11pm to practice.

Highlights of changes

1. Julia likes the idea of "express the intent", so she added a new function called getNoOfBuildings().

So,  here is the version to fix the bug.

Rewrite the fill function, make the function do one task:

public void fill(int origX, int origY, int x, int y, int curDistance, int[][] dist, int[][] reach,int[][] grid, bool[][] visited, Queue<Node> queue)

The above function is too complicated, Julia create a few bugs in the function. More than 8 arguments - too many!

Here is the version after some work on function design 

- get rid of too many arguments

- function much more easy to read, understand

- less error-prone

- function to do one task only

C# code is here.

Another version is here.

Lessons Julia learned through debugging:

1. using ref or not in C# language - does not matter

2. function design - simple, is important to review, avoid bugs

3. Queue is used for BFS, and when the node is added to queue. please also log the distance, and use it for next round. - Main bug - calculation, since each node has different distance to the building node.

More about BFS

1. BFS - how to think about the algorithm?

Tips: Try to start from simple things, like count how many building, empty lands, obstacles; then, figure out which one is meaningful to work with first.

3 choices - buildings, empty land, obstacle. Choose one and see if you can  make progress

buildings - very good. Do some simple task, put all buildings in a List data structure, easy to iterate.

empty land - kind of hard to do BFS - the question is to ask a node to all building distance sum - not sum - but the minimum of sum.

So, start from each building to do BFS

2. BFS - how to design a BFS function?

So many bugs in the first 2-3 hours coding, it takes 30 minutes to understand other people's idea and code.

Go through bugs one by one later. (To be continued)

3. Encourage herself to work on BFS algorithms in the future: 

Some facts:

1. Julia could not figure out how to handle this BFS problem on January 19, 2016, she has to read other people's solution first, and also analysis, and then, start to work on coding.

2. BFS  - Ask questions:

start from where - how many of them - what order to do BFS? order matter or not?

3. Julia could not finish the BFS algorithm writing in less than 30 minutes. A lot of bugs, confusion with BFS function design, and edge case handling.

4. Past experience on BFS

Julia is still working on BFS algorithms, and like to get more experience if possible. Here is another BFS practice she did in June 2015. More reading about Leetcode 317, click here. BFS algorithm review is here.

5. How to make BFS algorithm design experience fun, memorable?

- Have more discussion on the blog. Welcome comments.

Algorithms night (1)

January 17, 2016

Spent Sunday evening (8pm - 12pm) to work on algorithms questions. Just read the blogs, and get some ideas how to solve the problems. 

1. String parenthesis to see if all of them are pair correctly

Leetcode 20: valid parentheses

http://buttercola.blogspot.ca/2014/07/leetcode-valid-parentheses.html

http://www.shuatiblog.com/blog/2014/05/09/Valid-Parentheses/

2. Count the number of palindromes in  a string

 (January 28, 2016)
    Come back to write down ideas:
    1. First of all, do not count duplicate.
    2. Brute force solution:
 any substring of O(N^2) substrings to see if it is a palindrome;
 Add the substring of palindrome to a hashset if it is not in the hashset.
  And return the length of hashset
    3. Use recursive solution - using subproblem to solve. Cannot filter out duplicate - not good
    4. Better solution - use center point of string - 2n + 1, and then, go over each one, add all palindromes substring.

  Requirement: write a C# code in 10 minutes for the solution, using brute force one.

  https://github.com/jianminchen/AlgorithmsPractice/blob/master/NumberOfDistinctPalindromes.cs

3. Write a function to detect if the string has the unique character. 

Read the blog: 

http://stackoverflow.com/questions/19484406/detecting-if-a-string-has-unique-characters-comparing-my-solution-to-cracking

this blog provides good answers for the question of unique character:

Notice that this method doesn't allocate an array of booleans. Instead, it opts for a clever trick. Since there are only 26 different characters possible and there are 32 bits in an int, the solution creates an int variable where each bit of the variable corresponds to one of the characters in the string. Instead of reading and writing an array, the solution reads and writes the bits of the number.

Julia's comment: first blog about bit manipulation - surprising, after the reading, it is much easy to understand the code: 
Two bit operation: 
1<< val 
 |=  

It is always helpful to understand the 

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) { // NOTE: Are you sure this isn't 26?
        return false;
    }
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0) return false;
        checker |= (1 << val);
    }
    return true;
}

http://javahungry.blogspot.com/2014/11/string-has-all-unique-characters-java-example.html

4. A single linked list, delete a node but only know the node pointer which needs to be deleted. How to do it?

http://www.geeksforgeeks.org/in-a-linked-list-given-only-a-pointer-to-a-node-to-be-deleted-in-a-singly-linked-list-how-do-you-delete-it/

5. Leetcode/ Lintcode: binary tree maximum path sum

Leetcode 124: binary tree maximum path sum
http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-maximum-path-sum.html


Review the blog:
http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

6. Minimum height of a binary search tree

http://www.programcreek.com/2013/02/leetcode-minimum-depth-of-binary-tree-java/

string function - strStr - BoyerMoore algorithm - needle in hay

January 5, 2016

Read the Java code on the following website:
http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html

Write a C# version, and check in github, and see if it will help to memorize the algorithm.  

Read the webpage: (well written! now Julia knows two rules: bad character rule, the good suffix rule)
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html


previous study:

http://juliachencoding.blogspot.ca/2015/06/leetcode-strstr-function.html

http://juliachencoding.blogspot.ca/search/label/string%20functions%20review

Learn Google interview process - 25 things to learn

January 9, 2016

 Introduction

Julia spent time again in 2016 to review the video. She likes to take some notes, and then, look into them. So, she remembers now that interview white board question solving should be fun, and should be creative, and should be easy to work with, since the interviewer likes to drop hints, and make you  happy and see if you can solve the problem, or learn something from you as well.

Moishe Lettvin - What I Learned Doing 250 Interviews at Google

Moishe was in the hiring committee, and also taught the interview process. 

Write your own notes

Watch again in 2016, and this time Julia likes to take notes about 25 things about interview. 

1. It's Fun! 

Talk to new people, meeting new people is extremely fun, sharing expertise with people who have same knowledge - great fun. 

Learn through interview, how to interact, no matter undergraduate dropout or PH.D. 

2. Except when it isn't 

3 hours for preparation, before and after; meet the strangers 

Random things happens - 

Candidate cries, cannot figure out the solution; 

Some one just refused to write code; communication problems; People are jerks; people are refused to write code; for more senior position etc.  

3. Noisy, inaccurate, arbitrary (random, casual)

To write code on white board, it is difficult to do 

some cascading problem 

Noisy - interviewer may have a bad day, how to feel about interacting with a person

Interviewer may be in a bad day; you can get different results 

If you are in border line, you are invited to come back in 1 year - google is just generous

5 people can say no if they interview any hired person 

Google's response: 

Set the bar very high - false positive, false negative - not hire a bad person  

For example, one week, 8 of candidates,  say no to all of them 

4. Data is a blessing and a curse 

no correlation between interviewee and ... 

each interviewer give 1 - 4, 4 definitively hire, 2.0 - 3.0 range 

You can't put a number on stuff that matters

Written feedback - 3 or 4 pages narrative about the person 

Same as IQ, it is not accurate 

You can't even ask about stuff that matters - things to love work with, things about employee 

How to test it in the interview? 

Give them the question, see if she/he has passion, and their creative ability, their enthusiasm, maybe their sense of fun, pretty good habit to hack, come out the solution

Keypoint is like a criticism, not statistics. 

5. It's a team effort, and isolation hurts

One interviewer goes very deep in one area; two personalities clicks very well. 

Microsoft - hiring manager is responsible for saying yes/ no - hiring bar goes down a little bit

but Google, Hiring for Google, not for hiring for a team 

Analysis of hiring of Microsoft: 

  not be on malicious, just need to hire some one; bar will keep going down; no check on it. 

Analysis of hiring of Google: 

   very consistent. 

6. Be prepared! 

When you have to give out interview, you should be prepared. 

Having a structure will help: Google has 4-5 hiring - interview process class - basic outline 

10 minutes - 

40 minutes - question 

10 minutes - question to answer 

More nervous than interviewee - first interview to give. 

7. But, it's like jazz

unexpected thing will happen, will go side ways; 

Favorite interview questions:

Maybe they are heard; you can figure out quickly; improvise, 

Maybe they do not like to write code 

Maybe people have better ideas to write code 

Maybe people can 

Maybe be taught, interviewee may give out total out-of-surprise solution 

8. Please make mistakes!

It takes practice. calibrates, 3 people gives interviews together. 

people did more than 25 interviews. 

9. Every interview is a conversation (with goals) 

It is not a test, or something like putting through and see if the interviewee can survive

Conversation has goals, which is ok; Do not just stress the interviewer out; 

Primary goal: 

Happy candidate 

Make them happy

Do not get something from the candidate, but make them feel not good. 

It does not take much to gain notoriety - people blog about the bad interview process 

Interview is stressful Survey: Do you have good experience of Google interview? 

Other goal: Answer "Would I love to work with this person?"

Even the people is not in the same team, do you like to work with him; contribute the company, can he teach you, can they be taught by you, can he inspire you etc. ? Idea world, work with the people smart than me. You want to keep raising the bar.

Is this person having qualities, and then people love to work with? Can they contribute to the company

Other goal: give answer to "Would you love to work at this company?"

Talk about culture, how excited to work here.

Feel real Humanity sense during the interview while I am working here. 

Good interviewers are generous - Ask good questions when interview goes on. Honest to candidate, work hard on candidate. Ask good questions in the interview goes on. 

I learn something amazing, graph traversal problem for example, traverse the graph, and find all the words in them.

Second part, implement a dictionary to look up those words quickly. Use tries for that.

That is what far the interviewer gets on that question. But he asked the candidate, he got through that approximately 8 minutes. What else you can do, he showed me that traverse the graph and trie in parallel, magic and beautiful thing.

cannot write down the detail. 

Example:

1. Traverse graph, and build up a dictionary. A candidate spends 8 minutes to figure out. The candidate shows doing thing in parallel.

2. Random number, time stamp

superior smart, give me direction

3. Beauty math and engineering problem

Interviewer being prepared, knowledge

10. Time is of the essence - counter point of generous of interviewer

Time management - easy to get away from you as an interviewer. 

Candidate may talk too much not important, not relate to the conversation the interviewer likes to have. 

A few thoughts on technical interviews: 

11. Good question are like onions

naive solution in the crust, you can peel back, deep, more interesting problems going on. 

First technical interview question I asked, write a program to draw a circle - 

Microsoft, 1994, super nervous, five minutes small talk

Write a program to draw a circle - sin, cos, 2 * PI,

Interviewer says that it sucks, speed up

sqrt root 

All right, good job

- 15 minutes left, no square root - compute error - with right hint

compute error - high far away you are

congratulations: circle drawing algorithms by windows

questions goes to deeper and deeper, for the candidate, it is great. More iterate on something

Iterative on something

12. Strive for higher bandwidth

prefer for the white board to just talk to people, can get more data

First Microsoft interview, whole nervous whole day. 

Just give me a notebook and problem, and let me work on the problems. 

13. Artifice is inevitable

Being a candidate is not having a job.

Is this person enjoyable to be around? Is this person creative? Can this person learn? 

14. More signal; less noise

Let candidate know what they are here for; let interviewee prepare

Your job as an interviewer is to help them show their best work. That is what you want to see. You are not just trying to make them fail. 

15. This might be the best we can do

It probably isn't

Hack school is a good hiring tool - 2 months of coding, some one can finish or so on. 

15. Have Fun

      Learn

Questions?

1. Machine learning helps the interviewer to decide ...

Human input, the written feedback, hiring committee

2. Question: false positive

Worthy taking some risk on some one; Make a bad hire, cascading effects,

3. Microsoft hires for a team, Google hires for the company

hiring committee -

culture thing - 

4. How to hire people with domain knowledge? 1 person with domain knowledge

5. Personality fit vs strong technique skills

Ability to lean and pick things up; demonstrate Java and Java Script knowledge, so he/she can pick up PHP.

People cannot get the expertise you need.

6. Don't hire ass holes if he is perfect for the job. 

During interview, he is a domain expert; Some one creates a toxic environment. 

He is bad, drag people down;

7. Interviewers talk about, send an email for these emails. 

Microsoft email chain - hiring or not hiring / quiet sure

Poised or blessed by your first interviewer - a senior people if he is. 

Google does not allow to communicate, every one does not have context, what happened before. Without bias is better. 

8. Group interview - 2 interviewer, one interviewee

2 shade interviews - 2 shade interviews, just observe, do not say a word. 

9. If you have power to change, what to change?

Could you hang out? Could you talk? Can you communicate?

Do you have enough data for you to decide if you should hire? 

10. calibrate? new bees? How much weight?

Good questions, exercise the candidate

here is the place the interviewer has to hint

Apply something

Write solid code

Talk through ...

11. Who is focusing on? before interview

After the interview, people talk about the impressions, sort of things.

2-3 pages - take up code sample - two pages typical for feedback

If every one goes to wrap up meeting,

12. Google does follow up, it takes months to make a decision; now it only takes weeks.

Stumble early on, give hints on - just more you ask question, the more you know how to give hints.

13. behavior questions:

agree general ideas how to do behavior questions.

Program interview exposed.

14. turnaround time - how quickly to get back to the candidate?

Microsoft - last interview - you have the hiring manager to interview you.

Google - April, interview, at the end of June.

6th edition of book

Nov. 30, 2016

1. Google onsite interview - demo 

2. Passing the Google interview as a software engineer

- Proficiently

- Quickly  <- ask questions

- without mistakes

- Good practices

January 14, 2017

Google interview article

March 3, 2017 

Read quora answers provided by Moishe Lettvin.

Answer of Google interview, very good time to read the answer.
No degree, imposter syndrome; Julia did not get her Ph.D. degree, but she had a special experience on her Ph.D. study, she went through the immigration process and then became a Canadian citizen. She then went back to her career pursuit relentlessly through Hackerrank contest training.

Read Moishe Lettvin's answer to Is it necessary to complete graduation to get the software engineering job at Google? on Quora

pluralsight: online courses study

January 16

Just start to watch video courses on code school and pluralsight. And she likes to blog on this as well.

Julia did not have  time / motivation /confidence to go over MVC in last 5 years work as a full time programmer, but in less than 3 hours, went over MVC course, and found out that technologies are so easy to understand, also affordable to get best education - courses ($40/month, compared to IT course $500/each course, graduate research credit out-of-state $800 - $1000), and use it to apply at work.

The pluralsight.com service is such affordable,  make me connect to best of talents in the world, catch up all the technologies we need, or just curious, and then, master one or two of them a time if need.

Life is such a journey, and then, you find out that you are isolated, work alone, tired, and suddenly, you are connected to others, get back with more confidence.

That is the journey Julia likes to start with pluralsight.com / codeschool.com.

Dec. 28, 2015
http://juliachencoding.blogspot.ca/2015/12/code-school-courses-study.html

started to watch code school videos, learned Angular.JS, Ember.JS, bootstrap CSS framework, reviewed CSS, Html etc. Great teaching from instructors, better than my experience - work full time 3 years + on CSS, html, Java Script, Jquery. Good to know how to teach, how to be teachable, and enjoy the lectures.

January 15, 2016
Spent more than 3 hours to watch the videos on pluralsight.

"building applications with ASP.NET MVC 4"

January 28, 2016
Building a Web App with ASP.NET 5, MVC 6, EF7 and Angular JS
https://app.pluralsight.com/library/courses/aspdotnet-5-ef7-bootstrap-angular-web-app/table-of-contents

February 4, 2016

Web API design
https://app.pluralsight.com/library/courses/web-api-design/table-of-contents

Play-by-play learning AngularJS
https://app.pluralsight.com/library/courses/play-by-play-learning-angularjs-ken-cenerelli-john-papa/table-of-contents

AuglarJS: Get Started


AngularJS Fundamentals
https://app.pluralsight.com/library/courses/angularui-fundamentals/table-of-contents

Feb. 10, 2016
AngularUI Fundamentals

3 hours video lectures

http://stevemichelotti.com/new-pluralsight-course-yeoman-fundamentals/

reading:
https://github.com/angular-ui/ui-router/wiki

February 14, 2016

Build your career with Michael Lopp

And then, read the blog about Michael Lopp:

http://techcrunch.com/2015/08/01/a-conversation-with-michael-lopp-pinterests-head-of-engineering/

http://randsinrepose.com/

Good article to read:
http://recode.net/2014/06/10/pinterest-hires-long-time-apple-execs-to-lead-engineering-and-product-design/
http://randsinrepose.com/archives/what-to-do-when-youre-screwed/

http://randsinrepose.com/archives/the-culture-chart/

http://randsinrepose.com/archives/

February 16, 2016

So good to come cross this course, and then spend 3 hours to catch up responsive design in CSS. Save me a lot of time to catch up CSS.

Pluralsight:

Responsive In-Browser Web Page Design with HTML and CSS

https://app.pluralsight.com/library/courses/responsive-browser-web-page-design-html-css-2262/table-of-contents

March 1, 2016
Another 3 hours on course:
Building a Web App with ASP.NET 5, MVC 6, EF7 and Angular JS

check other two courses:
1. JavaScript for C# developers
2. Front-end web development Quick Start

Plan to watch this video:

https://app.pluralsight.com/library/courses/csharp-best-practices-collections-generics/table-of-contents

Leetcode 5: Longest substring palindrome

January 13, 2016

Read the blog: 

http://blog.csdn.net/linhuanmars/article/details/20888595
http://blog.csdn.net/linhuanmars/article/details/22777711

Please read 5-6 solution about this leetcode question, and then, collect all the wisdom. Try to have nice memory about the solution, some fun experience; therefore, it will be a quick and fun time to solve the similar problems in the future.

Do not rush to finish more leetcode questions. Try to focus on simple problems.

There are 5 solutions discussed in the following blog, most important is to give overview of 5 analysis, what is brute force solution - time, space complexity.

One way to make review more fun is to read more than 10 - 20 solutions, and know all the ideas out there, and then, write some code; Reading is most important to help understand algorithms, through a simple problem, common interview question.

http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-i.html

4 solutions in the above blog

one optimal solution - linear time solution in the following blog:
http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

This blog is in Chinese. Excellent! Try to summary a few tips to come out linear time optimal solution! Do something to get more involved.

http://www.felix021.com/blog/read.php?2040

spent 10 minutes to read the article, enjoyed the reading; a good article with very well explained brute force solution, how good is to work on linear solution in time complexity. 
https://www.akalin.com/longest-palindrome-linear-time

Read the blog:
http://www.acmerblog.com/leetcode-longest-palindromic-substring-5356.html

6th solution, a suffix tree solution:
http://www.allisons.org/ll/AlgDS/Tree/Suffix/

First blog about this leetcode question:

http://juliachencoding.blogspot.ca/2015/06/leetcode-longest-palndromic-substring.html

Another palindrome algorithm #9
https://github.com/jianminchen/Leetcode_C-/blob/master/9palindromeNumber.cs