HackerRank: Continuous Sequence Sum Test

Question:

Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T
Example

[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7


Solution

HackerRank: BotClean

Problem Statement

The goal of Artificial Intelligence is to create a rational agent (Artificial Intelligence 1.1.4). An agent gets input from the environment through sensors and acts on the environment with actuators. In this challenge, you will program a simple bot to perform the correct actions based on environmental input.

Meet the bot MarkZoid. It’s a cleaning bot whose sensor is a head mounted camera and whose actuators are the wheels beneath it. It’s used to clean the floor.

The bot here is positioned at the top left corner of a 5*5 grid. Your task is to move the bot to clean all the dirty cells.

Input Format

The first line contains two space separated integers which indicate the current position of the bot.
The board is indexed using Matrix Convention
5 lines follow representing the grid. Each cell in the grid is represented by any of the following 3 characters: ‘b’ (ascii value 98) indicates the bot’s current position, ‘d’ (ascii value 100) indicates a dirty cell and ‘-‘ (ascii value 45) indicates a clean cell in the grid.

Note If the bot is on a dirty cell, the cell will still have ‘d’ on it.

Output Format

The output is the action that is taken by the bot in the current step, and it can be either one of the movements in 4 directions or cleaning up the cell in which it is currently located. The valid output strings are LEFT, RIGHT, UP and DOWN or CLEAN. If the bot ever reaches a dirty cell, output CLEAN to clean the dirty cell. Repeat this process until all the cells on the grid are cleaned.

Sample Input #00

0 0
b---d
-d--d
--dd-
--d--
----d

Sample Output #00

RIGHT

Resultant state

-b--d
-d--d
--dd-
--d--
----d

Sample Input #01

0 1
-b--d
-d--d
--dd-
--d--
----d

Sample Output #01

DOWN

Resultant state

----d
-d--d
--dd-
--d--
----d

Task

Complete the function next_move that takes in 3 parameters posr, posc being the co-ordinates of the bot’s current position and board which indicates the board state to print the bot’s next move.

The codechecker will keep calling the function next_move till the game is over or you make an invalid move.

Scoring

Your score is (200 – number of moves the bot makes)/40. CLEAN is considered a move as well.

Once you submit, your bot will be played on four grids with three of the grid configurations unknown to you. The final score will be the sum of the scores obtained in each of the four grids.

Education Links

Solution

HackerRank: Remove Duplicate Elements from a Linked list

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3..

Solution

HackerRank: Same Tree problem

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

Example :

Input :

    1        1
/ \     / \
2   3   2 3

Output :
1 or True

Array Rotation: bug detection

The following code is supposed to rotate the array A by B positions.

So, for example,

A : [1 2 3 4 5 6]
B : 1

The output :

[2 3 4 5 6 1]

However, there is a small bug in the problem. Fix the bug and submit the problem.

Color Sort Problem

Given an array with n objects colored red, white or blue,
sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: Using library sort function is not allowed.

Example :

Input : [0 1 2 0 1 2]
Modify array so that it becomes : [0 0 1 1 2 2]

Solution

GCD algorithm in Java

Given 2 non negative integers m and n, find gcd(m, n)

GCD of 2 integers m and n is defined as the greatest integer g such that g is a divisor of both m and n.
Both m and n fit in a 32 bit signed integer.

Example

m : 6
n : 9

GCD(m, n) : 3

NOTE : DO NOT USE LIBRARY FUNCTIONS

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:

HackerRank: DynamicArray

Problem Statement

There are N sequences. All of them are initially empty, and you are given a variable lastans = 0. You are given Q queries of two different types:

  • 1 x y” – Insert y at the end of the ((x XOR lastans) mod N)th sequence.
  • 2 x y” – Print the value of the (y mod size)th element of the ((x XOR lastans) mod N)th sequence. Here, $size$ denotes the size of the related sequence. Then, assign this integer to lastans.

Note: You may assume that, for the second type of query, the related sequence will not be an empty sequence. Sequences and the elements of each sequence are indexed by zero-based numbering.

You can get more information about XOR from Wikipedia. It is defined as ^ in most of the modern programming languages.

Input Format

The first line consists of $N$, number of sequences, and $Q$, number of queries, separated by a space. The following $Q$ lines contains one of the query types described above.

Constraints
1 < N,Q < 10^5
0 < x < 10^9
0 < y < 10^9

Output Format

For each query of type two, print the answer on a new line.

Sample Input

2 5
1 0 5
1 1 7
1 0 3
2 1 0
2 1 1

Sample Output

7
3

Explanation

The first sequence is 5, 3 and the second sequence is 7.

Solution: