Forem: Xavier Chretien

Day 5

Xavier Chretien — Tue, 14 Jan 2020 19:11:15 +0000

I hope you had a good weekend (and Monday) I didn't have the time to write the posts of this weekend but I did have the time to code...so there is day 5 !!

Details

Asked by: Dropbox
Difficulty: Hard

Problem

Implement an efficient string matching algorithm.

Given a string of length N and a pattern of length k, write a program that searches for the pattern in the string with less than O(N * k) worst-case time complexity.

If the pattern is found, return the start index of its location. If not, return False.

My solution

Nothing really special about this one. Sadly, because of the ".length" I'm not under O(N*k).

/**
 * Search pattern into searchIn
 *
 * @param searchIn 
 * @param pattern substring to find in searchIn
 * @return start index in string of the pattern, null if not found
 */
fun find(searchIn: String, pattern: String): Int? {
    for (i in 0 until searchIn.length - pattern.length){
        for ((index, c) in pattern.withIndex()){
            if (searchIn[i + index] != c)
                break
            else if(index == pattern.length - 1)
                return i
        }
    }
    return null
}

Now I have a class, so see you tomorrow! 😃

Day 4: Look and say

Xavier Chretien — Thu, 09 Jan 2020 14:37:31 +0000

Let's go for day 4! Finally posting every day is really pleasant! I wanted to thank you who are reading this and a big thank you for your comments on the previous posts 😃

Now let's place the problem of the day!

Details

Difficulty: Medium
Asked by: Epic

Problem

The "look and say" sequence is defined as follows: beginning with the term 1 each subsequent term
visually describes the digits appearing in the previous term. The first few terms are as follows:

As an example, the fourth term is 1211, since the third term consists of one 2 and one 1.

Given an integer N, print the Nth term of this sequence.

My solution

I have to say this one took a moment to understand. After some research, I gave up trying to find a solution to determine the Nth term with some magic mathematics finally, I just determine all the terms until N. Not the best solution I agree.

/**
 * Determine the nth term of the "look and say" sequence
 *
 * @param n, index of the term we want, must be positive
 * @return the nth "look and say" term
 */
fun lookAndSayAt(n: Int): String {
    if(n < 1) return ""
    else if(n == 1) return "1"

    var scanningTerm = "1"

    for (i in 1 until n) {
        var currentTerm = ""

        var currentValue = scanningTerm[0]
        var numberOfCurrentValue = 1
        for (c in scanningTerm.substring(1)) {
            if (c == currentValue)
                numberOfCurrentValue++
            else {
                currentTerm += "$numberOfCurrentValue$currentValue"
                currentValue = c
                numberOfCurrentValue = 1
            }
        }
        currentTerm += "$numberOfCurrentValue$currentValue"
        scanningTerm = currentTerm
    }
    return scanningTerm
}

So do you have another solution? 😃

Day 3: From string to math

Xavier Chretien — Wed, 08 Jan 2020 14:13:30 +0000

Details

Difficulty: Hard
Programming language: Kotlin

Problem

Giving a string consisting of parentheses, single digits, positive and negative signs,
convert the string into a mathematical expression to obtain the answer.

Don't use eval or a similar built-in parser.

For example:

Given -1+(2+3), you should return 4

Solution

Before looking at my solution, which is probably not the best, why don't you give it a try? 😁

I decide to simply use a simple switch case (when in Kotlin)

/**
 * Parse and calculate the string passed in param
 *
 * @param calculation
 * @return result of the calculation
 */
fun parseAndCalculation(calculation: String): Int {
    var result = 0

    var multiplier = 1
    var subProblem = -1

    for ((index, c) in calculation.withIndex()) {
        if(subProblem == -1 || c != ')')
            when(c) {
                '+' -> multiplier = 1
                '-' -> multiplier = -1
                '(' -> subProblem = index
                ')' -> {
                    result += multiplier * parseAndCalcul(calculation.substring(subProblem + 1, index))
                    subProblem = -1
                }
                else -> result += multiplier * c.toString().toInt()
            }
    }

    return result
}

Day 2: Fixed point

Xavier Chretien — Tue, 07 Jan 2020 12:48:29 +0000

Difficulty: Easy
Programming language: Kotlin

Problem

