Google — The complete (interview) journey/ Cracking the software engineer interview

Please go to my medium page to read the full article 🙂

Software engineer – Another metaphor

1) What is the benefit of using a metaphor?

Software engineers love to use metaphor (at least in my case), the reason is, well, most of the time, our products (the running version on production) are existed only in our mind. There are limited things we can do to understand clearly about our products, and there are at least three ways we can comprehend our software: the business view, the machine view and the software engineer view.

Side track: At this point, one reader’s thought could be: Software engineer role is to integrate among business, machine and other engineers viewpoint? So, to be a good software engineer, we need to have knowledge in Business, Computer and Psychology? Which may even lead to a more interesting question: does any challenging profession require the combination of three or more perspectives?, which I would discussion further in later posts.

Coming back to the metaphor benefit, let’s give a simple example: imagine that you need to explain to a new hire what your system is doing, how would you approach it? A typical flow could be: first, tell him/her about what is the real life version of it (if exist) or at least some thing close to it, which makes sure that he/she will be set into the right direction. Then, we will iterate slowly from the high level technical design/diagram until ultimately, the code. We may have done this so many times that we don’t even realize that metaphor has been a powerful tool in our tool box we use in daily basis.

2) Why another metaphor?

Today, there are several metaphors that exists, which helps us to set the right mindset when thinking about how to approach a problem :

• Software development is like building
• Software development is like gardening
• Software development is like surgery

All of those are good one and have served us well.

• Remember that all models are wrong; the practical question is how wrong do they have to be to not be useful.

So, why another one?

I personally feel that all existing metaphors are too specific, they are solely focusing on the development process which is about the relation between the developers and their product: the code. However, are we forgetting about another important aspect of our job:  the relationship between business as well as other developers?

There should be some way to guide us to the correct direction, how should we interact with others? How should we negotiate with business people, with other engineers, with other team? What do we aim for in each discussion? What are our position in the organisation? What do we have and what don’t we have?

3) What is the metaphor?

Well, this metaphor is a direct deduction from another metaphor:

• If a company is a country, software engineer is the military force.

Yup, that’s the metaphor. It gives us a broader perspective of our profession. It is not focusing on our daily task: writing code, but give us a better idea of how our contribution relates to the overall business, what are the mentality of the engineers while designing, executing and making decision.

Think about it.

Every software is produced to either conquer new territory or protect our old one. Every tools we use could be considered the weapon we choose to accomplish the mission. We need to understand the big picture, thus take into consideration what should be the most important factors while working on a project. Once a problem arises out of our original plan, we could make decision to even overwrite existing decisions on the spot to keep the business moving, depending on the urgency of the problem.

4) How does that help?

The fun

It sheds the light into why doing software engineering is fun. It is not just about using cool weapons, which many of the young soldiers enjoy doing (which leads to something like: rather than choosing old classic pistol, we like to experiment with nuclear bomb). Countless discussions about what is the coolest, deathliest gun … are so uhm, distracted.

The fun of software engineering could also be: strategically executing the mission, utilising the least amount of resource and limiting casualty, creatively using what available in your hand to effectively solving the problem.

Inside our company

It also helps us during the negotiation/communications with other parties, we now know the position of us within the company. Software engineers are the one who executing and owning the product eventually, it is definitely up to us to define how to carry things out: time, resources and requirements in the final product/project to a certain extend. Controlling complexity and managing risk are usually mentioned, but now, we should view those in bigger landscape.

And others

Knowing about the current situation of the company could also help us to understand about the attitude/opportunity of the company towards engineers:

• A well established company (dairy cow phase), the military is something important but not crucial, the power of the military should be limited and in control.
• A growing company (unicorn phase), the military force is the most crucial, which involved in almost any decisions, with great impact and visibility.
• An early start-up (survival phase), well, every body is in the army.

5) Final thought

Software engineer is a challenging career choice with many opportunities as well as pitfalls. Choosing the right mindset/mental model could help you navigating through all complexities, focusing on the right direction as well as setting up the expectation and selecting the correct set of problems and challenges in each stage of your career.

