לפניך הגדרה של חמש פעולות הפועלות על מבנה נתונים כלשהו (שמות הפעולות אינם כתובים ב-Java או ב-C#):

insert(x) — מכניסה איבר x שערכו נתון (שלם) למבנה. showMin() — מחזירה את הערך הנמוך ביותר במבנה, בלי לשנות את המבנה. getMax() — מחזירה את האיבר שערכו הגדול ביותר במבנה, ומוציאה אותו מן המבנה (אם יש יותר מאיבר אחד בעל אותו הערך המקסימלי, מוציאה ומחזירה את זה שמופיע ראשון מבין השווים). exists(x) — פעולה בוליאנית: true אם קיים במבנה איבר שערכו x, אחרת false. div7() — פעולה בוליאנית: true אם קיים במבנה איבר שערכו מתחלק ב-7 בלי שארית, אחרת false.

השאלון עצמו נותן דוגמה פתורה (לא לביצוע): מבנה נתונים לביצוע insert ו-showMin בסיבוכיות O(1) ו-exists ו-getMax בסיבוכיות O(n) — הפתרון המוצע שם הוא רשימה מקושרת דו-כיוונית lst מטיפוס שלם, עם מצביע נוסף min לאיבר המינימלי: insert מכניס לראש הרשימה ומעדכן את min אם צריך (O(1)); showMin מחזיר את הערך שמצביע עליו min (O(1)); exists ו-getMax עוברים על כל הרשימה (O(n)).

בשני הסעיפים הבאים (א-ב) יש להציע — לכל אחד בנפרד — מבנה נתונים מתאים לדרישת הסיבוכיות השונה הנתונה, להסביר כיצד ממומשת כל פעולה, ולנמק מדוע המימוש עומד בדרישת הסיבוכיות.

הדוגמה הפתורה שבשאלון: רשימה מקושרת דו-כיוונית + מצביע min

lst (doubly linked, unsorted): head <-> ... <-> tail
min -> pointer to the current minimum node