حل مسئله و الگوریتم

قراره هر شب حدود ساعت ده یک مسئله رو توی کانال قرار بدم تا با هم حلش کنیم.

اول از همه مسئله های وب سایت leetcode رو قرار میدم تا با هم حلش کنیم.

از مسائل مبتدی شروع میکنیم تا برسیم به سخت ترین ها.
هدفمون اینه تا آخر سال 1402 حدود 90 تا مسئله رو با هم بررسی کنیم و کلی حل مسئلمون رو تقویت کنیم 🔥

بهترین جواب هر مسئله فرداش توی کانال قرار میگیره.

پس اگه دوست دارید حتما هشتگ problems رو از این به بعد دنبال کنید

(جواب مسئله با زبان پایتون و یا گو قرار میگیره)

#problems

@Syntax_fa

1. Two Sum
مسئله ی اول:

یک آرایه داریم و یک target
کاری که باید بکنید این است درون آرایه، اندیس دو عدد را پیدا کنید که جمع(داده) آنها مساوی با target شود و این جفت عدد(اندیس) را در output نشان دهید.
اگر جفت عدد پیدا نشد در خروجی [0, 0] را نمایش می‌دهیم.

یعنی داده‌ی اندیس x به علاوه داده‌ی اندیس y برابر شد با target، خروجی: [x, y]

ورودی: nums = [2,7,11,15], target = 9

خروجی: [0,1]

توضیحات: زیرا nums[0] + nums[1] == 9، و ما [0, 1] نمایش می‌دهیم.

(آرایه را در پایتون همان لیست در نظر بگیرید.)
(متغیر target یک عدد است که از ورودی دریافت می شود.)

بهینه ترین کد فردا قرار میگیره(همراه با توضیح جواب رو توی کامنت ارسال کنید تا بهترین جواب با اسم خودتون قرار بگیره)


#Problems

@Syntax_fa

یکی از روش های خوب و پر سرعت:

میایم یک مپ(دیکشنری) تعریف میکنیم.
درون آرایه پیمایش میکنیم.
اولین قدم چک میکنیم عددمون فاصلش با تارگت چقدره‌ (یکی از اشتباهاتی که بعضی از دوستان کردن این بود که چک کردن اگه عدد از target بزرگ تر بود کلا بیخیالش شه بره بعدی اما ممکنه عدد منفیم تو لیست باشه. پس هر کی اینکارو کرده تست رو رد نمیکنه)

بعد از اینکه بدست آوردیم که عددمون چقدر با target فاصله داره. توی دیکشنری دنبال اون عددی میگردیم که عنصر ما با اون جمع بشه مساوی با تارگت میشه.
توی دیکشنری اعداد رو به این صورت ذخیره میکنیم
{value: index}
سرچ درون لیست با o(1) انجام میشه.
اگه توی دیکشنری نبود عنصر رو با ایندکسش توی دیکشنری اضافه میکنیم و به پیمایش ادامه میدیم

تو بهترین حالت کمتر از o(n) هستش و تو بدترین حالت o(n) میشه.

مثال توی پایتون:

class Solution(object):
    def twoSum(self, nums, target):
        checked = {}
        for index, num in enumerate(nums, start=0):
            index2 = checked.get(target - num)
            if index2 is not None:
                return [index2, index]
            checked[num] = index
        return [0, 0]

مثال توی گو:

 Go
func twoSumWithMakeMapAndExtraAssign(nums []int, target int) []int {
  checked := make(map[int]int)
  for index, num := range nums {
    complete := target - num
    if _, ok := checked[complete]; ok {
      return []int{checked[complete], index}
    }
    checked[num] = index
  }
  return []int{}
}

نکته:
از نظر مصرف memory بهینه نیست. روش بهینه تر رو توی کامنت ها بگید.

#Problems

@Syntax_fa

2. Longest Substring Without Repeating Characters

مسئله دوم
سطح: متوسط

توضیح:
رشته s را دریافت کنید و تعداد کاراکتر های بدون تکرارش را در خروجی برگردانید.
 
مثال:
Example 1:

Input: s = "abcabcbb" 
Output: 3 

Explanation: The answer is "abc", with the length of 3

Example 2:

Input: s = "bbbbb"
Output: 1 

Explanation: The answer is "b", with the length of 1. 

Example 3:

Input: s = "pwwkew"
Output: 4

نکته:
رشته s می تواند شامل حروف انگلیسی، اعداد، سمبل ها و فاصله(space) باشد.

ورودی اعداد سمبل ها و حروف انگلیسی هستش.
ولی خروجی تعداد حروف بی تکرار انگلیسی

