שאלה בג'אווה

[neogod]

היה לי מבחן אתמול ואחת השאלות הייתה :

כתוב שיטה המקבלת רשימה מקושרת ומוסיפה אותה לרשימה מקושרת אחרת .

הרשימה צריכה להתווסף אחרי הרשימה הכי קצרההאחרונה של של איברים זהים עוקבים!!!

דוגמה :

_head->1->2->2

list->4->4->4

אז הפלט אמור להיות :

1->4->4->4->2->2

עכשיו כל זה אמור להעשות במעבר אחד על הרשימה הרשימה המקורית !!! ולא היה לי מושג איך בכלל לגשת לזהההההההההההה!!!!!!!

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

[exercise]

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

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

[neogod]

זה בערך היה הכיוון שלי, אבל לא הצלחתי לממש את זה במבחן!!!

וכן אי אפשר להעתיק את הרשימה למערך או כל דבר דומה !

והשאלה היא ממבחן של מבוא למדמח ושפת JAVA מהאו"פ והיא שווה 30 נקודות !

[exercise]

ואחרי זה מדברים על הבדלי הרמה בין מכללות / אוניברסיטאות לאוניברסיטאות מובילות...

בכל מקרה, מה הבעיה אם יש רעיון לממש אותו (בעיה באלגוריתם או בסינטקס של השפה?)

[neogod]

כנראה סתם לחץ של זמן עצבים וחוסר הרגל לכתיבת תוכניות על דף נייר ולא במחשב

הבעיה הייתה באלגוריתם,אתה מוזמן לתת לי כיוון אם בא לך

[exercise]

משהו כזה ?

cnt = MAX_INT;

ptr = orig_start;

insert_ptr == null;

tmp = 1;

while(ptr->next)

{

if (ptr->data == ptr->next->data)

{

tmp++;

} else {

if (tmp < cnt)

{

cnt = tmp;

insert_ptr = ptr->next;

}

tmp = 0;

}

ptr = ptr->next;

}

if (insert_ptr == null)

insert_ptr = ptr;

זה ימצא לך לאיפה להכניס, אחרי זה פשוט צריך להכניס.

[m1ke]

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

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

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

אך אם המספר אינו שווה, יש לבדוק אם המונה קטן מה-min הנוכחי -

א) אם לא, אז לאפס מונה ולהמשיך לרוץ הלאה.

ב) אם כן - לשמור את המצביע הנוכחי כנק' start,לשמור את המספר במונה כהמינימום ב-min לאפס מונה ולהמשיך לרוץ.

לאחר סוף הלולאה יש לבצע בדיקה נוספת כמו של סעיף ב' כדי לבדוק את המצב שהתת רשימה הכי קצרה לא היתה בסוף הרשימה המקורית.

כרגע אמור להיות לך בstart את המצביע לסוף הרשימה הקצרה ביותר. כל מה שנשאר לך לעשות הוא לרוץ על הרשימה החדשה, לשים ב-next של האלמנט הסופי שלו את ה-next של start ולבסוף start.next = list.

אני חייב להוסיף שהשאלה במועד א' היתה רצחנית יותר.

	public void addSubList(IntList list)
	{
		IntNode start = null;
		IntNode current = _head;
		int min = 0;				//could use Integer.MAX_VALUE 
		int count = 1;

		while(current.getNext() != null)	//iterate through list
		{
			if(current.getValue() == current.getNext().getValue())
				count++;
			else{
				if(min == 0 || count < min){
					start = current;
					min = count;
				}
				count = 1;
			}
			current = current.getNext();
		}

		if(min == 0 || count < min)		//must check (if start == null is not enough)
			start = current;

		IntNode i = list._head;			//iterate through 2nd list
		for(;i.getNext()!= null; i=i.getNext());
		i.setNext(start.getNext());		//set last to start.next
		start.setNext(list._head);		//set start.next to list.head
	}

[neogod]

אני לא מבין איך לא עשיתי את השאלה הזאת

בכל מקרה תודה על התשובות ...

ד"א מה ביקשו במועד א' בשתי השאלות הראשונות ?

[m1ke]

השאלה הראשונה היתה עם רקורסיה, היה צריך להחזיר את אורך המחרוזת הכי ארוכה המורכבת מתווים של מחרוזת שניה.

למשל אם מחרוזת אחת היא "אבגדהאבגד" והמחרוזת השניה היא "אבגד" אז יוחזר 4. אם המחרוזת היא "אדהאבהא" והמחרוזת השניה היא "אבגד" אז יוחזר 2 ואם המחרוזת היא "אבגד" והמחרוזת השניה היא "הוזח" אז יוחזר 0.

שאלה ממש קלילה לרקורסיה.

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

למשל א>ב>ב>ג יהפוך להיות א>ג

א>א>א>א יהפוך להיות NULL

א>ב>ג>ד יהפוך להיות ב>ג>ד

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

[neogod]

קיבלת כבר את הציון של הבחינה ?

[m1ke]

95 :jump: (ציון סופי 96)

[neogod]

חח יפה יפה....

איך מחושב הציון הסופי עם הממנים ? אם מתוך 30 נק' של הממנים יש לי 25 בערך, מה אינ מבטל וכיצד?

[m1ke]

תוריד את כל הציוני ממ"נים הנמוכים מהציון של המבחן (רק תזכור להשאיר לפחות 20 נק')

ואז תחשב את סכום ציוני הממ"נים חלקי סכום הנק הכולל שלהם.

מה שתקבל זה ממוצע הממ"נים. עכשיו תכפיל את המספר הזה באחוז שלו מהציון הסופי. כלומר אם הגשת ממ"נים ב25 נק' תכפיל ב0.25, אם הגשת ב30 אז ב0.3.

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

למשל ממוצע הממ"נים שלך במשקל של 20 נק' הוא 100 כלומר 100 * 0.2 = 20

והציון שלך בבחינת גמר היה 90, כלומר 90 * 0.8 = 72

72 + 20 = 92 הציון הסופי שלך.