2048 | ||
| Difficulty: Medium | Test Cases: 12 | Published: 2020-01-11 |
SummaryCompute the state of the 2048 puzzle after the player's move | ||
Description2048 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. | ||
InputThe 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
| ||
OutputFour 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 |
SummaryFind a linear ordering of courses to meet prerequisites | ||
DescriptionConsider 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. | ||
InputThe 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. | ||
OutputA 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 |
SummaryPerform a fundamental IPv4 routing check | ||
DescriptionA 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. | ||
InputTwo lines of input as follows:
| ||
OutputIf 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 |
SummaryDetermine if an array contains a duplicated entry | ||
DescriptionImagine 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. | ||
InputYour 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. | ||
OutputFor 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 |
SummaryFacebook Hacker Cup 2013 problem. | ||
DescriptionCredits: This problem appeared in the Facebook Hacker Cup 2013 Hackathon. | ||
InputYour program should read lines from standard input. Each line contains a message that you got from John. | ||
OutputPrint 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 |
SummaryDecode the binary coded decimal (BCD) date and time | ||
DescriptionImagine 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. 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
| ||
InputA 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
| ||
OutputA 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 |
SummaryDetermine the amount of change to be returned | ||
DescriptionThe 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: | ||
InputYour 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. | ||
OutputFor 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 |
SummaryTry to pass a chain | ||
DescriptionWe 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. | ||
InputYour 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]. | ||
OutputPrint out the status of the chain (GOOD or BAD). | ||
Christmas Lights | ||
| Difficulty: Medium | Test Cases: 8 | Published: 2019-10-04 |
SummaryCheck if a net of Christmas lights is 2-colorable | ||
DescriptionImagine 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. | ||
InputEach 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 | ||
OutputPrint 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 |
SummaryImplement a simple collaborative filter counting inversions | ||
DescriptionA 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:
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. | ||
InputEach 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
| ||
OutputPrint 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: | ||
Collaborative Filtering - Simple | ||
| Difficulty: Medium | Test Cases: 5 | Published: 2019-10-04 |
SummaryImplement a simple collaborative filter counting inversions | ||
DescriptionA 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:
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:
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. | ||
InputEach 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
| ||
OutputPrint 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 |
SummaryConvert colors from the HSV to the RGB model | ||
DescriptionA 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. | ||
InputEach 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. An example of the input: 036,078,100 153,071,100
| ||
OutputEach 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 |
SummaryConvert colors from the RGB to the CMYK model | ||
DescriptionA 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. | ||
InputEach 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
| ||
OutputEach 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 |
SummaryConvert colors from the RGB to the HSV model | ||
DescriptionA 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. | ||
InputEach 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
| ||
OutputEach 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. 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 |
SummaryGiven a range of numbers 1-N, determine how many ways the numbers can be arranged such that every consecutive pair sums to a prime. | ||
DescriptionAlice 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. | ||
InputThe inputs consist of one even integer on a line. Each integer N is 2 <= N <= 18. | ||
OutputPrint 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 |
SummaryCount the number of primes between two integers. | ||
DescriptionGiven two integers N and M, count the number of prime numbers between N and M (both inclusive). | ||
InputYour program should read lines from standard input. Each line contains two comma-separated positive integers. | ||
OutputPrint 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 |
SummaryCalculate a cumulative frequency of the grouped data | ||
DescriptionWrite 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: 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. | ||
InputA space-separated array of integers, that represents a daily commute time in minutes. For example: | ||
OutputA space-separated array of cumulative frequencies of data classes. Classes are sorted in ascending order. For example: | ||
Decimal To Binary | ||
| Difficulty: Medium | Test Cases: 6 | Published: 2012-10-08 |
SummaryPrint the binary representation of a decimal number. | ||
DescriptionGiven a decimal (base 10) number, print out its binary representation. | ||
InputYour program should read lines of text from standard input. Each line will contain a single integer. | ||
OutputFor 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 |
SummaryCount the number of ways to decode a string. | ||
DescriptionYou 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. | ||
InputYour 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. | ||
OutputPrint 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 |
SummaryMerge two CSV documents based on a key | ||
DescriptionWrite 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
| ||
InputTwo 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
| ||
OutputA 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 |
SummaryFaceBook Hacker Cup 2011: Output the number of ways to write X as the sum of two squares | ||
DescriptionCredits: This challenge appeared in the Facebook Hacker Cup 2011. | ||
InputYour 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. | ||
OutputFor 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 |
SummaryFind the shortest path to escape a dungeon | ||
DescriptionYou 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:
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. | ||
InputA 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.
For example: ###...##.. ....#....# #..###.#.# S#.#.#.#.. ...#...E#.
| ||
OutputThe 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 |
SummaryWrite a regular expression to validate an email address | ||
DescriptionWrite 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 name@domain.tld 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". | ||
InputYour program should read lines of text from standard input. Each line contains a string that may or may not be a valid email address. | ||
OutputFor 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 |
SummaryBuffer input to a cyclic process | ||
DescriptionYou 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. | ||
InputA comma-delimited line with the three variables: N, T, X | ||
OutputThe 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 |
SummaryDo 4 points make a square? | ||
DescriptionYou have coordinates of four points on a plane. Check whether they make a square. | ||
InputYour 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. | ||
OutputPrint true/false if the points make up a square. | ||
Fires in the Amazon | ||
| Difficulty: Medium | Test Cases: 12 | Published: 2020-01-11 |
SummaryValidate the imported dataset | ||
DescriptionWhen 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:
Write a program to validate the first dataset using the summary data from the second. | ||
InputTwo datasets in CSV format separated by one empty line. The first dataset has the following columns:
The second dataset has the following columns:
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
| ||
OutputPrint 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 |
SummaryFind the first non repeated character in a string. | ||
DescriptionWrite a program that finds the first non repeated character in a string. | ||
InputYour program should read lines of text from standard input. | ||
OutputFor 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 |
SummaryImplement an algorithm to check solvability of the 15 puzzle | ||
DescriptionThere 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.
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. | ||
InputA 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 | +----+----+----+----+
| ||
OutputPrint 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 |
SummaryConvert a hexadecimal number into a signed decimal | ||
DescriptionWrite 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. | ||
InputEach 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
| ||
OutputFor 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 |
SummaryCreate some fundamental set logic | ||
DescriptionWrite 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. | ||
InputTwo lines of input, each with a space-delimited series of values that represent the two sets. For example: 1 2 3 A B C | ||
OutputThe 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 |
SummaryDetermine if a sequence of numbers is a Jolly Jumper | ||
DescriptionCredits: Programming Challenges by Steven S. Skiena and Miguel A. Revilla | ||
InputYour 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. | ||
OutputFor 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 |
SummaryFind number words in the jumbled string | ||
DescriptionIn 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. | ||
InputA string formed from jumbled letters of numerals. For example: reuonnoinfe
| ||
OutputA 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 |
SummaryFinding the 'N' longest lines within a file. | ||
DescriptionWrite a program that finds the N longest lines from standard input. | ||
InputYour 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. | ||
OutputPrint 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 |
SummaryTry to become a native speaker | ||
DescriptionCredits: This is an adaptation of the original challenge that was created by David Arthur. | ||
InputYour 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. | ||
OutputFor each test case, output one line containing a translated string. | ||
Lowest Common Ancestor | ||
| Difficulty: Medium | Test Cases: 5 | Published: 2012-10-08 |
SummaryDetermine the lowest common ancestor within a tree | ||
DescriptionWrite 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 | ||
InputYour 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. | ||
OutputPrint to standard output the least common ancestor of the two nodes. | ||
Magic Numbers | ||
| Difficulty: Medium | Test Cases: 10 | Published: 2013-12-18 |
SummaryPrint out a list of all the magic numbers in a provided range | ||
DescriptionThere 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. | ||
InputThe input consists of two integers on a line, separated by spaces. Each integer A and B is 1 <= A <= B <= 10000. | ||
OutputPrint 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 |
SummaryFind the approximate median of the array | ||
DescriptionIn 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:
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. | ||
InputAn 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
| ||
OutputThe 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 |
SummaryFind the minimum number of coins to arrive at a total. | ||
DescriptionYou 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. | ||
InputYour program should read lines from standard input. Each line contains a positive integer number which represents the total you have to arrive at. | ||
OutputPrint 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 |
SummaryDetermine the Mth to last element of a sequence | ||
DescriptionWrite a program to determine the Mth to last element of a sequence. | ||
InputYour 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. | ||
OutputPrint 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 |
SummaryPrint the decimal number given its negabinary representation | ||
DescriptionGiven the negabinary representation (base -2) of an integer, convert it to the decimal (base 10) value. | ||
InputEach line of input contains a single integer value expressed as a negabinary value. | ||
OutputFor 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 |
SummaryPrint out a level structure of the computer network. | ||
DescriptionGiven 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. | ||
InputThe 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. | ||
OutputEach line represents a level (or layer) of the network, starting from source node on the first line which forms the first layer. 10 1 21 64 5 99
| ||
Attachments | ||
Network Space | ||
| Difficulty: Medium | Test Cases: 6 | Published: 2019-04-02 |
SummaryPerform a fundamental networking function | ||
DescriptionA 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. | ||
InputA standard CIDR block. For example: | ||
OutputTwo lines indicating the following:
For example: 192.168.0.0 255.255.0.0
| ||
Normalize Levels | ||
| Difficulty: Medium | Test Cases: 6 | Published: 2019-04-18 |
SummaryAdjust a series of scalars to match a target range | ||
DescriptionImagine 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:
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. | ||
InputEach line of input will be a comma-separated series of positive integers representing the stream of sound levels for each track. | ||
OutputPrint 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 |
SummaryGiven 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. | ||
DescriptionAlice 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. | ||
InputThe input consists of five integers on a line, separated by spaces. Each integer V is 0 <= V <= 52. | ||
OutputPrint 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 |
SummaryFind pairs of numbers in a sorted array whose sum is X | ||
DescriptionYou 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 | ||
InputYour 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. | ||
OutputFor 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 |
SummaryDetermine the number of one bits in an integer. | ||
DescriptionWrite a program to determine the number of 1 bits in the internal representation of a given integer. | ||
InputYour program should read lines of text from standard input. Each line will contain a single integer in decimal form. | ||
OutputFor 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 |
SummaryGiven a weight limit and a list of objects with specified weight and value, determine the maximum value of items without exceeding the weight limit. | ||
DescriptionBob 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. 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. | ||
InputThe 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. | ||
OutputPrint 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 |
SummaryDetermine if two rectangles overlap. | ||
DescriptionGiven 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. | ||
InputYour 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. | ||
OutputPrint out True if A and B intersect, False otherwise. | ||
Pangrams | ||
| Difficulty: Medium | Test Cases: 11 | Published: 2012-10-08 |
SummaryFind the missing alphabets | ||
DescriptionThe 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. | ||
InputYour program should read lines of text from standard input. Each line contains a sentence. | ||
OutputFor 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 |
SummaryPrint out pascals triangle up to a certain depth. | ||
DescriptionA 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
| ||
InputYour program should read lines from standard input. Each line contains a positive integer which indicates the depth of the triangle (1 based). | ||
OutputPrint 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 |
SummaryLead the way within the triangle | ||
DescriptionGiven 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 | ||
InputYour 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. | ||
OutputPrint out the maximum sum for a downward path in the triangle. | ||
Password Strength | ||
| Difficulty: Medium | Test Cases: 12 | Published: 2019-12-03 |
SummaryUse regular expressions to determine password strength | ||
DescriptionWrite 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:
All value ranges in the above description are inclusive. | ||
InputA string containing a password. For example: Nufu&YM21S
| ||
OutputPrint 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 |
SummaryEliminate every X item from a circular list | ||
DescriptionA 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. | ||
InputYour 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. | ||
OutputPrint 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 |
SummaryClose a hole in a wall | ||
DescriptionYou 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. | ||
InputYour 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. | ||
OutputFor 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 |
SummaryDefine whether a point is in a circle | ||
DescriptionGiven 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. | ||
InputYour 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. | ||
OutputPrint true/false if the point is in the circle. | ||
Predict the Number | ||
| Difficulty: Medium | Test Cases: 10 | Published: 2014-03-06 |
SummaryTry to go beyond the limits | ||
DescriptionThe example sequence 011212201220200112 ... is constructed as follows: | ||
InputYour program should read lines from standard input. Each line contains an integer N such that 0 <= N <= 3000000000. | ||
OutputPrint out the number which is at the Nth position in the sequence. | ||
Prime Numbers | ||
| Difficulty: Medium | Test Cases: 5 | Published: 2012-10-08 |
SummaryPrint prime numbers less than N | ||
DescriptionPrint out the prime numbers less than a given number N. You may assume that N is always a positive integer. | ||
InputYour program should read lines of text from standard input. Each line will contain an integer n < 4,294,967,295. | ||
OutputFor 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 |
SummaryImplement a priority queue data structure | ||
DescriptionWrite 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 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. | ||
InputThe 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
| ||
OutputPrint 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 |
SummaryApply a recursive median filter to a series of data | ||
DescriptionFinally, 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. 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. | ||
InputThe 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
| ||
OutputPrint 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 |
SummaryCalculate a relative frequency of the grouped data | ||
DescriptionWrite 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:
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. | ||
InputA space-delimited list integers that represents a set of daily commute times in minutes. For example: 14 15 15 14 13 19 21 10
| ||
OutputA 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 |
SummaryDelete specific characters from a string. | ||
DescriptionWrite a program to remove specific characters from a string. | ||
InputYour 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. | ||
OutputPrint 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 |
SummaryReverse elements in a list k items at a time. | ||
DescriptionGiven 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. | ||
InputYour 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. | ||
OutputPrint out the new comma separated list of numbers obtained after reversing. | ||
Reverse and Add | ||
| Difficulty: Medium | Test Cases: 4 | Published: 2012-10-08 |
SummaryContinually add a number to its reverse to arrive at a palindrome | ||
DescriptionCredits: Programming Challenges by Steven S. Skiena and Miguel A. Revilla | ||
InputYour 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) | ||
OutputFor 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 |
SummaryUnravel a special kind of lock | ||
DescriptionYou 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:
How To Scroll A Scrolling Number will visit every digit exactly once and end at the leftmost digit. For example, consider the Scrolling Number 6231.
| ||
InputThe 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. | ||
OutputPrint 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 |
SummaryTransform a binary sequence into a string | ||
DescriptionThere 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: 00 AAA
is possible because 0 can be either "A" or "AA". | ||
InputYour 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]. | ||
OutputFor 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 |
SummarySelect a set of points to minimize the distance | ||
DescriptionConsider 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. | ||
InputEach 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
| ||
OutputA 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 |
SummaryGiven a noisy source, find the message payload | ||
DescriptionMany 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. | ||
InputThe 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. | ||
OutputThe 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 |
SummaryConvert a signed decimal number into a hexadecimal | ||
DescriptionWrite 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). | ||
InputEach line of input contains one base 10 signed integer value. For example: -2 -50 2 112 -113
| ||
OutputFor 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 |
SummaryCreate a simple calculator | ||
DescriptionThe goal of this challenge is to create a simple calculator. 1 () Brackets 2 - Unary minus 3 ^ Exponent 4 *, / Multiply, Divide (left-to-right precedence) 5 +, - Add, Subtract (left-to-right precedence)
| ||
InputYour 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. | ||
OutputPrint 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. | ||
Single-Source Shortest Path | ||
| Difficulty: Medium | Test Cases: 7 | Published: 2019-10-04 |
SummaryFind the shortest paths from a source vertex to all other vertices in the undirected graph | ||
DescriptionWrite 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). | ||
InputThe 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 | ||
OutputEach 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 |
SummaryImplement a stack interface | ||
DescriptionWrite 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. | ||
InputYour program should read lines of text from standard input. Each line contains a sequence of space delimited integers. | ||
OutputFor 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 |
SummaryCheck a series of stock prices for a trading signal | ||
DescriptionA 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. | ||
InputA 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
| ||
OutputA date in ISO 8601 format where a Bearish Cross occurred. If no Bearish Cross happened, return the string NULL For example: | ||
Stock Trader - Bullish Cross | ||
| Difficulty: Medium | Test Cases: 5 | Published: 2019-04-18 |
SummaryCheck a series of stock prices for a trading signal | ||
DescriptionA 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. | ||
InputA 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
| ||
OutputA date in ISO 8601 format where a Golden Cross occurred. If no Golden Cross happened, return the string NULL For example: | ||
String Rotation | ||
| Difficulty: Medium | Test Cases: 10 | Published: 2014-03-06 |
SummaryFind if a string is the rotation of another string. | ||
DescriptionYou are given two strings. Determine if the second string is a rotation of the first string. | ||
InputYour program should read lines from standard input. Each line contains two comma separated strings. | ||
OutputPrint out True/False if the second string is a rotation of the first. | ||
Sudoku | ||
| Difficulty: Medium | Test Cases: 16 | Published: 2014-03-06 |
SummaryDetermine if a grid layout is a valid sudoku solution. | ||
DescriptionA Sudoku board is a 9 x 9 grid of cells where each cell contains a single digit from 1 to 9, inclusive. | ||
InputYour program should read lines from standard input. Each line contains a comma delimited list of digits in row-major order. | ||
OutputYour 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 |
SummaryDetermine the largest sum of contiguous integers in a sequence. | ||
DescriptionWrite 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. | ||
InputYour program should read lines of text from standard input. Each line will contain a sequence of comma-separated integers. | ||
OutputFor 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 |
SummaryCount of ways in which the sum of four numbers is zero | ||
DescriptionYou are given an array of integers. Count the numbers of ways in which the sum of 4 elements in this array results in zero. | ||
InputYour program should read lines from standard input. Each line consist of comma separated positive and negative integers. | ||
OutputPrint 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 |
SummaryGiven a level-order traversal, check whether a K-ary tree is symmetric | ||
DescriptionWrite 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.
_____7_____ / / \ 5 2 2 5 / \ / 4 9 9 4
__6__ / | 3 1 3 / / 8 8
| ||
InputThe 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
| ||
OutputPrint 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 |
SummaryGiven a pre-order traversal, check whether a K-ary tree is symmetric | ||
DescriptionWrite 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.
_____7_____ / / \ 5 2 2 5 / \ / 4 9 9 4
__6__ / | 3 1 3 / / 8 8
| ||
InputThe 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:
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
| ||
OutputPrint True if the tree is symmetric. Otherwise, print False. | ||
Topological Ordering | ||
| Difficulty: Medium | Test Cases: 12 | Published: 2019-08-07 |
SummaryFind a topological ordering of a directed acyclic graph | ||
DescriptionWrite 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). | ||
InputThe 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. | ||
OutputA 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 |
SummaryDetermine if a string 'B' occurs at the end of string 'A' | ||
DescriptionYou 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. | ||
InputYour program should read lines of text from standard input. Each line will contain two strings, A and B, separated by a comma. | ||
OutputFor 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 |
SummaryFind a minimum cut of the graph representing the transport network | ||
DescriptionIn 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. 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. | ||
InputEach 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. | ||
OutputTwo 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 |
SummaryDetermine if two URIs match | ||
DescriptionDetermine 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: | ||
InputYour program should read lines from standard input. Each line contains two urls delimited by a semicolon. | ||
OutputPrint out True/False if the URIs match. | ||
Unstacking | ||
| Difficulty: Medium | Test Cases: 8 | Published: 2019-06-24 |
SummaryFind a maximum score in the boxes unstacking puzzle | ||
DescriptionConsider 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. | ||
InputA positive integer N, that is the initial number of boxes in the stack. | ||
OutputThe maximum achievable score for the unstacking puzzle with N boxes. | ||
Attachments | ||
Valid Parentheses | ||
| Difficulty: Medium | Test Cases: 10 | Published: 2014-02-21 |
SummaryDetermine if string is made up of well-formed parentheses. | ||
DescriptionGiven a string consisting just of the characters (,),{,},[,] determine if it is well-formed or not. | ||
InputYour program should read lines from standard input. Each line contains a string consisting of the characters mentioned above. There is no whitespace between characters. | ||
OutputPrint out True if the string is well-formed, False otherwise. | ||