HackerRank: Alternating Characters

Problem

Shashank likes strings in which consecutive characters are different. For example, he likes ABABA, while he doesn’t like ABAA. Given a string containing characters A and B only, he wants to change it into a string he likes. To do this, he is allowed to delete the characters in the string.

Your task is to find the minimum number of required deletions.

Input Format

The first line contains an integer T, i.e. the number of test cases.
The next T lines contain a string each.

Output Format

For each test case, print the minimum number of deletions required.

Constraints

1T10
1≤ length of string 10^5

Sample Input

5
AAAA
BBBBB
ABABABAB
BABABA
AAABBB

Sample Output

3
4
0
0
4

Explanation

AAAA A, 3 deletions
BBBBB B, 4 deletions
ABABABAB ABABABAB, 0 deletions
BABABA BABABA, 0 deletions
AAABBB AB, 4 deletions because to convert it to AB we need to delete 2 A’s and 2 B’s

Solution

HackerRank: Modified Kaprekar Numbers

Problem:

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

Constraints:
0<p<q<100000

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

1
100

Sample Output

1 9 45 55 99

Explanation

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

Solution

HackerRank: Paint The Tiles

Problem

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.

Constraints

  • 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

5  
RRRRR

Sample Output 0

1

Sample Input 1

5  
RRBRR

Sample Output 1

3

Sample Input 2

5  
BRBRB

Sample Output 2

5

Explanation

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:

Solution: 

HackerRank: The Time in Words

Problem

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

Constraints
1H<12
0M<60

Output Format

Display the time in words.

Sample Input

5  
47  

Sample Output

thirteen minutes to six

Solution

 

HackerRank: Taum and B’day

Problem

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.

Constraints
1T10
0X,Y,Z,B,W10^9

Output Format

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

Sample Input

5
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

20
37
12
35
12

Explanation

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

Solution

HackerRank: Extra Long Factorials

Problem

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

N!=N×(N1)×(N2)××3×2×1

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

Output
Print the factorial of N.

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

Solution

 

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