برای اینکه تست کنید جوابتون درسته حتما به این وب سایت سر بزنید و کدتون‌ رو تست کنید:
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

جایزه:
به بهترین جواب کانفیگ ده گیگابایت شخصی داده میشود.

#Problems

@Syntax_fa

نکاتی در خصوص حل مسئله:

در مصاحبه‌ها برای شغل‌های مرتبط با برنامه‌نویسی عموماً توصیه می‌شود در حل مسائل و الگوریتم‌ها از ویژگی‌های خاص زبان استفاده نشود و مسائل به طور عام بدون اتکا به یک زبان ویژه حل شوند. دلایل این توصیه عبارتند از:

- در مصاحبه بررسی می‌شود که شخص چگونه می‌تواند مسئله را به طور عام حل کند، نه آنکه از یک زبان مشخص استفاده کند.

- در شرکت‌های مختلف زبان‌های برنامه‌نویسی متفاوتی مورد استفاده قرار می‌گیرند. پس مهم است که کاربردی بودن الگوریتم‌ها نشان داده شود.

- بدون اتکا به زبان، باید از مفاهیم پایه‌ای مانند ریاضیات، منطق و طراحی الگوریتم استفاده شود.

بنابراین در مصاحبه‌ها توصیه می‌شود که بدون استفاده از ویژگی‌های خاص زبان، مسائل را حل کرد تا قدرت تحلیل و حل مسئله فرد بهتر به نمایش گذاشته شود.

#Problems

@Syntax_fa

3. Integer to English Words

مسئله سوم
سطح:‌ سخت

توضیح:
یک عدد بزرگ تر مساوی با صفر (عدد حسابی) را با اسم متغیر num از ورودی دریافت میکنید و در خروجی بصورت حروف انگلیسی نمایشش می دهید.

مثال:

 LeetCode
Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"


Example 2:

Input: num = 12345
Output: "Twelve Thousand Three Hundred Forty Five"


Example 3:

Input: num = 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

نکته:
برای اینکه بتونیم خروجی رو به راحتی تست کنیم. هممون با یه ساختار کد بزنیم
توی پایتون به این شکل جواب رو بفرستید:

def numberToWords(num: int) -> str:
    """
    :type num: int
    :rtype: str
    """

توی گو:

func numberToWords(num int) string {
    
}

جایزه 💥:
به بهترین جواب کانفیگ ده گیگابایت شخصی داده میشود.

#Problems

@Syntax_fa

بهترین پاسخ برای امیرحسین عزیز هستش.

پاسخ:

