HackerRank: Manasa and Stones

Problem

Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either a or b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

Note: The numbers on the stones are in increasing order.

Input Format
The first line contains an integer T, i.e. the number of test cases. T test cases follow; each has 3 lines. The first line contains nn (the number of stones). The second line contains a, and the third line contains b.

Output Format
Space-separated list of numbers which are the possible values of the last stone in increasing order.

Constraints
1T10
1n,a,b10^3

Sample Input

2
3 
1
2
4
10
100

Sample Output

2 3 4 
30 120 210 300 

Explanation

All possible series for the first test case are given below:

  1. 0,1,2
  2. 0,1,3
  3. 0,2,3
  4. 0,2,4

Hence the answer 2 3 4.

Series with different number of final steps for second test case are the following:

  1. 0, 10, 20, 30
  2. 0, 10, 20, 120
  3. 0, 10, 110, 120
  4. 0, 10, 110, 210
  5. 0, 100, 110, 120
  6. 0, 100, 110, 210
  7. 0, 100, 200, 210
  8. 0, 100, 200, 300

Hence the answer 30 120 210 300.

Solution

Original solution source

System Design Interview Prep Material

System design is a very broad topic. Even a software engineer with many years of working experience at top IT company may not be an expert on system design. If you want to become an expert, you need to read many books, articles, and solve real large scale system design problems. This repository only teaches you to handle the system design interview with a systematic approach in a short time. You can dive into each topic if you have time. Of course, welcome to add your thoughts!

Table of Contents

System Design Interview Tips:

  • Clarify the constraints and identify the user cases Spend a few minutes questioning the interviewer and agreeing on the scope of the system. Remember to make sure you know all the requirements the interviewer didn’t tell your about in the beginning. User cases indicate the main functions of the system, and constraints list the scale of the system such as requests per second, requests types, data written per second, data read per second.
  • High-level architecture design Sketch the important components and the connections between them, but don’t go into some details. Usually, a scalable system includes web server (load balancer), service (service partition), database (master/slave database cluster plug cache).
  • Component design For each component, you need to write the specific APIs for each component. You may need to finish the detailed OOD design for a particular function. You may also need to design the database schema for the database.

Basic Knowledge about System Design:

Here are some articles about system design related topics.

Of course, if you want to dive into system related topics, here is a good collection of reading list about services-engineering, and a good collection of material about distributed systems.

Company Engineering Blogs:

If you are going to have an onsite with a company, you should read their engineering blog.

Products and Systems:

The following papers/articles/slides can help you to understand the general design idea of different real products and systems.

Hot Questions and Reference:

There are some good references for each question. The references here are slides and articles.
Design a CDN network Reference:

Design a Google document system Reference:

Design a random ID generation system Reference:

Design a key-value database Reference:

Design the Facebook news feed function Reference:

Design the Facebook timeline function Reference:

Design a function to return the top k requests during past time interval Reference:

Design an online multiplayer card game Reference:

Design a graph search function Reference:

Design a picture sharing system Reference:

Design a search engine Reference:

Design a recommendition system Reference:

Design a tinyurl system Reference:

Design a garbage collection system Reference:

Design a scalable web crawling system Reference:

Design the Facebook chat function Reference:

Design a trending topic system Reference:

Design a cache system Reference:

Good Books:

Object Oriented Design:

Tips for OOD Interview

Clarify the scenario, write out user cases Use case is a description of sequences of events that, taken together, lead to a system doing something useful. Who is going to use it and how they are going to use it. The system may be very simple or very complicated. Special system requirements such as multi-threading, read or write oriented.
Define objects Map identity to class: one scenario for one class, each core object in this scenario for one class. Consider the relationships among classes: certain class must have unique instance, one object has many other objects (composition), one object is another object (inheritance). Identify attributes for each class: change noun to variable and action to methods. Use design patterns such that it can be reused in multiple applications.

Useful Websites

Original Source

Unirest: Lightweight HTTP Request Client Libraries

UniRest

Unirest is a set of lightweight HTTP libraries available in multiple languages, built and maintained by the Mashape team.

Unirest.post("http://httpbin.org/post")
  .queryString("name", "Mark")
  .field("last", "Polo")
  .asJson()

Features

  • Make GET, POST, PUT, PATCH, DELETE, HEAD, OPTIONS requests
  • Both syncronous and asynchronous (non-blocking) requests
  • It supports form parameters, file uploads and custom body entities
  • Easily add route parameters without ugly string concatenations
  • Supports gzip
  • Supports Basic Authentication natively
  • Customizable timeout, concurrency levels and proxy settings
  • Customizable default headers for every request (DRY)
  • Customizable HttpClient and HttpAsyncClient implementation
  • Automatic JSON parsing into a native object for JSON responses
  • Customizable binding, with mapping from response body to java Object

