נתון קלאס שמממש מערך, הכנסה והוצאה ממנו מתרחשות ב O(1) ומילוי של המערך כולו באותו אלמנט לוקח O(n) .
איך היית מממש את המחלקה כך שגם הכנסת של אלמנט לכל התאים במכה יתרחש ב O(1), מה היית משנה?
לעבור עד אמצע המערך ולהחליף את האיבר במקום האינדקס עם האיבר שנמצא במקום האחרון פחות האינדקס
אוגוסט 2017
מצביע לאיבר הראשון שמתקדם קדימה לכיוון האמצע, מצביע לאיבר האחרון שמתקדם אחורה לכיוון האמצע. כל עוד המצביעים שונים זה מזה - בכל איטרציה לעשות swap בין האיברים.
איך לממש מחסנית שמחזירה את הערך המקסימלי בתוכה ב- O(1)
תשובות
הוסף תשובה
|
לצפיה בתשובות
אפריל 2016
נחזיק עוד מחסנית שתשמור ערכים מקסימלים.
בכל הכנסה למחסנית הרגילה, נבדוק מה הערך האחרון שהוכנס למחסנית העזר, אם הערך החדש גדול ממנו, נכניס אותו גם למחסנית העזר.
בכל הוצאה מהמחסנית, נבדוק האם הערך שמוצא נמצא בראש מחסנית העזר, אם כן נוציאו גם משם.
בכל רגע נתון הערך המקסימלי יהיה בראש מחסנית העזר ונוכל לשלפו ב O(1) כנדרש
2 ראיונות
1) ראיון עם 2 אנשי צוות כשעה וחצי מספרים על החברה על הצוות ושואלים שאלות
2) ראיון שני עם מנהל צוות או דרגה יותר בכירה עם עוד קצת שאלות טכניות
ואז משאבי אנוש וחתימת חוזה
שאלות מתוך הראיון
ראיון לחברת EMC RecoverPoint-
שאלה 1-
יש 2 מחרוזות
str1-"hello world"
str2-"adh"
צריך להחזיר את האות הראשונה שמופיעה במחרוזת STR1 וגם בSTR2- כלומר במקרה זה : פוינטר לתו H בSTR1
שאלה 2-
נתונה מחסנית ויש לה את הפונקציות push pop peek ויש עוד פונקציה של הערך המקסימלי במחסנית. יש לכתוב את הפונקציות כך שאחרי כל פעולה שאבצע תמיד אדע מה המקסימום במחסנית.
שאלה 3-
יש 99 תהליכונים(חוטים) ואין לך סמפור או את דרכי הנעילה הרגילים ויש 2 פונקציות פונקצית inc אשר כל שגיאה מעלה אינדקס כלשהו ב1 ופונקצית get שיודעת כמה שגיאות היו עד כה. כתוב/י דרך לכתוב את פונקצית inc
שאלה 4-
כמו 3 רק שיש תהליכון נוסף T100 שהוא לא חלק מהתוכנית ועליו לדעת ברמה הכי מדויקת מה מספר השגיאות .
תשובות
הוסף תשובה
|
לצפיה בתשובות
ינואר 2016
1 -
2 שיטות הראשונה לרוץ על המחרוזת הראשונה ועבור כל תו לרוץ על המחרוזת השניה במידה ואין התאמה זמן הריצה o(n^2)
השניה bucket כלומר לעשות מערך של 26 (כמות האותיות באנגלית ולרוץ על מחרוזת 1 לסמן T איפה שיש את האות ואז לרוץ בנפרד על המחרוזת השניה ולבדוק אם התו קיים
זמן ריצה o(n)
2- ליצור עוד מחסנית עזר אשר שומרת את הערכים המקסימלים, ועבור כל Push אם הערך גדול או שווה נכניס למחסנית עזר. עבור pop נוציא אם זה שווה לערך במחסנית עזר
3- ליצור מערך של 99 ועבור כל תהליכון נשמור בתא שלו את כמות השגיאות שהיו לו (לפי id של התהליכון נוכל לזהות כל אחד) וכדי לקבל תשובה נרוץ על המערך ונסכום מס שגיאות אמנם לא נקבל תשובה הכי מדויקת.
4- כמו 3 רק שניצור מערך של מבנים בערך אחד מס השגיאה ובערך 2 משתנה בוליאני T/F שמודיע אם בוצע שינוי והT100 ידע מי עבר שינוי.