File Naming

Description:

You are given an array of desired filenames in the order of their creation. Since two files cannot have equal names, the one which comes later will have an addition to its name in a form of (k), where k is the smallest positive integer such that the obtained name is not used yet.

Return an array of names that will be given to the files.

Example

For names = ["doc", "doc", "image", "doc(1)", "doc"], the output should be
fileNaming(names) = ["doc", "doc(1)", "image", "doc(1)(1)", "doc(2)"].

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.string names

    Constraints:
    5 ≤ names.length ≤ 15,
    1 ≤ names[i].length ≤ 15.

  • [output] array.string

Tests:
Solution(C#):

string[] fileNaming(string[] names) {
    List<String> result = new List<String>();
    Helper h = new Helper(names.Length);

    for (int i = 0; i < names.Length; i++) {
        int hash = h.calculateHash(names[i]),
        startPos =  h.searchHM(h.calculateHash(names[i])%h.hashMapSize, hash);
        if (h.hashMap[startPos].element == "") {
            h.hashMap[startPos] = new HashMapElement(names[i], hash, 1);
            result.Add(names[i]);
        }
        else {
            String newName = names[i] + "(" +
            h.hashMap[startPos].version + ")";
            int newNameHash = h.calculateHash(newName),
            position = h.searchHM(newNameHash % h.hashMapSize, newNameHash);

            while (h.hashMap[position].element != "") {
                h.hashMap[startPos].version++;
                newName = names[i] + "(" +
                h.hashMap[startPos].version + ")";
                newNameHash = h.calculateHash(newName);
                position = h.searchHM(newNameHash % h.hashMapSize, newNameHash);
            }
            h.hashMap[position] = new HashMapElement(newName, newNameHash, 1);
            result.Add(newName);
            h.hashMap[startPos].version++;
        }
    }
    return result.ToArray();
}
public class HashMapElement {
    public String element{get;set;}
    public int hash{get;set;}
    public int version{get;set;} //the smallest possible integer to use with this name

    public HashMapElement(String a, int b, int c) {
      element = a;
      hash = b;
      version = c;
    }
  };

public class Helper {
    public int hashMapSize{get;set;}
    public HashMapElement[] hashMap{get;set;}

    public Helper(int halfSize) {
        hashMapSize = halfSize * 2;
        hashMap = new HashMapElement[hashMapSize];
        for (int i = 0; i < hashMapSize; i++) {
            hashMap[i] = new HashMapElement("", -1, 0);
        }
    }

    public int calculateHash(String inputString) {
        int P = 997,
            M = 28001;
        int hashValue = 0;
        for (int i = 0; i < inputString.Length; i++) {
            hashValue = (hashValue * P + (int)inputString[i]) % M;
        }
        return hashValue;
    }

    public int searchHM(int position, int hash) {
        while (hashMap[position].element != ""
          && hashMap[position].hash != hash) {
            position = (position + 1) % hashMapSize;
        }
        return position;
    }
};

Christmas Tree

Description:

It’s Christmas time! To share his Christmas spirit with all his friends, young Christmas elf decided to send each of them a Christmas e-mail with a nice Christmas tree. Unfortunately, Internet traffic is very expensive in the North Pole, so instead of sending an actual image he decided to draw the tree using only asterisks ('*' symbols). He has given you the specs (see below) and your task is to write a program that would generate trees following the spec and some initial parameters.

Here is a formal definition of how the tree should be built but before you read it the elf HIGHLY recommends looking first at the examples that follow:

  • Each tree has a crown, that looks as follows:
     *
     *
    ***
    
  • Define a line as a horizontal group of asterisks and a level as a collection of levelHeight lines stacked one on top of the other.
  • Below the crown there are levelNum levels.
  • The tree is perfectly symmetric so all the middle asterisks of the lines lie on the center of the tree.
  • Each line of the same level (excluding the first one) has two more asterisks than the previous one (one on each end);
  • The number of asterisks in the first line of each level is chosen as follows:
    • the first line of the first level has 5 asterisks;
    • the first line of each consecutive level contains two more asterisks than the first line of the previous level.
  • And finally there is the tree foot which has a height of levelNum and a width of:
    • levelHeight asterisks if levelHeight is odd;
    • levelHeight + 1 asterisks if levelHeight is even.

Given levelNum and levelHeight, return the Christmas tree of the young elf.

Example

  • For levelNum = 1 and levelHeight = 3, the output should be
    christmasTree(levelNum, levelHeight) =
        ["    *",
         "    *",
         "   ***",
         "  *****",
         " *******",
         "*********",
         "   ***"]
    

    , which represents the following tree:

                ___
          *        |
          *        |-- the crown      
         ***    ___|       
        *****      |
       *******     |-- level 1
      ********* ___|
         ***    ___|-- the foot
    
  • For levelNum = 2 and levelHeight = 4, the output should be
    christmasTree(levelNum, levelHeight) = 
        ["      *", 
         "      *", 
         "     ***", 
         "    *****", 
         "   *******", 
         "  *********", 
         " ***********", 
         "   *******", 
         "  *********", 
         " ***********", 
         "*************", 
         "    *****", 
         "    *****"]
    

    , which represents the following tree:

                    ___ 
            *          |
            *          | -- the crown
           ***      ___|
          *****        |
         *******       | -- level 1
        *********      |
       ***********  ___|
         *******       |
        *********      | -- level 2
       ***********     |
      ************* ___|
          *****        | -- the foot
          *****     ___|
    

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer levelNum

    A positive integer, the number of levels.

    Constraints:
    1 ≤ levelNum ≤ 8.

  • [input] integer levelHeight

    The number of lines in each level.

    Constraints:
    3 ≤ levelHeight ≤ 8.

  • [output] array.string

    The Christmas tree according to the specs and the inputs. Output elements should not contain trailing whitespaces, and at least one of them should start with '*'symbol.

Tests:
Solution(C#):

string[] christmasTree(int levelNum, int levelHeight) {
    List<string> result = new List<string>();
    List<string> middles = new List<string>();
    List<string> foot = new List<string>();
    string topCrown ="*";
    string lastMiddleItem ="*";
    string middleItem ="***";
    string bottomCrown;
    for(int j=0;j<levelNum;j++) {
        for(int i=1;i<=levelHeight;i++) {
            if(j==0) {
                if(i>0) {
                    topCrown=" "+topCrown;
                }
            }
            middleItem = "*"+middleItem+"*";
            lastMiddleItem = middleItem;
            middles.Add(new string(' ', levelHeight - i +levelNum-j-1)+middleItem);
        }
        topCrown=" "+topCrown;
        middleItem = new string('*',(j+2)*2+1);
    }
    if(levelHeight%2==0) {
        levelHeight++;
        bottomCrown = new string(' ',(lastMiddleItem.Length - levelHeight)/2) + new string('*',levelHeight);
    }
    else {
        bottomCrown = new string(' ',(lastMiddleItem.Length - levelHeight)/2) + new string('*',levelHeight);
    }
    for(int j=0;j<levelNum;j++) {
        foot.Add(bottomCrown);
    }
    result.Add(topCrown);
    result.Add(topCrown);
    result.Add(topCrown.Replace(" *","***"));
    result.AddRange(middles);
    result.AddRange(foot);
    return result.ToArray();
}

Runners Meetings

Description:

Some people run along a straight line in the same direction. They start simultaneously at pairwise distinct positions and run with constant speed (which may differ from person to person).

If two or more people are at the same point at some moment we call that a meeting. The number of people gathered at the same point is called meeting cardinality.

For the given starting positions and speeds of runners find the maximum meeting cardinality assuming that people run infinitely long. If there will be no meetings, return -1instead.

Example

For startPosition = [1, 4, 2] and speed = [27, 18, 24], the output should be
runnersMeetings(startPosition, speed) = 3.

In 20 seconds after the runners start running, they end up at the same point. Check out the gif below for better understanding:

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.integer startPosition

    A non-empty array of integers representing starting positions of runners (in meters).

    Constraints:
    2 ≤ startPosition.length ≤ 10,
    -1000 ≤ startPosition[i] ≤ 1000.

  • [input] array.integer speed

    Array of positive integers of the same length as startPosition representing speeds of the runners (in meters per minute).

    Constraints:
    speed.length = startPosition.length,
    1 ≤ speed[i] ≤ 30.

  • [output] integer

    The maximum meeting cardinality or -1 if there will be no meetings.

Tests:
Solution(C#):

int runnersMeetings(int[] startPosition, int[] speed) {
    int result = 1;

    for (int i = 0; i < startPosition.Length; i++) {
        for (int j = i + 1; j < startPosition.Length; j++) {
            int distDiff = startPosition[j] - startPosition[i],
                speedDiff = speed[i] - speed[j],
                cnt = 0;
            if(speedDiff==0&&distDiff!=0)
                continue;
            for (int k = 0; k < startPosition.Length; k++) {
                if (startPosition[k] * speedDiff + speed[k] * distDiff
                    == startPosition[i] * speedDiff + speed[i] * distDiff) {            
                    cnt++;
                }
            }

            if (cnt==0) {
                continue;
            }

            if (cnt > result) {
                result = cnt;
            }
        }
    }
    if(result<2)
        result = -1;
    return result;
}

Cyclic String

Description:

You’re given a substring s of some cyclic string. What’s the length of the smallest possible string that can be concatenated to itself many times to obtain this cyclic string?

Example

For s = "cabca", the output should be
cyclicString(s) = 3.

"cabca" is a substring of a cycle string "abcabcabcabc..." that can be obtained by concatenating "abc" to itself. Thus, the answer is 3.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] string s

    Constraints:
    3 ≤ s.length ≤ 15.

  • [output] integer

Tests:
Solution(C#):

int cyclicString(string s) {
    for (int i = 1;i<=s.Length;i++) {
        string part = s.Substring(0,i);
        bool isRoot = true;
        for (int j = 0;j<s.Length;j++) {
            if (s[j] != part[j % part.Length]) {
                isRoot = false;
                break;
            }
        }
        if (isRoot) {
            return i;
        }
    }
    return 0;
}

Strings Crossover

Description:

Define crossover operation over two equal-length strings A and B as follows:

  • the result of that operation is a string of the same length as the input strings
  • result[i] is chosen at random between A[i] and B[i]

Given array of strings inputArray and a string result, find for how many pairs of strings from inputArray the result of the crossover operation over them may be equal to result.

Note that (A, B) and (B, A) are the same pair. Also note that the pair cannot include the same element of the array twice (however, if there are two equal elements in the array, they can form a pair).

Example

For inputArray = ["abc", "aaa", "aba", "bab"] and result = "bbb", the output should be
stringsCrossover(inputArray, result) = 2.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.string inputArray

    A non-empty array of equal-length strings.

    Constraints:
    2 ≤ inputArray.length ≤ 10,
    1 ≤ inputArray[i].length ≤ 10.

  • [input] string result

    A string of the same length as each of the inputArray elements.

    Constraints:
    result.length = inputArray[i].length.

  • [output] integer

Tests:
Solution(C#):

int stringsCrossover(string[] inputArray, string result) {
    int count = 0;
    for (int i = 0;i<inputArray.Length;i++) {
        for (int j = (i + 1);j<inputArray.Length;j++) {
            string chars1 = inputArray[i];
            string chars2 = inputArray[j];
            bool isCross = true;
            for (int k = 0;k<result.Length;k++) {
                if(result[k] != chars1[k] && result[k] != chars2[k]) {
                    isCross = false;
                    break;
                }
            }
            if (isCross) {
                count += 1;
            }
        }
    }
    return count;
}

Pair Of Shoes

Description:

Yesterday you found some shoes in your room. Each shoe is described by two values:

  • type indicates if it’s a left or a right shoe;
  • size is the size of the shoe.

Your task is to check whether it is possible to pair the shoes you found in such a way that each pair consists of a right and a left shoe of an equal size.

Example

  • For
    shoes = [[0, 21], 
             [1, 23], 
             [1, 21], 
             [0, 23]]
    

    the output should be
    pairOfShoes(shoes) = true;

  • For
    shoes = [[0, 21], 
             [1, 23], 
             [1, 21], 
             [1, 23]]
    

    the output should be
    pairOfShoes(shoes) = false.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer shoes

    Array of shoes. Each shoe is given in the format [type, size], where type is either 0 or 1 for left and right respectively, and size is a positive integer.

    Constraints:
    1 ≤ shoes.length ≤ 25,
    1 ≤ shoes[i][1] ≤ 100.

  • [output] boolean

    true if it is possible to pair the shoes, false otherwise.

Tests:
Solution(C#):

bool pairOfShoes(int[][] shoes) {
    List<int> shoes1=new List<int>();
    List<int> shoes2=new List<int>();
    foreach(int[] shoe in shoes) {
        int type = shoe[0], size = shoe[1];
        if(type == 0) {
            shoes1.Add(size);
        } else {
            shoes2.Add(size);
        }
    }
    shoes1.Sort();
    shoes2.Sort();
    if(shoes1.Count != shoes2.Count) {
        return false;
    }
    for(int i=0; i<shoes1.Count;i++) {
        if(shoes1[i] != shoes2[i]) {
            return false;
        }
    }
    return true;
}

Array Previous Less

Description:

Given array of integers, for each position i, search among the previous positions for the last (from the left) position that contains a smaller value. Store this value at position i in the answer. If no such value can be found, store -1 instead.

Example

For items = [3, 5, 2, 4, 5], the output should be
arrayPreviousLess(items) = [-1, 3, -1, 2, 4].

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.integer items

    Non-empty array of positive integers.

    Constraints:
    3 ≤ items.length ≤ 15,
    1 ≤ items[i] ≤ 200.

  • [output] array.integer

    Array containing answer values computed as described above.

Tests:
Solution(C#):

int[] arrayPreviousLess(int[] items) {
    List<int> result = new List<int>();
    for (int i = 0; i < items.Length; i++) {
        int substitute = -1;
        for (int j = 0; j < i; j++) {
            if (items[j] < items[i]) {
                substitute = items[j] ;
            }
        }
        result.Add(substitute);
    }

    return result.ToArray();
}