Installing

Is easy as pie. Kidding. It’s about as easy as doing these little steps:

With Maven

You can use Maven by including the library:

<dependency>
    <groupId>com.mashape.unirest</groupId>
    <artifactId>unirest-java</artifactId>
    <version>1.4.7</version>
</dependency>

There are dependencies for Unirest-Java, these should be already installed, and they are as follows:

<dependency>
  <groupId>org.apache.httpcomponents</groupId>
  <artifactId>httpclient</artifactId>
  <version>4.3.6</version>
</dependency>
<dependency>
  <groupId>org.apache.httpcomponents</groupId>
  <artifactId>httpasyncclient</artifactId>
  <version>4.0.2</version>
</dependency>
<dependency>
  <groupId>org.apache.httpcomponents</groupId>
  <artifactId>httpmime</artifactId>
  <version>4.3.6</version>
</dependency>
<dependency>
  <groupId>org.json</groupId>
  <artifactId>json</artifactId>
  <version>20140107</version>
</dependency>

If you would like to run tests, also add the following dependency along with the others:

<dependency>
  <groupId>junit</groupId>
  <artifactId>junit</artifactId>
  <version>4.11</version>
  <scope>test</scope>
</dependency>
<dependency>
  <groupId>commons-io</groupId>
  <artifactId>commons-io</artifactId>
  <version>2.4</version>
  <scope>test</scope>
</dependency>

Without Maven

Alternatively if you don’t use Maven, you can directly include the JAR file in the classpath:http://oss.sonatype.org/content/repositories/releases/com/mashape/unirest/unirest-java/1.4.7/unirest-java-1.4.7.jar

Don’t forget to also install the dependencies (org.json, httpclient 4.3.6, httpmime 4.3.6,httpasyncclient 4.0.2) in the classpath too.

There is also a way to generate a Unirest-Java JAR file that already includes the required dependencies, but you will need Maven to generate it. Follow the instructions at http://blog.mashape.com/post/69117323931/installing-unirest-java-with-the-maven-assembly-plugin

Creating Request

So you’re probably wondering how using Unirest makes creating requests in Java easier, here is a basic POST request that will explain everything:

HttpResponse<JsonNode> jsonResponse = Unirest.post("http://httpbin.org/post")
  .header("accept", "application/json")
  .queryString("apiKey", "123")
  .field("parameter", "value")
  .field("foo", "bar")
  .asJson();

Requests are made when as[Type]() is invoked, possible types include Json, Binary, String, Object.

If the request supports and it is of type HttpRequestWithBody, a body it can be passed along with.body(String|JsonNode|Object). For using .body(Object) some pre-configuration is needed (see below).

If you already have a map of parameters or do not wish to use seperate field methods for each one there is a.fields(Map<String, Object> fields) method that will serialize each key – value to form parameters on your request.

.headers(Map<String, String> headers) is also supported in replacement of multiple header methods.

Full Documentation @ unirest.io

jSoup: Java HTML Parser

jsoup is a Java library for working with real-world HTML. It provides a very convenient API for extracting and manipulating data, using the best of DOM, CSS, and jquery-like methods.

jsoup implements the WHATWG HTML5 specification, and parses HTML to the same DOM as modern browsers do.

  • scrape and parse HTML from a URL, file, or string
  • find and extract data, using DOM traversal or CSS selectors
  • manipulate the HTML elements, attributes, and text
  • clean user-submitted content against a safe white-list, to prevent XSS attacks
  • output tidy HTML

jsoup is designed to deal with all varieties of HTML found in the wild; from pristine and validating, to invalid tag-soup; jsoup will create a sensible parse tree.

Example

Fetch the Wikipedia homepage, parse it to a DOM, and select the headlines from theIn the news section into a list of Elements (online sample):

Document doc = Jsoup.connect("http://en.wikipedia.org/").get();
Elements newsHeadlines = doc.select("#mp-itn b a");

Open source

jsoup is an open source project distributed under the liberal MIT license. The source code is available at GitHub.

Getting started

  1. Download the jsoup jar (version 1.8.3)
  2. Read the cookbook introduction
  3. Enjoy!

Resources

HackerRank: Find Single Integer out of an Array

Problem Statement

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example :

Input : [1 2 2 3 1]
Output : 3

Solution

Logic:

The basic logic that A XOR A = 0 means that means all the doubles will be XOR’ed out to 0 and the remaining number will be the result of the XOR.

HackerRank: Sherlock and The Beast

Problem Statement

Sherlock Holmes suspects his archenemy, Professor Moriarty, is once again plotting something diabolical. Sherlock’s companion, Dr. Watson, suggests Moriarty may be responsible for MI6’s recent issues with their supercomputer, The Beast.

Shortly after resolving to investigate, Sherlock receives a note from Moriarty boasting about infecting The Beastwith a virus; however, he also gives him a clue—a number, NN. Sherlock determines the key to removing the virus is to find the largest Decent Number having NN digits.

A Decent Number has the following properties:

  1. Its digits can only be 3‘s and/or 5‘s.
  2. The number of 3‘s it contains is divisible by 5.
  3. The number of 5‘s it contains is divisible by 3.
  4. If there are more than one such number, we pick the largest one.

Moriarty’s virus shows a clock counting down to The Beast‘s destruction, and time is running out fast. Your task is to help Sherlock find the key before The Beast is destroyed!

Constraints
1T201≤T≤20
1N1000001≤N≤100000

Input Format

The first line is an integer, TT, denoting the number of test cases.

The TT subsequent lines each contain an integer, NN, detailing the number of digits in the number.

Output Format

Print the largest Decent Number having NN digits; if no such number exists, tell Sherlock by printing -1.

Sample Input

4
1
3
5
11

Sample Output

-1
555
33333
55555533333

Explanation

For N=1, there is no decent number having 1 digit (so we print 1−1).
For N=3, 555 is the only possible number. The number 5 appears three times in this number, so our count of 5‘s is evenly divisible by 3 (Decent Number Property 3).
For N=5, 33333 is the only possible number. The number 3 appears five times in this number, so our count of 3‘s is evenly divisible by 5 (Decent Number Property 2).
For N=11, 55555533333 and all permutations of these digits are valid numbers; among them, the given number is the largest one.

Solution:

Easy Rules: Java™ rules engine

Easy Rules is a Java rules engine inspired by an article called Should I use a Rules Engine? by Martin Fowler in which he says:

You can build a simple rules engine yourself. All you need is to create a bunch of objects with conditions and actions, store them in a collection, and run through them to evaluate the conditions and execute the actions.

Core features

  • Lightweight library and easy to learn API
  • POJO based development with annotation programming model
  • Useful abstractions to define business rules and apply them easily with Java
  • The ability to create composite rules from primitive ones
  • Dynamic rule configuration at runtime using JMX

Example

Hello World tutorial

This tutorial shows how to use Easy Rules in a very simple application. The goal is to ask the user if he is a friend of duke and says ‘Hello duke’s friend!’ only if he replies ‘yes’.

Based on this requirement, the rule is pretty straightforward :

  • The condition is that the user input must be equal to ‘yes’
  • The action is to say ‘Hello duke’s friend!’ to the user

First, let’s create a rule class:

@Rule(name = "Hello World rule",
    description = "Say Hello to duke's friends only")
public class HelloWorldRule {

    /**
     * The user input which represents the data
     * that the rule will operate on.
     */
    private String input;

    @Condition
    public boolean checkInput() {
        //The rule should be applied only if
        //the user's response is yes (duke friend)
        return input.equalsIgnoreCase("yes");
    }

    @Action
    public void sayHelloToDukeFriend() throws Exception {
        //When rule conditions are satisfied,
        //prints 'Hello duke's friend!' to the console
        System.out.println("Hello duke's friend!");
    }

    public void setInput(String input) {
        this.input = input;
    }

}

Then, we have to register an instance of this rule in a Easy Rules engine and launch the tutorial with the following class:

public class Launcher {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.println("Are you a friend of duke?[yes/no]:");
        String input = scanner.nextLine();

        /**
         * Declare the rule
         */
        HelloWorldRule helloWorldRule = new HelloWorldRule();

        /**
         * Set business data to operate on
         */
        helloWorldRule.setInput(input.trim());

        /**
         * Create a rules engine and register the business rule
         */
        RulesEngine rulesEngine = aNewRulesEngine().build();

        rulesEngine.registerRule(helloWorldRule);

        /**
         * Fire rules
         */
        rulesEngine.fireRules();

    }
}

You would get the following output:

Are you a friend of duke? [yes/no]:
yes
INFO: Rule 'Hello World rule' triggered.
Hello duke's friend!
INFO: Rule 'Hello World rule' performed successfully.

Source

