DEV Community: michael-2509

Valid Number

michael-2509 — Fri, 30 Sep 2022 18:27:40 +0000

Challenge
A valid number can be split up into these components (in order):

A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.

A decimal number can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One of the following formats:
One or more digits, followed by a dot '.'.
One or more digits, followed by a dot '.', followed by one or more digits.
A dot '.', followed by one or more digits.

An integer can be split up into these components (in order):

(Optional) A sign character (either '+' or '-').
One or more digit

Check leetcode for full code challenge

Approach
The challenge looked so simple until I started solving it. My initial approach was to check the data type and return the appropriate result whether the conditions were true or false. However, this approach won't work for all type cases, so I had to use another approach which lead to using the regex or regular expression in python which helps to check a specified text pattern.

With this approach, I was able to check the validity of the input based on the expressions I specified.

Merge k sorted list

michael-2509 — Thu, 29 Sep 2022 16:51:24 +0000

Challenge

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

APPROACH

This would be the first time I would be learning linked list so this took quite some time to figure out. However, let's jump right in.

I love this definition of linked list from freecodecamp: Linked Lists are a data structure that store data in the form of a chain. The structure of a linked list is such that each piece of data has a connection to the next one (and sometimes the previous data as well). Each element in a linked list is called a node

You can learn more about Linked lists here

Aproach
Having understood links, I rewrote my algorithm to solve the challenge this way:

Loop through the k linked-lists list.
Append the node element of the linked list to a new array.
If there are no empty list and list length equals one, sort new array.
Create a head node from the sorted array:
this is the first element of the linked list of the next elements of the list would be linked to
Loop through rest of the sorted array to link the current element to the previous nodes.

COMBINE TWO TABLES

michael-2509 — Wed, 28 Sep 2022 12:48:33 +0000

Chalenge
Write an SQL query to report the first name, last name, city, and state of each person in the Person table. If the address of a personId is not present in the Address table, report null instead.

Return the result table in any order.

Check leetcode for more info.

Approach
In this challenge we are to write a SQL code to read data from two separate tables. let's review some basis of SQL and the SQL statements I would use.

SQL is a language used to interact with the database. SQL stands for Structured Query Language.

select clause tells the query what column to read from the data.

from clause tells the query what data to use

joinclause tells query on additional table from which you would love to pull data

on clause specifies a logical statement to combine the table in from and join statement.

Now that we understand this basis, to solve this challenge, I wrote my query using select clause to the pull the firstname, lastname, city and state column. I used the from clause to specify the table I want to pull data, then used the joinclause to specify the other table I needed to pull data from and finally, on clause which I used to combine both tables in join.

UTF-8 Validation

michael-2509 — Tue, 27 Sep 2022 22:21:00 +0000

Another leetCode challenge on UTF-8 Validation.

PROBLEM
Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters). - You can use the link above to see more details.

SOLUTION
This was quite a challenge! let's look at the step to solve it.

Loop through the array.
Find the binary representation for each integer using the format method that takes in two arguments
Loop through the first octet sequence to determine if it is a valid UTF-8 encoding, by checking if the character is 1 - 4 bytes Long.
Check the next two bit of the sequence if they follow the rules, to check for validity

Rules
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

For a 1-byte character, the first bit is a 0, followed by its Unicode code.
For an n-bytes character, the first n bits are all one's, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

Number of Bytes   |        UTF-8 Octet Sequence
                       |              (binary)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x denotes a bit in the binary form of a byte that may be either 0 or 1.

Multi-Threaded FizzBuzz

michael-2509 — Mon, 26 Sep 2022 13:10:40 +0000

You have the four functions:

printFizz that prints the word "fizz" to the console,
printBuzz that prints the word "buzz" to the console,
printFizzBuzz that prints the word "fizzbuzz" to the console, and
printNumber that prints a given integer to the console.

You are given an instance of the class FizzBuzz that has four functions: fizz, buzz, fizzbuzz and number. The same instance of FizzBuzz will be passed to four different threads:

Thread A: calls fizz() that should output the word "fizz".
Thread B: calls buzz() that should output the word "buzz".
Thread C: calls fizzbuzz() that should output the word "fizzbuzz".
Thread D: calls number() that should only output the integers.

Modify the given class to output the series [1, 2, "fizz", 4, "buzz", ...] where the ith token (1-indexed) of the series is:

"fizzbuzz" if i is divisible by 3 and 5,
"fizz" if i is divisible by 3 and not 5,
"buzz" if i is divisible by 5 and not 3, or
i if i is not divisible by 3 or 5.

Implement the FizzBuzz class:

FizzBuzz(int n) Initializes the object with the number n that represents the length of the sequence that should be printed.
void fizz(printFizz) Calls printFizz to output "fizz".
void buzz(printBuzz) Calls printBuzz to output "buzz".
void fizzbuzz(printFizzBuzz) Calls printFizzBuzz to output "fizzbuzz".
void number(printNumber) Calls printnumber to output the numbers.

Example 1:

