10.1 פתיח הרצאה

פתיחה

• בפרק זה לא יהיו הרצאות ווידאו, הסיבה לכך היא שאתם צריכים לעבור בדקדקנות על כל ההרצאות טקסט, ולקרוא את כל הטקסטים המון פעמים כדי לוודא שאתם בכיוון הנכון.
• בנוסף זה יכולה להיות הזדמנות נהדרת בשבילכם עם הכוונה שלי (שכתובה בפרק) ללמוד לבד נושא מאוד מעניין שיעזור לכם בראיונות עבודה שלכם, ובכך לפתח את המסוגלות שלכם.
• בהצלחה!

אלגוריתמיקה לראיונות עבודה (הכנה מקצועית)

• בראיון עבודה בפיתוח כמעט תמיד יש שאלות אלגוריתמיקה.
• שאלות אלגוריתמיקה הם שאלות שמטרתם לבחון את החשיבה שלכם בתכנות ואת היכולת שלכם לפתור בעיה תכנותית, באמצעות כתיבת פונקציה כלשהי שהמראיין מבקש.
• בדרך כלל בבעיות אלגוריתמיקה משתמשים במבני נתונים ואלגוריתמים נפוצים, בפרק זה נעבור עליהם ונלמד על הדברים הנפוצים שסביר שנתקל בהם בראיון עבודה.
• בתרגול להרצאה הזו נעשה המון תרגילי אלגוריתמיקה נפוצים.

חידוד קטן: רשימה vs מערך

• עד כו למדנו שרשימות הן קבוצה של משתנים שצמודים אחד לשני ויכולים להיות עם המון סוגים של משתנים בפנים, ושאפשר להגדיל אותם באמצעות (remove ו - append).
• מערך הוא רשימה שאיי אפשר להגדיל בזמן ריצה (אי אפשר לעשות append), ומערך יכול להחזיק רק סוג אחד של משתנה, לא כמה בבת אחת.
• יש בהמון שפות תכנות שימוש במערכים - בפייתון פחות בזכות רשימות: אז בהמון שאלות אלגוריתמיקה מציינים את המילה מערך, פשוט הכירו שזה רשימה רגילה לחלוטין רק מעט מוגבלת יותר.

שאלת אלגורימיקה: שאלת 5 ו-7

דוגמה לשאלת אלגוריתמיקה: כתבו פונקציה שמקבלת את מספר ומחזירה מספר, אם הפונקציה מקבלת 5 החזירו 7, ואם הפונקציה מקבלת 7 החזירו 5. שימו לב: הפונקציה תקבל בוודאות או 7 או 5 - אין צורך לוודא מקרה אחר.
- פתרון לשאלה הזו יכול להיות הפתרון הבא:

def seven_five(number):
    if number == 7:
        return 5
    elif number == 5:
        return 7

המשך השאלה: פתרו את הבעיה מבלי להשתמש בif
- כיצד נוכל לפתור את הבעיה מבלי להשתמש בתנאי? נסו לחשוב על מה מיוחד ב5 ו7: שניהם מספרים. נוכל להשתמש בעובדה שקיבלנו מהשאלה ששניהם מספרים ולכתוב פעולה חשבונית שפותרת את הבעיה.
- איך נכתוב פונקציה שמתמשת בפעולות חשבון כדי לפתור את הבעיה? אם הפונקציה שלנו מקבלת 7, נוכל לחסר את המספר ב2 ואז נקבל 5. לעומת זאת אם נקבל את המספר 5, נוכל להוסיף לה 2 ואז נקבל 7.
נשמע טוב, אבל אם ננסה לפתור את הבעיה כך, נצטרך להשתמש בתנאי כמו בדוגמה הבאה:

def seven_five(number):
    if number == 7:
        return number-2
    elif number == 5:
        return number+2

- אז מה בכל זאת נוכל לעשות? האם יש פעולה חשבונית שאפשר לעשות על הפרמטר של הפונקציה, שגם אם נקבל 7 או 5, תמיד נחזיר את התשובה הנכונה? נסו לחשוב ביצירתיות: אם נעשה 5 + 7 נקבל 12: 5+7=12, כך שאם נעשה 12-7 נקבל 5, ואם נעשה 12-5 נקבל 7.
- לאנשים פה שמכירים משוואת מתמטיות, נוכל להתייחס לזה בצורה כזו:

5 + 7 = 12
x + y = 12
y = 12 - x

