HackerRank: ACM ICPC Team

Problem

You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.

Note Suppose a, b, and c are three different people, then (a,b) and (b,c) are counted as two different teams.

Input Format

The first line contains two integers, N and M, separated by a single space, where N represents the number of people, and M represents the number of topics. N lines follow.
Each line contains a binary string of length M. If the ith line’s jth character is 11, then the ith person knows the jth topic; otherwise, he doesn’t know the topic.

Constraints
2N500
1M500

Output Format

On the first line, print the maximum number of topics a 2-person team can know.
On the second line, print the number of 2-person teams that can know the maximum number of topics.

Sample Input

4 5
10101
11100
11010
00101

Sample Output

5
2

Explanation

(1, 3) and (3, 4) know all the 5 topics. So the maximal topics a 2-person team knows is 5, and only 2 teams can achieve this.

Solution

HackerRank: Lisa’s Workbook

Problem

Lisa just got a new math workbook. A workbook contains exercise problems, grouped into chapters.

  • There are n chapters in Lisa’s workbook, numbered from 1 to n.
  • The i-th chapter has ti problems, numbered from 1 to ti.
  • Each page can hold up to k problems. There are no empty pages or unnecessary spaces, so only the last page of a chapter may contain fewer than k problems.
  • Each new chapter starts on a new page, so a page will never contain problems from more than one chapter.
  • The page number indexing starts at 1.

Lisa believes a problem to be special if its index (within a chapter) is the same as the page number where it’s located. Given the details for Lisa’s workbook, can you count its number of special problems?

Note: See the diagram in the Explanation section for more details.

Input Format

The first line contains two integers n and k — the number of chapters and the maximum number of problems per page respectively.
The second line contains n integers t1,t2,,tn where ti denotes the number of problems in the ii-th chapter.

Constraints

  • 1n,k,ti100

Output Format

Print the number of special problems in Lisa’s workbook.

Sample Input

5 3  
4 2 6 1 10

Sample Output

4

Explanation

The diagram below depicts Lisa’s workbook with n=chapters and a maximum of k=3 problems per page. Special problems are outlined in red, and page numbers are in yellow squares.

There are 4 special problems and thus we print the number 4 on a new line.

Solution

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

HackerRank: CodeWhiz.java March 2016: Serve the Students

Problem

In this problem, there are 22 types of events: ENTER (a student enters the queue) or SERVED.

A unique token is assigned to any student entering the queue. The queue serves the students based on the following criteria:

  1. The student having the highest Cumulative Grade Point Average (CGPA) is served first.
  2. Any students having the same CGPA will be served by name in ascending case-sensitive alphabetical order.
  3. Any students having the same CGPA and name will be served in ascending token order.

Given a sequence of nn events, print the names of students who are yet to be served(based on above criteria). If the queue is empty, print EMPTY.

Input Format

The first line of input contains an integer, nn, denoting the total number of events. Each of the nn subsequent lines will be of the following two forms:

  1. ENTER name CGPA token – The student to be inserted into the priority queue.
  2. SERVED – The highest priority student in the queue was served.

Constraints

  • 2n1000
  • 0CGPA4.00 where CGPAR
  • 1token(i)10where each token(i) is a unique integer.
  • 2|name|30

Output Format

Print the names (based on the criteria) of the students who are not served at all after executing all n events; if every student in the queue was served, then print EMPTY.

Sample Input

12
ENTER John 3.75 50
ENTER Mark 3.8 24
ENTER Shafaet 3.7 35
SERVED
SERVED
ENTER Samiha 3.85 36
SERVED
ENTER Ashley 3.9 42
ENTER Maria 3.6 46
ENTER Anik 3.95 49
ENTER Dan 3.95 50
SERVED

Sample Output

Dan
Ashley
Shafaet
Maria

Explanation

Let’s call our queue Q.

n0: We add John to the empty queue.
Q0={(John, 3.75, 50)}