def numberToWords(num):
    d_one = {0: "", 1: "One ", 2: "Two ", 3: "Three ", 4: "Four ", 5: "Five ", 6: "Six ", 7: "Seven ", 8: "Eight ",
             9: "Nine ", 10: "Ten ", 11: 'Eleven ', 12: "Twelve ",
             13: "Thirteen ", 14: "Fourteen ", 15: "Fifteen ", 16: "Sixteen ", 17: "Seventeen ", 18: "Eighteen ",
             19: "Nineteen "}
    d_villagers = {2: "Twenty ", 3: "Thirty ", 4: "Forty ", 5: "Fifty ", 6: "Sixty ", 7: "Seventy ", 8: "Eighty ",
                   9: "Ninety "}

    def score(num):
        if num // 1_000_000_000 > 0:
            return score(num // 1_000_000_000) + "Billion " + score(num % 1_000_000_000)
        if num // 1_000_000 > 0:
            return score(num // 1_000_000) + "Million " + score(num % 1_000_000)
        elif num // 1_000 > 0:
            return score(num // 1_000) + "Thousand " + score(num % 1_000)
        elif num // 100:
            return d_one[num // 100] + "Hundred " + score(num % 100)
        elif num > 19:
            return d_villagers[num // 10] + d_one[num % 10]
        elif num <= 19:
            return d_one[num]

    return score(num).strip() if num != 0 else "Zero"

همچنین یه اشاره ای به جواب یکی از دوستان کنم. خیلی خوب کلک زدن😂

from num2words import num2words

def number_to_words(number):
    return num2words(number)


input_number = 1234567
output_words = number_to_words(input_number)
print(output_words)

#Problems

@Syntax_fa

مسئله چهارم
سطح:‌ ساده

توضیح:
برنامه ای بنویسید که خروجی زیر را داشته باشد

 Python
1
22
333
55555
88888888
13131313131313131313131313
212121212121212121212121212121212121212121

#Problems

@Syntax_fa

چند تا از جواب ها:

s= 1
i = 0
for h in range(7):
    s ,i = s+i,s
    for n in range(1,s+1):
        print(s,end="")
    print()

fib = [1, 1]
for _ in range(7):
 print(str(fib[1])*fib[1])
 fib.append(sum(fib))
 fib.pop(0)

first_sequence = 1
second_sequence = 1
sequence_counter = 1
while sequence_counter < 8:
    print_obj = str(second_sequence)
    print_num = second_sequence
    second_sequence += first_sequence
    first_sequence = second_sequence - first_sequence
    while print_num != 0:
        print(print_obj, end='')
        print_num -= 1
    print('')
    sequence_counter += 1

func Example() {
  number := 1
  oldNumber := 1

  for {
    for i := 0; i < number; i++ {
      fmt.Printf("%d", number)
    }

    fmt.Printf("\n")

    if number >= 21 {
      break
    }
    number, oldNumber = number+oldNumber, number
  }
}

کدوم بهتره ؟

#Problems

@Syntax_fa

مسئله پنجم
سطح: متوسط

توضیح:

ما سه آدرس زیر را داریم:
https://jsonplaceholder.typicode.com/todos/1
https://jsonplaceholder.typicode.com/todos/2
https://jsonplaceholder.typicode.com/todos/3

برنامه ای بنویسید که همزمان به هر سه آدرس درخواست get بزند و هرکدام که زودتر جواب داد. در خروجی response body را نمایش بدهد و بگوید پاسخ مال کدام آدرس است.
اگر بعد از گذشت 3 ثانیه هیچکدام از آدرس ها جواب ندادند. در خروجی Timeout را نمایش بدهد و برنامه متوقف شود.

(نمونه خروجی json رو تلگرام خودش زحمت کشید به پیام اضافش کرد)

(💥جایزه کانفیگ یه ماهه)

#Problems

@Syntax_fa

پاسخ در زبان گو:

package main

import (
  "io"
  "net/http"
  "time"
)

func main() {
  var result string

  todo1 := make(chan string)
  todo2 := make(chan string)
  todo3 := make(chan string)

  go GetRequestResponse(todo1, "https://jsonplaceholder.typicode.com/todos/1")
  go GetRequestResponse(todo2, "https://jsonplaceholder.typicode.com/todos/2")
  go GetRequestResponse(todo3, "https://jsonplaceholder.typicode.com/todos/3")

  select {
  case result = <-todo1:
    println("todo1")
    println(result)
  case result = <-todo2:
    println(todo2)
    println(result)
  case result = <-todo3:
    println("todo3")
    println(result)
  case <-time.After(time.Second * 3):
    println("Timeout")
  }
}

func GetRequestResponse(content chan<- string, url string) {
  res, err := http.Get(url)
  if err != nil {
    panic(err)
  }

  responseBody, err := io.ReadAll(res.Body)
  defer res.Body.Close()
  if err != nil {
    panic(err)
  }

  content <- string(responseBody)
}

با استفاده از قابلیت Select و channel ها میتوانیم چنین مسئله ای رو به سادگی حل کنیم.

#Problems

@Syntax_fa

پاسخ در زبان پایتون:

import asyncio
import aiohttp


async def fetch_data(url, session):
    async with session.get(url) as response:
        return await response.text(), url


async def main():
    urls = [
        "https://jsonplaceholder.typicode.com/todos/1",
        "https://jsonplaceholder.typicode.com/todos/2",
        "https://jsonplaceholder.typicode.com/todos/3",
    ]

    async with aiohttp.ClientSession() as session:
        tasks = [fetch_data(url, session) for url in urls]

        try:
            done, _ = await asyncio.wait(tasks, timeout=3, return_when=asyncio.FIRST_COMPLETED)
        except asyncio.TimeoutError:
            print("Timeout: No response within 3 seconds.")
            return

        for task in done:
            response_body, url = task.result()
            print(f"Response from {url}:\n{response_body}")

if __name__ == "__main__":
    asyncio.run(main())

زمانی که از asyncio استفاده میکنیم باید کتابخانه های ماهم از قابلیت async پشتیبانی کنند به همین دلیل از aiohttp بجای requests استفاده میکنیم.

#Problems

@Syntax_fa

یه سوال جالب بپرسیم از جنگو کارای کانال

این سوال توی stackoverflow مطرح شده.

فرض کنید کلاینتی یک درخواست رو سمت ما میفرسته. جنگو شروع میکنه به پراسس و یه سری کار هارو داره انجام میده.
کلاینت که browser هستش درخواست رو که هنوز پاسخش رو دریافت نکرده و در حال پراسس هستش، کنسل میکنه و یا کلا browser رو میبنده.

سمت جنگو چه اتفاقی میوفته؟
آیا راهی هست که توی جنگو وقتی کاربر کنسل میکنه مطلع بشیم و ما هم ادامه پراسس رو انجام ندیم یا اینکه اون پراسس ها باید پیش بره آیا خود جنگو این قضیه رو هندل میکنه ؟

به این لینک ها سر بزنید:
https://groups.google.com/g/django-users/c/3ksj4Clne4c

https://docs.djangoproject.com/es/1.10/ref/request-response/#streaminghttpresponse-objects

https://stackoverflow.com/questions/39451818/how-does-django-handle-cancelled-or-interrupted-requests

#Problems

@Syntax_fa

مسئله ششم (فیلسوفان حریص)
سطح: سخت

بریم سراغ یکی از معروف ترین مسائل برنامه نویسی

در علوم کامپیوتر مسئله فیلسوفان پشت میز غذاخوری یک مسئله تمثیلی است مربوط به طراحی هم روندی الگوریتم ها، که معمولاً برای نشان دادن مشکلات و تکنیک های همگام سازی و روش حل آن ها استفاده می شود. این مسئله در ابتدا در سال ۱۹۶۵ توسط آقای دیکسترا به عنوان یک تمرین امتحانی دانش آموزی طراحی شد.

بیان مسئله:
پنج فیلسوف ساکت در اطراف یک میز قرار می گیرند. روی میز کاسه های ماکارونی وجود دارد. چنگال هایی مابین هر جفت از فیلسوف های کنار هم قرار داده شده است. هر فیلسوف باید به صورت متناوب فکر کند و بخورد. با این حال، یک فیلسوف فقط زمانی می تواند ماکارونی بخورد که که هر دو چنگال سمت چپ و سمت راست را در اختیار داشته باشد. هر چنگال در هر لحظه فقط می تواند توسط یک فیلسوف استفاده شود و بنابراین، یک فیلسوف فقط زمانی می تواند از چنگال استفاده کند که چنگال توسط فیلسوف دیگر در حال استفاده نباشد. بعد از این که یک فیلسوف خوردنش تمام شد، باید هر دو چنگال را روی میز بگذارد تا بقیه از آن ها استفاده کنند. یک فیلسوف فقط می تواند چنگال سمت راست خود یا چنگال سمت چپ خود را، زمانی که موجود باشد، در اختیار بگیرد و نمی‌تواند قبل از در اختیار گرفتن هر دو چنگال خوردن را شروع کند. مقدار خوردن ارتباطی به حجم باقیمانده ماکارونی یا فضای معده افراد ندارد؛ به عبارتی، فرض بر این است که مقدار ماکارونی نامحدود است و مقدار خوردن نیز نامحدود است. مسئله این است که چگونه یک نظم رفتاری (الگوریتم همروندی) طراحی کنیم، به گونه‌ای که هیچ فیلسوفی گرسنه نماند؛ یعنی هر کدام بتواند به مدت نامتناهی و متناوباً بخورد و فکر کند. البته با فرض اینکه هیچ فیلسوفی نمی‌داند که چه زمانی سایر فیلسوفان قصد خوردن یا فکر کردن دارند.

این مسئله با این هدف طراحی شد که چالش های پیشگیری از بن بست را نشان دهد. بن بست یک وضعیتی از سیستم است که در آن هیچ پیشرفتی امکان پذیر نیست.

حتما سرچ کنید و بیشتر در مورد این مسئله بخونید (عکس توی کامنت رو نگاه کنید)

مسئله رو با استفاده از یکی از زبان ها حل کنید و از همه مهم تر بخوبی در مورد مسئله و راه حلتون توضیح بدید.

(جایزه کانفیگ 100 گیگابایتی بدون مدت زمان)

#Problems

@Syntax_fa

مسئله هفتم (پایتون)

سطح: ساده

ما همچین کدی را داریم:

def plus(...):
    ...


if __name__ == "__main__":
    number = ...

    plus(number)

    print(number)

تابع plus کارش این است که number را به علاوه یک کند.
چگونه می توانیم کاری کنیم که number زمانی که در تابع plus به علاوه یک می شود، موقع پرینت هم مقدارش بیشتر شده باشد؟

#Problems

@Syntax_fa

پاسخ:

یکی از روش ها استفاده از کلاس ها هستش

class MutableInteger:
    def __init__(self, number):
        self.number = number

    def __add__(self, other):
        self.number += other

    def __str__(self):
        return str(self.number)


def plus(number: MutableInteger):
    number += 1


if __name__ == "__main__":
    num = MutableInteger(1)

    plus(num)

    print(num)

روش بعدی استفاده از متغیر های گلوبال هستش:

def plus():
    global number
    number += 1


if __name__ == "__main__":
    number = 1

    plus()

    print(number)

#Problems

@Syntax_fa