תוכן העניינים[להתחבא][הופעה]
- 1. איך מגדירים מערך?
- 2. מערכים דינמיים: מה הם? מה מייחד אותם ממערכים בסיסיים?
- 3. כיצד משתנים מערך ומילון זה מזה?
- 4. רשום כמה מהיתרונות והחסרונות של מערכים.
- 5. למה מתייחס "מערך דל"?
- 6. מתי היית בוחר רשימה מקושרת על פני מערך?
- 7. מה מבדיל מערך אינדקס ממערך אסוציאטיבי?
- 8. אילו יתרונות יש ל-Heap על פני מערכים ממוינים?
- 9. האם נוכל להגדיר את גודל המערך להיות שלילי?
- 10. איך מאתרים את המספר השלם החסר במערך של 1 עד 100 אלמנטים?
- 11. איך מוצאים את האינדקס של אלמנט במערך?
- 12. איך אפשר להיפטר מאלמנט מסוים ממערך?
- 13. כיצד ניתן לאמת שוויון של שני מערכים?
- 14. כאשר אנו דנים במערכים, למה אתה מתכוון בביטויים "מימד" ו"Subscript"?
- קידוד שאלות ראיון
- 15. חפש זוג במערך שיש לו את הסכום שצוין
- 16. מיון מערך בינארי עם זמן ליניארי
- 17. מצא את המוצר הגדול ביותר עם שני אינטנטים במערך.
- 18. כיצד להעביר את כל האפסים של המערך לסוף
- 19. כיצד למיין מערך עם שני ערכים המתחלפים בפעולה אחת.
- 20. כיצד לשלב שני מערכים ממוינים במקום.
- 21. כיצד לסדר מחדש מערך של פריטים במיקומים גבוהים ונמוכים לסירוגין?
- 22. כיצד מחליפים כל אלמנט של מערך מבלי להשתמש באופרטור חלוקה במכפלה של כל אלמנט במערך?
- 23. מצא את האלמנט המוזר ביותר במערך בזמן לוגריתמי
- 24. איך להשיג את האלמנט הגדול הבא עבור כל אלמנט במערך מעגלי?
- 25. למצוא את ספירת ההיפוך של מערך?
- 26. מהי בעיית לכידת מי הגשם?
- סיכום
ראיונות קידוד מכילים סדרה של שאלות DSA. אתה צריך להיות מיומן עם מערכים אם אתה מתכונן לראיון הטכנולוגי הקרוב שלך עם FAANG או עסק טכנולוגי מסוג Tier-1 אחר.
ברוב ראיונות הקידוד, זה מגיע למקום השני ל-Strings. מערך הוא קיבוץ של רכיבי נתונים קשורים שנשמרו בסמיכות זה לזה בזיכרון.
מכיוון שהם מחוברים לכל שפות התכנות, כגון C, C++, Java, Python, Perl ו-Ruby, הם נמצאים בכל מקום. המשך לקרוא לתרגול אתגרי קידוד ושאלות ותשובות לראיונות המבוססים על מערכים.
Python ישמש בפוסט הזה כדי להתמודד עם בעיות הקידוד מכיוון שהוא פשוט לשימוש, הבנה וחייב להיות מוכר לרובנו.
בואו נתחיל.
1. איך מגדירים מערך?
- קבוצה של סוגי נתונים קשורים היא מערך.
- מערכים תמיד קבועים.
- אותו סוג של משתנה מאוחסן במספר מקומות על ידי אובייקטי מערך.
- טיפוסים פרימיטיביים והפניות לאובייקט תואמים אותו.
2. מערכים דינמיים: מה הם? מה מייחד אותם ממערכים בסיסיים?
קנה המידה האוטומטי שמעניקים מערכים דינמיים (המכונה גם מערכים ניתנים לגידול, מערכים הניתנים לשינוי גודל, מערכים הניתנים לשינוי או ArrayLists ב-Java) הוא יתרון משמעותי.
אתה תמיד חייב לדעת כמה אלמנטים המערך שלך יאחסן מראש מכיוון שלמערכים יש גודל קבוע. מערך דינמי, לעומת זאת, גדל ככל שאתה מוסיף לו חברים נוספים, כך שאתה לא צריך לדעת את הגודל המדויק שלו מראש.
3. כיצד משתנים מערך ומילון זה מזה?
זהו מערך מבוסס יסודות של שאלות ראיון שנשאלות באופן קבוע. להלן ההבחנות העיקריות בין מערכים ומילון:
- מערך הוא רשימה מסודרת של פריטים דומים. למילון, לעומת זאת, יש צמדי מפתח-ערך.
- גדלי מערכים יכולים להשתנות באופן דינמי. רעיונות דינמיים כאלה אינם קיימים במילונים.
- לפני השימוש במערך, יש לציין את גודלו. אין צורך להתאים אישית גדלי מילון.
- השתמש במשפט Redim אם ברצונך להרחיב את גודל המערך. במילונים ניתן להוסיף אלמנט ללא הצהרה.
4. רשום כמה מהיתרונות והחסרונות של מערכים.
יתרונות:
- מערכים יכולים למיין מספר אלמנטים בו זמנית.
- אחר מבני מידע, כמו ערימות, תורים, רשימות מקושרות, עצים, גרפים וכו', ניתן ליישם במערך.
- ניתן להשתמש באינדקס כדי להגיע לאלמנט של מערך.
חסרונות:
- יש להצהיר מראש על גודל מערך. עם זאת, ברגע הצהרת המערך, ייתכן שלא נהיה מודעים לגודל שאנו דורשים.
- מבנה המערך הוא סטטי. זה מרמז שגודל המערך תמיד קבוע ושלא ניתן להגדיל או להקטין את הקצאת הזיכרון.
5. למה מתייחס "מערך דל"?
מערך דל הוא מערך נתונים שיש בו הרבה ערכים עם אפס ערכים. לעומת זאת, מערך צפוף מכיל את רוב הפריטים שלו עם ערכים שאינם אפס. המדדים של מערך דליל, הממיר מספרים לאובייקטים, עשויים לכלול פערים. בהשוואה ל-HashMap, הם חסכוניים יותר בזיכרון.
6. מתי היית בוחר רשימה מקושרת על פני מערך?
בעת שימוש ברשימות מקושרות במקום מערכים, שקול:
- אתה לא צריך שום אלמנט כדי לקבל גישה אקראית.
- כאשר חיזוי זמני חיוני, אתה צריך הכנסה והסרות בזמן קבוע מהרשימה.
- על מנת ליצור תור עדיפות, ייתכן שיהיה עליך למקם פריטים במרכז הרשימה.
- אין לך מושג כמה ארוכה הרשימה. אם גודל המערך עולה, עליך להצהיר מחדש ולשכפל זיכרון, בדיוק כמו עם מערכים פשוטים.
7. מה מבדיל מערך אינדקס ממערך אסוציאטיבי?
ההבחנות העיקריות בין מערכים אסוציאטיביים למערך אינדקס מפורטות בטבלה הבאה.
- זוג מפתח-ערך בפורמט טקסט או מספרי משמש למיון מערך אסוציאטיבי. המפתחות של המערך המאונדקס הם כולם מספריים, וכל מפתח מחובר לערך מובחן.
- במערך אסוציאטיבי, המפתח עשוי להיות מחרוזת. מערך באינדקס עם מפתחות שלמים שמתחילים ב-0.
- טבלה בת שתי עמודות מחקה את ההתנהגות של מערך אסוציאטיבי. בדומה לטבלה של עמודה אחת, יש מערכים באינדקס.
- מפות הן סוג של מערך אסוציאטיבי. מערך אינדקס אינו מפה.
8. אילו יתרונות יש ל-Heap על פני מערכים ממוינים?
יעילות הזמן של שימוש ב-Heap על פני מערכים ממוינים היא היתרון העיקרי. בעוד שפעולות הערימה מהירות יותר, מיון מערך דורש זמן רב. ערימה יכולה לגלות את האלמנט הקטן ביותר במהירות רבה יותר מאשר ניתן למיין מערך.
ניתן לסדר אוסף נתון של מספרים באחת משתי דרכים באמצעות מערכים ממוינים. מצד שני, עבור אוסף נתון של מספרים, עשויה להיות יותר מערימה פוטנציאלית אחת.
9. האם נוכל להגדיר את גודל המערך להיות שלילי?
לא, איננו יכולים להגדיר מספר שלם שלילי בגודל של מערך. לא תהיה שגיאה בזמן הידור אם נכריז. עם זאת, בזמן ריצה ניתקל ב-NegativeArraySizeException.
10. איך מאתרים את המספר השלם החסר במערך של 1 עד 100 אלמנטים?
ניתן לחשב את סך הסדרה על ידי יישום הפונקציה הבאה: n (n + 1) / 2
רק אם למערך אין כפילויות או שחסר יותר ממספר שלם אחד תפעל פונקציה זו. אם למערך יש רכיבים כפולים, אתה יכול למיין את המערך כדי לראות אם יש אלמנטים שווים.
11. איך מוצאים את האינדקס של אלמנט במערך?
ניתן לגלות אינדקס של אלמנט באמצעות חיפוש ליניארי או בינארי. עד שהוא מאתר את ההתאמה של האלמנט הנדרש, פונקציית חיפוש ליניארית עוברת לולאה על כל אלמנט ואלמנט במערך. הוא מחזיר את האינדקס ברגע שהוא מאתר את האלמנט התואם. כתוצאה מכך, המורכבות הזמנית של החיפוש הליניארי היא O. (n). גם מערך ממוין וגם מערך לא ממוין יכול להשתמש בחיפוש לינארי.
באמצעות חיפוש בינארי, המחלק ללא הרף את המערך לשניים עד שהחציון של המרווח תואם את האלמנט הנדרש ומספק את האינדקס, ניתן לקבל את האינדקס של האלמנט אם המערך ממוין. כתוצאה מכך, המורכבות הזמנית של החיפוש הבינארי היא O. (log n).
12. איך אפשר להיפטר מאלמנט מסוים ממערך?
מכיוון שאינך יכול פשוט למחוק אלמנטים מהמערך המקורי מכיוון שהם סטים קבועים בגודל מוגדר, המראיין מבקש ממך להציע גישה אחרת ולטפל בבעיה שהשאלה מעוררת. דרך הפעולה הטובה ביותר היא ליצור מערך חדש על מנת למחוק אלמנט. אתה יכול לשכפל את האלמנטים מהמערך הראשון במערך הזה ולכלול רק את האלמנט שברצונך למחוק.
אסטרטגיה נוספת כוללת מציאת אלמנט המטרה במערך ולאחר מכן היפוך הסדר של כל הפריטים שנמצאים מימין לאלמנט היעד.
13. כיצד ניתן לאמת שוויון של שני מערכים?
תחילה עליך לאמת את האורכים של שני המערכים שסופקו. הפריטים התואמים של שני המערכים מושווים כאשר אורכם שווה. שני המערכים ייחשבו כשווים. אם כל זוג רכיבים בכל התכתבות שווה. לא מומלץ לגישה זו לבדוק את השוויון של שני מערכים אם המערכים גדולים בגודלם שכן זה ייקח הרבה זמן. אתה יכול גם להשתמש בשיטת equals() הכלולה במחלקה Arrays, עם זאת, אם המראיין יבקש ממך להשוות בין שני מערכים מבלי להשתמש בשיטות מובנות, הדרך הזו תהיה שימושית.
14. כאשר אנו דנים במערכים, למה אתה מתכוון בביטויים "מימד" ו"Subscript"?
"המימד" של מערך הוא מספר המדדים, או המנויים, הנדרשים לזיהוי כל חבר בודד. המנויים והמידות עשויים להיות לא ברורים. ממד הוא תיאור של טווח המפתחות המותרים, בעוד שכתב מנוי הוא מספר. דרוש מנוי אחד בלבד עבור כל מימד מערך.
לדוגמה, למערך arr[10][5] יש שני מימדים. מידות 10 על אחד ו-5 על השני. כדי לטפל במרכיבים שלו, אתה צריך שני מנויים. שניהם בין 0 ל-4; אחד בין 0 ל-9, כולל.
קידוד שאלות ראיון
15. חפש זוג במערך שיש לו את הסכום שצוין
לדוגמה,
קלט:
- מספרים = [8, 7, 2, 5, 3, 1]
- יעד = 10
פלט:
- זוג נמצא (8, 2)
- Or
- זוג נמצא (7, 3)
קלט:
- מספרים = [5, 2, 6, 8, 1, 9]
- יעד = 12
פלט:
- צמד לא נמצא
16. מיון מערך בינארי עם זמן ליניארי
מיין מערך בינארי בזמן ליניארי ובאזור קבוע. הפלט אמור להציג תחילה את כל האפסים, ולאחר מכן את כל אחד.
לדוגמה,
- קלט: { 1, 0, 1, 0, 1, 0, 0, 1 }
- פלט: { 0, 0, 0, 0, 1, 1, 1, 1 }
גישה פשוטה תהיה לחשב את המספר הכולל של 0s של המערך, נניח k, ולאחר מכן למלא את המדדים k הראשונים במערך ב-0s ואת המדדים הנותרים ב-1. לחלופין, נוכל לחשב כמה 1s הם בסך הכל ב- מערך k, מלאו את k המדדים האחרונים במערך ב-1, והשאירו את שאר המדדים מלאים ב-0.
לגישה הנתונה יש מורכבות זמן O(n) ואינה משתמשת באחסון נוסף, כאשר n הוא גודל הקלט.
17. מצא את המוצר הגדול ביותר עם שני אינטנטים במערך.
מצא את המכפלה הגדולה ביותר של שני מספרים במערך שלמים.
חשבו על המערך 10 3 5 6 2 כדוגמה. הצמד (-10, -3) או (5, 6) הוא המוצר הגבוה ביותר.
לחשוב על כל שילוב של אלמנטים ולהבין את המוצר שלהם זו גישה מטופשת. אם המוצר של הזוג הנוכחי גדול מהמוצר המקסימלי שהושג עד כה, עדכן את המוצר המקסימלי. הדפס את מרכיבי המוצר הסופי אחרון.
לפתרון שלמעלה, שבו n הוא כמות הקלט, יש מורכבות זמן של O(n2) ואינו תופס יותר מקום.
18. כיצד להעביר את כל האפסים של המערך לסוף
הזז את כל האפסים במערך שלמים עד הסוף. התשובה צריכה להימנע משימוש ברווח קבוע ולשמור על הסדר היחסי של מרכיבי המערך.
קלט: {1,2,3,0,8,0,4,7}
הפלט יהיה {1,2,3,8,4,7,0,0}
שים את האלמנט במיקום הזמין הבא במערך אם האלמנט הנוכחי אינו אפס. מלאו את כל המדדים הנותרים ב-0 ברגע שכל הפריטים של המערך עברו עיבוד.
לפתרון הקודם יש מורכבות זמן O(n), כאשר n הוא גודל הקלט.
19. כיצד למיין מערך עם שני ערכים המתחלפים בפעולה אחת.
מיין מערך בזמן הליניארי בהינתן שני פריטים שהוחלפו ומערך שכל הרכיבים שלו מסודרים בסדר עולה. העמד פנים שהמערך אינו מכיל כפילויות.
קלט:= [1,9,3,4,7,2] או [9,3,7,2,1,4] או [2,4,1,7,3,9]
פלט: = [1,2,3,4,7,9]
החל מהאלמנט השני במערך, המטרה היא להשוות כל אלמנט לקודמו. מיקום המחלוקת נשמר על ידי לקיחת שני מצביעים, x ו-y.
עדכן את x לאינדקס של האלמנט הקודם ואת y לאינדקס של האלמנט הנוכחי אם הראשון גדול מהאחרון. עדכן את y לאינדקס של האלמנט הנוכחי אם יתברר שהאלמנט הקודם גדול מהאלמנט הנוכחי.
לבסוף, החלף את האלמנטים באינדקסים x ו-y לאחר שסיימנו לעבד כל זוג אלמנטים סמוכים.
בשל העובדה שהשיטה הנ"ל מבצעת רק סריקה בודדת של מערך הקלט בגודל n, מורכבות הזמן שלו היא O(n). אין צורך בחדר נוסף לפתרון.
20. כיצד לשלב שני מערכים ממוינים במקום.
למזג את הפריטים של המערכים X[] ו-Y[] - שני מערכים ממוינים בגודל m ו-n כל אחד - על ידי שמירה על הסדר הממוין, כלומר על ידי מילוי X[] ב-m הראשון האלמנטים הקטנים ביותר ומילוי Y[] ב- האלמנטים הנותרים.
אם אלמנט במערך X[] כבר נמצא במיקום הנכון (כלומר, זה שהוא הקטן ביותר מבין האלמנטים הנותרים), התעלם ממנו; אחרת, החלף אותו באלמנט הקטן ביותר, שהוא במקרה גם האיבר הראשון של Y[]. כדי לשמור על הסדר הממוין לאחר ההחלפה, העבר את האלמנט (עכשיו ב-Y[0]) למיקומו הנכון ב-Y[].
גודל המערך הראשון הוא m וגודלו של המערך השני הוא n, ומורכבות הזמן היא O(mn).
21. כיצד לסדר מחדש מערך של פריטים במיקומים גבוהים ונמוכים לסירוגין?
ארגן מחדש מערך שלמים כך שכל איבר עוקב יהיה גדול מהרכיבים הקודמים והבאים. נניח שהמערך אינו כולל רכיבים כפולים.
מיון המערך או ניצול שטח נוסף אינם הכרחיים לגישה יעילה. התוכנית היא, מלכתחילה, החבר השני של המערך ולעלות בשניים עבור כל איטרציה של לולאה.
החלף את הרכיבים אם הרכיב האחרון חורג מהראשון. ברוח דומה, החלף את שני הפריטים אם האלמנט הבא גדול מהאלמנט הנוכחי. נקבל את המערך הרצוי התואם את ההגבלות שצוינו בסיום הלולאה.
22. כיצד מחליפים כל אלמנט של מערך מבלי להשתמש באופרטור חלוקה במכפלה של כל אלמנט במערך?
מבלי להשתמש באופרטור החלוקה, החלף כל רכיב במערך שלמים במכפלה של כל הרכיבים האחרים.
בזמן ליניארי ובמרחב קבוע, אנו יכולים להשתמש ברקורסיה כדי לטפל בבעיה זו. חישוב רקורסיבי של התוצרים של כל אלמנט בתת המערך הימני והעברת תוצר המשנה השמאלי כפרמטרים של פונקציה הוא הרעיון.
מורכבות הזמן היא O(n).
23. מצא את האלמנט המוזר ביותר במערך בזמן לוגריתמי
בהינתן מערך שלמים שבו לכל האיבר מלבד אחד יש מספרים זוגיים של התרחשויות, הבעיה היא לקבוע כמה פעמים יופיע אלמנט אחד זה. מצא את האלמנט האי-זוגי המתרחש בזמן לוגריתמי ובמרחב קבוע אם אותם אלמנטים מתרחשים בזוגות במערך ולעולם לא יכולים להיות יותר משני מופעים של אלמנט נתון ברציפות.
פעולת XOR מאפשרת לנו לפתור בעיה זו בזמן ליניארי. המטרה היא לבצע XOR כל אלמנט במערך. רק האלמנטים המוזרים המתרחשים נשארים לאחר שהאלמנטים המתרחשים זוגיים מבטלים זה את זה.
ניתן אפילו לפתור בעיה זו בזמן O(log(n)).
24. איך להשיג את האלמנט הגדול הבא עבור כל אלמנט במערך מעגלי?
יש למקם את האלמנט הגדול הבא עבור כל אלמנט במערך מספר שלם מעגלי. המספר השלם הגדול הראשון אחרי אלמנט x במערך הוא האלמנט הגדול הבא של אותו אלמנט.
מימין לשמאל, אנו עשויים לפעול על פריטי מערך. המטרה היא לבצע לולאה עבור כל אלמנט x עד שהערימה ריקה או שיש לנו אלמנט גבוה יותר מעליה. הגדר את האלמנט הגדול הבא של x שיופיע על גבי הערימה כאשר הוא מופיע.
25. למצוא את ספירת ההיפוך של מערך?
מצא את המספר הכולל של היפוכים של מערך. זוג I j) מכונה היפוך של מערך A אם I j) ו-(A[i] > A[j]). עלינו לספור כל זוג של אלה במערך.
ספירת כל איברי המערך שפחות ממנו מימין לו והוספת התוצאה לפלט היא גישה פשוטה.
לפתרון זה יש מורכבות O(n2), כאשר n הוא גודל הקלט.
26. מהי בעיית לכידת מי הגשם?
מציאת הכי הרבה מים שניתן ללכוד בקבוצה נתונה של סורגים ברוחב של יחידה אחת כל אחד ידוע כבעיית "לכידת גשמים".
המטרה היא לקבוע את הפס הגבוה ביותר שניתן למקם משמאל וימין של כל פס. המינימום של הסורגים המובילים משמאל וימין, בניכוי גובה הפס הנוכחי, הוא כמות המים שנאגרת על גבי כל פס.
סיכום
בהשוואה לנושאים אחרים של מבנה נתונים, מערכים פשוטים יותר. כדי לענות על שאלות ראיונות של מערך, אתה צריך להיות בעל הבנה בסיסית של מערכים.
עליך לסקור בהרחבה את היסודות של מערכים, כולל פעולות מערך (מהכרזה/יצירת מערך ועד גישה/שינוי של פריטי מערך), כמו גם מושגי תכנות כמו לולאות, רקורסיה ואופרטורים בסיסיים כדי לענות בהצלחה על שאלות ראיונות מערך. מכיר את הנושא לחלוטין.
עליך לבקש הבהרות אם יש לך שאלות. חשבו על חלוקת הנושא לחלקים ניתנים לניהול. ודא שיש לך את האלגוריתם בראש לפני שתתחיל בתכנות; רשום אותו או דמיינו אותו בתרשים זרימה. ואז להתחיל לכתוב קוד.
השאירו תגובה