שאלות ראיון [קל] - מציאת כפילויות במערך

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

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

LeetCode

דרישות:

• יעילות זמן : n
• יעילות מקום: n
  

הפתרון נעוץ בשימוש חכם במבני נתונים - במקרה הזה set.

בכל פעם שנעבור על המערך, נכניס את האיבר הנוכחי לתוך set ב-O(1) וגם נוכל לבדוק בעלות של O(1) האם פגשנו איבר כזה בעבר.

לפני שנציג את הפתרון - ננסה שנייה לחשוב למה פתרונות אחרים לא יתאימו.

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

ניתן להשתמש ב-dict אך אין צורך במקרה הזה.

גירסאות קשות יותר לשאלה:

• להחזיר את המספרים / התווים בעלי הכפילות: נמשיך את האיטרציה עד הסוף ונחזיר את הסט.
• להחזיר את כמות הכפילויות שיש לכל תו / מספר: נחזיר dict עם התווים וכמות הכפילויות שלהם.