Forem: SalahElhossiny

Distribute Candies

SalahElhossiny — Sat, 13 May 2023 06:09:45 +0000

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

class Solution(object):
    def distributeCandies(self, ct):
        return min(
            len(set(ct)), 
            len(ct) / 2
        )

Maximum Sum With Exactly K Elements

SalahElhossiny — Thu, 11 May 2023 10:02:37 +0000

You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:

Select an element m from nums.
Remove the selected element m from the array.
Add a new element with a value of m + 1 to the array.
Increase your score by m.
Return the maximum score you can achieve after performing the operation exactly k times.

class Solution(object):
    def maximizeSum(self, nums, k):
        totalSum = maximum = max(nums)
        for i in range(1, k):
            totalSum += (maximum + 1)
            maximum += 1
        return totalSum

Nested Array Generator

SalahElhossiny — Sat, 22 Apr 2023 11:00:54 +0000

Given a multi-dimensional array of integers, return a generator object which yields integers in the same order as inorder traversal.

A multi-dimensional array is a recursive data structure that contains both integers and other multi-dimensional arrays.

inorder traversal iterates over each array from left to right, yielding any integers it encounters or applying inorder traversal to any arrays it encounters.

var inorderTraversal = function*(arr) {
    arr = arr.flat(Infinity) 
    let i = 0, n = arr.length; 
    while(i < n){
        yield arr[i++]
    }
};

AWS App Runner

SalahElhossiny — Sat, 11 Mar 2023 17:03:58 +0000

AWS App Runner is a fully managed service that makes it easier to build, deploy, and run containerized applications. With AWS App Runner, developers can focus on building and improving their applications without worrying about the infrastructure. In this article, we will explore how to use AWS App Runner with Node.js code snippets.

Prerequisites:

Before we start, make sure you have an AWS account, Node.js installed on your machine, and have the AWS CLI configured on your machine.

Creating a Node.js application:

First, let's create a simple Node.js application that we will deploy to AWS App Runner. We will create a simple API that will return a "Hello World" message. Create a new folder for your project and initialize a new Node.js project by running the following command:

npm init -y

Next, install the express module by running the following command:

npm install express

Create a new file called index.js and add the following code to it:

const express = require('express');
const app = express();

app.get('/', (req, res) => {
  res.send('Hello World!');
});

app.listen(3000, () => {
  console.log('App is listening on port 3000!');
});

Deploying the application to AWS App Runner:

Now that we have created our Node.js application, let's deploy it to AWS App Runner. To do this, we will use the AWS CLI. Open a terminal or command prompt and run the following command:

aws apprunner create-service --service-name nodejs-app --source-configuration "ImageRepository={ImageIdentifier=nodejs-app,ImageRepositoryType=ECR},AutoDeploymentsEnabled=true" --region us-west-2

This command will create a new AWS App Runner service called "nodejs-app" and enable automatic deployments. The --source-configuration parameter specifies that the service should use an image stored in an Amazon Elastic Container Registry (ECR) repository with the identifier "nodejs-app".

After the service is created, you can view its status by running the following command:

aws apprunner describe-service --service-arn <SERVICE_ARN> --region us-west-2

Replace with the ARN of the service that was created in the previous step. The command will return information about the service, including its status.

Accessing the deployed application:

Once the service is deployed, you can access the application by running the following command:

aws apprunner list-operations --service-arn <SERVICE_ARN> --region us-west-2

This command will return a list of all the operations that were performed on the service, including the URL of the deployed application. Copy the URL and open it in a web browser. You should see a "Hello World" message.

Conclusion:

AWS App Runner makes it easy to deploy and run containerized applications without worrying about the infrastructure. In this article, we explored how to use AWS App Runner with Node.js code snippets. We created a simple Node.js application, deployed it to AWS App Runner, and accessed the deployed application. With AWS App Runner, developers can focus on building and improving their applications without worrying about the underlying infrastructure.

