Strong Connected Components

There are plenty of problems that could be solved by finding the set of strongly connected components of a directed graph ..

In this topic I will explain what is a Strongly Connected Component? and how to find the set of all Strongly Connected Components of a directed graph.

Strong Connected Components

A Strongly connected graph is a graph where each vertex could be visited from each other vertex of the graph, for example the following graph has 5 strongly connected components.

Algorithm to find SCC

 

One of the most famous algorithms that is used to find strongly connected components of a graph is known by the Kosaraju's algorithm. And It works as follows:

• DFS all nodes and save visited nodes in a stack S, push node only when finishing visit to all connected nodes.
• Inverse the original graph by reversing all arcs E(U, V) to be E(V, U) instead
• Pop each vertex V in S and DFS to get the strongly connected component that contains V.

Problem

 

To try this problem before reading my solution please visit CodeForces.

Your city has n junctions. There are m one-way roads between the junctions. As a mayor of the city, you have to ensure the security of all the junctions.

To ensure the security, you have to build some police checkposts. Checkposts can only be built in a junction. A checkpost at junction i can protect junction j if either i = j or the police patrol car can go to j from i and then come back to i.

Building checkposts costs some money. As some areas of the city are more expensive than others, building checkpost at some junctions might cost more money than other junctions.

You have to determine the minimum possible money needed to ensure the security of all the junctions. Also you have to find the number of ways to ensure the security in minimum price and in addition in minimum number of checkposts. Two ways are different if any of the junctions contains a checkpost in one of them and do not contain in the other.

 

Input

 

In the first line, you will be given an integer n, number of junctions (1 ≤ n ≤ 10⁵). In the next line, n space-separated integers will be given. The i^th integer is the cost of building checkpost at the i^th junction (costs will be non-negative and will not exceed 10⁹).

The next line will contain an integer m (0 ≤ m ≤ 3·10⁵). And each of the next m lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n; u ≠ v). A pair u_i, v_i means, that there is a one-way road which goes from u_i to v_i. There will not be more than one road between two nodes in the same direction.

Output

 

Print two integers separated by spaces. The first one is the minimum possible money needed to ensure the security of all the junctions. And the second one is the number of ways you can ensure the security modulo 1000000007 (10⁹ + 7).

 

Solution

Protocol Buffers

In this topic I will talk about a very nice project that is done by Google which is Protocol Buffers...

What is Protocol Buffer?

Its a method of serializing structured data in an efficient, fast, and simple way where you can control how the object looks like using a predefined language.

So basically you define the object structure using a language which called "Interface description language" and usually its written in files with extension .proto and can be then compiled using protoc utility to generate Java, C++, Python class files, and to create instances you can use the builder class generated along with the generated classes.

Interface description language

A simple way to define the fields, types, and in case required or optional and you also have to assign sequence number for the tool to uniquely identify each of them when serializing and de-serializing. You can see the example below and read more about the language to develop more advanced object types.

I would say this is a good way to serialize and de-serialize objects to be totally independent of the language used especially in systems that involve communication between heterogeneous systems which may be developed with different technologies and/or languages.

 

Complete Example

First you need to install protocol buffer compiler using the following command:

sudo apt-get install protobuf-compiler

Maven Build Script

Protocol Buffer File

Read and Write Proto Buff Objects (its just an example :D)

Monitoring tools and libraries

This quarter I have been assigned a task to design and implement a solution to monitor the accuracy of our results and the health of our system (e.g., Request durations, Error rate, Caching ratio, .... etc).

In the beginning I felt it might be a silly task, but then it turned out being an exciting task that I've learnt alot from as there are many open source technologies I have used during this project.

In this topic I will mention some of these systems and libs that might be useful for many of you to track the health of your system and give you a good indication of how good your system is. ;)

Metrics Library

Simply if you want to monitor your system you should expose data to measure and correctly monitor your system. This library is used to expose some metrics and store them via JMX, however it supports other ways to expose and report your metrics (e.g., Console Reporter, JMX, HTTP, CSV, ....).

