לפני שבועיים התחלתי להרגיש שאני מתגעגעת לפתירת "שאלות ראיונות". מאז שהתחלתי את העבודה החדשה שלי יצא לי להתעסק בהמון נושאים מרתקים וכיפיים, אבל לא בפתירת חידות אלגוריתמיות פשוטות.
להמשיך לקרוא "המספר הגדול הבא"
אז אתמול היה יום מאוד מיוחד, זה היה יום עם תאריך פלינדרומי – 02.02.2020 (ותודה ללא מדויק שבזכותו שמתי לב.
ואיזו דרך טובה* יותר יש לחגוג יום פלינדרומי מאשר עם אלגוריתם שבודק אם מילה היא פלינדרום?
*אלא אם כן אתן אייבופוביות כמובן. אם כן, אני מתנצלת מראש, ואולי כדאי שתצאו מהפוסט עכשיו 🤷♀️
השאלה הבאה לקוחה ממאגר השאלות של Google Code Jam, ואתן יכולות לנסות לפתור אותה כאן.
השאלה הולכת ככה –
שריפה פרצה בסנאט האמריקאי (אבוי!) וצריך לפנות משם את כל הסנטורים. במקום נמצאים סנטורים מ-N מפלגות שמסומנות באותיות A-N ובכל שלב של הפינוי אפשר להוציא עד שני סנטורים.
במהלך הפינוי הסנטורים עדיין יכולים להצביע על חוקים (כל כך שמחה שאני מתכנתת ולא פוליטיקאית!) ולכן צריך לוודא שבכל שלב של הפינוי אין אף מפלגה שחבריה מהווים יותר מ-50% מהקולות שנשארו בסנאט הבוער.
המטרה היא למצוא תוכנית פינוי שמקיימת את התנאים ומובטח לי שקיימת תוכנית כזו.
השנה ניהלתי את תהליך חיפוש העבודה הרציני הראשון של חיי.
העבודה הקודמת שלי הייתה עבודת הפיתוח הראשונה שלי, נכנסתי אליה כשהייתי סטודנטית, והחיפוש הנוכחי בעצם היתה הפעם הראשונה שחיפשתי עבודה כמפתחת בעלת ניסיון.
אם שוטטתן בפייסבוק לאחרונה כנראה נתקלתן בהתייחסויות לתרגיל (2+2)2÷8 (ואם לא, כדאי לקרוא את ההסבר של לא מדויק).
בקצרה, מדובר בתרגיל חשבוני שיש לו שני פתרונות אפשריים שנובעים מקונבנציות שונות של כתיבת מתמטית. אפשר להתייחס אליו כך –
8÷2*(2+2) = 8÷2*4 = 4*4 = 16
ואפשר להתייחס אליו כך –
8÷2*(2+2) = 8/(2*(2+2)) = 8/(2*4) = 8/8 = 1
אז לפני שמתחילה מלחמת עולם בסגנון ה-little endians מול ה-big endians, חשבתי לנסות ליצור אלגוריתם שיוכל לשרת את שני המחנות.
הרי, אף אחד לא מתווכח על החישוב עצמו, אלא רק על קונבנציית הכתיבה – אז אני הולכת לבנות מחשבון קסום שאפשר יהיה לקנפג, ויספק לכל משתמשת את התשובה שהיא מחפשת.
בחלק א' של פוסט זה הסברתי שאני רוצה לבנות מחשבון שיוכל לקבל קונפיגורציה של קונבנציית כתיבה, ולפתור תרגילים בהתאם.
הרעיון הגיע מהתרגיל (2+2)2÷8 שהוא ביטוי שיש לו שתי תוצאות שונות בעבור שתי קונבנציות כתיבה שונות.
בחלק הראשון של הפוסט בניתי את המחשבון שלי, ובחלק הנוכחי אני רוצה להוסיף לו קונפיגורציות.
נתון מערך של מספרים שונים זה מזה, והמשימה היא למצוא את האורך של הרצף הארוך ביותר שניתן ליצור מהמספרים במערך.
לדוגמא –
A = [2, 5, 3, 10, 9, 4] longest_subsequence_length(A) = 4 ([2,3,4,5])
להמשיך לקרוא "הרצף הארוך ביותר"פוסט הביטים שלי גרם לי לחשוב שאני לא מספיק עוצרת לבדוק כל מיני דרכים יצירתיות לפתור שאלות.
בדרך כלל אני מנסה להגיע לסיבוכיות הזמן/מקום האופטימלית, אבל תכל'ס זה יכול להיות ממש כיף לפעמים פשוט להתפרע, לצאת מהקופסא, ולחפש דרכים שהם אולי לא יעילות, אבל בהחלט מעניינות לעשות דברים.
להמשיך לקרוא "חזקות של 2"השבוע הנושא של bit manipulation עלה באחת מקבוצות הפייסבוק שאני חברה בהן כנושא שיכול להיות מבלבל ומאתגר בראיונות. הרעיון בדרך כלל בשאלות ביטים הוא לפתור משימה שהייתה יכולה להיות סופר פשוטה באמצעים רגילים, בלי להשתמש בפעולות מתמטיות, מחרוזות או כל אמצעי נוח אחר.
להמשיך לקרוא "OR XOR AND SHIFT"לפני שבועיים העליתי פוסט עם אלגוריתם שמוודא שלוח סודוקו הוא תקין (אתן יכולות לקרוא אותו פה) ולפני כמה ימים הקוראת העירנית @rinaarts הפנתה את תשומת לבי לעובדה שבפונקציה הבסיסית שמוודאה את לוח הסודוקו שלי השתמשתי באלגוריתם בזבזני בסיבוכיות (O(N2, ואף הציעה פתרון יעיל יותר ב-(O(N.
אז קודם כל, תודה לרינה 🙂
שנית, לפני שאגיע לפתרון החלופי שהיא הציעה, אני חייבת לשאול איך בעצם קרה המצב הזה?
אני ממש לא מתיימרת למצוא את הפתרון הטוב ביותר לכל שאלה, אבל הפעם אכן היה מדובר בטעות בולטת מאוד, איך פספסתי אותה?
