שאלה 1
בהנחה שהקלט תקין, ממש פונקציה char* compress(char* str( שמקבלת קלט מהסוג aaabbabc ומחזירה פלט מהסוג 3a2b1a1b1c
המשך:
ממש את הפונקציה הזו בצורה שהיא inplace כלומר לדרוס את המחרוזת הקיימת ובמקומה למלא את הערכים. הסבר מה הבעיות שאפשר להתקל בהן ואיך תפתור אותן.
המשך:
ממש זאת ב-O(n)
שאלה 2
נתון buffer שהוקצה לו זכרון בגודל 1024x1024. גודל כל בלוק הוא 1024.
ממש את הפונקציות הבאות בO(1): אתחול- void init_alloc(void* buff) שנקראת פעם אחת בתחילת התוכנית. ממש פונקציית void* alloc() שמחזירה כתובת לבלוק פנוי בתוך הבאפר. ממש פונקציית void free(void* ptr) ש"משחררת" את הזכרון ומפנה אותו לשימוש נוסף.
ניתן להניח שהקלט לפונקציית free תקין
תשובות
הוסף תשובה
|
לצפיה בתשובות
פברואר 2021
שאלה 1
השיטה הראשונה היא להקצות גודל מקסימלי של strlen(str)*2 + 1 עבור המחרוזת החדשה. לאחר מכן, לספור את כמות החזרות של תו מסוים ולכתוב את הערך '0' + count ומיד אחרי את התו שעליו חזרנו.
המשך:
הבעיות שיש עם ההשמה inplace הן דריסה של אברים שנצטרך אותם בהמשך וגם שאיננו יודעים כמה זכרון הוקצה למחרוזת (ניתן להניח שהוקצה מספיק)
המשך:
האזורים הבעייתיים הם המופעים הבודדים, למשל abc הם 3 מופעים בודדים. נעבור על כל המחרוזת מעבר ראשון ונספור את כמות המופעים הבודדים. לאחר מכן נעבור באיטרציה נוספת מהסוף להתחלה ונזיז את המופעים הבעייתיים למיקום הנכון עבורם (לא מומש אבל זה הרעיון הכללי)
שאלה 2
נאתחל counter בגודל מספר הבלוקים האפשריים (1024). בהתחלה בכל alloc נבצע counter-- עד שנגיע ל0. ברגע שביצעו free, נשתמש במבנה נתונים בצורה של רשימה מקושרת שתחזיק את הכתובת שהתפנתה. במידה והcounter שונה מ0, נקח את הכתובת הבאה בתור לפי הסדר. במידה והוא שווה 0, נקח את הכתובת הראשונה מהרשימה המקושרת של הכתובות הפנויות.
מאי 2021
אם המחרוזת מורכבת רק ממופעים בודדים, והאלגוריתם הוא Inplace אז האלגוריתם עם ההזזות יעלה n^2 כי עבור כל תו במקום ה i מזיזים n-i איברים מקום אחד קדימה.
ראיון של שעתיים, שתי שאלות בשפת סי.
1) בהנתן מערך תוציא את הסכום המקסימלי של איברים אבל לא כולל איברים סמוכים.
2) כתוב פונקציה המקבלת מצביע ל char ותהפוך כל מילה בו. כלומר: בהנתן המשפט: "hello world" הפונציה מחזירה "olleh dlrow". לא הופכים מקומות המילים אלא רק האןתיות שלהן.
CEVA is a publicly listed semiconductor intellectual property (IP) company, headquartered in Mountain View, California and specializes in DSP processor technology.
ראיון לתפקיד 
