CodeFights Problems

Stay tuned for more solution/explanations.

If you have a question you want to see the solution of, comment below so that I can help you!

Also, I figured out how to put actual code snippets with indentation and all, so, the newer ones will have the code as a text instead of an image.

How to Solve ‘treeLevelSum’ in CodeFights

The Problem

Given a binary tree and a number k, your task is to find the sum of tree nodes at level k. The binary tree is represented by a string tree with the format: (<node-value>(<left subtree>)(<right subtree>)).

Example

For tree = "(0(5(6()())(14()(9()())))(7(1()())(23()())))" and k = 2, the output should be

treeLevelSum(tree, k) = 44.

Explanation: The nodes at level 2 are 6, 14, 1, and 23, so the answer is 6 + 14 + 1 + 23 = 44.

Input/Output

  • [time limit] 4000ms (py)
  • [input] string tree

    A valid string representing a tree.

    Constraints:

    2 ≤ tree.length ≤ 105.

    All the values in a given tree are guaranteed to be integers.

  • [input] integer k

    Constraints:

    0 ≤ k ≤ 105.

  • [output] integer

    The total sum of all the values at level k in a tree.

The Solution

Capture.PNG

Continue reading “How to Solve ‘treeLevelSum’ in CodeFights”

How to Solve ‘numberof1Bits’ in CodeFights

The Problem

Note: Avoid using built-in functions that convert integers to their binary representations. Write the solution that uses O(k)operations per test, where k is the number of bits set to 1.

Write a function that takes an unsigned (positive) integer and returns the number of 1 bits its binary representation contains. This value is also known as the integer’s Hamming weight.

Example

For n = 13, the output should be
numberOf1Bits(n) = 3.

13 is represented in binary as 1101, so the function should return 3.

Input/Output

  • [time limit] 4000ms (py)
  • [input] integer n

    Constraints:
    0 ≤ n ≤ 231 - 1.

  • [output] integer

The Solution

Capture.PNG Continue reading “How to Solve ‘numberof1Bits’ in CodeFights”

The Problem

Sort the letters in the string s by the order they occur in the string t.

Example

  • For s = "weather" and t = "therapyw", the output should be
    sortByString(s, t) = "theeraw";
  • For s = "good" and t = "odg", the output should be
    sortByString(s, t) = "oodg".

Input/Output

  • [time limit] 4000ms (py)
  • [input] string s

    A string consisting only of lowercase English letters.

    Constraints:
    0 ≤ s.length ≤ 104.

  • [input] string t

    A string consisting only of unique lowercase English letters. It is guaranteed that t contains all of the letters that occur in s.

    Constraints:
    0 ≤ t.length ≤ 26.

  • [output] string

The Solution

Capture.PNG

Continue reading

How to solve ‘sortedSquaredArray’ in CodeFights

The Problem

Note: Come up with a linear solution, since that is what you would be asked to do in an interview.

You have a sorted array of integers. Write a function that returns a sorted array containing the squares of those integers.

Example

For array = [-6, -4, 1, 2, 3, 5], the output should be
sortedSquaredArray(array) = [1, 4, 9, 16, 25, 36].

The array of squared integers from array is: [36, 16, 1, 4, 9, 25]. When sorted, it becomes: [1, 4, 9, 16, 25, 36].

Input/Output

  • [time limit] 4000ms (py)
  • [input] array.integer array

    A sorted array of integers.

    Constraints:
    1 ≤ array.length ≤ 104,
    -104 ≤ array[i] ≤ 104.

  • [output] array.integer

    A sorted array of integers composed of the squared integers from the input array.

The Solution

upup.png

Continue reading “How to solve ‘sortedSquaredArray’ in CodeFights”

How to solve ‘reverseVowelsOfString’ in CodeFights

The question

Write a function that takes a string as input and returns the string with only the vowels reversed.
Note: The letters “a”, “e”, “i”, “o”, and “u” are vowels. The letter “y” is not a vowel.

Example

  • For s = "hello, world", the output should be
    reverseVowelsOfString(s) = "hollo, werld";
  • For s = "codefights", the output should be
    reverseVowelsOfString(s) = "cidefoghts";
  • For s = "eIaOyU", the output should be
    reverseVowelsOfString(s) = "UOaIye".

Input/Output

  • [time limit] 4000ms (py)
  • [input] string s

    Constraints:
    0 ≤ s.length ≤ 50.

  • [output] string

The Solution:

upup

 

Continue reading “How to solve ‘reverseVowelsOfString’ in CodeFights”