These metrics could be one of the following type:

Counters

You can use this metric to report something that increase and decrease over time (e.g., Bookings, Errors, Done requests, ... etc)

 

Histogram

I have found this metric type very useful to measure statistical changes of a sequence or series of data like (Request duration) .. for example you can update this metric with the duration of all done requests and measure at any point of time the mean, standard deviation, 75th percentile and so on to know how good your system at any point of time.

 

Timer

I didn't use this type of metrics but its mainly can be used for example to measure the duration of a request and get the rate of requests per second.

 

Health Checks

This one is also very useful if you have multiple subsystems that you need to check its health and see if anything happens, like health of database connection.

I used this lib and exposed all metrics via the JMX reporter and the results were amazing especially when you use other nice monitoring tools like the ones I will describe below.

Grafana

You can use Grafana to visualize your metrics and measure your system health over time.

I used Grafana to create multiple dashboards to measure the Error Rate, Cache Ratio, No Results Rate, and to measure the accuracy of our results.

I would recommend it for anybody wants to visualize and measure his system health and accuracy.

I will put some useful points about Grafana:

• Datasource - You can define multiple data sources and each one has its own query editor which supported by Grafana (e.g., InfluxDB, Graphite, ...)
• User - It supports user authentication and authorization via LDAP, Database, Google Authentication.
• Dashboard - You can group graphs in one dashboard and create multiple dashboards to track your system.
• Row - In one dashboard you can have multiple rows to organise how the graphs should look like.
• Panel - Panel has multiple types but for me the most important was the graph which you can define your graph with the not very powerful query editor :D. 

You can also define the period you need to see on each graph and the refresh rate of the whole dashboard.

Sample Images from Grafana website:

 

Non Technical Interview Tips

After writing my previous topics that covers only technical parts of interviews, I received questions to cover the non technical skills needed for interviews. So I decided to talk only about this in a separate topic.

Rejection Reason Example

The reason was that I'm not good in communicating my ideas, and didn't prepare for the interview environment which was a bit messy.

I think the following points are really important to care about when you have an interview, feel free to send me other tips to include.

Interview Environment

• Make sure that you set the best appointment for the interview which you are free and can sit in a quite place concentrating a solving very hard problems.
• If you are not sure that the internet speed will be stable for a Skype interview, ask them to call you on your phone.
•  Make a small test for your microphone, sound, internet, ...

Listen

One of the important skill interviewers assess is that you listen to questions, understand them, and not approaching solutions before making sure that you understand the problem and corner cases.

Hints

If you can't find a solution or struggled in one, you can ask them for hints.

Answers

Try to give short answers, and avoid speaking too much.

Internet Connection

I prefer DSL than Wireless and 3G. Its more stable. 

English

Try to speak slowly because they don't expect that you are super fluent in English. 

Assumptions

If you have assumptions write them on the shared document, so that they feel you know what you are doing.

Feedback

Never ever ask for feedback within the interview. 

HR vs Technical

Ask technical questions to tech people, and other questions like Salary, Vacations, Benefits, ... to HR.

Say No

If they asked you about something you don't know, feel free to say I don't know about this topic or technology. It would be ideal if you know something close to it and try to talk about instead.

Example

Do you know framework X? 

No. But I know framework Y which does the same task, and I think the concept is the same, So you can ask me about the concept or I may answer according to my experience to Y.

Feel free to comment and share the topic :).

Interview Experience

In this post I will talk about how to search, prepare, and pass a tough technical interview.

Searching for Jobs

I used to search for jobs but actually recruiters now are smart enough to find you if you have a good profile that could attract them calling you.

First make a good profile on Linkedin, and Xing. Put everything there and give small description about everything. In order to get noticed make sure that you include keywords that people use to search for candidates, and don't forget to update your current location and contact information regularly. Linkedin has a good job search that you can use to filter jobs that match your skills and needs e.g., Jobs by location.

