אז הנה אתה. הוקל. מותש. סוף סוף הגעת לגישה לפתור את שאלת הקידוד המסובכת שהמראיין שלך שואל אותך. אולי אפילו רשמת את זה על הלוח, שורה אחר שורה. ועשיתם זמן טוב! אתה רק 20 דקות מהפגישה. המראיין שלך צריך להתרשם.
ימין?
"זה יעבוד, אבל כל רעיונות כיצד לעשות זאת בצורה יעילה יותר?"
ליבך שוקע. חשבתם שסיימתם עם החלק בעיצוב האלגוריתמים המסובך! אתה מנסה לחשוב על דרכים נוספות לפתור את הבעיה, אך כל מה שאתה יכול לחשוב עליה הוא הגישה האחת שכבר הגעת אליה.
זה קורה כמעט לכולם. וזה לא בגלל שהם טיפשים. הסיבה לכך היא שלרוב האנשים אין שיטה לשיפור היעילות של האלגוריתמים שלהם.
אבל האמת, יש המון. בפעם הבאה שאתה גמוע, נסה ליישם את שלוש הגישות הנפוצות הללו.
1. השתמש במפת Hash
זה נכון. למפות Hash / מערכים / מילונים אסוציאטיביים (הם מופיעים בשמות רבים, תלוי באיזו שפת תכנות אתה משתמש) יש יכולת קסומה להפחית את זמן ההפעלה של האלגוריתמים.
לדוגמה, נניח שהשאלה הייתה למצוא את המספר החוזר ביותר במערך של מספרים.
המחשבה הראשונה שלך עשויה להיות לקפוץ לכמה לולאות. עבור כל אחד מהמספרים שלנו, ספר את הספירה שלו ובדוק אם זה המספר הגדול ביותר. איך משיגים את הספירה עבור כל מספר? עיין במערך וספור כמה פעמים הוא מתרחש! אז אנחנו מדברים על שני לולאות מקוננות. בפסודוקוד:
def get_mode (nums): max_count = 0 mode = null עבור potential_mode ב- nums: count = 0 for number in our_array: count + = 1 if count> = max_count: mode = potential_mode max_count = count count mode
כרגע, אנו עוברים את כל המערך שלנו פעם אחת עבור כל פריט במערך - אך אנו יכולים לעשות טוב יותר. בסימן O גדול, זה הזמן של O (n 2 ) בסך הכל.
אם אנו מאחסנים את הספירות שלנו במפת חשיש (מיפוי מספרים לספירות שלהם), נוכל לפתור את הבעיה רק בהליכה אחת במערך (O (n)!):
def get_mode (nums): max_count = 0 mode = null count = HashMap חדש, החל כל ערך ב- 0 עבור potential_mode במספרים: count + = 1 if count> max_count: mode = potential_mode max_count = סופרת מצב חזרה
הרבה יותר מהר!
2. השתמש במניפולציה של ביט
זה באמת יבדיל אותך מהחבילה. זה לא תקף לכל בעיה, אבל אם אתה שומר את זה בכיס האחורי ומפזר אותו בזמן הנכון, אתה נראה כמו כוכב רוק.
הנה דוגמה: נניח שהיה לנו מערך של מספרים, שכל מספר מופיע בו פעמיים, פרט למספר אחד המופיע רק פעם אחת. אנו כותבים פונקציה כדי למצוא את המספר הבודד, הלא חוזר.
האינסטינקט הראשון שלך יכול להיות להשתמש במפת חשיש, מכיוון שרק דיברנו על זה. זה אינסטינקט טוב שיש! וזה יעבוד עבור זה. אנו יכולים ליצור מפת "ספירות" דומה מאוד, ולהשתמש בזה כדי לראות איזה מספר מסתיים בספירה של 1.
אבל יש דרך אפילו טובה יותר. אם אתה מכיר את מניפולציות הסיביות, ייתכן שאתה מכיר את XOR. דבר אחד שמיוחד ב- XOR הוא שאם אתה XOR מספר עם עצמו, הקטעים "מבטלים" ל 0. לבעיה זו, אם אנו משנים את כל המספרים במערך יחד, נשאיר את המספר היחיד שלא לא מבטל:
def find_unrepeated (nums): unrepeated = 0 for num in nums: unrepeated = unrepeated XOR num return unrepeated
3. עבור מלמטה למעלה
כתוב פונקציה שמוצאת את מספר ה- Fibonacci "ה", בהינתן מספר n. זה קלאסי, וזה מתאים מאוד לחזרתיות:
def fib (n): אם n הוא 0 או 1: return 1 return fib (n-1) + fib (n-2)
אבל התשובה הרקורסיבית הפשוטה אינה היחידה! חשבו היטב מה הפונקציה הזו עושה. נניח ש- n הוא 5. כדי לקבל את התשובה, זה מכנה רקורסיבית fib (4) ו- fib (3). עכשיו, מה זה קורא לסיב (4)? זה מכנה fib (3) ו- fib (2). אבל פשוט אמרנו שכבר הייתה לנו קריאה ל- fib (3)! הפונקציה הרקורסיבית החמודה הזו עושה הרבה עבודה חוזרת. עלות הזמן הכוללת מתבררת כ- O (2 n ). זה רע - הרבה יותר גרוע מ- O (N 2 ).
במקום לעבור מ- n רקורסיבי למטה ל- 1, בואו נלך "מלמטה למעלה", מ -1 ל- n. זה מאפשר לנו לדלג על הרקורסיה:
def fib (n): הקודם = 0 הקודם_ הקודם = 1 עבור i בטווח 1 עד n: זרם = הקודם + הקודם_ הקודם הקודם_ הקודם = הקודם הקודם = הנוכחי החזר הנוכחי
הקוד ארוך יותר, אך הוא יעיל בהרבה! עד זמן O (n). כבונוס נוסף עם אלגוריתמים רקורסיביים בלתי גלויים אנו חוסכים מקום. כל אותן שיחות רקורסיביות מצטברות בערימת השיחות, שיושבת בזיכרון וספירה לכיוון עלות החלל שלנו. הפונקציה הרקורסיבית שלנו הייתה בעלות שטח O (n), אבל זה איטרטיבי לוקח שטח O (1).
בפעם הבאה שהמראיין שלך מבקש ממך לשפר את היעילות של הפיתרון שלך, נסה לעבור באסטרטגיות אלה ולראות אם הם עוזרים. עם מספיק תרגול, סביר להניח שתמצא את עצמך קופץ היישר לפיתרון האופטימלי, מדלג על הפיתרון התמים יותר. וזה דבר נהדר. זה לא אומר שאתה הופך להיות מראיין טוב יותר - זה אומר שאתה הופך למהנדס טוב יותר.