How to solve “sumOfTwo” in CodeFights

The Problem:

You have two integer arrays, a and b, and an integer target value v. Determine whether there is a pair of numbers, where one number is taken from a and the other from b, that can be added together to get a sum of v. Return true if such a pair exists, otherwise return false.

Example

For a = [1, 2, 3], b = [10, 20, 30, 40], and v = 42, the output should be
sumOfTwo(a, b, v) = true.

Continue reading “How to solve “sumOfTwo” in CodeFights”

How to Solve “efficientRoadNetwork” in CodeFights

The Problem:

Once upon a time, in a kingdom far, far away, there lived a king Byteasar III. As a smart and educated ruler, he did everything in his (unlimited) power to make every single system of his kingdom efficient. The king went down in history as a great road builder: during his reign a great number of roads were built, and the road system he created was the most efficient for those dark times.

When you started to learn about Byteasar’s III deeds in your history classes, the creeping doubt crawled into the back of your mind: what if the famous king wasn’t so great after all? According to the most recent studies, there were n cities in the Byteasar’s kingdom, which were connected by the two-ways roads. You managed to get information about this roads from the university library, so now you can write a function that will determine whether the road system in Byteasar’s kingdom was efficient or not.

A road system is considered efficient if it is possible to travel from any city to any other city by traversing at most 2 roads.

Example

  • For n = 6 and
    roads = [[3, 0], [0, 4], [5, 0], [2, 1],
              [1, 4], [2, 3], [5, 2]]
    

    the output should be

    efficientRoadNetwork(n, roads) = true.

    Here’s how the road system can be represented:

  • For n = 6 and
    roads = [[0, 4], [5, 0], [2, 1],
              [1, 4], [2, 3], [5, 2]]
    

    the output should be

    efficientRoadNetwork(n, roads) = false.

    Here’s how the road system can be represented:

    As you can see, it’s only possible to travel from city 3 to city 4 by traversing at least 3 roads.

Input/Output

  • [time limit] 7000ms (py)
  • [input] integer nThe number of cities in the kingdom.

    Constraints:

    1 ≤ n ≤ 250.

  • [input] array.array.integer roadsArray of roads in the kingdom. Each road is given as a pair [cityi, cityj], where 0 ≤ cityi, cityj < n and cityicityj. It is guaranteed that no road is given twice.

    Constraints:

    0 ≤ roads.length ≤ 35000,

    roads[i].length = 2,

    0 ≤ roads[i][j] < n.

  • [output] booleantrue if the road system is efficient, false otherwise.

The Solution:

up.PNG

The Explanation:

Basic graph knowledge. (Adjacency Matrix)

The rows are the sources of the edges. Columns are the targets.

If we have a road from x to y; we have a road from y to x. (Since roads are to both directions.)

If there is no road between two cities, the adj cell for those two will be zero infinity, but since we will check if it is shorter than 2 or not, we can just put any number bigger than 2. I put 4.

update the roads as we iterate over the roads array.

update path from each node to itself. We can say the length from each node to itself is zero.

I used floyd-warshall all-pairs-shortest-path algorithm since the limits on number of nodes is small and it’s easy to implement. (Complexity of this algorithm is high, so, with higher number of nodes, we would have to use a more efficient algorithm.)

Check if all the roads are shorter than 3, if not return False.

else, return True.

How to Solve “roadsBuilding” in CodeFights

The Problem:

Once upon a time, in a kingdom far, far away, there lived a king Byteasar II. There was nothing special neither about him, nor about his kingdom. As a mediocre ruler, he did nothing about his kingdom and preferred hunting and feasting over doing anything about his kingdom prosperity.

Luckily, his adviser, wise magician Bitlin, was working for the kingdom welfare daily and nightly. However, since there was no one to advise him, he completely forgot about one important thing: the roads. Over the years most of the two-way roads built by Byteasar II predecessors were forgotten and no longer traversable. Only a few roads can still be used.

Bitlin wanted each pair of cities to be connected, but couldn’t find a way to figure out which roads are missing. Desperate, he turned to his magic crystal, seeking help. The crystal showed him a programmer from the distant future: you! Now you’re the only one who can save the kingdom. Given the existing roads and the number of cities in the kingdom, you should use the most modern technologies and find out what roads should be built again to make each pair of cities connected. Since the magic crystal is quite old and meticulous, it will only transfer the information that is sorted properly.

The roads to be built should be returned in an array sorted lexicographically, with each road stored as [cityi, cityj], where cityi < cityj.

Continue reading “How to Solve “roadsBuilding” in CodeFights”