מיון ראשון מתוך שישה, גם שאר הראיונות היו מקצועיים
שאלות מתוך הראיון
יש לך רגיסטר של 32 ביטים. כתוב פונקציה שמוצאת את המיקום של הביט השלישי שערכו 1. איך תוכל לשפר את זמן הריצה של הפונקציה שכתבת?
תשובות
הוסף תשובה
|
לצפיה בתשובות
נובמבר 2023
מציאת המיקום של הביט השלישי שערכו 1, ברגיסטר של 32 ביטים:
int FindThird1(int reg)
{
int count = 0;
for (int i=0; i<32; i++)
{
count += (reg>>i)&1;
if (count == 3)
return i;
}
return -1;
}
שיפור זמן הריצה של הפונקציה – נחשב באופן חד-פעמי את המערכים הבאים:
• NumOf1s[256] – עבור כל ערך אפשרי ליחידה של 8 ביטים, נרשום את מספר הביטים ביחידה שערכם 1.
• First1[256] – עבור כל ערך אפשרי ליחידה של 8 ביטים, נרשום את מיקום הביט הראשון ביחידה שערכו 1.
• Second1[256] – עבור כל ערך אפשרי ליחידה של 8 ביטים, נרשום את מיקום הביט השני ביחידה שערכו 1.
מיון ראשון מתוך שישה, גם שאר הראיונות היו מקצועיים
שאלות מתוך הראיון
יש לך רגיסטר של 32 ביטים. כתוב פונקציה שמוצאת את המיקום של הביט השלישי שערכו 1. איך תוכל לשפר את זמן הריצה של הפונקציה שכתבת?
תשובות
הוסף תשובה
|
לצפיה בתשובות
מאי 2025
כל פעם עושים מודולו לשתיים, אם התשובה היא 1, הLSB הוא 1. מבצעים חלוקה ב-2 (שיפט ימינה) וממשיכים. סופרים ככה 3 פעמים 1, ושומרים את כמות ההזחות שעשינו, היא האינדקס של הביט 1 השלישי.
כדי לשפר זמן ריצה פשוט שומרים בזיכרון את כל המספרים האפשריים ב32 ביט ואיפה נצא הביט 1 השלישי, ומקבלים זמן ריצה O(1)
ראיון לתפקיד 