Next (possible) blog post:

• Meaning of life
• In the end of the day, we are all thinker
• How every unicorn company will eventually become dairy cow?

 

 

 

Beautiful problem – Number of integer solution for equation with constraints

Today, I have solved a beautiful problem (link). So, basically, the problem is counting the number of solution for this equation:

x1 + x2 + … + xn = A

With A is constant and x1 … xn are integer, and there are different constraints for each xi: 0 <= xi <= ci.

Without those additional constraints, this problem is the famous stars and bars problem. So basically, imagine that we have A stars on a row, and we need to put (n – 1) bars to separate those stars, how many way we can put our bars? See the connection? (Hint: notice that after we put (n – 1) bars, we separate those stars into n sections, which has zero or more stars)

•  The answer for above question is simple, add n – 1 stars into those A stars, the problem become, finding the number of ways to pick n – 1 stars from A + n – 1 stars, which basically is C (A + n – 1, n – 1)

Go back to the original problem, so, after getting the answer without those constraints, our job now is only to subtract  number of solution violated the constraints. But how do we find that number?

Let’s start by assuming that we only violated the constraint of the first variable x1, which is, x1 > c1. We define y1 = x1 – c1 – 1.

So, the problem becomes, finding all solutions which satisfy following conditions:

y1 + x2 + … + xn = A – c1 – 1.

And, 0 <= y1 <= c1, 0 <= xi <= ci.

Ah ha!, at that moment, we realize that this problem can be solved by applying Inclusion-exclusion principle.

So, the final result X is:

X = C (A + n – 1, n – 1) – C(A + n – 1 – c1 – 1, n – 1) – C (A + n – 1 – c2 – 1, n – 1) …. + C(A + n – 1 – c1 – c2 – 2, n – 1) + ….

 

 

 

 

My Google onsite interview

On July 2015, I received an email from a recruiter, asking whether I am interested in working at Google London. Without a doubt, I response to him showing my interest, Google has always been my favorite company. After few weeks, they have set up a phone interview with one Google engineer on August 2015.

Phone interview

Doing a lot of research before, I manage to answer almost all questions in this interview. The phone interview covered large range of topics, from algorithm, regex, network programming to bit manipulation, math calculation. The questions are simple, I understand that the phone interview’s purpose is mainly focus on finding a “red flag”, without trying too hard to see how good is your analytical thinking or system design. Obviously, those abilities will be tested more carefully in the onsite. A very logical decision from Google. I think Steve Yegge has explained well in his must-read article.

After one week, I received a call from my recruiter, telling me I have passed the interview, and I was invited to Google Sydney for onsite, as there is no development center in Singapore. Great! By reading tons of question and answer on Quora, I know Google will be very flexible in its timing, so I scheduled the interview two months forward, plenty of time to study, as well as prepare all necessary documents for my travel.

Preparation

There are two major topics that will be tested in the onsite, problem solving skill and system design. I used most of my time to prepare for system design questions, following guidelines in this amazing link. Wonderful stuff for to start.

Algorithm is my strong point, practicing algorithm for the pass 3 years, day by day, I am fairly confident about my skill. However, doing the question with similar difficulty and format, and practice to present your approach clearly is very important. I was focus on solving a lot of Topcoder problems 250 pt Div 1, which I believe have very similar difficulty level (of course, I know this by reading one Quora question).

Interviewing with your favorite company first is suicide, keeping that in mind, luckily, I got another onsite with Amazon right before Google onsite, fantastic, similar format, that would help me a lot.

Onsite

Finally, the day has come. After a long flight, six hours on the plane, I have arrived at Sydney’s airport. The weather in Sydney was beautiful, my friend there has walked me around to visit some famous places in this lovely harbor city. Nice experience, however, due to jet lag, and sleeping too much on the plane, as well as being both nervous and excited at the same time, I cannot sleep the day before the interview. Not a big deal, a cup of tea will solve the problem.