- נוכל לכתוב פונקציה שמחזירה 12 פחות המספר שקיבלנו, וכך תמיד נקבל את המספר ההופכי.

def seven_five(number):
    return 12-number

seven_five(5) # outputs 7
seven_five(7) # outputs 5

- האם נוכל להשתמש בשיטה הזו כדי למצוא עוד פתרונות?
כן, נוכל לעשות את אותו חישוב שעשינו עם כל הפעולות החשבוניות, למשל עם כפול:

# 5 * 7 = 35
# x * y = 35
# y = 35 / x
def seven_five(number):
    return 35/number

ננסה לחשוב על פתרון לא מתמטי, מה עוד נוכל לעשות? נוכל להשתמש ברשימה:
ניצור רשימה עם 7 מקומות, כאשר המקום ה7 יצביע על 5, והמקום ה5 יצביע על 7:

[0, 0, 0, 0, 5, 0, 7]

ואז נוכל פשוט לגשת למקום 5 ברשימה ונקבל 7 וכשניגש למקום 7 נקבל 5.

def seven_five(number):
    l = [0, 0, 0, 0, 7, 0, 5]
    return l[number-1]

- אל תשכחו להוסיף פחות 1, כי מתחילים לספור מ0 ברשימות.

דרך טובה יותר לבצע את זה זה באמצעות מילון:
- מילון זה מבנה נתונים מיוחד, כי לעומת רשימה למשל - לכל ערך במילון קיים גם מפתח.
נוכל להשתמש במילון בצורה הבאה, ניצור מילון שיראה כך:

d = {
    5: 7
    7: 5
}

- ועכשיו כאשר ניגש למפתח 5 במילון, נקבל 7. וכאשר ניגש למפתח 7 במילון, נקבל 5.

def seven_five(number):
    d = {
        5: 7
        7: 5
    }
    return d[number]

- מילון זה מבנה נתונים מאוד פופלורי בבעיות אלגוריתמיקה, השתמשו בו איפה שרק אפשר.
- שימו לב: בהמון מקומות תשמעו את המושג "hash table" או בעברית "טבלת גיבוב" - אלו שמות נרדפים למילון, נהוג להשתמש במושגים האלו בבעיות אלגוריתמיקה.

הערה חשובה:

• בבעיות אלגוריתמיקה, יש קצת נגיעה במתמטיקה כמו שראיתם למעלה: לצערי רוב החברות הייטק בראיונת עבודה מביאים בעיות אלגורימיקה כמו הדוגמה למעלה, וזה אומר שגם אם אתם מתכנתים מעולים, יש סיכוי שלא תעברו את הראיון בגלל האלגוריתמיקה, בפרק הבא, אנחנו נתרגל המון והמון אלגוריתמיקה, ואביא המון שאלות מפורסמות בראיונות עבודה. (שאלת 7 ו - 5 היא גם שאלה מפורסמת מראיונות עבודה)
• כך שאם לא התחברתם עד כו לאלגוריתמיקה, תשדלו בכל זאת לתרגל כמה שאפשר כי זה קריטי לגבי ראיונות עבודה.

תרגיל: two sum

• כתוב פונקציה שמקבלת שני פרמטרים: רשימה של מספרים, ומספר שנקרא target. הפונקציה צריכה למצוא שני מספרים ברשימה שהסכום שלהם יוצא target, הפונקציה מחזירה את המיקום של שני המספרים ברשימה.
  דוגמה:
  

  numbers=[4,3,8,6,2,4], target=5
  

  
  במקרה הזה 3 + 2 יוצא 5, אז הפונקציה תחזיר 1 ו- 4 (המקומות ברשימה של 2 ו- 5)
• שימו לב: תמיד יהיה רק פתרון אחד לקלט שתקבלו לפונקציה.
  פתרונות
• פתרון brute force: הפתרון הוא לכתוב 2 לולאות ותנאי שעוברות על כל קומבינציה של מספרים ובודקות האם הסכום שלהם יוצא הtarget, בצורה הבאה:
  

  def two_sum(nums: List[int], target: int) -> List[int]:  
      for i in range(len(nums)):
          for j in range(i + 1, len(nums)):
              if nums[i] + nums[j] == target:  
                  return [i, j]
  

  
  פתרון מסוג brute force זה פתרון שבו באמצעות מספר לולאות אנחנו עוברים על כל הקומבינציות ועושים משהו מסויים.
  הדוגמה למעלה הוא דוגמה לפתרון כזה, הסוג פתרון זה הוא הפתרון הכי פשוט והכי קל. למעשה בכמעט כל בעיית אלגוריתמיקה יש פתרון bruteforce
