الگوریتم‌ها در Golang (قسمت دوم): Reverse String/Array و یه دردسر دیگه با Tech Lead!

خب، بعد از اون ماجرای Two Sum که Tech Lead ما رو تو مصاحبه داغون کرد، امروز می‌خوایم یه الگوریتم دیگه رو حل کنیم که خیلی ساده به نظر می‌رسه، اما جزئیات شیطانی داره که می‌تونه تو مصاحبه گیرت بیاره!

🎯 هدف این سری مقالات

قراره از ساده شروع کنیم و به تدریج به سمت الگوریتم‌های پیچیده‌تر بریم. همه چیز رو با Golang پیاده‌سازی می‌کنیم و سعی می‌کنیم مثل یه مصاحبه واقعی پیش بریم.

📝 الگوریتم امروز: Reverse String/Array

صورت مسئله

یه آرایه یا استرینگ بهت میدن، باید برعکسش کنی. اگه میشه In-place (بدون استفاده از حافظه اضافی) انجامش بده.

مثال‌ها:

Input: “hello”

Output: “olleh”

Input: [1, 2, 3, 4, 5]

Output: [5, 4, 3, 2, 1]

Input: “a”

Output: “a”

Input: []

Output: []

محدودیت‌ها:

• طول آرایه/استرینگ: 0 <= length <= 10^5

• باید کارآمد باشه (نه O(n2)O(n^2)O(n2)!)

• باید Unicode رو درست هندل کنه (مثل فارسی و ایموجی)

🤔 انسان vs ماشین: چطور این مسئله رو حل می‌کنیم؟

وقتی ما انسان‌ها می‌خوایم یه کلمه رو برعکس کنیم، خیلی راحت از آخر شروع می‌کنیم و به اول می‌رسیم. مثلاً "سلام" رو می‌بینیم، بلافاصله می‌گیم "مالس".

اما کامپیوتر نمی‌تونه همینطوری یه‌دفعه ببینه! باید یه الگوریتم سیستماتیک بهش بدیم.

❌ راه‌حل ساده (اما نادرست برای مصاحبه!)

اولین چیزی که به ذهن می‌رسه اینه که از توابع آماده استفاده کنیم:

package main

import "fmt"

func reverseStringNaive(s string) string {
    // تو زبان‌هایی مثل Python می‌تونی بنویسی: s[::-1]
    // اما تو Go چی؟ تابع آماده نداریم!
    // پس باید خودمون بنویسیم
    return s // ❌ این کار نمی‌کنه!
}

func main() {
    fmt.Println(reverseStringNaive("hello"))
}

مشکل: تو Golang تابع built-in برای Reverse وجود نداره! پس باید خودمون پیاده‌سازی کنیم.

💥 اولین تلاش: راه‌حل Brute Force

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

package main

import "fmt"

// ❌ این راه‌حل چند مشکل داره!
func reverseArrayNaive(nums []int) []int {
    n := len(nums)
    result := make([]int, n) // حافظه اضافی O(n)
    
    for i := 0; i < n; i++ {
        result[i] = nums[n-1-i]
    }
    
    return result
}

func main() {
    arr := []int{1, 2, 3, 4, 5}
    reversed := reverseArrayNaive(arr)
    fmt.Println("Original:", arr)
    fmt.Println("Reversed:", reversed)
}

خروجی:

Original: [1 2 3 4 5]

Reversed: [5 4 3 2 1]

خب، کار می‌کنه! اما…

😤 Tech Lead وارد می‌شه: “این چیه نوشتی؟!”

Tech Lead کدت رو نگاه می‌کنه و می‌گه:

❌ مشکل ۱: استفاده از حافظه اضافی بی‌دلیل

“چرا یه آرایه جدید ساختی؟ می‌تونستی همون آرایه اصلی رو In-place تغییر بدی! این O(n)O(n)O(n) فضای اضافی لازم نیست.”

❌ مشکل ۲: برای String چی؟

“خب این برای آرایه کار می‌کنه، اما String چی؟ String ها تو Go Immutable هستن! نمی‌تونی مستقیم تغییرشون بدی.”

❌ مشکل ۳: Unicode رو فراموش کردی!

بیا یه تست بزنیم:

func reverseStringWrong(s string) string {
    bytes := []byte(s) // ❌ اشتباه!
    left, right := 0, len(bytes)-1
    
    for left < right {
        bytes[left], bytes[right] = bytes[right], bytes[left]
        left++
        right--
    }
    
    return string(bytes)
}

