שאלות מראיונות עבודה

[14 בינואר 2008] [24 תגובות]

לפני שהולכים לראיון עבודה בתחום התיכנות, מומלץ לרענן את הזיכרון בכל מיני נושאים שאיננו מתעסקים איתם ביום יום. מעבר לכך, מראיינים אוהבים לשאול שאלות תיכנות פשוטות ולראות כיצד אתם חושבים והאם תוכלו לתרגם את הרעיונות שלכם לקוד שפועל.

קיבצתי מספר שאלות ופיתרונות (אם ברצונכם לפתור את השאלות - אל תגללו יותר מדיי מכיוון שהפיתרון לכל שאלה נמצא ממש מתחתיה):


שאלה: ישנה רשימה מקושרת הממומשת על ידי המחלקה Link המחזיק שדה Data ושדה Link המצביע על החוליה הבאה בשרשרת.

  1. כתוב פונקציה בשם Reverse המקבלת רשימה ומחזירה את הרשימה הפוכה בצורה איטרטיבית.
  2. כתוב את אותה הפונקציה בצורה רקורסיבית.

(בדרך כלל יגידו לכם באיזה שפת תכנות לכתוב את הקוד, ולפעמים בעל פה)

פיתרון: (הקוד ב-Java)

// Iterative
link reverse(link head){
        link first = null;
        link i = head;
        link next;
        while(i!=null){
                next = i.next;
                i.next = first;
                first = i;
                i = next;
        {
        return first;
}

//Recursive
link reverse(link head){
        //empty list ? return empty list
        //one item list ? return that link(one link needs no reversing)
        if (head==null || head.next==null){
                return head;
        }

        //remember the second link
        link second = head.next;

        // set the head to the end of the new list
        head.next = null;

        //reverse the link from the second position
        link revlist = reverse(second);

        //add the head to the end of this list and return it
        second.next = head;
        return revlist;
}


שאלה: נתונה רשימה מקושרת, כיצד תבדוק האם יש בה מעגל ? n הוא מספר החוליות, זמן ריצת האלגוריתם צריך להיות חסום על ידי (O(n.

פיתרון: יש לרוץ על הרשימה בעזרת שני מצביעים. הראשון יבצע קפיצות רגילות של חוליה כל פעם(i=i.next) ואילו השני יבצע קפיצות כפולות(j=j.next.next). אם אחד המצביעים מצביע על חוליה null אזי הגענו לסוף הרשימה ולכן אין מעגל. אם שני המצביעים נמצאים על אותה החוליה(i=j) סימן שיש מעגל(מכיוון ש-i זז לאט יותר מ-j ולכן ללא מעגל לא יוכל לעקוף אותו).


שאלה: נתון קוד(בהמשך). יש להשלים את סימני השאלה כך שעל המסך יודפס:

6,7,6,7,6,7,6,7,6,7,6,7,6,7...

אסור להשתמש בפקודות מסוג if, while,for אלא רק על ידי ביטוי מתמטי. הקוד:

int x = ???;

while(true){

        x = ???;

        System.out.println(x + ",");

 }

פיתרון: בסימני השאלה הראשונים נכתוב x = 7 ובסימני השאלה השניים נכתוב x = 13-i - לכן בפעם הראשונה היה x שווה ל-6 ובפעם השנייה שווה ל-7 וכך הלאה לסירוגין.


לפעמים יבקשו שתחשבו בקול רם על שלבי הפיתרון, לפעמים יעזבו אותם לבד כדי שתחשבו על זה ופעמים אחרות ישבו מולכם ופשוט יסתכלו עליכם.

בהצלחה!

אם אהבת את הפוסט, אני שולח מדי פעם למייל עוד פוסטים מעניינים שלא תמיד מגיעים להתפרסם באתר. אתה מוזמן להצטרף לרשימה:
(אני שונא ספאם. אני מבטיח לעולם לא לשלוח משהו לא מעניין)

24 תגובות

  1. סרגיי | 8/10/2008 3:38:54 AM

    חשבתי על שאלה אחרונה ויצאתי עם פתרון אחר.

    x = 0X7.

    x = x ^ 0X1

    ההבדל בין שני מספרים רק בביט הימני. XOR בין שתי אחדות נותן 0 ובין 1 ל-0 נותן אחד. תהנו.

  2. טל | 8/10/2008 10:35:51 AM

    פתרון מאוד נחמד :) כל הכבוד. כשאני רואה שאלות כאלו, להפוך ביטים זה לא הדבר הראשון שעולה לי לראש...

    למי שלא עוקב, 7 בבינארית זה 111 ואילו 6 זה 110, סרגיי הציע לשנות רק את הביט האחרון מ-0 ל-1 כל פעם באמצעות האופרטור XOR.

  3. יניב | 12/8/2008 3:30:07 AM

    פתרון נוסף לשאלה האחרונה

     x = x == 6? 7 : 6;

  4. טל | 12/8/2008 12:30:59 PM

    הפתרון עובד, אבל לא עומד בתנאי: "אסור להשתמש בפקודות מסוג if, while,for אלא רק על ידי ביטוי מתמטי".

    אומנם איןן כאן IF מפורש, אך הוא בהחלט קיים.

    רוצים עוד שאלות?

  5. אלי | 12/14/2008 11:20:13 AM
    טל, אתה יכול להסביר איך התנאי של יניב עובד ואיך אפשר להציב את זה במקומות שונים ? ראיתי אנשים שמתעסקים עם זה אך אף פעם לא הבנתי את זה, אתה יכול להסביר לי את זה בבקשה ?
  6. טל | 12/14/2008 3:12:06 PM

    לא מזמן כתבתי על זה פוסט שלם: משפטי IF קצרים יותר ב-Java.

    בקצרה:

    x עומד להיות שווה לתוצאה של הביטוי הבא:

    x==6 ? 7 : 6

    ביטוי זה הוא למעשה משפט IF-ELSE: האם X שווה ל-6? אם כן, התשובה היא 7, אחרת התשובה היא 6.

    התשובה היא הערך החדש של X.

  7. אלי | 12/15/2008 10:47:55 AM

    כן, אני יודע JAVA פשוט לא ממש הבנתי איך הדברים האלה עובדים .. תודה על ההסבר טל

  8. אושרי כהן | 3/22/2010 3:27:34 AM
    פתרון נוסף שחבר שלי פתר לשאלה האחרונה
    int x = 7;
    while(true
    }
         x = x - ( (x%2) * 2 ) + 1
    בניגוד לתשובה של XOR הפעם זו תשובה שונה שגם ניתן לישם אותה בקלות על כל שני מספרים
  9. סמי וסומו | 4/19/2010 1:27:52 AM

    ועוד שיפור קטן...

    int x = 7

    הביטוי השני:

    x = (1-x%2) +6

    ככה גם ממש קל לדבג!

     

  10. רוני | 5/17/2010 10:53:03 AM

    הפתרון של סמי הכי ברור, קצר וקולע !!!!!!

     את כל שאר הפתרונות לא הצלחתי להבין בכלל בגלל כמות הפעולות!!

     

  11. רחל | 4/4/2011 9:39:50 AM

    לגבי השאלה של הרשימה מקושרת שצריך לבדוק אם היא מעגלית ע"מ לחסוך במעברים נוספים על הרשימה כפי שיהיה עפ"י הפתרון במקרה והרשימה בעלת מס' אברים זוגי 

    אפשר פשוט לשמור את ראש הרשימה במשתנה עזר ולהתחיל לרוץ מהאיבר הבא ובכל פעם לשאול האם i שוה למשתנה העזר -אם כן הרי שהרשימה מעגלית וחזרנו לראש הרשימה, אחרת נמשיך לבדוק עד שיענה על התנאי או שיהיה שוה לNull ואז הרשימה לא מעגלית.

  12. רחל | 4/4/2011 9:39:52 AM

    לגבי השאלה של הרשימה מקושרת שצריך לבדוק אם היא מעגלית ע"מ לחסוך במעברים נוספים על הרשימה כפי שיהיה עפ"י הפתרון במקרה והרשימה בעלת מס' אברים זוגי 

    אפשר פשוט לשמור את ראש הרשימה במשתנה עזר ולהתחיל לרוץ מהאיבר הבא ובכל פעם לשאול האם i שוה למשתנה העזר -אם כן הרי שהרשימה מעגלית וחזרנו לראש הרשימה, אחרת נמשיך לבדוק עד שיענה על התנאי או שיהיה שוה לNull ואז הרשימה לא מעגלית.

  13. יעקב | 4/18/2011 3:30:39 AM
    האם הפתרון שרחל מציעה נכון?
  14. טל | 4/18/2011 4:48:00 PM

    למיטב הבנתי את הצעת הפתרון של רחל, הפתרון אינו נכון.

    נניח וקיימת רשימה מקושרת שבה החל מהאיבר החמישי  והלאה ישנו מעגל. ראש הרשימה אינו חלק מן הלולאה ולכן שמירתו לא תעזור בזיהוי הלולאה.

  15. מחפשת עבודה | 4/25/2011 7:55:03 AM

    היי, תודה על השאלות והפתרונות .

    יש איפשהו באתר שלך שאלות נוספות מראיונות ב java ? 

  16. אביב | 4/25/2011 8:35:37 AM

    שלום, תוכל להסביר את הפתרון הרקורסיבי להפיכת הרשימה המקושרת ?

    תודה 

  17. משה | 7/2/2011 2:44:58 AM

    סתם ממוחי הקודח:

    בראשון: x=7

    בשני: x=((x+1) mod 2) + 6 

  18. שירלי | 10/5/2011 3:00:43 PM

    int x = 7;

    while(true){

            x = 42/x;

            System.out.println(x + ",");

     }

  19. נתי | 4/22/2012 3:42:12 AM

    int x = 7;

    while(true){

            x = (int) pow((double)(-1),x) + x;

            System.out.println(x + ",");

     }

  20. d | 7/23/2012 4:28:11 AM
    int x = 7;

    while(true){

           x = 7 % x + 6;
           System.out.print(x + ",");
    }
  21. יאיא | 1/30/2014 3:52:27 AM
    אני די חלוד  אבל האם זה גם פתרון אפשרי 

    int x = 7;

    while(true){

            x = 13%x;
            System.out.print(x + ",");
     }

  22. אריאל | 2/5/2014 2:48:05 AM

    חברים הפיתרון פשוט 13 פחות X זה הכל !!!!!!!!!!!!!!!!!!!

    int x = 7;

    while(true){

    x = 13-x;
    System.out.print(x + ",");
    }

     

  23. אריאל | 3/9/2014 12:11:44 PM
    שירלי יצאה הכי חכמה לדעתי...
  24. ישראל | 9/19/2014 9:10:01 AM

    בפתרון של היפוך הרשימה צריך לדעתי לאפס את המצביע לצומת הבאה של ראש הרשימה 

    בסוף הלולאה  חסר:

    head.next = null 

התגובות נעולות