ראיון עבודה שאורך כשעה וחצי ומכיל כמה שאלות תכנותיות וכמה חידות.
שאלות מתוך הראיון
1. נתון משתנה בעל 8 סיביות, יש לכתוב פונקציה בשפת סי
שתקבל את המשתנה ותחזיר את ההשתקפות של אותו משתנה. דוגמא:
עבור קלט של:
001011001
הפלט יהיה:
100110100
תשובות
הוסף תשובה
|
לצפיה בתשובות
פברואר 2021
בעזרת לולאה לאפס כל פעם 7 ביטים ולהשאיר רק 1, כאשר אנחנו כבר יודעים מה ערכו- ליצור משתנה חדש.
מרץ 2021
לפי הקלט והפלט זה מימוש של reverse string
אפשר לפתור על ידי מעבר יחיד , מאתחלים מצביע לתחילת המערך ולסופו ובכל איטרציה מחליפים בין הערכים שהשתיים מצביעים עליהם , לאחר מכן מקדמים את המצביע של תחילת המערך ומקטינים את המצביע של סוף המערך. האיטרציות יתבצעו כל עוד מתקיים שהמצביע להתחלה קטן מהמצביע לסוף
שאלה 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 איברים מקום אחד קדימה.
CEVA is a publicly listed semiconductor intellectual property (IP) company, headquartered in Mountain View, California and specializes in DSP processor technology.