func main() {
    fmt.Println(reverseStringWrong("hello"))  // ✅ کار می‌کنه
    fmt.Println(reverseStringWrong("سلام"))   // ❌ خراب می‌شه!
    fmt.Println(reverseStringWrong("Hello👋")) // ❌ ایموجی خراب می‌شه!
}

روجی:

olleh

Ù�اÙ�س // ❌ خراب شده!

�👋olleH // ❌ ایموجی خراب شده!

چرا؟

چون []byte هر بایت UTF-8 رو جداگانه می‌بینه. کاراکترهای فارسی و ایموجی چند بایتی هستن، پس وقتی بایت‌ها رو جابه‌جا می‌کنی، کاراکتر خراب می‌شه!

✅ راه‌حل بهینه: Two Pointer Technique

حالا بیا درست حل کنیم!

برای Array (In-place):

package main

import "fmt"

// reverseArray reverses an integer slice in-place
// Time Complexity: O(n)
// Space Complexity: O(1)
func reverseArray(nums []int) {
    if len(nums) < 2 {
        return // Edge case: empty or single element
    }
    
    left, right := 0, len(nums)-1
    
    for left < right {
        // Swap elements
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

func main() {
    arr := []int{1, 2, 3, 4, 5}
    fmt.Println("Before:", arr)
    reverseArray(arr)
    fmt.Println("After:", arr)
}

خروجی:

Before: [1 2 3 4 5]

After: [5 4 3 2 1]

توضیح:

1. دو pointer داریم: left از اول و right از آخر

2. تا وقتی left < right، عناصر رو Swap می‌کنیم

3. هر بار left یکی جلو و right یکی عقب می‌ره

4. وقتی به هم رسیدن، تموم شده!

پیچیدگی:

• زمانی: O(n) - فقط یک بار روی نصف آرایه حرکت می‌کنیم

• فضایی: O(1) - هیچ حافظه اضافی نمی‌خواد

برای String (با دقت Unicode):

package main

import "fmt"

// reverseString reverses a string correctly handling Unicode
// Time Complexity: O(n)
// Space Complexity: O(n) - due to rune slice conversion
func reverseString(s string) string {
    if len(s) < 2 {
        return s // Edge case
    }
    
    // ⚠️ Convert to []rune, NOT []byte!
    runes := []rune(s)
    left, right := 0, len(runes)-1
    
    for left < right {
        runes[left], runes[right] = runes[right], runes[left]
        left++
        right--
    }
    
    return string(runes)
}

func main() {
    // Test with different character sets
    fmt.Println(reverseString("hello"))      // ASCII
    fmt.Println(reverseString("سلام"))       // Persian
    fmt.Println(reverseString("Hello👋"))    // Emoji
    fmt.Println(reverseString("مرحبا"))      // Arabic
}

خروجی:

olleh

مالس

👋olleH

ابحرم

چرا []rune و نه []byte?

• []byte: هر بایت UTF-8 رو جداگانه می‌بینه → کاراکترهای چند بایتی خراب می‌شن

• []rune: هر کاراکتر Unicode رو یک واحد می‌بینه → درست کار می‌کنه

مثال:

“سلام” in UTF-8:

• As []byte: [216 179 217 132 216 167 217 133] (8 bytes)

• As []rune: [1587 1604 1575 1605] (4 runes)

اگه []byte استفاده کنی، بایت‌ها رو جابه‌جا می‌کنی و کاراکتر خراب می‌شه!

🧪 تست کردن با Table-Driven Tests

حالا باید کدمون رو تست کنیم. تو Go از Table-Driven Tests استفاده می‌کنیم:

package main

import (
    "reflect"
    "testing"
)

func TestReverseArray(t *testing.T) {
    tests := []struct {
        name     string
        input    []int
        expected []int
    }{
        {
            name:     "Normal case - odd length",
            input:    []int{1, 2, 3, 4, 5},
            expected: []int{5, 4, 3, 2, 1},
        },
        {
            name:     "Normal case - even length",
            input:    []int{1, 2, 3, 4},
            expected: []int{4, 3, 2, 1},
        },
        {
            name:     "Single element",
            input:    []int{42},
            expected: []int{42},
        },
        {
            name:     "Empty array",
            input:    []int{},
            expected: []int{},
        },
        {
            name:     "Two elements",
            input:    []int{1, 2},
            expected: []int{2, 1},
        },
        {
            name:     "Negative numbers",
            input:    []int{-1, -2, -3},
            expected: []int{-3, -2, -1},
        },
        {
            name:     "Mixed positive and negative",
            input:    []int{-5, 0, 5, 10},
            expected: []int{10, 5, 0, -5},
        },
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            // Make a copy since reverseArray modifies in-place
            input := make([]int, len(tt.input))
            copy(input, tt.input)
            
            reverseArray(input)
            
            if !reflect.DeepEqual(input, tt.expected) {
                t.Errorf("reverseArray() = %v, want %v", input, tt.expected)
            }
        })
    }
}

