[14 בינואר 2008] [24 תגובות]
לפני שהולכים לראיון עבודה בתחום התיכנות, מומלץ לרענן את הזיכרון בכל מיני נושאים שאיננו מתעסקים איתם ביום יום. מעבר לכך, מראיינים אוהבים לשאול שאלות תיכנות פשוטות ולראות כיצד אתם חושבים והאם תוכלו לתרגם את הרעיונות שלכם לקוד שפועל.
קיבצתי מספר שאלות ופיתרונות (אם ברצונכם לפתור את השאלות - אל תגללו יותר מדיי מכיוון שהפיתרון לכל שאלה נמצא ממש מתחתיה):
שאלה: ישנה רשימה מקושרת הממומשת על ידי המחלקה Link המחזיק שדה Data ושדה Link המצביע על החוליה הבאה בשרשרת.
- כתוב פונקציה בשם Reverse המקבלת רשימה ומחזירה את הרשימה הפוכה בצורה איטרטיבית.
- כתוב את אותה הפונקציה בצורה רקורסיבית.
(בדרך כלל יגידו לכם באיזה שפת תכנות לכתוב את הקוד, ולפעמים בעל פה)
פיתרון: (הקוד ב-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 וכך הלאה לסירוגין.
לפעמים יבקשו שתחשבו בקול רם על שלבי הפיתרון, לפעמים יעזבו אותם לבד כדי שתחשבו על זה ופעמים אחרות ישבו מולכם ופשוט יסתכלו עליכם.
בהצלחה!
חשבתי על שאלה אחרונה ויצאתי עם פתרון אחר.
x = 0X7.
x = x ^ 0X1
ההבדל בין שני מספרים רק בביט הימני. XOR בין שתי אחדות נותן 0 ובין 1 ל-0 נותן אחד. תהנו.
פתרון מאוד נחמד :) כל הכבוד. כשאני רואה שאלות כאלו, להפוך ביטים זה לא הדבר הראשון שעולה לי לראש...
למי שלא עוקב, 7 בבינארית זה 111 ואילו 6 זה 110, סרגיי הציע לשנות רק את הביט האחרון מ-0 ל-1 כל פעם באמצעות האופרטור XOR.
פתרון נוסף לשאלה האחרונה
x = x == 6? 7 : 6;
הפתרון עובד, אבל לא עומד בתנאי: "אסור להשתמש בפקודות מסוג if, while,for אלא רק על ידי ביטוי מתמטי".
אומנם איןן כאן IF מפורש, אך הוא בהחלט קיים.
רוצים עוד שאלות?
טל, אתה יכול להסביר איך התנאי של יניב עובד ואיך אפשר להציב את זה במקומות שונים ? ראיתי אנשים שמתעסקים עם זה אך אף פעם לא הבנתי את זה, אתה יכול להסביר לי את זה בבקשה ?
לא מזמן כתבתי על זה פוסט שלם: משפטי IF קצרים יותר ב-Java.
בקצרה:
x עומד להיות שווה לתוצאה של הביטוי הבא:
x==6 ? 7 : 6
ביטוי זה הוא למעשה משפט IF-ELSE: האם X שווה ל-6? אם כן, התשובה היא 7, אחרת התשובה היא 6.
התשובה היא הערך החדש של X.
כן, אני יודע JAVA פשוט לא ממש הבנתי איך הדברים האלה עובדים .. תודה על ההסבר טל
ועוד שיפור קטן...
int x = 7
הביטוי השני:
x = (1-x%2) +6
ככה גם ממש קל לדבג!
הפתרון של סמי הכי ברור, קצר וקולע !!!!!!
את כל שאר הפתרונות לא הצלחתי להבין בכלל בגלל כמות הפעולות!!
לגבי השאלה של הרשימה מקושרת שצריך לבדוק אם היא מעגלית ע"מ לחסוך במעברים נוספים על הרשימה כפי שיהיה עפ"י הפתרון במקרה והרשימה בעלת מס' אברים זוגי
אפשר פשוט לשמור את ראש הרשימה במשתנה עזר ולהתחיל לרוץ מהאיבר הבא ובכל פעם לשאול האם i שוה למשתנה העזר -אם כן הרי שהרשימה מעגלית וחזרנו לראש הרשימה, אחרת נמשיך לבדוק עד שיענה על התנאי או שיהיה שוה לNull ואז הרשימה לא מעגלית.
לגבי השאלה של הרשימה מקושרת שצריך לבדוק אם היא מעגלית ע"מ לחסוך במעברים נוספים על הרשימה כפי שיהיה עפ"י הפתרון במקרה והרשימה בעלת מס' אברים זוגי
אפשר פשוט לשמור את ראש הרשימה במשתנה עזר ולהתחיל לרוץ מהאיבר הבא ובכל פעם לשאול האם i שוה למשתנה העזר -אם כן הרי שהרשימה מעגלית וחזרנו לראש הרשימה, אחרת נמשיך לבדוק עד שיענה על התנאי או שיהיה שוה לNull ואז הרשימה לא מעגלית.
האם הפתרון שרחל מציעה נכון?
למיטב הבנתי את הצעת הפתרון של רחל, הפתרון אינו נכון.
נניח וקיימת רשימה מקושרת שבה החל מהאיבר החמישי והלאה ישנו מעגל. ראש הרשימה אינו חלק מן הלולאה ולכן שמירתו לא תעזור בזיהוי הלולאה.
היי, תודה על השאלות והפתרונות .
יש איפשהו באתר שלך שאלות נוספות מראיונות ב java ?
שלום, תוכל להסביר את הפתרון הרקורסיבי להפיכת הרשימה המקושרת ?
תודה
סתם ממוחי הקודח:
בראשון: x=7
בשני: x=((x+1) mod 2) + 6
int x = 7;
while(true){
x = 42/x;
System.out.println(x + ",");
}
int x = 7;
while(true){
x = (int) pow((double)(-1),x) + x;
System.out.println(x + ",");
}
אני די חלוד אבל האם זה גם פתרון אפשרי
חברים הפיתרון פשוט 13 פחות X זה הכל !!!!!!!!!!!!!!!!!!!
שירלי יצאה הכי חכמה לדעתי...
בפתרון של היפוך הרשימה צריך לדעתי לאפס את המצביע לצומת הבאה של ראש הרשימה
בסוף הלולאה חסר:
head.next = null