I arrived at Google office 10 minutes before the interview, and was welcomed warmly by the receptionist. He is a very polite and nice person, who gave me a cup of mint tea and even a cookie, extraordinary! … starting to love this place …

Few minutes later, a Google engineer guided me to the interview’s room. And the battle began…

• First interview

My first interview was conducted by a senior engineer, he asked me some warm up questions, and after the introduction, we started to tackle the first problem, which was also the only problem in this interview.

An algorithm problem, a string processing problem, and its difficulty was out of my expectation. That was my first feeling. Being interviewed at Amazon and various other companies, I have never seen this type of difficulty. After first few minutes becoming more and more nervous, without any sight of “A ha” moment,  I decided to explain and implement my brute force solution, an O(n ^ 3) solution.

This turned out to be a good decision, after I proposed my solution, the interviewer admitted that this was almost the best I can do, except some other optimizations, which would bring the solution from O (n ^ 3) to O(n ^2).

Being too nervous, and still try to looking for a smart solution, I was lost and needed a lot of hint from the interviewer to derive the optimal solution. Big mistake, I should be focus on my code, rather than a smart move to impress the interviewer, that is the first lesson. Try to optimize your code! Think ahead of the interviewer two or three steps, but not more than that!

The interview ended by a very tricky optimization that I hardly believe someone can come up within a short amount of time, but it turned out that actually, there were two people, arrived at that point. Hat off to them.

One more point to note is, my interviewer was so nice, I felt like I was working with him, not interviewed by him, this has helped me a lot to relieve my stress and focused on solving the problem without much worrying about my interview. Very nice Google!

• Second interview

My second interview was with two engineers, one was training to be interviewer, not so surprise, I have done so many research, thank again to Quora. This time, the question was another string processing problem.

Being a lot more confident after the first interview, I quickly figured out the optimal solution, an O(n) solution, then implemented it without any difficulties. The interview asking me some questions to clarify my choice of data structure, and I answered them flawlessly, he looked satisfied.

However, I was being so confident, that, I forgot the first lesson. I think this question was done, and stop thinking or trying to improve it. Another big mistake! I should have written the solution in a better way, or try to test it at least.

• Third interview

My third interview was with one young engineer. We began with a game theory questions. Tough one, I cannot think of any solution except brute force, I considered to use Nim, but after a while, I didn’t think it was applicable for this problem. Try not to make the same mistake as the first interview, I started to explain and implement the brute force solution with the interviewer, and also suggest few optimizations. He was satisfied with my solution, and we moved to the next question.

The second question was a two dimensional dynamic programming problem, tough to come up with a formula, but once you did, implementation is straight forward. I started with implementing the recursive formula, and also mentioned about the dynamic programming approach. Nailed it!

• Lunch time

One engineer took me to lunch, we had a nice lunch and chit chat a little bit about working environment and culture at Google, the food was surprisingly good, it made me feel sleepy also :))

• Fourth interview

Fourth interview was between me and two other engineers, one junior and one very senior. We started by doing some performance approximation calculations, bit and bytes, straight forward, but can cause a lot of problem if you don’t understand the underlying concept.

After that, the interview was focus on a simplify version of a real world problem. Tough, but within my reach. Coming up with an optimal solution, then focus on optimizing and reasoning about the choices, I was kind of used to the process. I think I have done well in this interview.

• Final interview

Finally, system design, I started to being nervous again. This type of interview can go from very abstract to very detail level, which focusing on testing your engineering sense. (Common sense and logical thinking)

It turned out that it was an interesting and relaxing interview, we discussed a lot of problems from designing overall architecture to addressing performance problem, from handling transferring message to storing data. Feeling like we were truly teammates, we have enjoyed the interview very much.

Result

One week later, my recruiter told me about the result, I have done well on last three interviews, but not so good on the first two. However, the overall feed back was positive, so she would submit it to the hiring committee.