Input: n = 15
Output: [1,2,"fizz",4,"buzz","fizz",7,8,"fizz","buzz",11,"fizz",13,14,"fizzbuzz"]

Example 2:

Input: n = 5
Output: [1,2,"fizz",4,"buzz"]

Logic

loop through n , n times.
check for every value of n ranging from 1 to n, if it mets the condition
Print out the right word.

Code Logic

for i in range(1,self.n+1):
            if "condition is true":
                "printWord()"

Let's understand this First!
Let's assume the order of thread execution is as follows Thread A, Thread B, Thread C and Thread D. The first step would be to write the logic of the code in the each of methods that run our functions to suit what each method is suppose to print out.

We loop through n and check if each value of n ranging from 1 to n mets the condition in the method. Unfortunately, Knowing the order of the thread and that Thread A runs first which automatically calls buzz method.

This would leave us in a complex situtation because Thread A would have to run n number of times before Thread B picks up. Sadly this is not we want to achieve. We want a situation where Thread A pauses after the first iteration permitting Thread B to run and then, Thread C picks up after Thread B's first iteration and same for Thread D. In other words, I want to keep all threads in sync.

To achieve this, we can use a threading object called barrier
Think of barrier as a delay that interupts a thread from continuing it's operation giving room to the next thread to carry out it's function and any other threads before the initial thread picks up from where it's last stop.

Code

from threading import Barrier

class FizzBuzz:
    def __init__(self, n: int):
        self.n = n
        self.block = Barrier(4)

    # printFizz() outputs "fizz"
    def fizz(self, printFizz: 'Callable[[], None]') -> None:

        for i in range(1,self.n+1):
            if i%5!=0 and i%3==0:
                printFizz()
            self.block.wait()

    # printBuzz() outputs "buzz"
    def buzz(self, printBuzz: 'Callable[[], None]') -> None:

        for i in range(1,self.n+1):
            if i%3!=0 and i %5 ==0:
                printBuzz()
            self.block.wait()


    # printFizzBuzz() outputs "fizzbuzz"
    def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:

        for i in range(1,self.n+1):
            if i%5==0 and i%3==0:
                printFizzBuzz()
            self.block.wait()

    # printNumber(x) outputs "x", where x is an integer.
    def number(self, printNumber: 'Callable[[int], None]') -> None:

        for i in range(1,self.n+1):

            if (i % 3) !=0 and (i%5) !=0:
                printNumber(i)
            self.block.wait()

Understanding the Code

Initialize barrier to 4, making it understand that 4 threads would be in sync. This would mean all 4 thread must hit the wait

self.block = Barrier(4)

Starting our Program, Thread A calls Buzz method, The loop begins from 1 then our if statement is skipped because the condition is false which leads to the next line of code self.bar.wait(). This prevents buzz method from running next iteration and giving control to next thread which is Thread B.

# printBuzz() outputs "buzz"
    def buzz(self, printBuzz: 'Callable[[], None]') -> None:

        for i in range(1,self.n+1):
            if i%3!=0 and i %5 ==0:
                printBuzz()
            self.block.wait()

The advantage of this approach is that all threads would remain blocked when they call wait()until the barrier reaches the specified number of threads waiting to be blocked before they get unblocked.

Sort Character by frequency

michael-2509 — Sun, 25 Sep 2022 22:14:48 +0000

Challenge
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example 1:

Input: s = "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa" Output: "aaaccc" Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers. Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.

Algorithm

Find the frequencyof each character string.

To achieve this, the counter function, item method and bucket in python is used.

The Counter.items() method helps to see the elements of the list along with their respective frequencies in a tuple.

Bucket Sort is a comparison-type algorithm which assigns elements of a list we want to sort in Buckets, or Bins. The contents of these buckets are then sorted, typically with another algorithm. After sorting, the contents of the buckets are appended, forming a sorted collection
Bucket Sort can be thought of as a scatter-order-gather approach towards sorting a list, due to the fact that the elements are first scattered in buckets, ordered within them, and finally gathered into a new, sorted list.

sort in decreasing order

The string is now sorted in reverse order based on the frequency using the reverse function in python.

Print in Order

michael-2509 — Sat, 24 Sep 2022 22:46:26 +0000

Challenge
Suppose we have a class:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

Note:

We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seem to imply the ordering. The input format you see is mainly to ensure our tests' comprehensiveness.

Let's Understand the challenge

What an Instance and a Thread?
An object is an instance of a class. In the example below, phone is a class while instance of phone is phone_one. Therefore to create an instance of foo would be to create an object.

class Phone:
    def __init__(self):
        self.brand = "samsung"
        self.model = "A50 
        self.color = "blue"

#object 
phone_one = Phone()

A thread is a set of operations that would be operated at different time sequence. It allow's one perform different actions at different time sequence instead of the order of execution.
let's say you have to wait for an input to complete action one, you can move to the next available action, action two while you await action one.

import threading
import time

def eat(food):
    print("preparing to eat",food)
    time.sleep(1)
    print("back to eating ",food)