• פתרון hash table: כמו שהשתמשנו בhash table בבעיית 5 ו- 7, אפשר להשתמש גם פה.
  • ניצור מילון חדש
  • נעבור על כל המספרים ברשימה
  • על כל מספר ברשימה ונעשה שני פעולות: 1. נוסיף אותו למילון, מצורף למיקום שלו ברשימה. ו2. נבדוק אם target - num (המספר שאנחנו רוצים למצוא) נמצא במילון.
    כך אנחנו שומרים את כל המספרים במילון, ואז זה מאפשר לנו לעבור על הרשימה של המספרים רק פעם אחת, כי נוכל פשוט לבדוק האם המספר המשלים למספר עליו אנחנו עוברים וtarget נמצא במילון.
    

    def two_sum(nums: List[int], target: int) -> List[int]:  
        hash_map = {}  
        for i in range(len(nums)):  
            complement = target - nums[i]
            if complement in hash_map:  
                return [hash_map[complement], i]  
            hash_map[nums[i]] = i
    

אנוטציה big O

• ברוב הראיונות עבודה, יבקשו מכם להגיד מה time complexity ו- הspace complexity של האלגוריתם שכתבתם. הדירוג הזה, אמור לבטא עד כמה יעיל האלגוריתם שכתבתם מבחינת זמן ריצה, ומבחינת כמות זכרון שתפסתם במחשב.

סיבוכיות זמן - time complexity