I was happy, but also understood that my chance was not so high. Hiring an engineer with an over-the-fence interview performance, without any significant accomplishment or support from other employee, I think rejection was not an unexpected result. And I was right, I was rejected few days later.

Final thought

I had an amazing experience, Google is far more better than I was expected, I have met a lot of nice and cool people, and even though the result was not good, it cannot destroy the good feeling towards the company. I was working with extremely nice and friendly recruiter, who tried her best to help me through out the process, thank you so much!

Some lessons :

• Always start from the simplest solution, and try to improve it, don’t stop working and thinking to make the solution better and better.
• Every decision should be backed by good reasons.
• You need to understand your tool, pros and cons, don’t just use it, reason about it.
• The problem of competitive programming is, when you arrive at a working solution, you stop, but when interviewing, you need to come up with a perfect solution.

Update:

Useful links

https://github.com/vasanthk/how-web-works#googles-g-key-is-pressed

https://www.ntu.edu.sg/home/ehchua/programming/webprogramming/HTTP_Basics.html

https://www.interviewbit.com/problems/tiny-url/#_=_

https://www.educative.io/collection/5668639101419520/5649050225344512

https://www.hiredintech.com/system-design

https://tianpan.co/hacking-the-software-engineer-interview/?isAdmin=true

https://github.com/donnemartin/system-design-primer#system-design-interview-questions-with-solutions

https://crackstation.net/hashing-security.htm#properhashing

https://aws.amazon.com/architecture/well-architected/

https://github.com/mister0/How-to-prepare-for-google-interview-SWE-SRE

 

 

 

 

 

 

 

 

 

 

 

Why reading is important!

Reading is important, we have heard about this million times, but why?

         If I have seen further it is by standing on the shoulders of giants.

Issac Newton

Human has long history of development, many things we experience, we have done in life have been done by someone, somewhere, and may already be noted.

         Human being have the ability to learn and understand without having experience.

J.K. Rowling, Speak at Harvard Commencement.

Reading is like travelling, a journey to one stranger’s mind, where you learn to understand, to empathy with the author. With the help of your own experience, imagination, and logical thinking, the gap between author and reader maybe overcome, thus, helping readers gaining invaluable knowledge.

http://www.quora.com/Why-is-reading-so-important

Reading is enlightening. Your action, your life is the reflection of what you believe in, and by reading, we enlarge our own mind, our own world, it gives us motivation and feeling of believing, thus, pushes us out of our boundary,  urges us to experience what we haven’t known.

In the end, I believe enhancing our reading experience is one of the basic but most important step for human evolution.

Reading is an art!

When we read: textbooks, programming books, technical books, … we not just read it, we need to think, we need to digest, we need to learn… we need to force our brain to work.

Reading book is like taking in a stream, an information stream, and we, our brain need to process it, absorb it, translate it into something benefit us.

Most of us, when reading a book, to make the best use of it, we take notes, lot of notes, this is the first step. Those notes are something linear, something roughly processed from the original stream.

After taking all the notes, we need to reorganize, restructure them into something more brain-friendly, and this is called a mind map http://www.informationtamers.com/WikIT/index.php?title=What_is_a_mind_map%3F

So, how can we convert from a text to a mind map? http://www.mindmapinspiration.com/how-to-convert-text-to-mind-map-paul-foreman/ actually, it is simple, just listen to your brain.

After reading a book, for weeks, or years latter, we want to re-read it, now, the information presented in mind map form become a great advantage, we don’t need to read, or reprocess a rough stream again, we have something cooked, something delicious for our brain, something just right to read. http://www.quora.com/What-advantages-do-mindmaps-offer-over-linear-lists

In the end, there is a need to create, to store a mind-map from a book. What is the best way to store something, to manage, to share something? It is on the computer, or the internet. But, we lack of a tool to do all of the processing stuff…

This is the beginning of my project PDFTransReader.

Hello world!

Hi!

Welcome to my blog. From now, I am starting to take notes about my learning experience, about how I see the world around me. Hopefully, it can benefit me and maybe you. Enjoy 🙂