def movie(movie):
    print("watching", movie)
    print("Done watching")


x = threading.Thread(target=eat, args=("rice",))
x.start()

y = threading.Thread(target=movie, args=("spiderman",))
y.start()

what you expected as output

preparing to eat rice
back to eating  rice
watching spiderman
Done watching

Actual output

preparing to eat rice
watching spiderman
Done watching
back to eating  rice

If you observe the flow while running eat function, we out of the eat function to the movie function before the final execution of eat and this is because we encoutered a delay in eat function

So to solve this challenge i used a lock object that thread provides. when we have two or more threads access a shared piece of data is called race condition. which is the case in this challenge. Having the same instance of foo pass to the three different threads.

To solve a race condition, a common method is to used the Lock object that thread provides. Lock allows one thread to run at a time until the lock is released before next thread runs

import threading
from threading import Lock

class Number:
    def __init__(self):
        self.lock_one = threading.Lock()
        self.lock_two = threading.Lock()
        self.lock_one.acquire()
        self.lock_two.acquire()

    def first(self, num) -> None:
        print("one", num)
        self.lock_one.release()


    def second(self, num) -> None:
        self.lock_one.acquire()
        print("two", num)
        self.lock_two.release()


    def third(self,num) -> None:
        self.lock_two.acquire()
        print("three", num)

  #object      
num_instance = Number()

thread_a = threading.Thread(target=num_instance.third, args=(1,))
thread_a.start()

thread_b = threading.Thread(target=num_instance.second, args=(2,))
thread_b.start()

thread_c = threading.Thread(target=num_instance.first, args=(3,))
thread_c.start()

OUTPUT

one 3
two 2
three 1

BONUS

Palindrome

michael-2509 — Fri, 23 Sep 2022 19:10:04 +0000

QUESTION
Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

STEP

Reverse Integer
Compare integer and reversed integer

CODE

Reverse Integer

The integer x is converted to a string using toString() method and a for loop is applied to convert the string to it's reverse state using the decrementing for loop

//convert interger to string
  var str = x.toString()

//reverse string
 let reverseStr = ""
    for(condition){
       //logic to reverse string
    }

Compare integer and reversed integer string

The condition statement if else was used to compare interger x and the reversed string str using type coercion, otherwise the condition would return false even if it's a palindrome number.

Type coercion helps convert one value type to another which make is it easy to compare values of difference types. Since I'm comparing a string and an interger, I used loose equality == which makes use of type coercion. In this case, string is coerced to an integer before comparism

//loose equality(using type coercion)
123 == "123" -> true
// strict comparis
123 === "123" -> false`

if(condition) {
        return true 
    } else{
        return false
    }

Final Run

var isPalindrome = function(x) {
    //convert interger to string
    var str = x.toString()

    //reverse string
    //var reverseStr = str.split("").reverse().join("")
    let reverseStr = ""
    for(condition){
       //logic to reverse string
    }

    //check for palindrome
  if(condition) {
        return true 
    } else{
        return false
    }
};

How to remove specific element occurrence from an Array.

michael-2509 — Thu, 22 Sep 2022 18:09:54 +0000

QUESTION
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

STEP
Since we want to remove all occurrences of a particular value from the array, we can use this approach

Loop through the array

while(condition){}

The while method reiterates sets of action within the curly braces until conditions are met or becomes false.

For the condition to remain true, the while loop checks if the integer value can be found in the array, otherwise the condition becomes false and the loop is exited. So I used the includes method on the array to achieve this.

Remove the specific integer val that occurs in array

array.splice("start", "deleteCount")

To remove ocurrences of the specific value, i used the splice array method and indexOf method to create the logic to remove the values.

The splice takes in a first argument(start) which in this case would be the index of the integer value I want to remove and a second value(deleteCount) which I specified to be "1" so just a single element is remove from the array begining from (start)

To determine the (start) value, I used the indexOf method. indexOf returns the index of the first occurrence of a specific value within the array.

How the Code Runs
The while loop checks if the integer value can be found in the array nums. If true, it go ahead to remove the first occurrence of the integer value from the array using splice and indexOf logic, this process repeats itself until the while condition is false.

Final code.

var removeElement = function(nums,
val){ 
    //loop through array 
   while (condition){ 
   //remove element from the array using splice method.
  nums.splice("start",1); } 
    return nums.length; 
};

BONUS
If you ever wonder how this can be applied to a real project.

You can use this approach to filter out specific genre from a list of movie genre on a movie website. Allowing user to remove specific genre they no longer want to see on movies page.

Removing duplicates

michael-2509 — Wed, 21 Sep 2022 22:52:15 +0000

Challenge
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Solution
The initial approach I took was the filter and indexOf method on the array to sort the unique elements

However this approach gave me slight challenge so I had to think a little hard to create a new algorithm to solve it.

Algorithm

Check the first two arrays for duplication
if they are duplicates, replace the second array index with the next array index
if they are not duplicates, leave arrays the same