Medium Programming Challenges

2048
Difficulty: Medium	Test Cases: 12	Published: 2020-01-11
Summary Compute the state of the 2048 puzzle after the player's move
Description 2048 is a sliding block puzzle game created by Gabriele Cirulli. The game is played on a 4 x 4 grid, which consists of numbered tiles. Numbers are powers of 2 in the range from 2 to 2048 inclusive. The goal of the game is to slide tiles on the grid to combine them into a tile with the number 2048. Every turn, the player slides all the tiles simultaneously in the chosen direction (left, right, up, or down). The tiles move as far as possible until they are stopped by either another tile or the border of the grid. If two tiles of the same number collide while moving, they will merge into a single tile with the total value of the two tiles that collided. The resulting tile cannot merge with another tile again in the same move. Note that if more than two tiles with the same numbers in one row are moved, the fusing process must be executed pairwise and starting from the grid's edge at the destination direction. For example, if the player moves the row 2 2 2 2 to the right the result will be 0 0 4 4. And if the player moves the row 4 0 4 4 to the left the result will be 8 4 0 0.
Input The first line of input contains one of the string values left, right, up, or down to describes the direction of the move requested by the player. The next four lines describe a valid state of the 2048 puzzle. Every line has four integers from the set {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024] and represents a corresponding row of the 4 x 4 grid. A cell with a zero is considered to be empty. For example: right 0 4 0 4 32 32 32 16 8 8 8 8 2 0 0 4
Output Four lines with four integers representing the puzzle's state after the player's move is completed. Integers in the line must be space-delimited. Empty cells in the grid are described with zeroes. In the real 2048 game, after each move, a new tile with a value of 2 or 4 will randomly appear in an empty cell. You can ignore this behavior in your solution and determine the state of the grid immediately before the new tile would appear. For example: 0 0 0 8 0 32 64 16 0 0 16 16 0 0 2 4

Academic Schedule
Difficulty: Medium	Test Cases: 12	Published: 2019-08-07
Summary Find a linear ordering of courses to meet prerequisites
Description Consider an academic program that consists of N courses. Every course is designated by an integer index from 0 to N - 1. Some courses have others as prerequisites. For example, if course 2 is a prerequisite of course 3 you must finish course 2 before enrolling in course 3. You can attend only a single course at a time. Build a schedule to complete all courses in a linear sequence and to satisfy all prerequisites for every course. If more than one variant of possible schedule exists, use the schedule where courses with smaller indices are finished first.
Input The first line contains a positive integer representing the number of courses in the academic program. Each additional line describes the prerequisites of a given course as a space-delimited set of indices. Every set of prerequisites has at least two indices. The first index in the set denotes the course for which a prerequisite exists. All other indices designate which courses are required for the first. For example: 4 1 0 2 0 3 1 2 The first row means that there are 4 courses in the academic program. The second and third rows define that course 0 must be taken before courses 1 and 2. And the fourth row defines that courses 1 and 2 must be taken before course 3.
Output A schedule containing a space-delimited list of courses, in the order of their attendance. For example: 0 1 2 3 For this example, another schedule exists 0 2 1 3. But we must select the variant 0 1 2 3 where course 1 (with a smaller index) is attended before course 2 (with a greater index).

Am I local?
Difficulty: Medium	Test Cases: 6	Published: 2019-04-02
Summary Perform a fundamental IPv4 routing check
Description A network block is defined by an IP address and a subnet mask. The mask value separates the network address from the internal address based on how many bits are hidden by the mask. For example, an 8-bit subnet mask is expressed as 255.0.0.0. An IP address of 10.21.8.15 with that mask applied reveals a network address of 10.0.0.0. Your challenge is to inspect an IP address and mask number, then decide if another IP address is on that local network. Considering the IP block 10.0.0.0 and a subnet mask of 255.0.0.0, we can represent this like so: 10.0.0.0/8 (this is called CIDR notation). As an example, the address 10.21.8.15 would be on the local network. The address 11.34.57.1 would not.
Input Two lines of input as follows: IPv4 Network block in standard CIDR notation IPv4 Address to Check
Output If the IP address is in the subnet defined by the CIDR, print "True". Otherwise, print "False".

Array Absurdity
Difficulty: Medium	Test Cases: 5	Published: 2012-10-08
Summary Determine if an array contains a duplicated entry
Description Imagine we have an immutable array of size N which we know to be filled with integers ranging from 0 to N-2, inclusive. Suppose we know that the array contains exactly one duplicated entry and that duplicate appears exactly twice. Find the duplicated entry.
Input Your program should read lines of text from standard input. Each line begins with a positive integer N, the size of the array, followed by a semicolon, followed by a comma separated list of positive numbers ranging from 0 to N-2, inclusive.
Output For each line of input, print to standard output the duplicated entry, each on its own line.

