הכנה לראיונות עבודה מצריכה מימוש של BFS/DFS ?

[Be1n]

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

אני יודע לכתוב את הפאסודו-קוד שלהם, אך האם אני צריך לדעת לממש אותם בקוד ?

ואם כן, האם יש מימוש מומלץ שאתם מכירים ?

מצאתי מקור שנראה לי בסדר, אבל אני לא בטוח.

BFS Graph Algorithm(With code in C, C++, Java and Python)

Breadth first traversal or Breadth first Search is a recursive algorithm for searching all the vertices of a graph or tree data structure. In this tutorial, you will understand the working of bfs algorithm with codes in C, C++, Java, and Python.

www.programiz.com

המימוש שם נראה לכם תקין ?


תודה !

 

[user32]

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

 

[חזי2003]

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

 

[Nuke1985]

בכל מקרה, אם אתה שואל אם בראיון תצטרך לממש אז התשובה שרוב הסיכויים שלא.

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

 

[Be1n]

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

קיים הבדל בין לדעת את הפסאודו קוד לבין לממש את האלגוריתם בשפה כלשהי.
יכול לנבוע מהרבה סיבות, כגון: מבני הנתונים הספציפים לשפה (תור/מחסנית וכדומה).

בנוסף, עדיף לעשות זאת פעם ראשונה שלא מול מראיין וכך להגיע משופשף יותר בראיון עצמו, לא ?

 

[Nuke1985]

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

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

 

[Be1n]

אני בוגר טרי..

פשוט היצע העבודות לכאלה כרגע שואף לאפס.

לזכרוני, לא מימשנו אותם בקוד, אלא יותר דיברנו עליהם בפסאודו קוד..

 

[choo]

אני בוגר טרי..

פשוט היצע העבודות לכאלה כרגע שואף לאפס.

לזכרוני, לא מימשנו אותם בקוד, אלא יותר דיברנו עליהם בפסאודו קוד..

אם ככה - כדאי שתתחיל לטחון קוד בבית. חפש את הספר cracking the coding interview והתחל לענות על שאלות משם בצורה מפורטת בכתב (אל תסתפק בלהגיע למצב של "אני יודע מה הכיוון" - פתור עד הסוף, כולל מקרי קצה וכולל לבדוק את עצמך). במקביל, תרגל כתיבת קוד - במרבית ראיונות העבודה ידרשו ממך לכתוב קוד ממש. יש מקומות שידרשו שהוא גם יעבור קומפילציה ויעבוד על מגוון קלטים. גם אם יבקשו ממך לענות על זה ברמה של פסאודו-קוד, לכל מראיין יש הגדרה אחרת של מה זה "פסאודו קוד" - ואם תפגין יכולת להסביר פתרונות בניפנופי ידיים אבל תיכשל בכתיבת קוד - לא תצליח לעבור ראיונות עבודה. דווקא משום שיש מעט מאוד משרות פתוחות - רצוי שתגיע לכל ראיון כשאתה משופשף בפתרון שאלות אלגוריתמיות ובכתיבת קוד - כדי שלא תפספס הזדמנויות רק בגלל שמוסד הלימודים שלך "חיפף" בתחום הזה.

 

[Darklos]

אם ככה - כדאי שתתחיל לטחון קוד בבית. חפש את הספר cracking the coding interview והתחל לענות על שאלות משם בצורה מפורטת בכתב (אל תסתפק בלהגיע למצב של "אני יודע מה הכיוון" - פתור עד הסוף, כולל מקרי קצה וכולל לבדוק את עצמך). במקביל, תרגל כתיבת קוד - במרבית ראיונות העבודה ידרשו ממך לכתוב קוד ממש. יש מקומות שידרשו שהוא גם יעבור קומפילציה ויעבוד על מגוון קלטים. גם אם יבקשו ממך לענות על זה ברמה של פסאודו-קוד, לכל מראיין יש הגדרה אחרת של מה זה "פסאודו קוד" - ואם תפגין יכולת להסביר פתרונות בניפנופי ידיים אבל תיכשל בכתיבת קוד - לא תצליח לעבור ראיונות עבודה. דווקא משום שיש מעט מאוד משרות פתוחות - רצוי שתגיע לכל ראיון כשאתה משופשף בפתרון שאלות אלגוריתמיות ובכתיבת קוד - כדי שלא תפספס הזדמנויות רק בגלל שמוסד הלימודים שלך "חיפף" בתחום הזה.

מחזק ומוסיף - תתאמן בכמה דרכים:
- על IDE עם Intellisense
- על Notepad בלי Intellisense
- על דף ועט

 

[מחפשת עבודה17]

אם ככה - כדאי שתתחיל לטחון קוד בבית. חפש את הספר cracking the coding interview והתחל לענות על שאלות משם בצורה מפורטת בכתב (אל תסתפק בלהגיע למצב של "אני יודע מה הכיוון" - פתור עד הסוף, כולל מקרי קצה וכולל לבדוק את עצמך). במקביל, תרגל כתיבת קוד - במרבית ראיונות העבודה ידרשו ממך לכתוב קוד ממש. יש מקומות שידרשו שהוא גם יעבור קומפילציה ויעבוד על מגוון קלטים. גם אם יבקשו ממך לענות על זה ברמה של פסאודו-קוד, לכל מראיין יש הגדרה אחרת של מה זה "פסאודו קוד" - ואם תפגין יכולת להסביר פתרונות בניפנופי ידיים אבל תיכשל בכתיבת קוד - לא תצליח לעבור ראיונות עבודה. דווקא משום שיש מעט מאוד משרות פתוחות - רצוי שתגיע לכל ראיון כשאתה משופשף בפתרון שאלות אלגוריתמיות ובכתיבת קוד - כדי שלא תפספס הזדמנויות רק בגלל שמוסד הלימודים שלך "חיפף" בתחום הזה.

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

 

[מחפשת עבודה17]

מניסיון של מישהי שהתראיינה עד לפני לא מזמן - כן, תשב ותממש.

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

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

ואני ממליצה לתרגל באתרים כמו Leetcode או Codility שגם בודקים את התשובה שאתה מגיש להם כדי להבין איך הן מחפשות מקרי קצה וכך ללמוד איך לבדוק את המימוש שלך.

 

[Be1n]

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

את מדברת על ההתחשבות בOverflow ? (מכיר את זה אם כן)

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

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

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

ואני ממליצה לתרגל באתרים כמו Leetcode או Codility שגם בודקים את התשובה שאתה מגיש להם כדי להבין איך הן מחפשות מקרי קצה וכך ללמוד איך לבדוק את המימוש שלך.

אני עובר עליהם לעיתים רחוקות, אני מעדיף לעבור על חידות ושאלות מאתרים כמו glassdoor שמועמדים מעלים..
אשתדל לעבור עליהם יותר.

תודה רבה !!!

 

[מחפשת עבודה17]

לגבי DFS על עץ הרעיון הוא לשים את האובייקט הנוכחי (אם הוא קיים כמובן ולא ריק - מקרה קצה) בסטאק, וללכת שמאלה כמה שאתה יכול עד שאתה יכול עד שאתה מגיע לערך שהוא Null - רק אז אתה מוציא את האובייקט העליון מהסטאק, פועל עליו, ואז פונה לילד הימני שלו ומתחיל את התהליך מההתחלה (כלומר הולך שמאלה כמה שאתה יכול וכו'). הייתי ממליצה לך בשיא הרצינות לתרגל את זה ולחשוב על מקרי קצה וכו'.

 

[Darklos]

BFS זה לולאה פשוטה ותור.
DFS זה רקורסיה פשוטה.
והטריק היחיד בשניהם זה לבדוק שלא עברת כבר על האיבר (כדי לא להתקע במעגל), וגם הוא לא רלוונטי אם נתון עץ בלי מעגלים.
תלמד לממש אותם, חבל ליפול דוקא על זה.

ואל תפסיק ב-BFS/DFS, תלמד לממש גם:
- אלגוריתם מיון כלשהו, למשל Merge Sort
- ערימת מינימום\מקסימום
- טבלת גיבוב (Hash Map) - כתבתי על זה פוסט אתה מוזמן לקרוא: איך לבנות טבלת גיבוב

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

 

[Be1n]

BFS זה לולאה פשוטה ותור.
DFS זה רקורסיה פשוטה.
והטריק היחיד בשניהם זה לבדוק שלא עברת כבר על האיבר (כדי לא להתקע במעגל), וגם הוא לא רלוונטי אם נתון עץ בלי מעגלים.
תלמד לממש אותם, חבל ליפול דוקא על זה.

ואל תפסיק ב-BFS/DFS, תלמד לממש גם:
- אלגוריתם מיון כלשהו, למשל Merge Sort
- ערימת מינימום\מקסימום
- טבלת גיבוב (Hash Map) - כתבתי על זה פוסט אתה מוזמן לקרוא: איך לבנות טבלת גיבוב

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

אלגוריתם מיון - אני מכיר 2 מימושים של מיון מהיר (אחד מcracking the code והשני בעזרת runner - מעדיף את השני)
שוקל אולי לעבור גם על מיון מיזוג.
ערמת מינימום עברתי ומימשתי לפני חודש בערך.
בנוסף עברתי גם על:
חיפוש בינארי (עם מציאת האינדקס הכי קיצוני - מבעיית "מצא את מספר המופעים של האלמנט X")
בעיית הבחירה (מצא את האיבר הi בגודלו)
מציאת איבר רוב
חידות למיניהן
ועוד..

תודה על הקישור

 

[Nuke1985]

BFS זה לולאה פשוטה ותור.
DFS זה רקורסיה פשוטה.

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