Finally when a recruiter asks for your CV or contact, don't just reply with messages like "Hey please find the attached CV as you requested", prepare a template message like the following one:

Hello,

I'm a Software Engineer with solid algorithms, problem solving, and data structures skills. I have excellent experience in back-end development and you can check my skills and all the details about me in my CV and the following links and profiles.

- My blog contains lots of technical content (e.g., Algorithms, Problem solved by me, Administration, Java technology, Linux/Minix kernel topics, and some open source projects done by me) here is the link for it. Link

- My Github profile which contains all the projects done by me and projects I managed to contribute in. Link

- Topcoder profile: This website makes regular algorithms contests between the most professional engineers around the world and my progress in it is excellent. Link

- LinkedIn profile which contains general and detailed information about my experience both work experience and open source experience and it also contains most of the technologies I use and have knowledge about them. Link

- My SourceForge Page which contains binary packages of my projects for developers/students to download them and use them freely.

Preparation Time

Now you should put a plan for your preparation. I used to have the following plan to prepare for interviews:

• Check Glassdoor for sample previous interviews of this company or a company with the same business.
• Record all questions in one file with small categorization.
• Spend only 1 day in this task and try to collect as much questions as you can.
• Solve or review my solution at leetcode.
• Checking my How to prepare for an interview series.
• Studying problems in Cracking coding interview book.
• Studying Hacking google interview handouts.
• Solving 2 or 3 design questions.
• Refresh my knowledge about Caching, Hashing, Distributed Systems, Parallel Computing, Computer Architecture, Unit Testing, Software Control Managers,...etc
• Asking one of my friends to interview me.

Interview Process

Usually you will do a series of phone interviews 2 or 3, and you will be asked 2 or 3 coding questions that you can pass easily if you are well prepared. They may also ask you to write test cases for your solution and you have to cover all the cases.

For Testing:

Use the following strategy: As an example consider that he asks you to print an array of numbers:

• Best cases test: {1, 2, 3}, {-1, -2, -3}, {1000000, 28, 27}
• Load test {A very large array}, {INT_MAX, INT_MIN}
• Random test {-1, 2, 77, 10082, 87273, 928, -91837, 28737}
• Corner cases test {}, NULL, {1}, {-1}, {0}, {0, 1, -1}, {1, 2}

May be they need more than that and for such cases you can ask them for hint :) .. Its OK to ask for hints by the way ;)

At the end of the interview he may ask you some tricky questions, or open ended questions .. So be prepared.

Onsite Interview

In the onsite interview you will have around 5 or 6 technical interviews that will cover all aspects of skills that you may or may not have. Example:

• 3 Coding Interviews.
• 1 Architecture and Design Interview.
• 1 Interview with the Engineering Manager or Hiring Manager.

You should:

• Be patient and listen to the full question.
• Ask questions, usually they give you partial information to check what you will do!
• Start demonstrating how would you approach this problem
• When he asks you to code, start coding
• Code carefully on the board, and try write clean code
• When you finish coding, explain it briefly
• He will ask you to analyse it, try to be smart and give him a proof for your analysis :).

Offer Time

• Congratulations ;) you made it!
• Reserve a Visa appointment
• Read the contract carefully, and discuss it with the recruiter
• Ask for relocation package
• Negotiate your salary
• Accept the offer
• Prepare your papers
• Good bye, don't come back :)

I hope you liked the post, please leave a comment and share it.

Project Lombok

Lombok  is a plugin that Java developers can use to save time and effort writing repeated code like one we see in data classes. I will describe it with examples and will include a link to video and the project site to download and try.

Consider the following data class Student which has some attributes and access to it Getters/Setters.

Too much code for a data class :-S

Look at Lombok and what it can do :-P


You can also control if you want only getters or setters using the @Getter and @Setter annotation before each attribute.


Now the code looks more pretty and readable as a data class. It has lots of other useful annotations that will save you lots of repeated code.

For example you can look at the @Cleanup annotation and what it does.

References:

• Project Lombok homepage 
• Intellij Lombok plugin