מבחן בכתב (שעה וחצי), 5 שאלות.
1. נותנים לך ארגומנט הבנוי מסוגריים מהסוגים הבאים: (){}[]. צריך לזהות מתי ארגומנט לא חוקי. דוגמה לארגומנט חוקי: ( [ ]{ } ). דוגמה לארגומנט לא חוקי: ({)}
2. נתונה רשימה מקושרת. N חוליות. לכל חוליה יש ערך שלם (int) ואת ה-next שלה ברשימה. צריך להוריד את חוליה X (לדוגמה) מהרשימה. יש לך את הפוינטר ל-head, ל-end ול-X. אסור שזמן הריצה יהיה O(n)
3. קיימת מטריצה בגודל nXm יש לתת אלגוריתם שעבור כל ערך 0 בתא מסוים (לדוגמה: תא [i,j]) כל הערכים באותה שורה (i) ועמודה (j) יאופסו גם הם. זמן ריצה O(n*m)
4. הם מתארים תוכנה ומבקשים לצייר דיאגרמת קלאסים שלה
5. שאלת קוד ב-#C. צריך לתקן טעויות.
את התשובות ניתן לכתוב בפסאודו-קוד. אין דרישה לכתיבה ב-#C
תשובות מוצעות:
שאלה 1:
קלאסית, משתמשים במחסנית.
אפשר לראות רעיון לפתרון כאן:
http://www.java2s.com/Code/Java/Collections-Data-Structure/BracketChecker.htm
שאלה 2:
שאלה נפוצה, הרעיון בה הוא להעתיק לאיבר הנוכחי את התוכן והלינק של האיבר הבא, ובעצם למחוק את האיבר הבא (שאת התוכן שלו העתקת לנוכחי X וכך התוכן אותו ביקש ממך למחוק נמחק). התשובה שכבר נכתבה בדיון נכונה, צריך רק להתייחס למקרה קצה בוא X וא האיבר האחרון (גם צויין בתגובה אחרת).
שאלה 3:
נראה לי הצלחתי לחשוב על פתרון:
קצת קשה להסביר במילים, אבל העקרון כזה – בונים שני מערכי עזר בגודל n ו-m, אחד מיועד לציר X ושני לציר Y.
פעם אחת סורק את המטריצה, שומרים באיזה קואורדינה בX ו-Y יש 0 (נניח 2 מערכים ושומרים באינדקס המתאים) זה יוצא mxn.
לאחר מכן רץ עוד פעם על המטריצה מההתחלה, ומשווה כל תא מול האינדקס המתאים במערכים, לבדוק אם יש 0. אם יש, משווה את התא ל-0.