Tag Archives: matching

Utopian Identification Number: Hackerrank

Problem link: https://www.hackerrank.com/challenges/utopian-identification-number

Problem Statement:
A new identification number is given for every Citizen of the Country Utopia and it has the following format.

1. The string must begin with between 0 and 3 (inclusive) lowercase letters.
2. Immediately following the letters, there must be a sequence of digits. The length of this segment must be between 2 and 8, both inclusive.
3. Immediately following the numbers, there must be at least 3 uppercase letters.

Your task is to find out if a given identification number is valid or not.
Continue reading


Detect HTML Tags: Hackerrank

Problem link: https://www.hackerrank.com/challenges/detect-html-tags

Problem Statement:
In this problem you will use regular expressions to help you detect the various Tags used in an HTML document.

Here are a few examples of tags:

The “p” tag for paragraphs:

<p>This is a paragraph</p>

It is also okay to have one or more spaces before or after the tag name:

<  p >This is also a paragraph</p>

Then, there is also something called a void or an empty tag such as:


Some tags can also have attributes. For example, here we see the “a” tag which is used for adding links to a document.

<a href="http://www.google.com">Google</a> 

There are also tags such as this which haven’t been split into an opening and closing tag:

In the above case, “a” is the tag and “href” is an attribute, the value of which is “http://www.google.com”. Ignore any attributes. Your task is to find out all the tags present in the given document.
Continue reading

String Similarity: Hackerrank

Problem link: https://www.hackerrank.com/challenges/string-similarity

Problem Statement:
For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings “abc” and “abd” is 2, while the similarity of strings “aaa” and “aaab” is 3.

Calculate the sum of similarities of a string S with each of it’s suffixes.
Continue reading

CompletingBrackets : TopCoder Problem 5977

[The problem appeared in TopCoder SRM 280 (Div-1, Level-1) and TopCoder SRM 280 (Div-2, Level-2)]

Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=5977

Problem Statement:
A series of brackets is complete if we can pair off each left bracket ‘[‘ with a right bracket ‘]’ that occurs later in the series. Every bracket must participate in exactly one such pair.

Given a String text add the minimal number of brackets to the beginning and/or end of text to make it complete. Return the result.
Continue reading

SpamDetector : TopCoder Problem 2229

[The problem appeared in TopCoder SRM 205 (Div-1, Level-1) and TopCoder SRM 205 (Div-2, Level-2)]

Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=2229

Problem Statement:
You are writing part of a spam detection system. Your job is to analyze the subject lines of e-mail messages and return a count of known spam signalling keywords in the subject lines. Your task is made more difficult by the spammers who try to hide the keywords in several ways. Here we will consider just one obfuscation technique: duplicating characters. Duplicating characters means taking an existing character in a word and inserting more copies of that character into the same place in the word. This process can then be repeated on a different character in the word. The spam signalling keyword “credit” might be modified to “creddiT”, “CredittT” or “ccrreeeddiitt”, etc., but not “credict”.

For the purposes of this problem we will consider subject lines which contain only letters and spaces. The “words” in the subject line are delimited by spaces. A word in the subject line is considered a “match” if the entire word is the same as at least one entire keyword, after possibly removing some duplicated characters from the subject word. A keyword that matches only part of a subject word or a subject word that matches only part of a keyword does not count. Note that if a keyword contains a double letter, the subject word must also contain (at least) a double letter in the same position to match (“double letter” means two consecutive letters in the word that are the same). For this application, all matches (and the use of the term “same”) are case insensitive.

Given a subject line and a list of keywords, return the count of words in the subject line which “match” words in the keyword list. If multiple words in the subject line match the same keyword, they are each counted, but a word in the subject line that matches multiple keywords is only counted once.
Continue reading