Local Mail Server With HMailServer

When we write code to push out emails to our customers or visitors, we want to be confident it’s going to arrive at the destination, looking the way we expect.

Most local windows server setups with XAMPP or WAMP won’t by default be setup with a mail server and setting one up can be a pain.

Luckily hMailServer is an option that you may want to try out

hMailServer

This quick step-by-step guide should get you up and running with local mail functionality and a test script in under 20 minutes.

Start by going to www.hmailserver.com, click download in the menu and choose the latest build (hMailServer 5.6.4 – Build 2283).

Browse to the download location and open the exe file.

Follow Next as shown:

 

 

For testing the Mail You can follow the following tutorial

Gearman

What is Gearman?

Gearman provides a generic application framework to farm out work to other machines or processes that are better suited to do the work. It allows you to do work in parallel, to load balance processing, and to call functions between languages. It can be used in a variety of applications, from high-availability web sites to the transport of database replication events. In other words, it is the nervous system for how distributed processing communicates. A few strong points about Gearman:

  • Open Source It’s free! (in both meanings of the word) Gearman has an active open source community that is easy to get involved with if you need help or want to contribute. Worried about licensing? Gearman is BSD.
  • Multi-language – There are interfaces for a number of languages, and this list is growing. You also have the option to write heterogeneous applications with clients submitting work in one language and workers performing that work in another.
  • Flexible – You are not tied to any specific design pattern. You can quickly put together distributed applications using any model you choose, one of those options being Map/Reduce.
  • Fast – Gearman has a simple protocol and interface with an optimized, and threaded, server written in C/C++ to minimize your application overhead.
  • Embeddable – Since Gearman is fast and lightweight, it is great for applications of all sizes. It is also easy to introduce into existing applications with minimal overhead.
  • No single point of failure – Gearman can not only help scale systems, but can do it in a fault tolerant way.
  • No limits on message size – Gearman supports single messages up to 4gig in size. Need to do something bigger? No problem Gearman can chunk messages.
  • Worried about scaling? – Don’t worry about it with Gearman. Craig’s List, Tumblr, Yelp, Etsy,… discover what others have known for years.

Content is being updated regularly, so please check back often. You may also want to check out other forms of communication if you would like to learn more or get involved!

How Does Gearman Work?

Gearman
Gearman Architecture

A Gearman powered application consists of three parts: a client, a worker, and a job server. The client is responsible for creating a job to be run and sending it to a job server. The job server will find a suitable worker that can run the job and forwards the job on. The worker performs the work requested by the client and sends a response to the client through the job server. Gearman provides client and worker APIs that your applications call to talk with the Gearman job server (also known as gearmand) so you don’t need to deal with networking or mapping of jobs. Internally, the Gearman client and worker APIs communicate with the job server using TCP sockets. To explain how Gearman works in more detail, lets look at a simple application that will reverse the order of characters in a string. The example is given in PHP, although other APIs will look quite similar.

How Is Gearman Useful?

Gearman
Gearman Working

You can use Gearman as an interface between a client and a worker written in different languages. If you want your PHP web application to call a function written in C, you could use the PHP client API with the C worker API, and stick a job server in the middle.

Gearman can also be useful when the worker code is put on a separate machine (or cluster of machines) that are better suited to do the work.
Say your PHP web application wants to do image conversion, but this is too much processing to run it on the web server machines.
You could instead ship the image off to a separate set of worker machines to do the conversion, this way the load does not impact the performance of your web server and other PHP scripts. By doing this, you also get a natural form of load balancing since the job server only sends new jobs to idle workers. If all the workers running on a given machine are busy, you don’t need to worry about new jobs being sent there. This makes scale-out with multi-core servers quite simple. You may have 16 cores on a worker machine. Start up 16 instances of your worker (or perhaps more if they are not CPU bound). It is also seamless to add new machines to expand your worker pool, just boot them up, install the worker code, and have them connect to the existing job server.

For more details on specific uses and installations, go to Gearman’s examples page.

Color Thief

A script for grabbing the color palette from an image.
Uses JavaScript and the canvas tag to make it happen.

How to use

Get the dominant color from an image

var colorThief = new ColorThief();
colorThief.getColor(sourceImage);
getColor(sourceImage[, quality])
returns {r: num, g: num, b: num}

Build a color palette from an image

In this example, we build an 8 color palette.

var colorThief = new ColorThief();
colorThief.getPalette(sourceImage, 8);
getPalette(sourceImage[, colorCount, quality])
returns [ [num, num, num], [num, num, num], ... ]

Demo More from Original Author