Question ( I MADE A IMAGE OF A TEST )
DESIGN A WEB CRAWLER (class diagram +pseudo code).
A web crawler starts with a list of URLs to visit , As the crawler visits it identifies all the hyperlink in the page and adds them to the list OF URLs to visit and then recursively visit them
1. תעצב שרת של הודעות כמו whatsapp? כאן הם רוצים לראות איך אתה מעצב מערכת. איזה קומפוננטות יהיו בשרת.
2. תכתוב פונקציה שבודקת האם העץ מאוזן/ מלא, כלומר אם יש לכל אב שני בנים וכל העלים באותו הגובה, כאן לא מספיק רק לבדוק ברקורסיה האם שני הבנים קיימים לכל אב אלא צריך לבדוק האם כל העלים באותו הגובה.
3. יש לך k רשימות ממוינות עם מספרים, כתוב פונקציה שבוחרת את הטווח המינמלי האפשרי כך שבטווח זה יהיה לפחות מספר אחד מכל רשימה. לדוגמא:
רשימה 1 – 1 20 21
רשימה 2 – 2 22 24
רשימה 3 – 30 40 50
אז הטווח המינימלי הוא 21-30 כי 21 מופיע ברשימה ה1, 22 ו 24 מופיעים ברשימה ה2 ו30 מופיע ברשימה ה3
4. כתוב פונקציה שמקבלת גבהים ומשקלים של אנשים בצורה (180,85),(190,60),(150,100),…
ומחזירה את האנשים ומספרם של אלו שאפשר לבנות מהם מגדל כך שהחוק הוא שכל בנאדם שמעל לבנאדם אחר הוא גם רזה יותר וגם נמוך יותר מהקודם. זה לא ממויין אז אני מעריך שצריך אולי למיין לפי גבהים ולפי משקלים.
5. שאלת בונוס – תתאר מחלקה שמספקת מנעול רק כאשר אין deadlock.מצאתי את הפיתרון כאן:
http://stackoverflow.com/questions/5171 … -deadlocks
היו 5 שאלות חלק יחסית קלות אבל היו כמה די קשות במיוחד השאלת בונוס.
1) קיימת פונקציה שאומרת אם מחרוזת היא תת מחרוזת של מחרוזת אחרת. בהינתן שתי מחרוזות איך ניתן באמצעות קריאה אחת בלבד של הפונקציה הנ"ל לדעת האם מחרוזת אחת היא סיבוב ציקלי של השניה, למשל "יאיר" "ריאי" תתן תשובה חיובית.
פתרון מוצע: כך את המחרוזת יאיר ותבנה ממנה מחרוזת עם כל הסיבובים האפשריים: "יאיריאי".
ואז תבדוק אם ריאי היא תת מחרוזת שלה.
בונוס:
כתוב פונקציה שמקבלת שני מספרים ומחזירה מקסימום שלהם ללא השוואות.
פתרון מוצע:
בהינתן a b
dif = a-b
sign = 1 if dif is negetive 0 if positive (עושים זאת ע"י פעולות bitwise שנuתנות את ביט הסימן של dif)
ולבסוף החזר
a – (a-b)*sign
1. נתון מערך בגודל m x n כך ש m,n לא בהכרח שווים . צריך להדפיס את איברי המערך בצורה ספירלית
כלומר אם נתון
1 2 3 4
5 6 7 8
9 10 11 12
תדפיס:
ZZZ 4 3 2 1 5 9 10 11 12 8 7 6 ZZZ
ה- ZZZ זה רק ליישור שורה. 5 לולאות מהגיהינום.
2. יש n איברים ולכל איבר יש ערך. צריך למצוא מבנה נתונים שאיתו אפשר ב o(1) בלבד לעשות את כל הפעולות הבאות:
1. לשנות ערך של איבר
2. להחזיר ערך של איבר
3. לשנות את כל הערכים של כל האיברים (זה כמובן הקושי פה)
פתרון מוצע: http://stackoverflow.com/questions/10005544/interview-qu%D0%B5stion-data-structure-to-set-all-values-in-o1
שאלה שלישית:
צריך לתאר UML של מעלית.
שאלת הגיון:
אתה מחזיק מגילה ובה K משפטים:
רק משפט אחד מהמשפטים שבמגילה זו הוא נכון.
בדיוק שני משפטים מהמשפטים שבמגילה זו הם נכונים.
בדיוק שלושה משפטים מהמשפטים שבמגילה זו הם נכונים.
*
*
*
כל המשפטים במגילה זו הם נכונים.
אילו מהמשפטים במגילה נכונים???
פתרון מוצע: רק המשפט הראשון נכון.
נתונה פונקציה – random 5 שמחזירה מספר רנדומלי בין 1 ל 5 ממש את random 7.
תשובה מוצעת:
int randbit( void )
{
while( 1 )
{
int r = rand5();
if( r <= 4 ) return(r & 1);
}
}
int randint( int nbits )
{
int result = 0;
while( nbits– )
{
result = (result<<1) | randbit();
}
return( result );
}
int rand7( void )
{
while( 1 )
{
int r = randint( 3 ) + 1;
if( r <= 7 ) return( r );
}
}
1. The 2 Eggs Problem – Building of 100 floors, You need to find the breakable floor. (google it…)
2. NXN pixels picture, each pixel is 4 bit. You need to build a method for rotating the pic in 90 degree.
3. Data structure of UML: create Class Diagram:
a. some Receivers – first answer
b. one Manager – second answer
c. some Directors –third answer.
If Receiver can't take the call , it moves to Manager,
If Manager can't take the call, it moves to Director
4. Bonus:
Data structure of Two Tress:
T1 – Tree with millions of nodes
T2 – Tree with hundreds of nodes
You need to write algorithm which saying wheatear T2 is sub-tree of T1 ?
T2 is sub-tree of T1 if there is a node in T1 that which all his descending exists
שאלות גירסא 1:
1.describe using uml or other programming language an elevator
2.יש לך n משפטים
אומרים לך להגיד לכל משפט האם הוא אמת שקר או אי אפשר לדעת
אבל זה שונה מהמגילות
כל משפט נראה כך:
there is exactly one false sentence
there are exactly two false …
there are exacyly n false
3.
תתארי מבנה נתונים שאת יכולה לעשות את כל הפעולות הבאות בo(1)
יש לך
insert(location,value)
reset(value)
pull(index)
חסרה פה שאלה נוספת ושאלת בונוס(לא זוכרת נדמה לי שהן מופיעות בקובץ גם)
גירסא 2:
עמוד 54(1.1):
Implement an algorithm to determine if a string has all unique characters What if you
can not use additional data structures?
עמוד 54 (1.6):
Given an image represented by an NxN matrix, where each pixel in the image is 4
bytes, write a method to rotate the image by 90 degrees Can you do this in place?
לא סגורה על זה אבל נראה לי שהיתה שאלה:Assume you have a method isSubstring which checks if one word is a substring of
another Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using
only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”)
(1.8)
עמוד 78 שאלה 2 היתה
שאלת זריקת ה2 ביצים ממגדל היתה
שאלת בונוס :
עמוד 60 שאלה 4.7 (שני עצים)
חלק מהשאלות והפתרונות מופיעים כאן:
http://www.valleytalk.org/wp-content/uploads/2012/10/CrackCode.pdf
יש שתי טבלאות, a ו-b, ב-a יש 30 שורות וב-b יש 20. כמה שורות תקבל בתוצאה של
select * from a,b
תשובה מוצעת: 600.