ראיון ראשון. 2 אנשים מראיינים. שואלים על התפקיד הקודם ואז שאלות טכניות.
שאלות מתוך הראיון
1. כתוב פונק אשר מוחקת איבר ברשימה מקושרת דו כיוונית כאשר בקלט הפונק' נתון מצביע לאיבר אותו רוצים למחוק. (אחכ מבקשים להתייחס למקרי קצה: כאשר ישנו איבר אחד בלבד ברשימה, שאין איברים כלל וכו')
2. תאר אלגוריתם של הפונק' המקבלת 2 סטרינגים ובודקת האם אחת היא פרמוטציה של השניה. על סיבוכיות הריצה להיות (O(n.
3. מימוש critical section: ישנם 2 מעבדים עם זיכרון משותף. 2 המעבדים רוצים לקרוא/לעתוב לאותו קטע זיכרון. כיצד תגן עליו מפני התנגשות בין 2 המעבדים.
תשובות
הוסף תשובה
|
לצפיה בתשובות
ספטמבר 2016
1. טריוואלי
2. מאתחלים מערך בגודל 256 (בגלל שיש 256 תווים בקוד ה ASCI) ובכל תא שמים bool false. לאחר מכן עוברים על המחרוזת הראשונה ועבור על תו במחרוזת נלך לאינדקס שמייצג אותו במערך ונשנה את התא לTRUE. לאחר מכן נעבור באותו האופן על המחרוזת השניה, ואם נתקלנו ב false זה אומר שהוא לא פרמוטציה.
3. נקצה 2 ביטים בזיכרון.
ביט1- רק למעבד 1 יש גישה אליו.
ביט2 - רק למעבד 2 יש גישה אליו.
כאשר מעבד 1 רוצה לגשת לזיכרון המשותף הוא מעלה את ביט1 ל"1" ואז בודק אם ביט2 שווה "1", אם לא אז הוא רשאי לגשת לזיכרון. אם כן אז הוא מוריד את ביט1 ל"0" והוא מחכה עד שביט2 יהיה שווה "0".
פברואר 2017
1. טריוויאלי, אבל בכל זאת:
מקבלים מצביע p לאיבר X. ממנו מגיעים לX-1 (מצביע קודם-ל ברשימה דו-כיוונית). מעדכנים בX-1 את המצביע הבא ברשימה לX+1 .
עוברים לX+1. מעדכנים את המצביע הקודם-ל ל X-1.
עכשיו משחררים את הזיכרון של X בעזרת p.
ניתן להבחין במקרי קצה לפי הערך של המצביעים הבא ברשימה או קודם ברשימה (אם הם NULL ... ).
2) יש טעות בפתרון שלמעלה. הוא לא יעבוד אם יש תווים שחוזרים על עצמם.
לדוגמה, המחרוזות ABC ו ABB יסווגו כתמורה אחת של השנייה...
התיקון: מערך התווים יכיל במקום בוליאנים, מונה של מספר המופעים של התו הנוכחי.
במעבר על המחרוזת הראשונה, לכל תו, נגדיל באחד את המונה שלו.
בהתחלה כל הכניסות במערך יהיו מאופסות.
במעבר על המחרוזת השנייה, לכל תו, נקטין באחד את המונה שלו.
אם אחרי שסיימנו את המעבר על המחרוזת השנייה, כל האיברים במערך שווים לאפס, המחרוזות הם תמורה אחת של השנייה.
דצמבר 2017
לגבי סעיף 2, יש טעות קטנה בפתרון שמעליי, ע"פ הפתרון שלו יש לעבור על כל אות במערך בלולאה ולבדוק כמה אותיות זהות לה יש, אבל העלות של זה היא o(n^2) ולכן הוא לא יקבל את מה שהם רצו. הם התכוונו לעשות זאת על ידי NOT כך שאם לדוגמה אות כלשהי מופיע 3 פעמים והמערך שלנו מאותחל לאפס, נקבל 1 בסוף, אנחנו אמורים לקבל חזרה מערך של אפסים. אם לא קיבלנו זאת, אז יש לנו טעות וזו לא פרמוטציה