n1: We add Mark to the queue; Q1={(John, 3.75, 50),(Mark, 3.8, 24)

n2: We add Shafaet to the queue; Q2={(John, 3.75, 50),(Mark, 3.8, 24),(Shafaet, 3.7, 35)}

n3: Mark is served as he has the highest CGPA; P3={(John, 3.75, 50),(Shafaet, 3.7, 35)}

n4: John is served next as he has the highest CGPA; P4={(Shafaet, 3.7, 35)}

n5: We add Samiha to the queue; Q2={(Shafaet, 3.7, 35),(Samiha, 3.85, 36)}

n6: Samiha is served as she has the highest CGPA; P6={(Shafaet, 3.7, 35)}

n7 through n10, the next four students are added giving us:  Q10={(Shafaet, 3.7, 35),(Ashley, 3.9, 42),(Maria, 3.6, 46),(Anik, 3.95, 49),(Dan, 3.95, 50)}

n11: Anik is served because though both Anil and Dan have the highest CGPA but Anik comes first when sorted in alphabetic order; P11={(Dan, 3.95, 50),(Ashley, 3.9, 42),(Shafaet, 3.7, 35),(Maria, 3.6, 46)}

As all events are completed, we print names of each remaining students on a new line.

Solution

 

HackerRank: CodeWhiz.java March 2016: Maximum and Minimum

Problem

The locked code in your editor passes array A (of size N) and index i to the print method, whose try block attempts to print element A[i]; if i is Out-of-Range, an Array Index Out Of Bounds Exception is thrown.

Complete the code in your editor so that it prints the maximum and minimum elements in array A—regardless of whether or not an exception is thrown.

Input Format

The first line contains an integer, N, the number of elements in A.
The second line contains N space-separated integers describing A.
The third line contains an index, i, to be accessed.

Note: Input from stdin handled by the locked code in the editor.

Constraints

  • 1N100
  • 1000Aj1000 where 1jN

Output Format

The try block will print the value accessed at A[i]; if an Exception is thrown, it will be printed by the locked code in your editor.
You must print the respective maximum and minimum values in array A as a single pair of space-separated integers on a new line—regardless of whether an exception is thrown.

Note: Observe that your max/min values may print on either the first or second line, depending on whether or not an Exception was thrown!

Sample Input 0

12
-12 0 1 -899 23 45 96 10 75 23 0 33
100

Sample Output 0

96 -899
java.lang.ArrayIndexOutOfBoundsException

Sample Input 1

10
4 908 -05 445 -208 325 -2 -718 863 400
9   

Sample Output 1

400
908 -718

Explanation

Sample 0:
N=12, i=100, maximum(A)=96, and minimum(A)=899
A‘s indices range from 0 to 11, so attempting to access index 100 throws an Exception. The maximum and minimum values in the array are printed on a new line as a pair of space-separated integers. The program’s control flow then returns to main where the the Exception is caught and printed on a new line.

Sample 1:
N=10, i=9, maximum(A)=908, and minimum(A)=718
A‘s indices range from 0 to 9, so an attempt to access index 9 will be successful and the value at A[9] (i.e.: 400) is printed on a new line. The program’s control flow then proceeds to print the maximum and minimum values in A as a pair of space-separated integers on a new line.

Solution

HackerRank: CodeWhiz.java March 2016: Java Singleton

Problem

“The singleton pattern is a design pattern that restricts the instantiation of a class to one object. This is useful when exactly one object is needed to coordinate actions across the system.”
Wikipedia: Singleton Pattern


Complete the Singleton class in your editor which contains the following components:

  1. A private Singleton non parameterized constructor.
  2. A public String instance variable named strstr.
  3. Write a static method named getSingleInstance that returns the single instance of theSingleton class.

Once submitted, our hidden Solution class will check your code by taking a String as input and then using yourSingleton class to print a line.

Input Format

You will not be handling any input in this challenge.

Output Format

You will not be producing any output in this challenge.

Sample Input

hello world

Sample Output

Hello I am a singleton! Let me say hello world to you

Solution

HackerRank: Library Fine

Problem:

The Head Librarian at a library wants you to create a program that calculates the fine for returning a book after the return date. You are given the actual and the expected return dates. Calculate the fine as follows:

  1. If the book is returned on or before the expected return date, no fine will be charged. In other words, the fine is 0.
  2. If the book is returned in the same calendar month as the expected return date, the fine = 15 Hackos × the number of late days.
  3. If the book is not returned in the same calendar month but in the same calendar year as the expected return date, the fine = 500 Hackos × the number of late months.
  4. If the book is not returned in the same calendar year, the fine is fixed at 10000 Hackos.

Input
You are given the actual and the expected return dates in D M Y format on two separate lines. The first line contains the D M Y values for the actual return date and the next line contains the D M values for the expected return date. Here’s a sample:

9 6 2015
6 6 2015

Constraints:
1D31
1M12
1Y3000
The given date is a valid date on a Gregorian calendar.

Output
Print a single value representing the fine.
The sample output for the above input would be 45.
Since the actual return date is 3 days later than expected, the fine is calculated as 15×3=45 Hackos.

Solution

HackerRank: Cavity Map

Problem

You are given a square map of size n×nn×n. Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has strictly smaller depth. Two cells are adjacent if they have a common side (edge).

You need to find all the cavities on the map and depict them with the uppercase character X.

Input Format

The first line contains an integer, nn, denoting the size of the map. Each of the following nn lines contains nnpositive digits without spaces. Each digit (1-9) denotes the depth of the appropriate area.

Constraints
1n1001≤n≤100

Output Format

Output nn lines, denoting the resulting map. Each cavity should be replaced with character X.

Sample Input

4
1112
1912
1892
1234

Sample Output

1112
1X12
18X2
1234

Explanation

The two cells with the depth of 9 fulfill all the conditions of the Cavity definition and have been replaced by X.

Solution

HackerRank: The Grid Search

Problem

Given a 2D array of digits, try to find the occurrence of a given 2D pattern of digits. For example, consider the following 2D matrix:

1234567890  
0987654321  
1111111111  
1111111111  
2222222222  

Assume we need to look for the following 2D pattern:

876543  
111111  
111111

If we scan through the original array, we observe that the 2D pattern begins at the second row and the third column of the larger grid (the 8 in the second row and third column of the larger grid is the top-left corner of the pattern we are searching for).

So, a 2D pattern of P digits is said to be present in a larger grid G, if the latter contains a contiguous, rectangular 2D grid of digits matching with the pattern P, similar to the example shown above.

Input Format
The first line contains an integer, T, which is the number of test cases. T test cases follow, each having a structure as described below:
The first line contains two space-separated integers, R and C, indicating the number of rows and columns in the grid G, respectively.
This is followed by R lines, each with a string of C digits, which represent the grid G.
The following line contains two space-separated integers, r and c, indicating the number of rows and columns in the pattern grid P.
This is followed by r lines, each with a string of c digits, which represent the pattern P.

Constraints
1T5
1R,r,C,c1000
1rR
1cC

Test Case Generation
Each individual test case has been generated by first specifying the size (R and C) of the large 2D matrix, and then randomly generating the digits in it. A limited number of digits in the larger matrix may be changed by the problem setter (no more than 5% of the total number of digits in the matrix). So the larger 2D matrix is almost-random. The pattern matrix has been manually-curated by the problem setter.

Output Format
Display ‘YES’ or ‘NO’, depending on whether (or not) you find that the larger grid GG contains the rectangular pattern PP. The evaluation will be case sensitive.

Sample Input

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

Sample Output

YES
NO

Explanation

The first test in the input file is:

10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530

As one may see, the given 2D grid is indeed present in the larger grid, as marked in bold below.

7283455864  
6731158619  
8988242643  
3830589324  
2229505813  
5633845374  
6473530293  
7053106601  
0834282956  
4607924137  

The second test in the input file is:

15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

The search pattern is:

99
99

This cannot be found in the larger grid.

Solution