Balanced Smileys
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Facebook Hacker Cup 2013 problem.
Description Credits: This problem appeared in the Facebook Hacker Cup 2013 Hackathon. Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go :(. Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon. A message has balanced parentheses if it consists of one of the following: - An empty string "" - One or more of the following characters: 'a' to 'z', ' ' (a space) or ':' (a colon) - An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'. - A message with balanced parentheses followed by another message with balanced parentheses. - A smiley face ":)" or a frowny face ":(" Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.
Input Your program should read lines from standard input. Each line contains a message that you got from John.
Output Print out the string "YES"/"NO" (all quotes for clarity only) stating whether or not it is possible that the message had balanced parentheses.

Binary Coded Decimal - Decoding
Difficulty: Medium	Test Cases: 12	Published: 2019-07-15
Summary Decode the binary coded decimal (BCD) date and time
Description Imagine that you are prototyping an electronic device based on the Arduino platform and you are using a real-time clock (RTC) chip to get the current date and time. The microcontroller program reads the date and time from the RTC chip memory where it is stored as binary coded decimal (BCD) values. See the attachments tab for the format description. Note that the month can have less than 31 days (28 or 29 days for February, 30 days for April, June, September, and November). Write a program to convert date and time from BCD representation in the memory of the RTC chip to the string with its decimal representation. In the BCD code, every decimal digit is encoded with its four-bit binary value. Encoding all digits of the decimal number and concatenating the binary codes into one string you will get a resulting BCD code. In other words, each of two nibbles of each byte of the BCD code represents a decimal digit. For example, the number 17 can be represented like so: 0001 0111 1    7 17
Input A string with date and time in BCD bytes, starting from the most significant byte (year) and ending with the least significant byte (seconds). A space is used to separate four-bit nibbles in the BCD code and make it more readable. For example: 0001 0111 0000 0101 0010 1001 0000 0010 0000 0101 0100 1000 0011 0001
Output A string with the decimal representation of the date and time in the following format: HH:MM:SS [Day of the Week] [Date of the Month] Month Year An 'Error' string in the case of incorrect input. Hours, minutes, seconds and date of the moth are represented with two decimal digits each. The year is represented with four digits. For example: 05:48:31 Monday 29 May 2017
Attachments

Cash Register
Difficulty: Medium	Test Cases: 10	Published: 2012-10-08
Summary Determine the amount of change to be returned
Description The goal of this challenge is to design a cash register program. You will be given two decimal numbers. The first is the purchase price (PP) of the item. The second is the cash (CH) given by the customer. Your register currently has the following bills/coins within it: 'PENNY': .01, 'NICKEL': .05, 'DIME': .10, 'QUARTER': .25, 'HALF DOLLAR': .50, 'ONE': 1.00, 'TWO': 2.00, 'FIVE': 5.00, 'TEN': 10.00, 'TWENTY': 20.00, 'FIFTY': 50.00, 'ONE HUNDRED': 100.00 The aim of the program is to calculate the change that has to be returned to the customer.
Input Your program should read lines of text from standard input. Each line contains two numbers which are separated by a semicolon. The first is the Purchase price (PP) and the second is the cash(CH) given by the customer.
Output For each line of input print a single line to standard output which is the change to be returned to the customer. In case the CH < PP, print out ERROR. If CH == PP, print out ZERO. For all other cases print the amount that needs to be returned, in terms of the currency values provided. The output should be alphabetically sorted.

Chain Inspection
Difficulty: Medium	Test Cases: 11	Published: 2014-03-06
Summary Try to pass a chain
Description We use a special generator to produce chains of elements. Don't ask why we need them, we're not sure that somebody knows the answer for this question. A chain is represented by a string of name-address pairs. So the first element is the name of a pair and the second one (address) is pointing to the name of a next pair. E.g. BEGIN-3;4-2;3-4;2-END # GOOD 77-END;BEGIN-8;8-11;11-77 # GOOD In examples above we can pass through the chains from the 'BEGIN' to the 'END' without missing any single pair. In the first case we moved from 'BEGIN' to 3, from 3 to 4, from 4 to 2, from 2 to 'END'. In the second case we moved from 'BEGIN' to 8, from 8 to 11, from 11 to 77, from 77 to 'END'. Our generator was producing only good chains, but something went wrong and now it generates random chains and we are not sure if it's a good chain or a bad one. E.g. BEGIN-3;4-3;3-4;2-END # BAD 77-END;BEGIN-8;8-77;11-11 # BAD In the first case the 'END' is unreachable because we have a loop between 3 and 4. In the second case we can reach the 'END' but we missed one pair (11-11). We know that for a BAD chain the generator first produces a GOOD chain but after that it may replace existing address in some pairs with an address from another pair. It never replaces an address in a pair to an addresses which isn't present in the original chain. You can help us by writing a program that investigates the input and finds GOOD and BAD chains.
Input Your program should read lines from standard input. Each line is a chain. The pairs are separated by semicolon, the names and the address are separated by dash. The number of pairs in a chain is in range [1, 500]. The addresses are integers in range [2, 10000].
Output Print out the status of the chain (GOOD or BAD).

Christmas Lights
Difficulty: Medium	Test Cases: 8	Published: 2019-10-04
Summary Check if a net of Christmas lights is 2-colorable
Description Imagine that you are creating a net of LED lights for Christmas decorations. The net is made from lights of two possible colors, joined together with string. There is one rule for the design of the net: any given string must only connect lights of different colors. Write a program that checks if it's possible to assign one of the two colors for every light in a given layout of the net.
Input Each line describes one light in the net with a space-delimited set of integers of the adjacent lights. In other words, the set contains neighbors of the current light connected by a string. Lights are indexed from 0 to (n - 1). The first line of input corresponds to the light with index 0, the last line corresponds to the light with index (n - 1). Here is a sample description of a layout: 1 3 4 6 0 2 1 3 0 2 0 5 4 6 0 5 The first row means that the light with index 0 is connected with lights 1, 3, 4, and 6. The second row means that the light with index 1 is connected to lights 0 and 2, and so on. See the attachments tab for a diagram of this example
Output Print True if it's possible to select one of two colors for every light in the net such that adjacent lights always have different colors. Otherwise, print False.
Attachments

Collaborative Filtering
Difficulty: Medium	Test Cases: 5	Published: 2019-05-31
Summary Implement a simple collaborative filter counting inversions
Description A Recommender System is capable of predicting the preferences of an active user for a set of items. For example, an online store can suggest a product to the shopper based on a history of purchases or page views. One of the traditional approaches to construct such a system is to use Collaborative Filtering. It does not require any information about the items themselves and makes recommendations based on the past behavior of many users. Usually, collaborative filtering can be reduced to two steps: Look for users with similar interests as the active user Use ratings from the other users identified above to make a prediction for the active user Your task is to implement the first step using the number of inversions in the lists of user ratings as a numerical similarity measure. An Inversion is a pair of elements (Si, Sj) of the sequence, such that i < j and Si > Sj. For example, a sorted array (1,2,3,4,5) has zero inversions. Array (5,1,2,3,4) has four inversions (5,1), (5,2), (5,3), (5,4). Array (1,3,5,2,4) has three inversions (3,2), (5,2), (5,4). The maximum possible number of inversions in the array with n elements is . Suppose we asked several people to rank three music genres. Now, we can form lists with ratings for each person from the most favorite genre to the least favorite. See the input description below for an example. If a person in this set has identical preferences and ranks items exactly the same way as the active user, the number of inversions in the array would be zero. In general, the more inversions the array has, the more varied preferences are. In our example, Alice has 1 inversion compared to Bob. Meanwhile, John has 3 inversions compared to Bob. So, Alice has more preferences in common with Bob and she is more suitable as the basis of a prediction.
Input Each line contains a user name and an ordered list of their preferences separated by a colon. Items in the list are comma-separated. The first line of the input has an active user (the user whom a prediction is for). For example: Bob:Rock,Blues,Jazz Alice:Rock,Jazz,Blues John:Jazz,Blues,Rock
Output Print the list of users to be considered for making a recommendation. The list must be sorted by the number of inversions in ascending order. If two users have the same count of inversions sort them alphabetically. For example: Alice,John

Collaborative Filtering - Simple
Difficulty: Medium	Test Cases: 5	Published: 2019-10-04
Summary Implement a simple collaborative filter counting inversions
Description A Recommender System is capable of predicting the preferences of an active user for a set of items. For example, an online store can suggest a product to a shopper based on a history of purchases or page views. One of the traditional approaches for constructing such a system is to use Collaborative Filtering. It does not require any information about the items themselves and makes recommendations based on the past behavior of many users. Usually, collaborative filtering can be reduced to two steps: Look for users with similar interests as the active user Use ratings from the other users identified above to make a prediction for the active user Your task is to implement the first step using the number of inversions in lists of ratings from other users as a numerical similarity measure. An Inversion is a pair of elements (Si, Sj) within the sequence, such that i < j and Si > Sj . Inversions can be counted by iterating over the array and counting the number of elements that are smaller than the current element and are placed to the right of it. Here are a few examples: Sorted array (1,2,3,4,5) has zero inversions Array (5,1,2,3,4) has four inversions: (5,1), (5,2), (5,3), (5,4) Array (1,3,5,2,4) has three inversions: (3,2), (5,2), (5,4) The maximum possible number of inversions in an array with n elements is . Suppose we asked several people to rank three music genres. We then form a list of ratings for each person from their most favorite to least favorite genre. See the input description below for an example. In that example, Bob is our active user and we are going to make a prediction for him. We can enumerate items in his list in ascending order Rock -> 0, Blues -> 1, Jazz -> 2 and replace each genre with their numeric value for all users. Because the array for the active user is already sorted, it has zero inversions. If a person in this set has identical preferences and ranks items exactly the same way as the active user, the number of inversions in the array would be zero. In general, the more inversions the array has, the more varied those preferences are. For users in the current example we have: Alice:0,2,1 John:2,1,0 Now it's a straightforward process to calculate the number of inversions for each user. Alice has 1 inversion: (2,1). And John has 3 inversions: (2,1), (2,0) and (1,0). So Alice has more preferences in common with Bob and is more suitable as the basis of a prediction.
Input Each line contains a user name and an ordered list of their preferences separated by a colon. Items in the list are comma-delimited. The first line of the input is the active user (the user whom a prediction is for). For example: Bob:Rock,Blues,Jazz Alice:Rock,Jazz,Blues John:Jazz,Blues,Rock
Output Print the list of users to be considered for making a recommendation. The list must be sorted by the number of inversions in ascending order. If two users have the same count of inversions sort, them alphabetically. For example: Alice,John

Color Model - HSV to RGB
Difficulty: Medium	Test Cases: 12	Published: 2019-07-15
Summary Convert colors from the HSV to the RGB model
Description A software company specializing in graphics processing has been developing a next generation image editor. The code for the editor represents images in memory as an array of pixels. The color of each pixel is stored in the RGB model as a triplet of red, green and blue components (R, G, B). An 8-bit integer is used for every component, giving a value range from 0 to 255. However, the color picker tool can return a color in the HSV model. And it's required to convert the selected color to the RGB model for further usage in the editor. Write a function to convert image pixels from HSV to RGB. Use the following formulas to calculate the RGB components: Where R’, G’, B’ are normalized values of red, green, and blue components.
Input Each line contains three comma-separated 8-bit integers that are the hue, saturation, and value respectively. Every number is represented with three decimal digits. The first integer is the hue expressed in degrees from 0 to 359. The second and third integers are the saturation and value in percent. An example of the input: 036,078,100 153,071,100
Output Each line is a comma-separated triplet of 8-bit integer values (R, G, B). Every value is in the range 0 to 255 and is represented with three decimal digits. Round each calculated value to the nearest integer, rounding half to the next higher integer. For example, 11.5 should be rounded to 12, 10.29 to 10, and 2.75 to 3. An example of the output: 255,175,056 074,255,174

Color Model - RGB to CMYK
Difficulty: Medium	Test Cases: 5	Published: 2019-06-24
Summary Convert colors from the RGB to the CMYK model
Description A software company specializing in graphics processing has been developing a next generation image editor. The code for the editor represents images in memory as an array of pixels. The color of each pixel is stored in the RGB model as a triplet of red, green and blue components (R, G, B). An 8-bit integer is used for every component, giving a value range from 0 to 255. However, the printing pipeline of the application requires an image in the CMYK color model. Write a function to convert image pixels from RGB to CMYK. Use the following formulas to calculate cyan C, magenta M, yellow Y, and black key K colors as a real number between 0 and 1: Where R’, G’, B’are normalized values of red, green, and blue components. In other words, their values are converted from an 8-bit integer to a real value from 0 to 1.
Input Each line is a comma-separated triplet of 8-bit integer values (R, G, B). Every value is in the range 0 to 255 and is represented with three decimal digits. For example: 255,175,055 075,255,175
Output Each line contains four 8-bit integers corresponding to CMYK colors in the range from 0 to 255. Every number is represented with three decimal digits. The order of colors is (C, M, Y, K). Round each calculated value to the nearest integer, rounding half to the next higher integer. For example, 11.5 should be rounded to 12, 10.29 to 10, and 2.75 to 3. An example of the output: 000,080,200,000 180,000,080,000

Color Model - RGB to HSV
Difficulty: Medium	Test Cases: 12	Published: 2019-07-15
Summary Convert colors from the RGB to the HSV model
Description A software company specializing in graphics processing has been developing a next generation image editor. The code for the editor represents images in memory as an array of pixels. The color of each pixel is stored in the RGB model as a triplet of red, green and blue components (R, G, B). An 8-bit integer is used for every component, giving a value range from 0 to 255. However, the tools for adjusting colors require an image in the HSV color model. Write a function to convert image pixels from RGB to HSV. Use the following formulas to calculate the hue H, saturation S, and value V: Where R’, G’, B’ are normalized values of red, green, and blue components. In other words, their values are converted from the 8-bit integer to the real value from 0 to 1.
Input Each line is a comma-separated triplet of 8-bit integer values (R, G, B). Every value is in the range 0 to 255 and is represented with three decimal digits. For example: 255,175,055 075,255,175
Output Each line contains three comma-separated 8-bit integers that are the hue, saturation, and value respectively. Every number is represented with three decimal digits. The first integer is the hue expressed in degrees from 0 to 359. If you get a negative hue, just add 360 to it for adjusting the range. The second and third integers are the saturation and value in percent. Round each calculated value to the nearest integer, rounding half to the next higher integer. For example, 11.5 should be rounded to 12, 10.29 to 10, and 2.75 to 3. An example of the output: 036,078,100 153,071,100

Consecutive Primes
Difficulty: Medium	Test Cases: 10	Published: 2014-01-10
Summary Given a range of numbers 1-N, determine how many ways the numbers can be arranged such that every consecutive pair sums to a prime.
Description Alice has an even number of N beads, and each bead has a number from 1 to N painted on it. She would like to make a necklace out of all the beads, with a special requirement: any two beads next to each other on the necklace must sum to a prime number. Alice needs your help to calculate how many ways it is possible to do so. Example: N = 4 There are two possible ways to build the necklace. Note that the last bead connects to the first bead. 1 2 3 4 1 4 3 2 So the answer is 2.
Input The inputs consist of one even integer on a line. Each integer N is 2 <= N <= 18.
Output Print a line containing the number of ways to make a necklace according to the above rules.

Counting Primes
Difficulty: Medium	Test Cases: 10	Published: 2014-02-21
Summary Count the number of primes between two integers.
Description Given two integers N and M, count the number of prime numbers between N and M (both inclusive).
Input Your program should read lines from standard input. Each line contains two comma-separated positive integers.
Output Print out the number of primes between N and M (both inclusive).

Cumulative Frequency of Data Classes
Difficulty: Medium	Test Cases: 7	Published: 2019-07-15
Summary Calculate a cumulative frequency of the grouped data
Description Write a program to analyze the statistics of employees' daily commute time. Determine the number of data classes k as the smallest integer such that 2k >= N. Where N is the number of observations in the data sample. Group the raw data into classes and calculate their cumulative frequencies. Classes have an equal width. For example, if the company has 8 employees and their commute times in minutes are: 14 15 15 14 13 19 21 10 This data can be grouped into 3 classes because of 23 >= 8. So, we can define the following class limits 10-13, 14-17, and 18-21, dividing the commute time range from minimum to maximum into three subranges with equal width. The next table shows a distribution of the data between classes, frequency and cumulative frequency for each class.
Input A space-separated array of integers, that represents a daily commute time in minutes. For example: 14 15 15 14 13 19 21 10
Output A space-separated array of cumulative frequencies of data classes. Classes are sorted in ascending order. For example: 2 6 8

Decimal To Binary
Difficulty: Medium	Test Cases: 6	Published: 2012-10-08
Summary Print the binary representation of a decimal number.
Description Given a decimal (base 10) number, print out its binary representation.
Input Your program should read lines of text from standard input. Each line will contain a single integer.
Output For each input integer, print the binary representation to standard output, one per line, with no leading zeros.

Decode Numbers
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Count the number of ways to decode a string.
Description You are given an encoded message containing only numbers. You are also provided with the following mapping:   A : 1 B : 2 C : 3 ... Z : 26 Given an encoded message, count the number of ways it can be decoded.
Input Your program should read lines from standard input. Each line contains an encoded message of numbers. You may assume that the test cases contain only numbers.
Output Print out the different number of ways it can be decoded. Note: 12 could be decoded as AB(1 2) or L(12). Hence the number of ways to decode 12 is 2.

Document Merge
Difficulty: Medium	Test Cases: 4	Published: 2019-04-18
Summary Merge two CSV documents based on a key
Description Write a program that will parse, combine, and output CSV documents. This will require you to work through the data and merge the data sets appropriately based on a unique "ID" identifier for each row. For example: ID,Name,Start,End 16,Abraham Lincoln,1861,1865 Merged with: ID,Name,Start,End 15,James Buchanan,1857,1861 Would result in: ID,Name,Start,End 15,James Buchanan,1857,1861 16,Abraham Lincoln,1861,1865
Input Two CSV-like documents split by an empty line. The first line of each "document" will be the header, with data following afterwards. Each value should always be treated as a string and will be separated by a comma as a control character. Each individual document should only contain unique IDs. The ID value should always be a string with a valid numeric value. The headers of both documents will be consistent. Each document will have at least one row in addition to the header. For example: ID,Name,Start,End 16,Abraham Lincoln,1861,1865 ID,Name,Start,End 15,James Buchanan,1857,1861
Output A single CSV-like document as a result of the provided original documents. The first line should be the header with merged data on subsequent rows, sorted by the ID column. The output should only present one row per unique ID value. If a duplicate ID is provided, use the value in the second document in the results. For example: ID,Name,Start,End 15,James Buchanan,1857,1861 16,Abraham Lincoln,1861,1865

Double Squares
Difficulty: Medium	Test Cases: 2	Published: 2012-10-08
Summary FaceBook Hacker Cup 2011: Output the number of ways to write X as the sum of two squares
Description Credits: This challenge appeared in the Facebook Hacker Cup 2011. A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3^2 + 1^2. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 3^2 + 1^2 (we don't count 1^2 + 3^2 as being different). On the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2. NOTE: Do NOT attempt a brute force approach. It will not work. The following constraints hold: 0 <= X <= 2147483647 1 <= N <= 100
Input Your program should read lines of text from standard input. The first line will contain a single integer, N. The next N lines will contain one number, X, per line.
Output For each input X, print to standard output the number of ways X can be expressed as the sum of two squares, one number per line.

Dungeon Escape
Difficulty: Medium	Test Cases: 11	Published: 2019-11-15
Summary Find the shortest path to escape a dungeon
Description You are lost in a dungeon and need to find the shortest path out. The dungeon is a grid of R rows and C columns. It's composed of two types of cells: Passable cells where you can move up, down, left, or right Impassable cells filled with solid rock You cannot move diagonally between cells. Write a program to determine if it is possible to escape by finding the shortest path to the exit.
Input A map of the dungeon shown as R lines with C characters in each line. Every character corresponds to a cell of the dungeon's grid and designates its properties. Passable cells are marked with a period . Impassable cells are marked with a hash # The start position is at cell S The exit is at cell E For example: ###...##.. ....#....# #..###.#.# S#.#.#.#.. ...#...E#.
Output The same map of the dungeon but each . character must be replaced with and asterisk * character along the shortest path from the start to the exit. For example: ###***##.. ..**#**..# #.*###*#.# S#*#.#*#.. ***#..*E#. If there is no path to escape print Trapped.

Email Validation
Difficulty: Medium	Test Cases: 12	Published: 2012-10-08
Summary Write a regular expression to validate an email address
Description Write a program that uses regular expressions to determine if a string is a valid email address. For this challenge, let's define a valid email address as [e-mail] where "name" can contain the characters a-z, A-Z, 0-9, _, and . (dot). And "domain" can contain the characters a-z, and -. "name" and "domain" must be non-empty. "tld" can be "com", "org", or "net".
Input Your program should read lines of text from standard input. Each line contains a string that may or may not be a valid email address.
Output For each input string, print 'true' to standard output if the string is a valid email address as defined in this challenge. Otherwise print 'false'. Print one string per line.

Ferris Wheel
Difficulty: Medium	Test Cases: 6	Published: 2019-04-02
Summary Buffer input to a cyclic process
Description You are planning to meet a friend at a carnival. Your friend says to meet on the Ferris Wheel that she just boarded. She was at the front of the line when the ride opened and is holding a seat for you in the same car. The ride has N cars with 4 seats each and lasts for T minutes. It has been running at full capacity since it opened, except for your seat which is being saved. When you arrive, the line has X people in front of you. You also saw your friend just spin past the boarding point on the Ferris Wheel. Given all these criteria, your program must decide how many people you need to let pass you in line so that you board the same car with your friend.
Input A comma-delimited line with the three variables: N, T, X
Output The number of people you need to allow past you in line. If meeting with your friend on the ride is not possible, your output must be -1.

Find a Square
Difficulty: Medium	Test Cases: 11	Published: 2014-03-06
Summary Do 4 points make a square?
Description You have coordinates of four points on a plane. Check whether they make a square.
Input Your program should read lines from standard input. Each line has four (x,y) coordinate pairs separated by a comma and a space. All numbers in input are integers between 0 and 10.
Output Print true/false if the points make up a square.

Fires in the Amazon
Difficulty: Medium	Test Cases: 12	Published: 2020-01-11
Summary Validate the imported dataset
Description When data is imported into any software environment, there is a risk of introducing bad or invalid data. An essential step before doing any data analysis is to first validate the data to be used. This can save time and avoid problems later. Imagine a data science team investigating forest fires in the Tropical Forests of the Amazon. They have two datasets in CSV format: The first dataset represents the gathered statistics of forest fires by the month and year for different states in Brazil The second dataset has a summary of the total number of fires per year across the entire country Write a program to validate the first dataset using the summary data from the second.
Input Two datasets in CSV format separated by one empty line. The first dataset has the following columns: year - the year when forest fires happened state - Brazilian state month - the month when forest fires happened number - the number of reported fires in that year, state, and month The second dataset has the following columns: year - the year when forest fires happened number - the total number of reported fires in that year For example: year,state,month,number 2000,Rio,Novembro,18 2002,Pernambuco,Fevereiro,64 2001,Mato Grosso,Maio,112 2003,Roraima,Janeiro,547 2002,Maranhao,Julho,4 2003,Rio,Março,9 2000,Roraima,Outubro,25 2001,Paraiba,Janeiro,11 year,number 2002,68 2000,43 2003,556 2001,123
Output Print True if the first dataset appears to be valid. Otherwise, print False.

First Non-Repeated Character
Difficulty: Medium	Test Cases: 4	Published: 2012-10-08
Summary Find the first non repeated character in a string.
Description Write a program that finds the first non repeated character in a string.
Input Your program should read lines of text from standard input.
Output For each line of input, print the first non-repeated character to standard output, one character per line.

Game of Fifteen Simple
Difficulty: Medium	Test Cases: 9	Published: 2019-10-04
Summary Implement an algorithm to check solvability of the 15 puzzle
Description There is a puzzle called Game of Fifteen. The puzzle has 15 numbered tiles and a blank square arranged in a 4 × 4 grid. Any numbered tile adjacent to the blank square can be slid into the blank space. The object of the puzzle is to use the empty space to move tiles around until they are organized in ascending order (left-to-right and top-to-bottom). The empty square must end up in the bottom right corner, where the number 16 would land. For example, here is an illustration of a layout where 3 moves would completes the puzzle:   +----+----+----+----+      +----+----+----+----+     |  1 |  2 |  3 |  4 |      |  1 |  2 |  3 |  4 |     +----+----+----+----+      +----+----+----+----+     |  5 |  6 |  7 |  8 |      |  5 |  6 |  7 |  8 |     +----+----+----+----+  ->  +----+----+----+----+     |  9 |    | 10 | 12 |      |  9 | 10 |    | 12 |     +----+----+----+----+      +----+----+----+----+     | 13 | 14 | 11 | 15 |      | 13 | 14 | 11 | 15 |     +----+----+----+----+      +----+----+----+----+     +----+----+----+----+      +----+----+----+----+     |  1 |  2 |  3 |  4 |      |  1 |  2 |  3 |  4 |     +----+----+----+----+      +----+----+----+----+     |  5 |  6 |  7 |  8 |      |  5 |  6 |  7 |  8 |  -> +----+----+----+----+  ->  +----+----+----+----+     |  9 | 10 | 11 | 12 |      |  9 | 10 | 11 | 12 |     +----+----+----+----+      +----+----+----+----+     | 13 | 14 |    | 15 |      | 13 | 14 | 15 |    |     +----+----+----+----+      +----+----+----+----+  Not all initial puzzle layouts can be solved! Half of the nearly 21 million (16 Factorial) possible layouts are impossible to solve. To analyze the game, it's important to think about row and column moves separately. A row move is a move where a tile slides horizontally to the empty space. It does not change relative order of the tiles. A column move is a move where tile slides vertically. It will change the relative order of exactly three pairs of tiles. The term Inversion can be used to describe these movements in a more concise way. A pair of tiles is inverted if but appears after while inspecting the grid in row major order. A puzzle has zero inversions when it has been solved because all elements are ordered. For example, the puzzle below has four inversions: (11, 10), (12, 10), (13, 10), and (15, 14). +----+----+----+----+ |  1 |  2 |  3 |  4 | +----+----+----+----+ |  5 |  6 |  7 |  8 | +----+----+----+----+ |  9 |    | 11 | 12 | +----+----+----+----+ | 13 | 10 | 15 | 14 | +----+----+----+----+ Considering row and columns moves, we can say that a row move never changes the parity of the number of inversions, and a column move always changes it. Enumerating rows from 1 to 4, from top to bottom, it's possible to make a similar statement about the parity of the row containing the empty square. That row, and therefore that row's parity, can only be changed by a column move. Looking at a solved puzzle, we can see that it has zero inversions and the empty square is placed on the fourth row. That's why the parity of the number of inversions is equal to the parity of the row containing the empty square: 0%2 == 4%2. And our analysis of the row and column moves suggests that this property is invariant. It is always maintained in all tile movements. In our example with four inversions and the empty square in the third row, that invariant is not preserved: 4%2 != 3%2. That's why it is impossible to solve the puzzle in that example. Your task is to write a program that checks if it is possible to rearrange the tiles and solve the puzzle for a given layout.
Input A comma-delimited list of integers that represent the initial layout of the tiles in row-major order. The empty tile is designated by a zero. For example, this list: 10,2,8,4,0,14,7,5,13,1,6,3,15,12,11,9 ...represents the following state: +----+----+----+----+ | 10 |  2 |  8 |  4 | +----+----+----+----+ |    | 14 |  7 |  5 | +----+----+----+----+ | 13 |  1 |  6 |  3 | +----+----+----+----+ | 15 | 12 | 11 |  9 | +----+----+----+----+
Output Print True if the puzzle can be solved. If the puzzle cannot be solved, print False.

Hex to Signed Decimal
Difficulty: Medium	Test Cases: 12	Published: 2020-02-08
Summary Convert a hexadecimal number into a signed decimal
Description Write a program to convert a hexadecimal number (base 16) into signed decimal (base 10). The hexadecimal number is a single byte (8-bits), so the decimal signed integer will be in the range from -128 to 127.
Input Each line of input contains one hexadecimal number having exactly 2 digits without leading prefix 0x. All alpha characters (A through F) in the input will be uppercase. For example: FE CE 02 70 8F
Output For each line of input, print the base 10 signed integer value. Print one number per line, with no leading zeros. For example: -2 -50 2 112 -113

John Venn
Difficulty: Medium	Test Cases: 5	Published: 2019-04-02
Summary Create some fundamental set logic
Description Write a program that accepts two sets of alpha-numeric characters and performs an efficient matching between them. Finally, display the results. The intent of this challenge is to play with set theory. Avoid using pre-built framework functions that perform this work in a single line of code. Instead, illustrate how you would efficiently operate with two sets of data when trying to match values between them. There are many ways to approach this algorithm so be creative.
Input Two lines of input, each with a space-delimited series of values that represent the two sets. For example: 1 2 3 A B C X 11 G M 2 9 3 C N R
Output The set of values that exist in both input sets, sorted alpha-numerically. For example: 2 3 C If no common values exist, output NULL

Jolly Jumpers
Difficulty: Medium	Test Cases: 4	Published: 2012-10-08
Summary Determine if a sequence of numbers is a Jolly Jumper
Description Credits: Programming Challenges by Steven S. Skiena and Miguel A. Revilla A sequence of n > 0 integers is called a jolly jumper if the absolute values of the differences between successive elements take on all possible values 1 through n - 1. eg. 1 4 2 3 is a jolly jumper, because the absolute differences are 3, 2, and 1, respectively. The definition implies that any sequence of a single integer is a jolly jumper. Write a program to determine whether each of a number of sequences is a jolly jumper.
Input Your program should read lines of text from standard input. Each line will contain an integer n < 3000 followed by a proposed jolly jumper sequence of length n, which is a list of space separated integers. For example: '4 1 4 2 3'. The first '4' indicates the sequence is of length 4, i.e. n = 4, and '1 4 2 3' represents the jolly jumper sequence.
Output For each line of input, print to standard output 'Jolly' or 'Not jolly' using the criteria in this challenge.

Jumbled Numbers
Difficulty: Medium	Test Cases: 12	Published: 2020-01-11
Summary Find number words in the jumbled string
Description In this challenge, you're given a string containing jumbled letters from several concatenated words. Each word is a numeral from zero to nine. Each numeral may be used multiple times in the jumbled string. Write a program that returns integers corresponding to the numerals used to form the jumbled string. Integers must be sorted in ascending order. For example, reuonnoinfe are shuffled letters of the strings one four nine. Your program's output should be 149.
Input A string formed from jumbled letters of numerals. For example: reuonnoinfe
Output A sequence of integers used to form the string in ascending order. For example: 149

Longest Lines
Difficulty: Medium	Test Cases: 2	Published: 2012-08-21
Summary Finding the 'N' longest lines within a file.
Description Write a program that finds the N longest lines from standard input.
Input Your program should read lines of text from standard input. The first line contains the value of N, which will be a positive integer. Ignore empty lines in the input. You can assume that your program will receive at least N non-empty lines.
Output Print to standard output the longest N lines from the input, sorted from longest line to shortest. Ensure that there are no trailing spaces on each line you print nor extra empty lines between your output lines.

Lost in Translation
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Try to become a native speaker
Description Credits: This is an adaptation of the original challenge that was created by David Arthur. We have come up with the best possible language called Codel. To translate text into Codel, we take any message and replace each English letter with another English letter. This mapping is one-to-one and onto, which means that the same input letter always gets replaced with the same output letter, and different input letters always get replaced with different output letters. A letter may be replaced by itself. Spaces are left as-is. For example (and here is a hint!), our translation algorithm includes the following three mappings: 'b' -> 'n', 'j' -> 'u', and 'v' -> 'g' is based on the best possible replacement mapping, and we will never change it. It will always be the same. In every test case. We will not tell you the rest of our mapping because that would make the problem too easy, but there are a few examples below that may help.
Input Your program should read lines from standard input. Each line consists of a string in Codel, made up of one or more words containing the letters 'a' - 'z'. There will be exactly one space (' ') character between consecutive words and no spaces at the beginning or at the end of any line.
Output For each test case, output one line containing a translated string.

Lowest Common Ancestor
Difficulty: Medium	Test Cases: 5	Published: 2012-10-08
Summary Determine the lowest common ancestor within a tree
Description Write a program to determine the lowest common ancestor of two nodes in the following binary search tree, which you may hard code in your program:              30               |             --+--             |   |             8   52             |           --+--           |   |           3   20               |             --+--             |   |            10   29
Input Your program should read one line of text from standard input. The line will contain two integers, separated by a space, which represent two nodes within the pictured binary search tree.
Output Print to standard output the least common ancestor of the two nodes.

Magic Numbers
Difficulty: Medium	Test Cases: 10	Published: 2013-12-18
Summary Print out a list of all the magic numbers in a provided range
Description There are two wizards, one good and one evil. The evil wizard has captured the princess. The only way to defeat the evil wizard is to recite a set of magic numbers. The good wizard has given you two numbers, A and B. Find every magic number between A and B, inclusive. A magic number is a number that has two characteristics: 1. No digits repeat. 2. Beginning with the leftmost digit, take the value of the digit and move that number of digits to the right. Repeat the process again using the value of the current digit to move right again. Wrap back to the leftmost digit as necessary. A magic number will visit every digit exactly once and end at the leftmost digit. For example, consider the magic number 6231. 1. Start with '6'. Advance 6 steps to '3', wrapping around once. 2. From '3', advance to '2'. 3. From '2', advance to '1'. 4. From '1', advance to '6'.
Input The input consists of two integers on a line, separated by spaces. Each integer A and B is 1 <= A <= B <= 10000.
Output Print each magic number between A and B, inclusive, on a line. If there is no magic number between A and B, print -1.

Median of Medians
Difficulty: Medium	Test Cases: 8	Published: 2019-05-31
Summary Find the approximate median of the array
Description In a data structure such as an array, the pivot is the element that is selected by an algorithm to perform certain operations around. For example, Quicksort and Selection algorithms use a pivot to partition the array into two parts. For these algorithms, a good pivot choice will give a balanced partitioning of the array, which is close to the 50/50 split. That means that the best pivot is the median. This leads to circular logic, however. For example, to sort the array with Quicksort we need a median, and to find the median we need to sort the array. To break that circular logic we can use a good approximation of the median instead of the real value. One possible approach is to use a randomly selected element as a pivot, which is what Randomized Quicksort does. Another approach is to find an approximate median deterministically. The Median of Medians algorithm can be used for that: Divide the list into sublists with k elements. The last sublist may contain fewer than k elements. Sort each sublist, get its median and append it to another list containing medians of sublists. If the medians list has a length more than k, compute its median recursively, proceeding with step 1. If the medians list has k elements or fewer, sort it and determine its median. Return it as a pivot. If an array is of odd length, the median is the middle element after the array has been sorted. If an array is of even length, there are two middle elements after it has been sorted. In this case, we will define the median as the left (first) of these two middle elements.
Input An integer number k on the first line which is the length to use for sublists in the algorithm. The second line contains space-separated integers of the array. For example: 3 1 2 5 4 6 3 7 8
Output The integer number selected as the pivot by Median of Medians algorithm. For example: 4

Minimum Coins
Difficulty: Medium	Test Cases: 10	Published: 2014-02-21
Summary Find the minimum number of coins to arrive at a total.
Description You are given 3 coins of value 1, 3 and 5. You are also given a total which you have to arrive at. Find the minimum number of coins to arrive at it.
Input Your program should read lines from standard input. Each line contains a positive integer number which represents the total you have to arrive at.
Output Print out the minimum number of coins required to arrive at the total.

Mth to last element
Difficulty: Medium	Test Cases: 4	Published: 2012-10-08
Summary Determine the Mth to last element of a sequence
Description Write a program to determine the Mth to last element of a sequence.
Input Your program should read lines of text from standard input. Each line will contain a series of space delimited integers. The last integer in the series is M.
Output Print to standard output, the Mth integer from the end of the sequence, one integer per line. If M is larger than the sequence size, print a blank line.

Negabinary To Decimal
Difficulty: Medium	Test Cases: 7	Published: 2019-10-04
Summary Print the decimal number given its negabinary representation
Description Given the negabinary representation (base -2) of an integer, convert it to the decimal (base 10) value.
Input Each line of input contains a single integer value expressed as a negabinary value.
Output For each line of input, print the base 10 integer value. Print one per line, with no leading zeros.

Network Level Structure
Difficulty: Medium	Test Cases: 8	Published: 2019-07-16
Summary Print out a level structure of the computer network.
Description Given a computer network represented as a set of nodes and links between them, print out a level structure of that network. In other words, find a partition of network nodes into layers that have equal distance from a given source node. Assume that the network is connected, meaning that there are no separated segments of the network with no path from the source node.
Input The first line contains the integer address of the source node. Each next line describes connections of one node with others in the network using a space-separated list of integer addresses. The first element of the list is the address of the current node, and all other elements are the addresses of the nodes that are connected to it. Addresses are in the range from 0 to 255 inclusive. For example: 10 64 10 21 21 64 10 10 64 1 21 1 10 99 5 99 1 5 1 See the attachments tab for the graph representation of this network.
Output Each line represents a level (or layer) of the network, starting from source node on the first line which forms the first layer. The second line contains a sorted space-separated list of second layer's nodes addresses, and so on. For example: 10 1 21 64 5 99
Attachments

Network Space
Difficulty: Medium	Test Cases: 6	Published: 2019-04-02
Summary Perform a fundamental networking function
Description A network block is defined by an IP address and a subnet mask. The mask value separates the network address from the internal address based on how many bits are hidden by the mask. For example, an 8-bit subnet mask is expressed as 255.0.0.0. An IP address of 10.21.8.15 with that mask applied reveals a network address of 10.0.0.0. We can represent this like so: 10.0.0.0/8 (this is called CIDR notation). Given a standard CIDR block, describe the subnet by returning the Network Address and Subnet Mask in dotted decimal notation.
Input A standard CIDR block. For example: 192.168.0.0/16
Output Two lines indicating the following: Network address Subnet Mask For example: 192.168.0.0 255.255.0.0

Normalize Levels
Difficulty: Medium	Test Cases: 6	Published: 2019-04-18
Summary Adjust a series of scalars to match a target range
Description Imagine a music studio has a set of recorded audio tracks they are mixing. The tracks each have their own range of audio levels. To mix them into a single track, the studio wants you to adjust them individually so they all fall into the same volume range. Write a program that reads in a set of signal levels. The range of levels in each track can be any integer from 0 to 32767. Your program must return the same set of tracks but adjusted so they all peak at the same level of 100. For example, consider these three tracks: 28,54,812,438 12,35,78,26 18,2,212,5 Your algorithm should: Determine the max value M for each track. In the example, these would be 812, 78, and 212 respectively. Calculate the damping factor d for each track as Apply the weighting factor to each track's series of values as v x d where v is the given value in the series The results for each series should all have the same peak level. For fractional values, round to the nearest whole number. Midpoint rounding should be upward/away from zero. For example, the value 3.5 should round to 4.
Input Each line of input will be a comma-separated series of positive integers representing the stream of sound levels for each track.
Output Print out a comma-separated series of the normalized values for each track, one track per line of output in the order they were input. Using the example above, the correct output would be: 3,7,100,54 15,45,100,33 8,1,100,2

Number Operations
Difficulty: Medium	Test Cases: 10	Published: 2013-12-20
Summary Given five numbers 0-52, determine if it is possible to rearrange the numbers and use plus, minus, or times operations to produce the number 42.
Description Alice has invented a new card game to play with Bob. Alice made a deck of cards with random values between 1 and 52. Bob picks 5 cards. Then, he has to rearrange the cards so that by utilizing the operations plus, minus, or times, the value of the cards reach Alice's favorite number, 42. More precisely, find operations such that ((((val1 op1 val2) op2 val3) op3 val4) op4 val5) = 42. Help Bob by writing a program to determine whether it is possible to reach 42 given 5 card values. For example, Bob picks 5 cards out of the deck containing 40, 1, 3, 4, and 20. Bob rearranges the cards and supplies four operations, so that 4 * 20 - 40 + 3 - 1 = 42.
Input The input consists of five integers on a line, separated by spaces. Each integer V is 0 <= V <= 52.
Output Print a line containing "YES" if it is possible to reach the value 42 according to the rules of the game, or "NO" otherwise.

Number Pairs
Difficulty: Medium	Test Cases: 6	Published: 2012-10-08
Summary Find pairs of numbers in a sorted array whose sum is X
Description You are given a sorted array of positive integers and a number X. Print out all pairs of numbers whose sum is equal to X. Print out only unique pairs and the pairs should be in ascending order
Input Your program should read lines of text from standard input. Each line will contain a comma separated list of sorted numbers, followed by a semicolon, followed by the integer X.
Output For each line of input, print to standard output the pairs of numbers that sum to X. Print the pairs in ascending order (the first number of each pair should be less than or equal to the second number). If no pair exists that sums to X, print the string NULL.

Number of Ones
Difficulty: Medium	Test Cases: 6	Published: 2012-10-08
Summary Determine the number of one bits in an integer.
Description Write a program to determine the number of 1 bits in the internal representation of a given integer.
Input Your program should read lines of text from standard input. Each line will contain a single integer in decimal form.
Output For each input integer, print to standard output the number of bits that are one in the integer's binary form, one integer per line.

Optimize Value
Difficulty: Medium	Test Cases: 8	Published: 2013-12-21
Summary Given a weight limit and a list of objects with specified weight and value, determine the maximum value of items without exceeding the weight limit.
Description Bob has just won a shopping spree at his favorite store, Acme Electronics. Acme has provided Bob with a shopping cart that can hold L pounds of items. Bob wants to maximize the total value of items he can place into his shopping cart, without exceeding the weight limit. He can take no more than one of each available item. For example, Bob has a shopping cart that can hold 10 pounds of items, and there are 4 items in the store: 5 4 3 2 10 8 4 8 Bob can maximize the value of his cart by selecting one item of value 10 (weight 8) and one of value 3 (weight 2) for a total of 13.
Input The input consists of a line containing two integers L and N, separated by a space. L is the maximum weight of items that he may place into his shopping cart, and N is the number of types of items in the store. Then N lines follow, each containing two integers P and W separated by a space. P contains the price of the item, and W contains the weight of the item. 1 <= L, N, P, W <= 1000.
Output Print a line containing the maximum total price of all items that Bob can fit into his cart.

Overlapping Rectangles
Difficulty: Medium	Test Cases: 10	Published: 2014-02-21
Summary Determine if two rectangles overlap.
Description Given two axis-aligned rectangles A and B, determine if the two overlap. The rectangles are considered overlapping if they have at least one common point.
Input Your program should read lines from standard input. Each line contains 8 comma-separated coordinates. The coordinates are upper left x of A, upper left y of A, lower right x of A, lower right y of A, upper left x of B, upper left y of B, lower right x of B, lower right y of B.
Output Print out True if A and B intersect, False otherwise.

Pangrams
Difficulty: Medium	Test Cases: 11	Published: 2012-10-08
Summary Find the missing alphabets
Description The sentence "A quick brown fox jumps over the lazy dog" contains every single letter in the English alphabet. Such sentences are called pangrams. You are to write a program which takes a sentence and outputs all the letters it is missing which prevent it from being a pangram. You should ignore the case of the letters in the input sentence, and your output should be all lowercase letters in alphabetical order. You should also ignore all non US-ASCII characters. In case the input sentence is already a pangram, output the string NULL.
Input Your program should read lines of text from standard input. Each line contains a sentence.
Output For each line of input, print to standard output all the letters it is missing, in lowercase, sorted in alphabetical order. If there are no missing letters, print the string NULL.

Pascal's Triangle
Difficulty: Medium	Test Cases: 10	Published: 2014-02-21
Summary Print out pascals triangle up to a certain depth.
Description A Pascals triangle row is constructed by looking at the previous row and adding the numbers to its left and right to arrive at the new value. If either the number to its left/right is not present, substitute a zero in it's place. More details can be found here: Pascal's triangle. E.g. a Pascal's triangle up to a depth of 6 can be shown as:          1         1   1       1   2   1     1   3   3   1   1   4   6   4   1 1   5  10   10  5   1
Input Your program should read lines from standard input. Each line contains a positive integer which indicates the depth of the triangle (1 based).
Output Print out the resulting pascal triangle up to the requested depth in row major form.

Pass Triangle
Difficulty: Medium	Test Cases: 5	Published: 2014-03-18
Summary Lead the way within the triangle
Description Given a triangle of numbers, start at the top point of the triangle and find the largest possible sum that can be accumulated from traveling to adjacent numbers down the triangle. You must move down the rows, not up or across. E.g.   5   9 6  4 6 8 0 7 1 5
Input Your program should read lines from standard input. Each test case consists of multiple lines. The first line in each test case indicates the number of lines N in the triangle. The next N lines form a triangle of space delimited integers. The integers are in range [1, 99]. Each triangle has between 1 and 300 lines.
Output Print out the maximum sum for a downward path in the triangle.

Password Strength
Difficulty: Medium	Test Cases: 12	Published: 2019-12-03
Summary Use regular expressions to determine password strength
Description Write a function that uses regular expressions to determine a password's strength. A valid password for this challenge is a UTF-8 encoded string consisting of a minimum of 6 and a maximum of 25 characters. The accepted range of characters is [U+0021, U+007A] in the Basic Latin Unicode block. Use the following rules to determine the password strength: A strong password must have at least one lowercase letter [U+0061, U+007A], one uppercase letter [U+0041, U+005A], one digit [U+0030, U+0039], and one special character (all other characters from the valid range in the Basic Latin block). The length of a strong password must be at least 10 characters. The rule for a password of medium strength is the same as for strong, except it will not contain special characters and its length must be greater or equal to 8 characters. A password with the special character but shorter than 10 characters has a medium strength. For example, iT*2spX*8 is of medium strength. All other valid passwords are weak. All value ranges in the above description are inclusive.
Input A string containing a password. For example: Nufu&YM21S
Output Print out the password's strength: strong, medium, or weak. Print invalid if the password is not valid.

Picking Teams
Difficulty: Medium	Test Cases: 9	Published: 2019-04-02
Summary Eliminate every X item from a circular list
Description A group of children are picking teams for a game of soccer. The way they pick teams is to line up all the players and select one person at a time from that line. Starting from the first player in line, the person to be selected will always be "X" people down the line from the last player picked. When the end of the line is reached, counting resumes from the start of the line. Write a program that will return a list of players in the order they get selected to play.
Input Your program should read a single line from standard input. That line will contain two comma-separated positive integers X and Z, where X is how many people to count when selecting the next player and Z is the number of people in line.
Output Print out the index of all the players (0 to Z-1, space delimited) in the order they will be selected.

Pile of Bricks
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Close a hole in a wall
Description You have a pile of bricks. Every brick has its index number and coordinates of opposite vertices. You know that somewhere on the wall there is a rectangular hole, and you are given coordinates of opposite vertices of that hole. You must determine which bricks may pass through that hole. In situations where the brick and the hole have an equal sizes, we assume that it can pass through this hole. All the holes are two-dimensional. All of the bricks are three-dimensional.
Input Your program should read lines from standard input. Each line contains coordinates of opposite vertices of a hole (before the pipe char) separated by space and the list of bricks you need to check. Each brick is enclosed in parentheses where the 1st number is a brick's index number, the 2nd and 3rd group of numbers are the brick's coordinates of opposite vertices (separated by a space), each brick is divided by semicolon. Coordinates are in range [-100, 100]. The list of bricks you need to check will not exceed 15.
Output For each set of bricks, print out a list of bricks (their index numbers in ascending order separated by commas) that can pass through the hole. If no bricks can pass through the hole, print a hyphen (-).

Point in Circle
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Define whether a point is in a circle
Description Given coordinates for the center of a circle, its radius, and coordinates of a point, you need to determine whether this point is located inside of this circle.
Input Your program should read lines from standard input. Each line defines the center point of the circle, the radius, and the point in question. See the example test cases for the exact format. All numbers in the input are between -100 and 100.
Output Print true/false if the point is in the circle.

Predict the Number
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Try to go beyond the limits
Description The example sequence 011212201220200112 ... is constructed as follows: 1. The first element in the sequence is 0. 2. For each iteration, repeat the following action: take a copy of the entire current sequence, replace 0 with 1, 1 with 2, and 2 with 0, and place it at the end of the current sequence. E.g. 0 -> 01 -> 0112 -> 01121220 -> ... Create an algorithm which determines what number is at the Nth position in the sequence (using 0-based indexing).
Input Your program should read lines from standard input. Each line contains an integer N such that 0 <= N <= 3000000000.
Output Print out the number which is at the Nth position in the sequence.

Prime Numbers
Difficulty: Medium	Test Cases: 5	Published: 2012-10-08
Summary Print prime numbers less than N
Description Print out the prime numbers less than a given number N. You may assume that N is always a positive integer.
Input Your program should read lines of text from standard input. Each line will contain an integer n < 4,294,967,295.
Output For each line of input, print out the prime numbers less than N, in ascending order, comma delimited. (There should not be any spaces between the comma and numbers)

Priority Queue Implementation
Difficulty: Medium	Test Cases: 12	Published: 2020-01-11
Summary Implement a priority queue data structure
Description Write a program implementing a priority queue. Each element is a pair containing a value and an associated priority. Elements are processed in the queue according to their priority. The value and priority are both integers. The priority queue should have enqueue and dequeue methods: The enqueue method must insert a given element into the queue The dequeue method must remove the element with the highest priority first. If elements have the same priority, they must be removed in the order in which they were inserted. The queue must also have a certain capacity, which is the maximum number of elements allowed in the data structure. If the queue is full and contains at least one element with a priority less than the priority of an element to be inserted, the enqueue method must insert the new element by replacing the existing element with the lowest priority in the queue. If the queue is full but doesn't contain elements with the lower priority, the enqueue method must do nothing. Similarly, the dequeue method must do nothing if the queue is empty. You will be asked to perform a sequence of operations and then print the state of the queue after processing all operations.
Input The first line of input contains a positive integer which sets the capacity of the queue. Each additional line contains the string name of an operation to be performed: enqueue or dequeue. The enqueue string will be followed by two integers: a value and a priority of the element to be inserted into the queue. For example: 3 enqueue 5 3 enqueue 6 5 enqueue 1 -1 dequeue enqueue -2 0 dequeue enqueue 3 1 enqueue 4 2
Output Print the value and priority of each element the queue will contain after all operations have been applied, separated by a space. Each element must be printed on a separate line. The order of the elements must be in descending order of their priorities. For example: 4 2 3 1 -2 0 Print Empty if the queue will be empty after all operations.

Recursive Median Filter
Difficulty: Medium	Test Cases: 7	Published: 2019-05-31
Summary Apply a recursive median filter to a series of data
Description Finally, you get the latest measurements in your scientific experiment. It was not easy to collect that data. A lot of noise is present in the space around your secret laboratory. But you know that it's not hard to improve the quality of the measured signal, applying a median filter to the raw data from analog-to-digital converters. In standard median filter output is at some point is the median value of N samples around that point. Another way to describe that is a window of size N elements slides over the input signal, element by element. On every step, the median of the elements in the window is written to the output. The median of the set of integers is the middle element in the sorted list of these numbers. In recursive median filter output is the median of elements in the current window. But now, in the left half of that window input signal is replaced by output from the previous steps. Write a program that filters out the noise from the raw data, using the recursive median filter. For simplicity, assume that the size of the filter window is always odd. Do not process the boundaries of the input signal, where it's not enough elements to compose a window of the necessary size. In other words, just crop the signal. If the filter's window size is 5 you will lose 2 first and 2 last elements. Also, use input elements at the beginning of the signal where there are no outputs for the left part of the filter's window. For example, let's filter signal 17 18 19 37 21 22 23 85 25 26 using a window of size 3. For the first 3 elements 17 18 19 the median is 18. Shifting filter's window to the next 3 elements 18 19 37 gives 19 as an output. 19 37 21 outputs 21, and so on. +------+----------+----------+--------+  | step | input    | window   | median |  |      | elements | elements |        |  +------+----------+----------+--------+  |   1  | 17 18 19 | 17 18 19 |   18   |  +------+----------+----------+--------+  |   2  | 18 19 37 | 18 19 37 |   19   |  +------+----------+----------+--------+  |   3  | 19 37 21 | 19 37 21 |   21   |  +------+----------+----------+--------+  |   4  | 37 21 22 | 21 21 22 |   21   |  +------+----------+----------+--------+  |   5  | 21 22 23 | 21 22 23 |   22   |  +------+----------+----------+--------+  |   6  | 22 23 85 | 22 23 85 |   23   |  +------+----------+----------+--------+  |   7  | 23 85 25 | 23 85 25 |   25   |  +------+----------+----------+--------+  |   8  | 85 25 26 | 25 25 26 |   25   |  +------+----------+----------+--------+ Processing all integers from the set will result in 18 19 21 21 22 23 25 25. As you can see, there are no spikes and outlying elements in the output data set.
Input The first line contains an odd integer, the size of the filter's window. Each next line of the input has a comma-separated series of positive integers. That is raw data of the measured signal. For example: 3 5,5,5,15,5,5,5 1,2,3,25,5,6,52,7,8
Output Print out a comma-separated series of integers, that is a result of applying the recursive median filter to the raw input data. For example: 5,5,5,5,5 2,3,5,5,6,7,7

Relative Frequency of Data Classes
Difficulty: Medium	Test Cases: 8	Published: 2019-08-07
Summary Calculate a relative frequency of the grouped data
Description Write a program to analyze the daily commute times for a group of employees. Determine the number of data classes k as the smallest integer such that 2k >= N, where N is the number of observations in the data set. Group the raw data into these classes and calculate their relative frequencies. Classes have an equal width. For example, if there are eight employees in a sample and their commute times in minutes are: 14 15 15 14 13 19 21 10 This set would be grouped into 3 classes because 23 >= 8. Since each class is of equal width, the three classes would be: 10-13 minutes 14-17 minutes 18-21 minutes The table below shows a distribution of the data across classes by frequency and relative frequency, which is expressed as a percentage of the whole set.
Input A space-delimited list integers that represents a set of daily commute times in minutes. For example: 14 15 15 14 13 19 21 10
Output A space-delimited array of relative frequencies of data classes in percent. Classes must be sorted in ascending order. Round each value to the nearest integer, rounding half to the next higher integer. 11.5 rounds to 12 10.29 rounds to 10 2.75 rounds to 3 Sample Output: 25 50 25

Remove Characters
Difficulty: Medium	Test Cases: 4	Published: 2012-10-08
Summary Delete specific characters from a string.
Description Write a program to remove specific characters from a string.
Input Your program should read lines of text from standard input. Each line of input will be a string followed by a comma followed by characters that need to be scrubbed.
Output Print to standard output the scrubbed strings, one per line. Trim out any leading/trailing whitespaces if they occur.

Reverse Groups
Difficulty: Medium	Test Cases: 10	Published: 2014-02-21
Summary Reverse elements in a list k items at a time.
Description Given a list of numbers and a positive integer k, reverse the elements of the list, k items at a time. If the number of elements is not a multiple of k, then the remaining items in the end should be left as is.
Input Your program should read lines from standard input. Each line contains a list of numbers and the number k, separated by a semicolon. The list of numbers are comma delimited.
Output Print out the new comma separated list of numbers obtained after reversing.

Reverse and Add
Difficulty: Medium	Test Cases: 4	Published: 2012-10-08
Summary Continually add a number to its reverse to arrive at a palindrome
Description Credits: Programming Challenges by Steven S. Skiena and Miguel A. Revilla The problem is as follows: choose a number, reverse its digits and add it to the original. If the sum is not a palindrome (which means, it is not the same number from left to right and right to left), repeat this procedure. eg. 195 (initial number) + 591 (reverse of initial number) = 786 786 + 687 = 1473 1473 + 3741 = 5214 5214 + 4125 = 9339 (palindrome) In this particular case the palindrome 9339 appeared after the 4th addition. This method leads to palindromes in a few step for almost all of the integers. But there are interesting exceptions. 196 is the first number for which no palindrome has been found. It is not proven though, that there is no such a palindrome.
Input Your program should read lines of text from standard input. Each line will contain an integer n < 4,294,967,295. Assume each line of input will always have an answer and that it is computable with less than 1000 iterations (additions)
Output For each line of input, generate a line of output which is the number of iterations (additions) to compute the palindrome and the resulting palindrome. (they should be on one line and separated by a single space character)

Scrolling Numbers
Difficulty: Medium	Test Cases: 10	Published: 2020-01-11
Summary Unravel a special kind of lock
Description You have been given a special kind of lock to open called a "Scrolling Combination Lock". The lock has 9 keys numbered from 1 to 9. Additionally, there are two numbers printed below the keys suggesting a range of values. To open the lock, you must enter all the numbers in the range that are "Scrolling Numbers". A Scrolling Number is a number that has two characteristics: No digits repeat themselves All digits in the number "scroll" through themselves How To Scroll Beginning with the leftmost digit, take that digit's value D and move D digits to the right. When scrolling, if the last digit of the number is reached, wrap back to the leftmost digit as many times as needed to move to total of D digits. After scrolling to a new digit, repeat the process using the new digit's value for D. A Scrolling Number will visit every digit exactly once and end at the leftmost digit. For example, consider the Scrolling Number 6231. Start with the digit '6' Advance 6 steps, wrapping around once, to the digit '3' From '3', advance to '2', again wrapping around once From '2', advance to '1' From '1', advance to '6' in a final wrap
Input The input is the range of integers to consider for the lock, expressed in the format: A, B Each integer A and B is 1 <= A <= B <= 10000.
Output Print all Scrolling Numbers between A and B, inclusive, each on a single line. These are the combinations that will open the lock. If there are no Scrolling Numbers between A and B, print -1.

Sequence Transformation
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Transform a binary sequence into a string
Description There are two sequences. The first sequence consists of digits "0" and "1", the second one consists of letters "A" and "B". The challenge is to determine whether it's possible to transform a given binary sequence into a string sequence using the following rules: 1. "0" can be transformed into non empty sequence of letters "A" ("A", "AA", "AAA" etc.) 2. "1" can be transformed into non empty sequence of letters "A" ("A", "AA", "AAA" etc.) or to non empty sequence of letters "B" ("B", "BB", "BBB" etc) Within a sequence, a binary digit does not necessarily have to translate to the same sequence of letters. In other words, the transformation: 00 AAA is possible because 0 can be either "A" or "AA".
Input Your program should read lines from standard input. Each line contains a binary sequence and a sequence of letters "A" and "B" separated by a single whitespace. The length of the binary sequence is in range [1, 150]. The length of the string sequence is in range [1, 1000].
Output For each test case print out "Yes" if the transformation is possible, otherwise print "No".

Set Selection
Difficulty: Medium	Test Cases: 8	Published: 2019-05-31
Summary Select a set of points to minimize the distance
Description Consider a set of m groups, each group having some number of points in a one-dimensional space. Each point is expressed by its coordinate on a line. Write a program to choose exactly one point from every group to form a new set, such that the distance between first and last points in the new set is the minimum possible.
Input Each line of input contains a list of space-separated integers for each group. For example: 21 1 150 289 -321 160 3 30 170 22 6 7
Output A space-separated sorted list of integers of the formed set. For example: 1 3 6

Signal Lock
Difficulty: Medium	Test Cases: 5	Published: 2019-04-02
Summary Given a noisy source, find the message payload
Description Many file formats have information that extends beyond the main payload. For example, an image file may contain extensive metadata that is not part of the visually-rendered graphic. Write a program that will seek a blob of information for a header and footer, extracting the payload in between them. Try to do this efficiently.
Input The first line of input will have the payload's header and footer separated by a pipe character "|". Each will be a raw, UTF-8 byte sequence. All subsequent lines of input will be a wrapped character array that is not human-readable. This will contain the payload you seek. There will be only one payload per blob.
Output The payload characters are written in a single line of output. No header or footer should be included.

Signed Decimal to Hex
Difficulty: Medium	Test Cases: 12	Published: 2020-02-08
Summary Convert a signed decimal number into a hexadecimal
Description Write a program to convert a signed decimal (base 10) number into hexadecimal (base 16). The decimal signed integer is in the range from -128 to 127, so the hexadecimal number will be a single byte (8-bits).
Input Each line of input contains one base 10 signed integer value. For example: -2 -50 2 112 -113
Output For each line of input, print the hexadecimal number having exactly 2 digits without leading prefix 0x. All alpha characters (A through F) in the output should be uppercase. Print one number per line. For example: FE CE 02 70 8F

Simple Calculator
Difficulty: Medium	Test Cases: 10	Published: 2014-03-18
Summary Create a simple calculator
Description The goal of this challenge is to create a simple calculator. The following operations should be supported (in order of precedence): 1   ()       Brackets 2   -        Unary minus 3   ^        Exponent 4   *, /     Multiply, Divide (left-to-right precedence) 5   +, -     Add, Subtract (left-to-right precedence)
Input Your program should read lines from standard input. Each line contains a  mathematical expression. Each number in input expression is greater than -20,000 and less than 20,000. Each output number is greater than -20,000 and less than 20,000.
Output Print out the result of the calculation. If the output number is a floating point number it should be rounded to the 5th digit after the dot. E.g 14.132646 gets 14.13265, 14.132644 gets 14.13264, 14.132645 gets 14.13265. If the output number has less than 5 digits after the decimal point, you don't need to add zeros. Note: don't use any kind of eval function.

Single-Source Shortest Path
Difficulty: Medium	Test Cases: 7	Published: 2019-10-04
Summary Find the shortest paths from a source vertex to all other vertices in the undirected graph
Description Write a program to find the shortest paths from one source vertex to all other reachable vertices in the given undirected graph. Edges of the graph have no weights and the length of the path is the number of edges between two vertices. The graph can be disconnected, i.e. consisting of multiple pieces. If a vertex is not reachable from the source vertex the path between them is equal to infinity. Every vertex in the graph has a unique string name consisting of alphanumeric characters (UTF-8).
Input The first line contains the name of the source vertex. The second line has a list of edges. Every edge is described as a comma-delimited pair of names of adjacent vertices. Edges are separated with a semicolon in the list. For example: A A,B;B,C;A,C;B,D;C,D;D,E;F,G;G,H;F,H See the attachments tab for a diagram of this example
Output Each line contains a space-delimited vertex name and a positive integer number, which is equal to the length of the shortest path from the source vertex. If there is no path to some vertex from the source, print INF instead of the integer length. Sort lines in the alphabetical order by vertex name and do not include the source vertex in the output. For example: B 1 C 1 D 2 E 3 F INF G INF H INF
Attachments

Stack Implementation
Difficulty: Medium	Test Cases: 5	Published: 2012-10-08
Summary Implement a stack interface
Description Write a program implementing a stack interface for integers. The interface should have 'push' and 'pop' functions. You will be asked to 'push' a series of integers and then 'pop' and print out every alternate integer.
Input Your program should read lines of text from standard input. Each line contains a sequence of space delimited integers.
Output For each line of input, user your stack interface to print to standard output a new sequence containing every alternate integer from the input in reverse order (space delimited), one sequence per line.

Stock Trader - Bearish Cross
Difficulty: Medium	Test Cases: 5	Published: 2019-04-18
Summary Check a series of stock prices for a trading signal
Description A classic stock trading pattern happens when a 9-Day Moving Average (9-DMA) crosses the 50-Day Moving Average (50-DMA). This can be indicative of a bullish or a bearish setup, depending on the direction. When the 9-DMA crosses below the 50-DMA from above, it is Bearish. When the 9-DMA cross above the 50-DMA from below, it is Bullish. Write a program that reads in a series of dates and prices, calculates the 9-DMA and 50-DMA, then returns the dates of any bearish signals that occurred. NOTE: The Moving Average cannot be calculated for a given day if there is not enough historical data to cover the period in question. For example, a series of prices that begin on January 1 cannot have a 9-DMA calculated before January 9 since 9 days of historical prices do not exist until January 9.
Input A series of Date|Price pairs in non-localized format. Dates will follow ISO 8601 format YYYY-MM-DD. Prices will be a two-decimal value with no currency indications. For example: 2016-01-01|22.05 2016-01-02|22.45 2016-01-03|23.57
Output A date in ISO 8601 format where a Bearish Cross occurred. If no Bearish Cross happened, return the string NULL For example: 2016-01-03

Stock Trader - Bullish Cross
Difficulty: Medium	Test Cases: 5	Published: 2019-04-18
Summary Check a series of stock prices for a trading signal
Description A classic stock trading pattern happens when a 9-Day Moving Average (9-DMA) crosses the 50-Day Moving Average (50-DMA). This can be indicative of a bullish or a bearish setup, depending on the direction. When the 9-DMA crosses above the 50-DMA from below, it is Bullish. When the 9-DMA cross below the 50-DMA from above, it is Bearish. Write a program that reads in a series of dates and prices, calculates the 9-DMA and 50-DMA, then returns the dates of any bullish signals that occurred. NOTE: The Moving Average cannot be calculated for a given day if there is not enough historical data to cover the period in question. For example, a series of prices that begin on January 1 cannot have a 9-DMA calculated before January 9 since 9 days of historical prices do not exist until January 9.
Input A series of Date|Price pairs in non-localized format. Dates will follow ISO 8601 format YYYY-MM-DD. Prices will be a two-decimal value with no currency indications. For example: 2016-01-01|22.05 2016-01-02|22.45 2016-01-03|23.57
Output A date in ISO 8601 format where a Golden Cross occurred. If no Golden Cross happened, return the string NULL For example: 2016-01-03

String Rotation
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Find if a string is the rotation of another string.
Description You are given two strings. Determine if the second string is a rotation of the first string.
Input Your program should read lines from standard input. Each line contains two comma separated strings.
Output Print out True/False if the second string is a rotation of the first.

Sudoku
Difficulty: Medium	Test Cases: 16	Published: 2014-03-06
Summary Determine if a grid layout is a valid sudoku solution.
Description A Sudoku board is a 9 x 9 grid of cells where each cell contains a single digit from 1 to 9, inclusive. A valid Sudoku board has the following properties: - Each row contains no duplicate digits - Each column contains no duplicate digits - Each 3 x 3 sub-grid contains no duplicate digits (there are 9 sub-grids) For this challenge, you will be given a 9 x 9 Sudoku board where every cell is populated with a digit from 1 to 9. For a 9 x 9 board, there are 9 sub-grids, each 3 x 3 in size. Write a program that determines whether each input board is valid.
Input Your program should read lines from standard input. Each line contains a comma delimited list of digits in row-major order.
Output Your program should print "True" if the input grid is a valid Sudoku board or "False" if it is not.

Sum of integers
Difficulty: Medium	Test Cases: 4	Published: 2012-10-08
Summary Determine the largest sum of contiguous integers in a sequence.
Description Write a program to determine the largest sum of contiguous integers in a sequence. Contiguous means that the integers are adjacent to each other. Take -4, 2, -5, 0, 3 as an example. For this example the largest sum would be 3 and was obtained from the subsequence 0, 3.
Input Your program should read lines of text from standard input. Each line will contain a sequence of comma-separated integers.
Output For each line of input, print to standard output the sum of the largest contiguous subsequence in each sequence, one integer per line. In other words, of all the possible contiguous subsequences for a given set, find the one with the largest sum, and print that sum.

Sum to Zero
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Count of ways in which the sum of four numbers is zero
Description You are given an array of integers. Count the numbers of ways in which the sum of 4 elements in this array results in zero.
Input Your program should read lines from standard input. Each line consist of comma separated positive and negative integers.
Output Print out the count of the different number of ways that 4 elements sum to zero.

Symmetry of a K-ary Tree - Level-Order
Difficulty: Medium	Test Cases: 12	Published: 2020-08-21
Summary Given a level-order traversal, check whether a K-ary tree is symmetric
Description Write a program to check whether a K-ary tree is symmetric or not. A tree is symmetric if its data and shape remain unchanged when it is reflected around the root node. Tree nodes will contain integer values only. Consider two examples below. The following tree is symmetric:     _____7_____    /    / \         5    2   2    5  / \           /    4   9         9   4 The following tree is not symmetric:     __6__    /  |       3   1   3  /       / 8       8
Input The first line is a positive integer K, which is the maximum number of children of any node in the tree. The second line contains the level-order traversal of the K-ary tree. In this traversal, every node of the current level is visited before proceeding with the next level. Essentially, it is a breadth-first search running on the tree. Any absent child (NULL pointer) of a given node is marked with a # character in the traversal. The input string is a space-delimited mix of integers and # characters. There will be no trailing # characters in the string, it will always end with the value of the last node in the tree traversal. The first example above, which is symmetric, would be described as: 4 7 5 2 2 5 # 4 9 # # # # # # # # # # 9 4
Output Print True if the tree is symmetric. Otherwise, print False.

Symmetry of a K-ary Tree - Pre-Order
Difficulty: Medium	Test Cases: 12	Published: 2020-08-21
Summary Given a pre-order traversal, check whether a K-ary tree is symmetric
Description Write a program to check whether a K-ary tree is symmetric or not. A tree is symmetric if its data and shape remain unchanged when it is reflected around the root node. Tree nodes will contain integer values only. Consider two examples below. The following tree is symmetric:     _____7_____    /    / \         5    2   2    5  / \           /    4   9         9   4 The following tree is not symmetric:     __6__    /  |       3   1   3  /       / 8       8
Input The first line is a positive integer K, which is the maximum number of children of any node in the tree. The second line contains the pre-order traversal of the K-ary tree to be inspected. The nodes are traversed in the following order: Node Children from left to right (from 0 to K - 1). Any absent child (NULL pointer) of a given node is marked with a # character in the traversal. The input string is a space-delimited mix of integers and # characters. There will be no trailing # characters in the string, it will always end with the value of the last node in the tree traversal. The first example above, which is symmetric, would be described as: 4 7 5 # 4 # # # # 9 # # # # # 2 # # # # 2 # # # # 5 # 9 # # # # 4
Output Print True if the tree is symmetric. Otherwise, print False.

Topological Ordering
Difficulty: Medium	Test Cases: 12	Published: 2019-08-07
Summary Find a topological ordering of a directed acyclic graph
Description Write a program that finds a topological ordering of a directed graph. Assume that the graph has no cycles. A topological ordering or topological sort of a directed graph is an ordering of the vertices of the graph such that for every directed edge U,V (from vertex U to vertex V), U is placed before V in the ordering. Another way to think about this is a placement of all vertices of the graph in a single row such that all edges only go forward in the ordering. See input and output descriptions, and the attachments tab for an example of a graph and its topological ordering. Note that more than one variant of topological ordering can exist for a graph. In such a case, the result should be user ordering where vertices with smaller indices come first (are written closer to the left).
Input The first line contains a positive integer representing the number of vertices in the graph. Each additional line contains a space-delimited series of vertex indices describing one or more edges of the graph. The first number in the line is a vertex index of the tail for all edges represented in the current line. Every additional number is a vertex index of the head of the corresponding edge. For example, consider the following input: 4 0 1 2 1 3 2 3 The first row means that there are 4 vertices in the graph. The second row describes two edges, one from vertex 0 to vertex 1 and another from vertex 0 to vertex 2. The third row means that there is an edge from vertex 1 to vertex 3, and so on. See the attachments tab for an image representation of this graph and its topological ordering.
Output A topological ordering of the graph as a space-delimited list of vertex indices. For example: 0 1 2 3 In this example, there is another correct topological ordering 0 2 1 3. But we must select the variant 0 1 2 3 where vertex 1 (with a smaller index) is placed before the vertex 2 (with a greater index).
Attachments

Trailing String
Difficulty: Medium	Test Cases: 6	Published: 2012-10-08
Summary Determine if a string 'B' occurs at the end of string 'A'
Description You are given two strings A and B. Print the number 1 if string B occurs at the end of string A. Otherwise, print the number 0.
Input Your program should read lines of text from standard input. Each line will contain two strings, A and B, separated by a comma.
Output For each input line, print the number 1 if the second string occurs at the end of the first string, or 0 if it does not, one digit per line.

Transport Network - Minimum Cut
Difficulty: Medium	Test Cases: 7	Published: 2019-07-15
Summary Find a minimum cut of the graph representing the transport network
Description In a strategy game, a player's base has a transport network, which is used for the interaction of all buildings and structures. While the player is constructing and developing his base, his AI opponent is planning an attack. The first step in this attack is to determine the weakest place in the connection between parts of the player's base and separate the base into two pieces. Write a program to find the most vulnerable partitioning of the transport network. The number of roads connecting these two pieces must be minimum possible. The transport network consists of nodes representing buildings and roads that connect nodes. Every building has an integer index from 0 to n assigned to it.
Input Each line describes connections of one building with others in the network using a space-separated list of integer indices. The first element of the list is the index of the current building, and all other elements are the indices of the buildings that are connected by roads with the current building. For example: 0 1 5 1 0 2 5 2 1 3 4 3 2 4 4 2 3 5 0 1 The first row means that the building with index 0 is connected to the buildings 1 and 5. The second row describes that there are roads from building 1 to buildings 0, 2, and 5. See the attachments tab for an image representation of this transport network.
Output Two lines with space-separated sorted indices of the buildings representing the split of the network into two parts. The first line describes the part of the network containing the building with index 0. For example: 0 1 5 2 3 4
Attachments

URI Comparison
Difficulty: Medium	Test Cases: 10	Published: 2014-03-06
Summary Determine if two URIs match
Description Determine if two URIs match. For the purpose of this challenge, you should use a case-sensitive octet-by-octet comparison of the entire URIs, with these exceptions: 1. A port that is empty or not given is equivalent to the default port of 80 2. Comparisons of host names MUST be case-insensitive 3. Comparisons of scheme names MUST be case-insensitive 4. Characters are equivalent to their % HEX HEX encodings. (Other than typical reserved characters in urls like , / ? : @ & = + $ #)
Input Your program should read lines from standard input. Each line contains two urls delimited by a semicolon.
Output Print out True/False if the URIs match.

Unstacking
Difficulty: Medium	Test Cases: 8	Published: 2019-06-24
Summary Find a maximum score in the boxes unstacking puzzle
Description Consider a stack of N boxes that you must flatten into multiple stacks, each containing a single box, through a series of steps. With each step, you are allowed to split one stack of boxes into two non-empty stacks. After each step, a score will be calculated by multiplying the heights of the stacks after the split. For example, if you split a single stack of 8 boxes into 2 stacks of 4 boxes each, the score for that step will be 4 x 4 = 16 points for that step. The process ends when there are N stacks, each containing a single box. The final score for the puzzle will be the sum of the points calculated across all steps. See the attachments tab for an example with the stack of 8 boxes. Given the initial number of the boxes in the stack, calculate the maximum achievable score.
Input A positive integer N, that is the initial number of boxes in the stack.
Output The maximum achievable score for the unstacking puzzle with N boxes.
Attachments

Valid Parentheses
Difficulty: Medium	Test Cases: 10	Published: 2014-02-21
Summary Determine if string is made up of well-formed parentheses.
Description Given a string consisting just of the characters (,),{,},[,] determine if it is well-formed or not.
Input Your program should read lines from standard input. Each line contains a string consisting of the characters mentioned above. There is no whitespace between characters.
Output Print out True if the string is well-formed, False otherwise.