שאלת היגיון...

[fortunes]

ברור שאני יודע

ואל כל כך ברור לי מה ציפית לשמוע למען האמת...

 

[vinney]

וכך אתה נכשל ברעיון עבודה.

אמרתי לך שהפתרון שלי לא נכון, אמרתי לך שהוא לא נכון כי אני מתבסס על הנחה שלא מתקיימת. שאלתי אותך מה ההנחה, ואתה הלכת לחפש בעיות בסיבוכיות. למה?

בפתרון שלי יש הנחה שלא מתקיימת. אם הייתה מתקיימת - הפתרון שלי היה נכון, הוא רץ בסיבוכיות הנכונה. מה לא בסדר?

 

[vinney]

*ראיון

 

[fortunes]

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

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

בפתרון ההתחלתי שהצעתי אגב זאת בעיה שהתגברתי עליה...

 

[vinney]

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

למה?

מה הבעיה בזה? למה זה לא נכון?

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

 

[fortunes]

אני לא מבין את הניסוח...

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

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

 

[vinney]

הבעיה לא "זה בעיה"

כשאני שואל מה לא בסדר אני לא מצפה לשמוע "מה זאת אומרת? זה לא בסדר!", אני מצפה לשמוע למה זה לא בסדר.

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

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

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

 

[fortunes]

קודם כל, תודה רבה על ההשקעה בתשובות.

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

 

[vinney]

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

 

[פרסאוס]

ככה בהצצה מהירה

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

 

[vinney]

הפתרון של הבחור עונה על השאלה במדויק.

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

 

[טרול המתכנן]

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

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