func TestReverseString(t *testing.T) {
    tests := []struct {
        name     string
        input    string
        expected string
    }{
        {
            name:     "Simple ASCII",
            input:    "hello",
            expected: "olleh",
        },
        {
            name:     "Single character",
            input:    "a",
            expected: "a",
        },
        {
            name:     "Empty string",
            input:    "",
            expected: "",
        },
        {
            name:     "Persian text",
            input:    "سلام",
            expected: "مالس",
        },
        {
            name:     "Arabic text",
            input:    "مرحبا",
            expected: "ابحرم",
        },
        {
            name:     "Emoji",
            input:    "Hello👋",
            expected: "👋olleH",
        },
        {
            name:     "Mixed emoji",
            input:    "🚀Go💻",
            expected: "💻oG🚀",
        },
        {
            name:     "Palindrome",
            input:    "racecar",
            expected: "racecar",
        },
        {
            name:     "Persian palindrome",
            input:    "ساکاس",
            expected: "ساکاس",
        },
        {
            name:     "Numbers as string",
            input:    "12345",
            expected: "54321",
        },
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            result := reverseString(tt.input)
            if result != tt.expected {
                t.Errorf("reverseString() = %q, want %q", result, tt.expected)
            }
        })
    }
}

اجرای تست:

  go test -v

خروجی:

=== RUN TestReverseArray

=== RUN TestReverseArray/Normal_case_-_odd_length

=== RUN TestReverseArray/Normal_case_-_even_length

…

— PASS: TestReverseArray (0.00s)

=== RUN TestReverseString

=== RUN TestReverseString/Simple_ASCII

=== RUN TestReverseString/Persian_text

…

— PASS: TestReverseString (0.00s)

PASS

🚨 دام‌های رایج که باید ازشون دوری کنی

۱. فراموش کردن Edge Cases

                                            content_copy                        go// ❌ Crash می‌کنه اگه آرایه خالی باشه!
func reverseBad(nums []int) {
    for i := 0; i < len(nums)/2; i++ {
        // اگه nums خالی باشه، len(nums)-1-i منفی می‌شه!
        nums[i], nums[len(nums)-1-i] = nums[len(nums)-1-i], nums[i]
    }
}

تست:

reverseBad([]int{}) // ❌ Panic: index out of range!

۲. استفاده از []byte برای String

// ❌ Unicode رو خراب می‌کنه
func reverseStringBroken(s string) string {
    bytes := []byte(s)
    // ... swap logic ...
    return string(bytes)
}

// Test:
reverseStringBroken("سلام") // ❌ Output: gibberish!

۳. ساختن آرایه جدید بی‌دلیل

// ❌ O(n) space - غیر بهینه!
func reverseWithExtraSpace(nums []int) []int {
    result := make([]int, len(nums))
    for i := 0; i < len(nums); i++ {
        result[i] = nums[len(nums)-1-i]
    }
    return result
}

چرا بد است؟

• حافظه اضافی O(n) می‌خواد

• وقتی می‌تونی In-place حل کنی، چرا حافظه هدر بدی؟

۴. استفاده از strconv یا String Concatenation تو حلقه

// ❌ خیلی کند! O(n^2) می‌شه
func reverseStringSlow(s string) string {
    result := ""
    for i := len(s) - 1; i >= 0; i-- {
        result += string(s[i]) // String concatenation is O(n)!
    }
    return result
}

چرا کند است؟

• هر بار += یه string جدید می‌سازه (String ها Immutable هستن)

• پیچیدگی می‌شه O(n2)!

📊 مقایسه راه‌حل‌ها

۱. ساختن آرایه جدید

result := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
    result[i] = nums[len(nums)-1-i]
}

• پیچیدگی زمانی: O(n)

• پیچیدگی فضایی: O(n)

• Unicode Safe: ✅

