that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].
Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
תשובות
הוסף תשובה
|
לצפיה בתשובות
דצמבר 2020
int solution(int A[],int N){
int counters[N] = {0};
for(int i=0; i
if(A[i]>=1 && A[i]<=N)
counters[A[i-1]]++;
for(int j=1;j<=N;j++)
if(counters[j-1]==0)
return j;
return N+1;
}
דצמבר 2022
השאלה היא האם יש מספרים שליליים. אם כן אנחנו יכולים לוותר על זיכרון נוסף של counters. נניח שאין מספרים שליליים או שלפחות 'נמחק' אותם (אנחנו עוברים פעם ראשונה ומוחקים כל מספר שלילי ואפסים ושמים במקומם 1 - כי מספר שלילי והמספר אפס בכל מקרה לא מעניינים אותנו ולא משנים את התוצאה). אם לא נראה את המספר 1 (מבלי שהפכנו מספר שלילי ל1) אז ישר נחזיר שהמספר 1 חסר.
ואז נעבור על המערך פעם שנית - על כל מספר x בין 1 לבין N (- גודל המערך) שנקבל - נלך לתא הx-1 ונשנה את ערכו מחיובי לשלילי, (ככה נסמן שכבר ראינו את המספר שמסמל את התא הזה).
כל מספר אחר (x הוא 0 או גדול מN) נדלג עליו ולא נעשה כלום.
ככה נמשיך עד שנגיע לסוף המערך.
נעבור על המערך פעם שלישית. הפעם נבדוק כל ערך בתא i - אם הוא שלילי - נמשיך הלאה (זה אומר שאכן ביקרנו את התא i ושינינו את ערכו לשלילי).
אם הוא לא שלילי, נחזיר את האינדקס (i) פלוס 1 - כי בעצם לא ביקרנו בו ולא שינינו אותו לשלילי.
סה"כ הזיכרון שהשתמשנו הוא O(1) - בשביל boolean לבדוק האם ראינו כבר את המספר 1 או לא, במעבר הראשון.
שלב ראשון - מבחן ממוחשב שנערך בפלטפורמת Codility שמכיל שתי שאלות. בשביל להמשיך לשלב הבא עליי היה לענות נכונה על שתי השאלות בשעתיים.
שאלות מתוך הראיון
1. במחרוזת נתונה אסור שיהיו 3 או יותר אותיות זהות ברצף. עליך להחזיר מחרוזת מתוקנת. דוגמא: מקבלים aabeeexx, מחזירים aabeexx.
2. נתונה מטריצה של intים בגודל 2*N. בכל אחד מהתאים יכול להיות 0 או 1.
נתון סכום השורה העליונה, סכום השורה התחתונה ומערך של סכומי הטורים.
על סמך הנתונים האלה תמלא את המטריצה כך שסכומי הטורים יהיה נכון וסכומי השורות יהיה נכון ולהחזיר מחרוזת שמייצגת את המטריצה.
דוגמא: סכום שורה עליונה: 3
סכום שורה תחתונה: 2
סכומי הטורים: [2,1,0,1,1]
מחזירים: "11001,10010"
ראיון לתפקיד 