Count Complete Tree Nodes

SalahElhossiny — Tue, 15 Nov 2022 05:19:04 +0000

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.


class Solution(object):
    def countNodes(self, root):
        if not root: 
            return 0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

Word Ladder

SalahElhossiny — Sat, 12 Nov 2022 18:05:00 +0000

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        s = set(wordList)
        l = list("abcdefghijklmnopqrstuvwxyz")

        queue = deque([])
        queue.append([beginWord,0])

        while queue:
            a, b = queue.popleft()
            if a == endWord:
                return b + 1
            for j in range(len(a)):
                for i in l:
                    if (a[:j] + i + a[j+1:]) in s \
                    and (a[:j] + i +a[j+1:]) != beginWord:
                        s.remove(a[:j]+i+a[j+1:])
                        queue.append([a[:j]+i+a[j+1:],b+1])

        return 0

Find Median from Data Stream

SalahElhossiny — Sat, 12 Nov 2022 04:40:26 +0000

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.


import heapq
class MedianFinder:
    def __init__(self):
        self.big, self.small = [], []

    def addNum(self, x: int) -> None:
        even = len(self.big) == len(self.small)
        heapq.heappush(self.big if even else self.small, -heapq.heappushpop(
                self.small, 
            -heapq.heappushpop(self.big, x)) * (1 if even else -1)
            )      

    def findMedian(self) -> float:
        return self.big[0] if len(self.big) > len(self.small) else (self.big[0] - self.small[0]) / 2

Max Area of Island

SalahElhossiny — Tue, 08 Nov 2022 06:57:46 +0000

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        visit = set()

        def dfs(r, c):
            if (
                r < 0
                or r == ROWS
                or c < 0
                or c == COLS
                or grid[r][c] == 0
                or (r, c) in visit
            ):
                return 0

            visit.add((r, c))
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)


        area = 0

        for r in range(ROWS):
            for c in range(COLS):
                area = max(area, dfs(r, c))

        return area

Reorder Data in Log Files

SalahElhossiny — Sun, 06 Nov 2022 09:09:35 +0000

You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

Letter-logs: All words (except the identifier) consist of lowercase English letters.
Digit-logs: All words (except the identifier) consist of digits.
Reorder these logs so that:

The letter-logs come before all digit-logs.
The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
The digit-logs maintain their relative ordering.
Return the final order of the logs.


class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:

        def get_key(log):
            _id, rest = log.split(" ", maxsplit=1)
            return (0, rest, _id) if rest[0].isalpha() else (1, )

        return sorted(logs, key=get_key)

Most Common Word

SalahElhossiny — Sun, 06 Nov 2022 07:32:13 +0000

Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.

The words in paragraph are case-insensitive and the answer should be returned in lowercase.


import re

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        #List words in paragraph, replacing punctuation with ' ' and all lower case
        paragraph = re.subn("[.,!?;']", ' ', paragraph.lower())[0].split(' ')

        #Remove any '' or words in banned from paragraph list
        paragraph = list(filter(lambda x: x not in banned + [''], paragraph))

        #Return most common word in filtered list
        return Counter(paragraph).most_common(1)[0][0]

Orderly Queue

SalahElhossiny — Sun, 06 Nov 2022 01:45:36 +0000

You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string..

Return the lexicographically smallest string you could have after applying the mentioned step any number of moves.


class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k == 1:
            return min(s[i:] + s[:i] for i in range(len(s)))
        else:
            return ''.join(sorted(s))

Partition Labels

SalahElhossiny — Sat, 05 Nov 2022 06:19:09 +0000

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.


class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        count = {}
        res = []
        i, length = 0, len(S)

        for j in range(length):
            c = S[j]
            count[c] = j

        curLen = 0
        goal = 0

        while i < length:
            c = S[i]
            goal = max(goal, count[c])
            curLen += 1

            if goal == i:
                res.append(curLen)
                curLen = 0
            i += 1

        return res