We can determine how "out of order" an array A is by counting the number of inversions it has. Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element.
Given an array, count the number of inversions it has. Do this faster than O(N^2) time.
You may assume each element in the array is distinct.
For example, a sorted list has zero inversions. The array [2, 4, 1, 3, 5] has three inversions: (2, 1), (4, 1), and (4, 3). The array [5, 4, 3, 2, 1] has ten inversions: every distinct pair forms an inversion.
תשובות
הוסף תשובה
|
לצפיה בתשובות
ספטמבר 2021
I have an O(NlogN) solution:
For each element, calculate the difference in position between the sorted (asc) and unsorted array. If an element "moved left" by x, add x to the counter.
שלב ראשון: ראיון של שעה ובו נשאלת שאלה אלגוריתמית אחת
שלב שני: 5 ראיונות, ראיון behavioral question ו-4 ראיונות טכניים, שאלות אלגוריתמיות עם כתיבת קוד מסודר
שאלות מתוך הראיון
נתונה מטריצה של 1 ו 0, המשבצות שיש בהן 1 מכילות ממתק, ויש רובוט שצריך לעבור מהמשבצת העליונה השמאלית למשבצת התחתונה הימנית. תכתוב פונקציה שמחשבת מספר מקסימלי של ממתקים שהרובוט יכול לאסוף במסלול מהמשבצת הראשונה לאחרונה.
ראיון לתפקיד 