• In-place: ❌

۲. Two Pointer برای Array

left, right := 0, len(nums)-1
for left < right {
    nums[left], nums[right] = nums[right], nums[left]
    left++
    right--
}

• پیچیدگی زمانی: O(n)

• پیچیدگی فضایی: O(1) ⭐ بهترین!

• Unicode Safe: ✅

• In-place: ✅

۳. Two Pointer برای String با []rune

runes := []rune(s)
left, right := 0, len(runes)-1
for left < right {
    runes[left], runes[right] = runes[right], runes[left]
    left++
    right--
}
return string(runes)

• پیچیدگی زمانی: O(n)

• پیچیدگی فضایی: O(n)

• Unicode Safe: ✅ ⭐ درست!

• In-place: ❌ (چون String ها Immutable هستن)

۴. استفاده از []byte برای String

bytes := []byte(s)
// ... swap logic ...
return string(bytes)                      

• پیچیدگی زمانی: O(n)O(n)O(n)

• پیچیدگی فضایی: O(n)O(n)O(n)

• Unicode Safe: ❌ ⚠️ فارسی و ایموجی خراب می‌شه!

• In-place: ❌

۵. String Concatenation (بدترین روش!)

result := ""
for i := len(s) - 1; i >= 0; i-- {
    result += string(s[i])
}

• پیچیدگی زمانی: O(n2)O(n^2)O(n2) ⚠️ خیلی کند!

• پیچیدگی فضایی: O(n)O(n)O(n)

• Unicode Safe: ✅

• In-place: ❌

نتیجه‌گیری:

• برای Array: روش Two Pointer با O(1)O(1)O(1) فضا بهترینه

• برای String: روش Two Pointer با []rune تنها راه درست و Unicode-safe هست

💡 نکات طلایی برای مصاحبه

۱. همیشه Edge Cases رو بپرس

قبل از شروع کد نوشتن:

• “آیا ورودی می‌تونه خالی باشه؟”

• “آیا باید In-place باشه یا می‌تونم آرایه جدید برگردونم؟”

• “آیا String می‌تونه کاراکترهای غیر ASCII داشته باشه؟”

۲. Trade-off رو توضیح بده

“برای آرایه می‌تونیم In-place باشیم با O(1) فضا، اما برای String چون Immutable هست، مجبوریم []rune بسازیم که O(n) فضا می‌خواد.”

۳. Unicode رو فراموش نکن

“از []rune استفاده می‌کنم تا کاراکترهای چند بایتی مثل فارسی و ایموجی خراب نشن.”

۴. پیچیدگی رو بگو

“پیچیدگی زمانی O(n) چون یک بار روی آرایه حرکت می‌کنیم. پیچیدگی فضایی برای آرایه O(1) چون In-place هست، اما برای String O(n) چون باید []rune بسازیم.”

🎓 خلاصه و نکات کلیدی

✅ Two Pointer Technique: بهترین روش برای Reverse کردن

✅ In-place: برای آرایه ممکنه، برای String نه

✅ []rune not []byte: برای Unicode Safety

✅ Edge Cases: خالی، تک عنصری، Palindrome

✅ پیچیدگی: O(n) زمانی، O(1) یا O(n) فضایی

🚀 کد نهایی کامل

                                            package main

import "fmt"

// reverseArray reverses an integer slice in-place
// Time: O(n), Space: O(1)
func reverseArray(nums []int) {
    if len(nums) < 2 {
        return
    }
    
    left, right := 0, len(nums)-1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

// reverseString reverses a string correctly handling Unicode
// Time: O(n), Space: O(n)
func reverseString(s string) string {
    if len(s) < 2 {
        return s
    }
    
    runes := []rune(s)
    left, right := 0, len(runes)-1
    
    for left < right {
        runes[left], runes[right] = runes[right], runes[left]
        left++
        right--
    }
    
    return string(runes)
}

func main() {
    // Test array
    arr := []int{1, 2, 3, 4, 5}
    fmt.Println("Before:", arr)
    reverseArray(arr)
    fmt.Println("After:", arr)
    
    // Test string
    fmt.Println("\nString tests:")
    fmt.Println(reverseString("hello"))
    fmt.Println(reverseString("سلام دنیا"))
    fmt.Println(reverseString("Hello👋World🌍"))
}
                        

حالا آماده‌ای که Tech Lead رو با یه راه‌حل تمیز، بهینه و Unicode-safe قانع کنی! 🎯