Last active
March 13, 2023 17:48
-
-
Save P-A-R-U-S/f5ad2c621dae2765ee7885168d5caff8 to your computer and use it in GitHub Desktop.
Facebook: Passing Yearbooks
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package Facebook | |
import "testing" | |
/* | |
Passing Yearbooks | |
There are n students, numbered from 1 to n, each with their own yearbook. | |
They would like to pass their yearbooks around and get them signed by other students. | |
You're given a list of n integers arr[1..n], which is guaranteed to be a permutation of 1..n | |
(in other words, it includes the integers from 1 to n exactly once each, in some order). | |
The meaning of this list is described below. | |
Initially, each student is holding their own yearbook. | |
The students will then repeat the following two steps each minute: | |
Each student i will first sign the yearbook that they're currently holding | |
(which may either belong to themselves or to another student), and then they'll pass it to student arr[i]. | |
It's possible that arr[i] = i for any given i, in which case student i will pass their yearbook back to themselves. | |
\Once a student has received their own yearbook back, they will hold on to it and no longer participate in the passing process. | |
It's guaranteed that, for any possible valid input, | |
each student will eventually receive their own yearbook back and will never end up holding more than one yearbook at a time. | |
You must compute a list of n integers output, | |
whose ith element is equal to the number of signatures that will be present in student i's yearbook once they receive it back. | |
Signature | |
int[] findSignatureCounts(int[] arr) | |
Input | |
n is in the range [1, 100,000]. | |
Each value arr[i] is in the range [1, n], and all values in arr[i] are distinct. | |
Output | |
Return a list of n integers output, as described above. | |
Example 1 | |
n = 2 | |
arr = [2, 1] | |
output = [2, 2] | |
The first student will sign their own yearbook and pass it to the second, who will also sign it and pass it back to the first student, resulting in 2 signatures. Meanwhile, the second student's yearbook will similarly be signed both by themselves and then by the first student. | |
Example 2 | |
n = 2 | |
arr = [1, 2] | |
output = [1, 1] | |
Each student will simply pass their yearbook back to themselves, resulting in 1 signature each. | |
*/ | |
func findSignatureCounts(arr []int) []int { | |
result := make([]int, len(arr)) | |
i:=1 | |
counter := 0 | |
for counter < len(arr) { | |
if arr[i-1] == i { | |
if result[i-1] == 0 { | |
counter++ | |
} | |
i++ | |
continue | |
} | |
result[arr[i-1]-1] = 1 | |
i, arr[i-1] = arr[i-1], i | |
counter++ | |
} | |
for i = 0; i < len(arr);i++ { | |
result[i] += 1 | |
} | |
return result | |
} | |
func Test_Passing_Yearbooks(t *testing.T) { | |
testDatas := []struct{ | |
arr []int | |
result []int | |
}{ | |
{[]int{2, 1}, []int{2, 2}, }, | |
{[]int{1, 2}, []int{1, 1}, }, | |
{[]int{1, 3, 4, 2, 5}, []int{1, 2, 2, 2, 1}, }, | |
{[]int{}, []int{}, }, | |
{[]int{1,2,3,4,5,6,7,8,9,10}, []int{1,1,1,1,1,1,1,1,1,1}, }, | |
{[]int{10,9,8,7,6,5,4,3,2,1}, []int{2,2,2,2,2,2,2,2,2,2}, }, | |
} | |
IsInt32ArraysEquals := func (a []int, b []int) bool { | |
if len(a) != len(b) { | |
return false | |
} | |
for i, v := range a { | |
if v != b[i] { | |
return false | |
} | |
} | |
return true | |
} | |
for _, td := range testDatas { | |
r := findSignatureCounts(td.arr) | |
if !IsInt32ArraysEquals(r, td.result) { | |
t.Errorf("Source:%d \n Exepected: %d\n Actual: %d\n", | |
td.arr, | |
td.result, | |
r) | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@yumium it was 2 year ago. I might need to check test cases.