• כדי לחשב את סיבוכיות הזמן של האלגוריתם שלכם בצורה הקלה ביותר, נסו לחשוב על הקלט הגרוע ביותר שאתם יכולים להביא לאלגוריתם: קראו לו נניח n, ונסו להבין את כמות השורות קוד שהמחשב יצטרך להריץ תלוי בn.
  דוגמה: brute force
  נקח לדוגמה את פתרון הbrute force שלנו לtwo sum:
  

  ```python
  def two_sum(nums: List[int], target: int) -> List[int]:  
      for i in range(len(nums)):
          for j in range(i + 1, len(nums)):
              if nums[i] + nums[j] == target:  
                  return [i, j]
  

  
  נניח ואורך הרשימה היה n: בגלל שיש פה שני לולאות אחת בתוך השנייה, לכל n ריצות של הלולאה הראשונה, רץ עוד פעם n בלולאה השנייה. כך שכמות הריצות הן: n*n אז הסיבוכיות זמן היא: n^2. אז למראיין תגידו את המשפט הבא:
  אם n הוא אורך הרשימה, סיבוכיות זמן הריצה היא O(n^2)
  דוגמה: hash map

נקח לדוגמה את פתרון הhash table שלנו לtwo sum:

def two_sum(nums: List[int], target: int) -> List[int]:  
    hash_map = {}  
    for i in range(len(nums)):  
        complement = target - nums[i]
        if complement in hash_map:  
            return [hash_map[complement], i]  
        hash_map[nums[i]] = i

נניח ואורך הרשימה היה n: בגלל שיש פה לולאה אחת, אנחנו עוברים על הלולאה n פעמים, אז סיבוכיות הזמן היא n: (n^1)
אז למראיין תגידו את המשפט הבא:
אם n הוא אורך הרשימה, סיבוכיות זמן הריצה היא O(n)

דוגמה: 5 ו- 7
נקח לדוגמה את אחד הפתרונות שלנו לשאלת 5 ו- 7:

def seven_five(number):
    return 12-number

- פה אין רשימה, (אין n) ובגלל שאין פה שום לולאה או שום משתנה כלשהו עם גודל מסויים כמו רשימה: סיבוכיות זמן הריצה היא O(1). שימו לב: זה O(1) לא בגלל כמות השורות, אלה בגלל כמות הסיבוכיות של השורות: רק בגלל שאין פה סוג של לולאה, ויש פה פשוט קוד פשוט שרץ בלי שום קפיצות כלשהן הסיבוכיות שלו היא O(1). ענו למראיין: סיבוכיות זמן הריצה היא O(1)

בעתיד נעבור על עוד המון פתרונות לתרגילים, ובכל אחד מהם אסביר על זמן הריצה, זה בסדר אם זה לא נראה כל כך ברור כרגע: ברוב המוחלט של הראיונות לא תצטרכו להסביר איזשהי הוכחה מתמטית לזמן הריצה כך שאפשר אפילו ללמוד בעל פה שכמות הלולאות תרמוז על סיבוכיות זמן הריצה, נלמד בהמשך על כל מיני מקרה קצה.
- אם יש לכם באלגוריתם שלכם מספר לולאות, כמו לולאה אחת, ואז עוד לולאה בתוך לולאה: הtime complexity יהיה פשוט O(n^2) כי תמיד הלולאה הגדולה ביותר לוקחת.

סיבוכיות מקום: space complexity

• כדי לחשב את הspace complexity של האלגוריתם שלכם בצורה הקלה ביותר, פשוט תבדקו באיזה מבנה נתונים אתם משתמשים, לכל מבנה נתונים יש סיבוכיות מקום שונה:
• לתוכנה שיש בה רק משתנים רגילים (לא רשימות או כדומה) הspace complexity שלה הוא O(1).
• לתוכנה שיש לה רשימה/מערך/סט/טאפל שמכיל רשימה של משתנים (לא רשימות), למשל מספרים: הspace complexity שלה הוא O(n) כאשר n הוא גודל המערך.
• לתוכנה שיש לה רשימה שמכילה רשימות - זה נקרא רשימה דו מימדית, הspace complexity שלה יהיה O(n^2) כאשר n הוא גודל המערכים.
• לתוכנה שיש לה רשימה שמכילה רשימות שמכילות עוד רשימות - זה נקרא רשימה טריפל מימדית, הspace complexity שלה יהיה O(n^3) כאשר n הוא גודל המערכים. אם אתם נתקלים ברשימה עוד יותר מסובכת (כנראה שלא), זכרו שהכמות מימדים שלה משליכה על הspace complexity שבהתאם.
• זכרו בעל פה: הspace complexity של מילון הוא O(n), בעתיד שנלמד על עוד מבני נתונים אציין את הspace complexity שלהם:
• אם יש לכם באלגוריתם מספר מבני נתונים, כמו גם משתנים, גם מילון וגם רשימה דו מימדית, תמיד המבנה נתונים הגדול ביותר לוקח את הspace complexity: למשל במקרה זה התשובה הייתה O(n^2)
  דוגמה:
  

  def seven_five(number):
      return 12-number
  

• הspace complexity יהיה O(1) - אין פה משתנים בכלל
  

  def two_sum(nums: List[int], target: int) -> List[int]:  
      for i in range(len(nums)):
          for j in range(i + 1, len(nums)):
              if nums[i] + nums[j] == target:  
                  return [i, j]
  

• הspace complexity יהיה O(1) - יש פה רק שני משתנים מספרים
  

  def two_sum(nums: List[int], target: int) -> List[int]:  
      hash_map = {}  
      for i in range(len(nums)):  
          complement = target - nums[i]
          if complement in hash_map:  
              return [hash_map[complement], i]  
          hash_map[nums[i]] = i
  

• הspace complexity יהיה O(n) כאשר n הוא אורך הhash map.

חיפוש

חיפוש לפי הסדר

• נניח יש לנו רשימה בעלת 1000 איברים עם המון מספרים, איך נוכל למצוא בה מספר ספציפי שאנחנו יודעים שנמצא ברשימה? דרך אחת, היא פשוט לעבור על כל המספרים ולבדוק האם המספר קיים.
• הנה דוגמה לפונקציה שמקבלת רשימה ומחפשת איבר, בדרך הזו:
  

  def search_item(items, item):
      for i in items:
          if i == item:
              return i
  
  search_item([1,9,4,2,7,67,11,78,3,14,68,8,24,5,10], 24)
  

• זכרו, כשאנחנו מחפשים לפי הסדר בצורה כזו: אנחנו צריכים לעבור על כל הרשימה.

חיפוש בינארי

• איך נוכל ליעל את מהירות החיפוש שלנו? הניחו שאנחנו צריכים למצוא את המספר 14 ברשימה מסודרת - מקטן לגדול כמו:
  

  [1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 14, 24, 67, 68, 78]
  

  
  במקום להשתמש בלולאה ולעבור על כל תא, נעשה את זה בצורה חכמה יותר.
• נחלק את הרשימה בדיוק באמצע, ונשלוף את האיבר שנמצא שם: במקרה שלנו זה 9.
  
  ונשאל שני שאלות: האם המספר שאנחנו מחפשים (14) הוא גדול מ9 או שווה לו? בגלל ש14 גדול מ9 כבר שללנו את כל החצי הראשון של הרשימה כולל 9, חשבו על זה: בגלל שהרשימה מסודרת מקטן לגדול, והאיבר האמצעי ברשימה הוא 9, כל מספר שבא לפני 9 הוא לא יהיה 14. אז אנחנו יכולים לשלול את כל החצי הראשון: עכשיו המשימה שלנו היא קלה יותר, כי עכשיו אנחנו צריכים למצוא מספר ברשימה קטנה יותר:
  

  [10, 11, 14, 24, 67, 68, 78]
  

• עכשיו נעשה בדיוק אותו הדבר, נחלק את הרשימה בדיוק באמצע, ונשלוף את האיבר שנמצא שם: במקרה שלנו זה 24:
  
  ונשאל, האם המספר שאנחנו מחפשים (14) הוא גדול מ24 או 24?
  לא - ובגלל זה אפשר לשלול עוד חלק ברשימה:
  
• עכשיו נעשה בדיוק אותו הדבר, נחלק את הרשימה בדיוק באמצע, ונשלוף את האיבר שנמצא שם: במקרה שלנו זה 11:
  
  ונשאל, האם המספר שאנחנו מחפשים (14) הוא גדול מ11 או 11?
  לא - ובגלל זה אפשר לשלול עוד חלק ברשימה:
  

• עכשיו נעשה בדיוק אותו הדבר, נחלק את הרשימה בדיוק באמצע, ונשלוף את האיבר שנמצא שם: במקרה שלנו זה 14:
  
  ונשאל, האם המספר שאנחנו מחפשים (14) הוא גדול או שווה ל14?
  כן - מצאנו את 14.

• הטכניקה שהצגתי נקראת חיפוש בינארי, ואפשר לראות שב4 פעולות מצאנו את המספר שחיפשנו, לעומת חיפוש רגיל שהיה לוקח 11 פעולות במקרה הזה (מוזמנים לספור)
  שימו לב - חיפוש בינארי עובד רק אם הרשימה מסודרת מקטן לגדול!

• דוגמה לקוד של חיפוש בינארי:
  שימו לב: בקוד low ו-high הם משתנים שמסמנים את ההתחלה של הרשימה והסוף שלה, וכל פעם שאנחנו מקטינים את הרשימה אז אנחנו משנים את high ו-low בהתאם. בכל ריצה של הלולאה אנחנו מחשבים את mid בהתאם לlow ולhigh כך שכל פעם mid יהיה האמצע של low וhigh שנדע מתי לחצות אותה:
  אני יודע שהקוד קצת מסובך בהתחלה, אבל נסו להבין אותו:
  

  def binary_search(arr, x):
      low = 0
      high = len(arr) - 1
      mid = 0
  
      while low <= high:
  
          mid = (high + low) // 2
  
          # If x is greater, ignore left half
          if arr[mid] < x:
              low = mid + 1
  
          # If x is smaller, ignore right half
          elif arr[mid] > x:
              high = mid - 1
  
          # means x is present at mid
          else:
              return mid
  
      # If we reach here, then the element was not present
      return -1
  

• שימו לב! הtime complexity של הbinary search הוא לא O(n)! הוא O(log n).*
  מדוע? אני לא אכנס למתמטיקה שעומדת מאחורי הקלעים, כי זה לא קורס מתמטיקה. המטרה של הקורס היא להכין אתכם לעולם הייטק, ולהפוך אתכם למתכנתים חזקים, ואני חושב שיש המון חלקים באלגוריתמיקה - בעיקר החלקים המתמטים שפשוט לא רלוונטים. זכרו את זה שהסיבוכיות זמן של binary search היא O(log n) בעל פה. זכרו: הסיבוכיות זמן של חיפוש ביאנרי היא טובה יותר מO(n) (מסתם לולאה), כך
  הspace complexity של binary search הוא O(1).
• נקודה חשובה: המימוש הזה של חיפוש בינארי מחזיר לנו את המיקום של המספר שמצאנו.

תרגיל: two sum 2

• התרגיל זהה לתרגיל two sum, רק שהפעם הרשימה היא ממויינת מקטן לגדול.
  דוגמה:
  

  numbers=[2,3,4,4,6,8], target=5
  

  
  במקרה הזה 3 + 2 יוצא 5, אז הפונקציה תחזיר 1 ו- 0 (המקומות ברשימה של 2 ו- 3)
• שימו לב: תמיד יהיה רק פתרון אחד לקלט שתקבלו לפונקציה.
  פתרונות
• פתרון brute force: הפתרון הוא לכתוב 2 לולאות ותנאי שעוברות על כל קומבינציה של מספרים ובודקות האם הסכום שלהם יוצא הtarget, בצורה הבאה:
  

  def two_sum(nums: List[int], target: int) -> List[int]:  
      for i in range(len(nums)):
          for j in range(i + 1, len(nums)):
              if nums[i] + nums[j] == target:  
                  return [i, j]
  

• פתרון binary search: למעשה בגלל שבפתרון brute force אנחנו פשוט עוברים על כל המספרים פעמיים עם שני לולאות, ובגלל שהרשימה ממוינת, אפשר פשוט לעשות חיפוש בינארי, כדי למצוא את המספר שאנחנו מחפשים יותר ביעילות, ננסה לחפש כמו בפתרון של two sum את המספר המשלים באמצעות target-num
  

  def two_sum(nums: List[int], target: int) -> List[int]:  
      for i in range(len(nums)):
          complement = target - nums[i]
          j = binary_search(nums, complement) # O(log(n))
          if j:
              return [i, j]       
  

  
  זוהי דוגמה לאיך חיפוש בינארי יכול לעזור לנו לחפש ערך בתוך רשימה בצורה מהירה יותר: הסיבוכיות זמן של האלגורתים תהיה O(n*log n), כי אנחנו עושים לולאה (O(n)), שמכילה חיפוש בינארי (O(log n)).
  ובפתרון הזה הסיבוכיות מיקום תהיה O(1).
• פתרון two pointers: עוד שיטה נפוצה לפתור בעיות אלגוריתמיקה היא באמצעות שיטת "2 מצביעים", בשיטה הזו אנחנו משתמשים בשני משתנים שעוברים על רשימה בו זמנית, במקרה הזה נעשה אחד מההתחלה לסוף ואחד מהסוף להתחלה.
  בגלל שהרשימה ממיונת, נוכל לפתור את הבעיה כך עם שני מצביעים:
  • ניצור מצביע left שיצביע על תחילת הרשימה, ומצביע right שיצביע על סוף הרשימה.
  • כל עוד המבציעים לא נפגשו: left != right, נזיז את המצביעים בצורה הבאה:
  • אם הסכום של המספרים עליהם יש מצביעים שווה לtarget, נחזיר אותם, אם הסכום קטן מtarget, נקדם את left צעד קדימה, אם הסכום גדול מtarget, נקח את right אחורה.
  • כך נמשיך עד שנמצא את המספרים שסכומם הtarget, ואם לא מצאנו שום התאמה, אנחנו מחזירים [-1\,-1]
    

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            current_sum = numbers[left] + numbers[right]
            if current_sum == target:
                return [left+1, right+1]
            elif current_sum < target:
                left += 1
            else:
                right -= 1
        return [-1, -1]
    

• אם n הוא גודל הרשימה nums, הtime complexity הוא O(n) ו- הspace complexity יהיה O(1).

חזרה:

• מה עשינו השיעור:
  • בעית אלגוריתמיקה 7 ו - 5
  • בעית אלגוריתמיקה two sum
  • בעית אלגוריתמיקה 2 two sum
  • יתרונות של שתי מצביעים, חיפוש בינארי ומילון (hash table) בבעיות אלגוריתמיקה
  • למדנו על פתרון brute force שקיים כמעט עבור כל בעיית אלגוריתמיקה.
  • למדנו על time/space complexity ואיך אפשר להגדיר מה הbig O של הפונקציה שלנו.

תרגול

• חוץ מהתרגולים שאני עושה איתכם בשיעורים, קיימים עוד מאות בעיות אלגוריתמיקה מעולות באתר ליטקוד: https://leetcode.com/problemset/, זהו אתר עם המון בעיות אלגוריתמיקה בהמון נושאים, חלקם למדנו וחלקם עוד נלמד - וכל בעיה מכילה רמזים, פתרון באינטרנט, ודוגמאות.
• עשו כמה שיותר בעיות באתר, שחקו עם האתר ולמדו להשתמש בו.