A fixed point in an array is an element whose value is equal to its index.
Given a sorted array of distinct elements, return a fixed point, if one exists. Otherwise, return false.

For example:

Given [-6, 0, 2, 40], you should return 2
Given [1, 5, 7, 8], you should return false

My solution

This is an easy one and I don't want to go to a very complex solution. Let's just iterate the array and find the fixed point 😄

/**
 * Find each fixed point in a sorted array.
 *
 * @param array, sorted array
 * @return an list with each fixed points, the list is empty if there is no fixed points.
 */
fun findFixedPoint(array: IntArray): List<Int>{
    if(array[1] < array[0]) throw IllegalArgumentException("Array not sorted")

    val pointFixedFound = mutableListOf<Int>()
    for ((index, value) in array.withIndex()) {
        if(index == value){
            pointFixedFound.add(index)
        }
    }

    return pointFixedFound.toList()
}

UPDATED VERSION

.ltag__user__id__287760 .follow-action-button { background-color: #093656 !important; color: #ffffff !important; border-color: #093656 !important; }

Nick Holmes

Time flies while you're having fun, but then one day your bio says something about being a 30+ year veteran in software engineering. Still, I've not seen it all, let alone done it all (yet).

suggests in the comments, I didn't really follow the question asked. The question is to return A fixed point not all fixed points, so there is the updated version (thanks again to Nick Holmes).

fun findFixedPoint(array: IntArray): Int? {
    val pointFixedFound = mutableListOf<Int>()

    for ((index, value) in array.withIndex()) {
        if(index == value){
            return index
        } else if (value > index) {
            break
        }
    }
    return null
}

The function returns null if there is no fixed point because I didn't find if this is possible to return an int or false in Kotlin, so I return null instead.

31 days of problems

Xavier Chretien — Mon, 06 Jan 2020 23:22:09 +0000

Why?

This is the beginning of a new year (and decade) 🎉 so it's time for a new commitment, last year I challenged myself on 365 days of coding problems with DailyCodingProblems and...I gave up after only 2 or 3 weeks...
This year I will try again! For 31 days and why not more, but let's do 31 days for now.

Why try again?

To motivate myself I choose to publish my solution of the daily problem here because you will probably have other solutions and that would be great to discuss algorithmic here.

Why do that?

Because it's fun! It's a good technique to improve your logic and secondly next year I will have to pass a technical interview for the last internship of my studies and I want to be prepared!

How this series will work

First of all, this is my first series of articles and my first real article so don't hesitate to comments, I want to improve my writing skills (and my English also).
Every two days (or one time a week) I will post a problem I received and my solution, you can find here the repo don't hesitate to check the repo 😃.

Day 1

Difficulty: Medium
Programming language used: Kotlin

Problem

Write a function, throw_dice(N, faces, total) that determines how many ways it is possible to
throw N dices with some number of faces each to get a specific total.

For example:
throw_dice(3, 6, 7) should return 15.

My solution

I used a concept called dynamic programming (DP) to solve this one.
Finding how many ways it is possible to throw N dices to get a specific amount (X) is equivalent to find (and sum) how many ways it is possible to throw N-1 dices to get an X-1 amount, N-1 to get X-2, N-1 to get X-3, etc..until X and N equals 1.

/**
 * Determine how many ways it is possible to throw N dices with the number of faces each to get the total
 *
 * @param N, number of dices
 * @param faces, number of faces of each dice
 * @param total, the sum of the dices we would like to get
 * @return Int, number of ways
 */
fun throw_dice(N: Int, faces: Int, total: Int): Int {
    val subProblems = Array(N+1) { IntArray(total+1) { 0 } }

    var i = 1
    while (i < total && i < faces) {
        subProblems[1][i] = 1
        i++
    }

    for (w in 2..N) {
        for (j in 1..total) {
            for (k in 1..faces) {
                if(k >= j)
                    break
                subProblems[w][j] += subProblems[w - 1][j - k]
            }
        }
    }

    return subProblems[N][total]
}

Fuchsia.dev

Xavier Chretien — Fri, 28 Jun 2019 20:19:19 +0000

The documentation for the ~~new~~ ~~future~~ ~~I don't know how to call it~~ OS of Google is now available on fuchsia.dev, so during the time the project compile on my laptop I was wondering what do you think about it and what do you expect also ? 🤔