HackerRank: Modified Kaprekar Numbers


A modified Kaprekar number is a positive whole number n with d digits, such that when we split its square into two pieces – a right hand piece r with d digits and a left hand piece l that contains the remaining d or d1 digits, the sum of the pieces is equal to the original number (i.e. l + r = n).

Note: r may have leading zeros.

Here’s an explanation from Wikipedia about the ORIGINAL Kaprekar Number (spot the difference!): In mathematics, a Kaprekar number for a given base is a non-negative integer, the representation of whose square in that base can be split into two parts that add up to the original number again. For instance, 45 is a Kaprekar number, because 45² = 2025 and 20+25 = 45.

The Task
You are given the two positive integers p and q, where p is lower than q. Write a program to determine how many Kaprekar numbers are there in the range between p and q (both inclusive) and display them all.

Input Format

There will be two lines of input: p, lowest value q, highest value


Output Format

Output each Kaprekar number in the given range, space-separated on a single line. If no Kaprekar numbers exist in the given range, print INVALID RANGE.

Sample Input


Sample Output

1 9 45 55 99


1, 9, 45, 55, and 99 are the Kaprekar Numbers in the given range.


HackerRank: Paint The Tiles


Nikita has a line of N tiles indexed from 0 to N−1. She wants to paint them to match a color configuration, C, which is comprised of 2 colors: Red(R) and Blue(B)

In one stroke, Nikita can paint 1 or more adjacent tiles a single color. After she finishes painting, each tile(i) should be painted color C(i).

It should be noted that it is not allowed to apply more than 1 stroke on a tile.

Given the required color configuration, find and print the minimum number of strokes required for Nikita to paint all N tiles.

Note: In a line of tiles, 2 tiles with the indices i and j are considered adjacent only if |ji|=1.

Input Format

The first line contains a single integer, N, denoting the number of tiles to be painted.
The second line contains a string, C, denoting the desired color configuration.

For each character C(i) in C:

  • If C(i)=“R”, it means the ith tile must be painted red.
  • If C(i)=“B”, it means the ith tile must be painted blue.


  • 1N1000
  • C(i){“R”, “B”}

Output Format

Print the minimum number of strokes required to paint all tiles in the desired color configuration.

Sample Input 0


Sample Output 0


Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2



Sample Case 0:

Nikita will paint all 5 consecutive tiles red in a single stroke:

Sample Case 1:

Nikita will need 3 strokes to paint all 5 tiles:


HackerRank: The Time in Words


Given the time in numerals we may convert it into words, as shown below:

5:00 → five o’ clock
5:01 → one minute past five
5:10 → ten minutes past five
5:30 → half past five
5:40 → twenty minutes to six
5:45 → quarter to six
5:47 → thirteen minutes to six
5:28 → twenty eight minutes past five

Write a program which prints the time in words for the input given in the format mentioned above.

Input Format

There will be two lines of input:
H, representing the hours
M, representing the minutes


Output Format

Display the time in words.

Sample Input


Sample Output

thirteen minutes to six



HackerRank: Taum and B’day


Taum is planning to celebrate the birthday of his friend, Diksha. There are two types of gifts that Diksha wants from Taum: one is black and the other is white. To make her happy, Taum has to buy B number of black gifts and W number of white gifts.

  • The cost of each black gift is X units.
  • The cost of every white gift is Y units.
  • The cost of converting each black gift into white gift or vice versa is Z units.

Help Taum by deducing the minimum amount he needs to spend on Diksha’s gifts.

Input Format

The first line will contain an integer T which will be the number of test cases.
There will be T pairs of lines. The first line of each test case will contain the values of integers B and W. Another line of each test case will contain the values of integers X, Y, and Z.


Output Format

T lines, each containing an integer: the minimum amount of units Taum needs to spend on gifts.

Sample Input

10 10
1 1 1
5 9
2 3 4
3 6
9 1 1
7 7
4 2 1
3 3
1 9 2

Sample Output



  • Sample Case #01: There is no benefit to converting the white gifts into black or the black gifts into white, so Taum will have to buy each gift for 1 unit. So cost of buying all gifts will be: 101+101=20.
  • Sample Case #02: Again, we can’t decrease the cost of black or white gifts by converting colors. We will buy gifts at their original price. So cost of buying all gifts will be: 52+93=10+27=37.
  • Sample Case #03: We will buy white gifts at their original price, 1. For black gifts, we will first buy white one and color them to black, so that their cost will be reduced to 1+1=2. So cost of buying all gifts will be: 32+61=12.
  • Sample Case #04: Similarly, we will buy white gifts at their original price, 2. For black gifts, we will first buy white one and color them to black, so that their cost will be reduced to 2+1=3. So cost of buying all gifts will be: 73+72=35.
  • Sample Case #05: We will buy black gifts at their original price, 1. For white gifts, we will first black gifts worth 1 unit and color them to white with another 2 units, so cost for white gifts is reduced to 3 units. So cost of buying all gifts will be: 31+33=3+9=12.


HackerRank: Extra Long Factorials


You are given an integer N. Print the factorial of this number.


Input consists of a single integer N, where 1N100.

Print the factorial of N.

For an input of 25, you would print 15511210043330985984000000

Note: Factorials of N>20 can’t be stored even in a 64bit long long variable. Big integers must be used for such calculations. Languages like Java, Python, Ruby etc. can handle big integers, but we need to write additional code in C/C++ to handle huge values.

We recommend solving this challenge using BigIntegers.



HackerRank: ACM ICPC Team


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.


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

Sample Output



(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.


HackerRank: Lisa’s Workbook


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.


  • 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



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.


HackerRank: Manasa and Stones


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.


Sample Input


Sample Output

2 3 4 
30 120 210 300 


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.


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


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.


  • 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

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

Sample Output



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.