הויפט זייט » תורה ודעת » טעכנאלאגיע » פראבלעם סאלווינג אין קאוד

פראבלעם סאלווינג אין קאוד

26 פאסטס אין ארכיוו · אשכול #14319

יוניווערסיטי_בחור » מיטוואך נאוועמבער 4, 2020 4:07 pm

· #462066

האבענדיג נישט לאנג צוריק גראדואירט פון יוניווערסיטי אין קאמפיוטינג טרעף איך זיך אריינקוקן רעאליטעט אין פנים, אויפ'ן יאגד נאך א סאפטוועיר אינדזשענירינג דזשאב. רעדענדיג מיט אנדערע אין די אינדוסטריע און האבנדיג אדורכגעגאנגען א האנדפול פון אינטערוויאוס איז פשוט אז ס'איז אן ענין פון פרעקטיס. דער ענין איז מער איבערן פארמאגן די קאוועליטעט פון פראבלעם סאלווינג ווי איבער קענען דער פראגרעמינג שפראך אדער יענער פראגרעמינג לענגוויטש. ווי מער פרעקטיס די העכער זענען די שאנסן און מעגליכקייטן צו אדורכמאכן אזא אינטערוויאו.

אלזא האב איך מיך דערטראכט צו אזא המצאה. כדי איך זאל האבן אן אינסענטיוו צו פראקטאצירן די עקסערסייזעס וועל איך יעדן טאג אי"ה פאוסטן א פראבלעם און אנשטרענגען זיך ביי די ענדע טאג צו אויפקומען מיט א סעלושען. אנדערע זענען אוודאי וועלקאם אליינס אויפצוקומען מיט סעלושענס און פאוסטן פריער. אבער, איך וויל אזא פאר יעדע פראבלעם זאלן זיין צוויי געווינער. איינער, דער וואס טרעפט צו דאס ערשטע א סעלושען און די צווייטער, אויב נישט דער זעלביגער, דער וואס טרעפט אויס די מערסט עפישענט/עפעקטיווער סעלושען. עפישענסי מעסט זיך אין ביג 0 נאטעישאן און סאטרידזש. עלעגענסי און רידעביליטי (קאמענטס וכדומה) איז א פלוס.

מען מעג אויך אוודאי ארויפלייגן אייגענע עקסערסייזעס אדער פערטיגע סעלושענס צו זיי, להגדיל תורה ולהאדירה.

איך גיי די עקסערסייזעס ברענגען פון די פארשידענע פלאטפארמען עוועילעבל אנליין. איך הויב אן מיט א סייט מיט די נאמען Codility און איך בין מניח אז קיין קאפירייטס איז נישטא נישט אויף באקאנט מאכן די סעלושענס און איך נישט אויף סקרינשוטן די פראבלעם, אין די ארגינעלע פארמאט, ווייל איך מאך עס נישט פאר געלט און די פראבלעמען זענען צוגענגליך פאר יעדעם מיט א פרייע אקאונט. איך נעם מיך נישט אונטער אייביג איבערצוטייטשן די פראבלעם דיסקרופציע אויף אידיש און ווי אויך וועל איך נישט מסביר זיין די בעסיק פראגרעמינג קאנצעפטן וואס זענען א פרי-רעקוויזיט צו פארשטיין די פראבלעמען אדער סעלושענס. איך נעם אן אז דא דרייען זיך א גענוג הויכער נומער פון מענטשן וואס קענען אדער ארבעטן אין פראגרעמינג און קענען מיטהאלטן אויף דער לעוול אהנע שוועריגקייטן. איך וועל אנהויבן מיט'ן נוצן #C אלס די שפראך אין וועלכער איך וועל אימפלעמענטן די סעלושענס. איר זענט וועלקאם צו נוצן סיי וועלכער שפראך וואס איז ריזנעבלי פארשטענדליך.

אקעי, סאוי פראבלעם #0:

א פראש זוכט אריבער צוטאנצן א שמאלע (רוהיגע) סטריעם פון וואסער. ער קען דאס נאר טוהן דורכן טאנצן אויף בלעטלעך וואס פאלן ארויף איבערן סטרעים. ער ברויך ווארטן ביז עס פארעמט זיך א ליניע פון בלעטלעך אקראס די סטריעם פון איין זייט צו די אנדערע. כדי צו אנקומען פון דער זייט סטריעם צו דאס אנדערס ברויך דער פראש טאנצן פון פאזיציע 1 צו פאזיציע X. פאלגענד איז אן אררעי וואס רעפרעזענטירט די צייטן און די פאזיציעס ווען און וואו אויף די ריווער די בלעטעלעך פאלן:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

A[0] = 1 מיינט אז אין טיים פרעים 0, א בלעטעלע פאלט אויף פאזיציע 1. די פראש קען נאר אריבערטאנצן הערשט נאכוואס אלע פאזיציעס פון 1 ביז X זענען צוגעדעקט (מען קען אננעמען אז די סטריעם איז רוהיג אזוי אז איינמאל א בלעטעלע פאלט ערגעצוואו בלייבט זי וואו זי איז. שרייב א פונקציע וואס קריגט A און א פאזיציע X, אלס פאראמעטערס. X איז די ענד פאזיציע צו וואו דער פראש ברויך אנקומען און טרעף די ערשטע טיים פרעים וואס די פראש קען אריבערטאנצן די וואסער, ווייל אלע פאזיציעס האבן א בלעטל איבער זיי.

למשל אין די פריערדיגע דוגמא: די פונקציע גיבט צוריק 6 היות ערשט אין טיים פרעים 6 פאלט א בלעטעלע אויף די לעצטע פאזיציע - 5.

📎 FrogRiverOneDesc - Copy.png

אישתישבי » מיטוואך נאוועמבער 4, 2020 5:22 pm

· #462070

די רעדסט פין פרעש.

שרייב א פאנקשען וואס גיבט צוריק אלע נעמען פין אלע פיילס אויף דער קאמפיוטער.

יוניווערסיטי_בחור » דאנערשטאג נאוועמבער 5, 2020 3:23 am

· #462088

אישתישבי
די רעדסט פין פרעש.

שרייב א פאנקשען וואס גיבט צוריק אלע נעמען פין אלע פיילס אויף דער קאמפיוטער.

די פראבלעמען זענען געשריבן געווארן דורך מענטשן וואס ארבעטן יארן אין די אינדוסטריע און די אונטערליגנדע פארבלעמען זענען אזעלכע וואס זיי שטויסן זיך אן ביי די ארבעט נאכאמאל און נאכאמאל, יעדע מאל אונטער אן אנדער שלייער און זיי האבן דערקענט א געוויסער פעטערן דערצו. די מעשה'לע איז נאר צו גיבן קאנטעקסט אבער די אנדערלייאינג פראבלעם איז נישט אוועקצומאכן אלס בלויז טעארעטיקעל.

מיך איז געליגן אויפ'ן צונג דאס וואס עמינדב האט דיך געענטפערט. און מסתמא איז דאס אויך א טריוויאל פראבלעם. איך שטעל מיך פאר אז דו הויבסט אן פון די רוט דירעקטערי און אסומינג דו האסט עדמין צו אלע דירעקטעריס און פיילס ווייטער, בעטסטו רעקורסיוולי פאר פאר די נעמען פון אלע פיילס און פאלדערס/דירעקטעריס אין די טשיילד דירעקטעריס אזוי ביז דו קומסט אן צו א ליעף. בקיצור, א באורינג פראבלעם.

גרעפיקסער » דאנערשטאג נאוועמבער 5, 2020 8:40 am

· #462094

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

יוניווערסיטי_בחור » דאנערשטאג נאוועמבער 5, 2020 3:37 pm

· #462114

#0 Solution

        public static int solution(int X, int[] A)
        {
            Dictionary<int, int> dict = new Dictionary<int, int>();//A dictionary only holds unique keys
            for (int i = 0; i < A.Length; i++)
            {
                dict.TryAdd(A[i], i);//puts the content as the key and the index as the value. If the key is already there, the item (key & value) is discarded and not added.
                if (dict.Count() == X)//max of each element is X as that covers all positions across the stream.
                    break;
            }
            if (dict.Count() < X)
                return -1;
            else
                return dict.Values.Max();

        }

איך ווייס אז ס'איז נישט די מערסט עפישענט סעלושען ווייל ס'פעסט נישט פאר גרויסע אינפוט גענוג שנעל. אויב איינער האט א שנעלערע סעלושען וואלט איך עפרישיעיטעד.

יוניווערסיטי_בחור » דאנערשטאג נאוועמבער 5, 2020 3:38 pm

· #462115

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

ווייל אפשר דעמאלטס האסטו א טשאנס זיי זאלן דיך נישט איבערנעמען.

גרעפיקסער » דאנערשטאג נאוועמבער 5, 2020 3:53 pm

· #462117

יוניווערסיטי_בחור
גרעפיקסער
אנטשולדיגט פארן זיך אריינמישן דא וויבאלד איך האב נישט קיין חלום פון פארשטיין צו פראגרעמינג, איך וויל נאר וויסן דער מיינונג פונעם עולם בנוגע זיך לערנען די זאכן היינט צו טאגס בשעת ווען זיי זאגן אז AI גייט בקרוב איבערשטייגן און איבערנעמען דעם פאך פון די מענטשהייט...

ווייל אפשר דעמאלטס האסטו א טשאנס זיי זאלן דיך נישט איבערנעמען.

נעעע.... דאס זיכער נישט.
אויב איבערנעמען גייט דאס זיין אלל די וועי! עי.איי. איז פיהל, פיהל קליגער (אין די ענינים) פון די קליגע מענטשן.

יא, מסתם גאר געציילטע, ממש די אן טאפ אף די ליין העט מען נאך דארפן האבן.

רביה''ק זי''ע » דאנערשטאג נאוועמבער 5, 2020 4:16 pm

· #462119

מ'האלט נאך זייער א ווייטע וועג אז קאמפיוטערס זאלן קענען אליינס שרייבן קאוד, ווער רעדט נאך פון שרייבן גאנצע פראגרעמס און פאררעכטן באגס, ווען דאס וועט געשעהן וועלן א גרויסע טייל דשאבס שוין לאנג זיין א פארגאנגעהייט, AI דעוועלאפמענט וועט זיין פון די לעצטע דשאבס צו גיין.

אישתישבי » דאנערשטאג נאוועמבער 5, 2020 6:48 pm

· #462133

[ציטאט אראפגענומען]

עס גיבט נישט אלע פיילס.

אישתישבי » דאנערשטאג נאוועמבער 5, 2020 6:49 pm

· #462134

יוניווערסיטי_בחור
אישתישבי
די רעדסט פין פרעש.

שרייב א פאנקשען וואס גיבט צוריק אלע נעמען פין אלע פיילס אויף דער קאמפיוטער.

די פראבלעמען זענען געשריבן געווארן דורך מענטשן וואס ארבעטן יארן אין די אינדוסטריע און די אונטערליגנדע פארבלעמען זענען אזעלכע וואס זיי שטויסן זיך אן ביי די ארבעט נאכאמאל און נאכאמאל, יעדע מאל אונטער אן אנדער שלייער און זיי האבן דערקענט א געוויסער פעטערן דערצו. די מעשה'לע איז נאר צו גיבן קאנטעקסט אבער די אנדערלייאינג פראבלעם איז נישט אוועקצומאכן אלס בלויז טעארעטיקעל.

מיך איז געליגן אויפ'ן צונג דאס וואס עמינדב האט דיך געענטפערט. און מסתמא איז דאס אויך א טריוויאל פראבלעם. איך שטעל מיך פאר אז דו הויבסט אן פון די רוט דירעקטערי און אסומינג דו האסט עדמין צו אלע דירעקטעריס און פיילס ווייטער, בעטסטו רעקורסיוולי פאר פאר די נעמען פון אלע פיילס און פאלדערס/דירעקטעריס אין די טשיילד דירעקטעריס אזוי ביז דו קומסט אן צו א ליעף. בקיצור, א באורינג פראבלעם.

איז רעד ווערטער. וואס איז דא דער טשעלענדזש?

יוניווערסיטי_בחור » דינסטאג נאוועמבער 10, 2020 5:20 pm

· #462418

מען איז שולדיג אסאך. אקעי וועלן מיר פאוסטן אפאר אויף איינמאל.

#1
שרייב א פונקשן וואס באקומט א 2D אררעי פון דאטס און סטארס. די סטארס דייטן אן מינעס אין די עריע רעפרעזענטירט ביי די 2D אררעי. די פונקשן זאל צוריקגיבן א 2D אררעי מיט נומערן ארום [אלע זייטן] יעדע אינדעקס ווי עס האט געפונען א מינע. אויב א געוויסע אינדעקס איז אדזשעסענט צו מער ווי איין מינע וועט די נומער זיין אזויפיל וויפיל מינעס עס איז אדזשעסענט צו. סאוי למשל אויב די אינפוט איז:
📎 Screenshot 2020-11-10 214619 - Copy.png
זאל די אוטפוט זיין:
📎 Screenshot 2020-11-10 214808 - Copy.png
#2
אימעדזשין אן אררעי פון N נומבערס אוואו יעדער נומבער קען זיין נאר אדער איינס אדער זיראו. די עלעמענטס אין די אררעי רעפרעזענטירן קארן אויף א הייוועי. א זיראו רעפרעזענטירט א קאר וואס פירט צו מזרח און א איינס - א קאר וואס פארט צו מערב. די גאול איז צו ציילן די פארלעך פון פארבייפארנדע קארס.

מיר זאגן אז א פארל (P, Q) אוואו P>=0, P<Q, Q<N גייען איינעם דעם צווייטן פארביי ווען P פארט צו מזרח און Q פארט צו מערב. למשל, קאנסידער אן אררעי עז אינפוט:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1

מיר האבן די פאלגנדע פינף פארלעך וואס גייען איינעם דעם צווייטן פארביי:
(0,1)
(0,3)
(0,4)
(2,3)
(2,4)

שרייב א פונקציע וואס באקומט א נישט-ליידיגע אררעי פון N נומבערס (וואו יעדע עלעמענט איז אדער איינס אדער זיראו) און ס'זאל צוריקגעבן די נומבער פון פארבייפארנדע פארלעך. אויב די נומער פון פארבייפארנדע פארלעך איז מער פון א ביליאן, זאל די פונקציע צוריקגעבן נעגעטיוו 1. די לופ זאל נישט זיין מער ווי 0(n). דאס הייסט ס'זאל נישט האבן א נעסטעד לופ.
📎 Screenshot 2020-11-10 220958 - Copy.png

#3
לו יצוייר אן אררעי פון N אינטעדזשערס איז פעססד.א פערמיוטעישן איז ווען יעדע אינטעדזשער פון איינס ביז N געפינט זיך אין די אררעי נאר איינמאל. ד.מ. למשל אויב איז איין נומבער אויסגעלאזט אדער געדאפלט איז עס נישט קיין פערמיוטעישן. לדוגמה:
A[0] = 4
A[1] = 1
A[2] = 3
A[3] = 2

איז א פערמיוטעישן.

אבער:
A[0] = 4
A[1] = 1
A[2] = 3

איז נישט א פערמיוטעישן.

שרייב א פונקציע וואס געגיבן אן אררעי מיט N אינטעדזשערס גיבט צוריק 1 אויב די אררעי איז א פערמיוטעישן און 0 אויב ס'איז נישט.

📎 Screenshot 2020-11-10 221707 - Copy.png

יוניווערסיטי_בחור » מיטוואך נאוועמבער 11, 2020 1:10 pm

· #462445

Problem #4

Write a function that given an array returns how many of the elements have their right and left
neighbours' sum equal to twice their own value. That is a[i] *2 == a[i-1] + a[i+1]
If there isn't a right or a left neighbour, treat the right or left value as 0
Your function should not explicitly check if i is out of bounds. For eg { 2, 4, 6, 6, 3 } returns 3

יוניווערסיטי_בחור » דאנערשטאג נאוועמבער 12, 2020 3:40 am

· #462478

Solution #1 in Java

[code=php]import java.util.ArrayList; public class Main { public static void main(String[] args) { System.out.println(); mineFinder(new char[][]{ {'*', '.', '.', '.'}, {'.', '.', '.', '.'}, {'.', '*', '.', '.'}, {'.', '.', '.', '.'} }); System.out.println(); mineFinder(new char[][]{//example of two asterisks next to each other {'*', '.', '.', '.'}, {'.', '*', '.', '.'}, {'.', '.', '.', '.'}, {'.', '.', '.', '.'} }); } public static int[][] mineFinder(char[][] arr) { int[][] mapped = new int[arr.length][arr[0].length]; for (char i = 0; i < arr.length; i++) {//loop to replace 0 for dots and a number below zero representing // the number of possible adjacent asterisk you can have next to each other; as we don't want to override //an asterisk which sits next to another. for (char j = 0; j < arr[0].length; j++) { if (arr[i][j] == '.') mapped[i][j] = 0; else mapped[i][j] = -8; } } for (int i = 0; i < mapped.length; i++) {//outer nested loop to traverse 2D array for (int j = 0; j < mapped[0].length; j++) { if (mapped[i][j] < 0) { for (int r = i - 1; r < i + 2; r++) {//inner nested loop to check all round a given asterisk for out of bounds for (int c = j - 1; c < j + 2; c++) { if (r >= 0 && c >= 0 && r < arr.length && c < arr[0].length && !(r == i && c == j)) { mapped[r][c]++;//every time we find an asterisk, we're bumping up all indices around it by one } } } //inner two loops ends } } } for (int i = 0; i < arr.length; i++) {//formats arr back to numbers and asterisks for (int j = 0; j < arr[0].length; j++) { if (mapped[i][j] < 0) arr[i][j] = '*'; else arr[i][j] = (char) (mapped[i][j] + '0');//49 is ASCII value for 1. (0 is 48.) System.out.print(arr[i][j]); } System.out.println(); } return mapped; } } [/code]

יוניווערסיטי_בחור » דאנערשטאג נאוועמבער 12, 2020 3:52 am

· #462481

Solution #2

[code=php] public static int solution(int[] A) { int numOfOs = A.Count(i => i == 0); int count = 0; var zerosFound = 0; for (int i = 0; i < A.Length; i++) { if (A[i] == 0) { zerosFound++;//record every zero found count += (A.Length - (i + 1)) - (numOfOs - zerosFound);//the number of permutations is: for every zero found, the sums of all the subsequent 1s added together //or, the number of 1s multiplied by the number of 0s that come strictly before (leftwards) themselves. //So each time we encounter a 0, the number of 1s left to find is the number of indices left, minus the number of 0s left to find. if (count > 1000000000) return -1; } } return count; } [/code]

יוניווערסיטי_בחור » דאנערשטאג נאוועמבער 12, 2020 3:54 am

· #462482

Solution #3 (permutations)

[code=php] public static int solution(int[] A) { HashSet<int> hashSet = new HashSet<int>(); foreach (var e in A) hashSet.Add(e);//deals with duplicates if (hashSet.Count() < A.Count()) return 0; return A.Except(Enumerable.Range(1, A.Length)).Count()==0 ? 1 : 0; //deals with omissions } [/code]

יוניווערסיטי_בחור » דאנערשטאג נאוועמבער 12, 2020 3:56 am

· #462484

(arithmetic means) Solution #4

[code=php] public static int countArithmeticMeans(int[] a) { int count = 0; int prev = 0; int i; for (i = 0; i < a.Length - 1; i++) { if (a[i] * 2 == prev + a[i + 1]) count++; prev = a[i]; } if (a[i] * 2 == prev) count++; return count; }[/code]

יוניווערסיטי_בחור » פרייטאג נאוועמבער 13, 2020 2:30 am

· #462544

Problem #5

דאס איז שוין אביסל שווערער.

דו ווערסט געגיבן N קאונטערס, אנהויב זענען אלע 0. די קאונטערס האבן צוויי אפערעישאנס מען קען טוהן אויף זיי.

אינקריסן אן אינדיווידועל קאונטער X מיט איינס
אינקריסן אלע קאונטערס צו די וואליו פון די יעצטיגע העכסטע קאונטער פון צווישן אלע קאונטערס.

חוץ מזה, ווערסטו אויך געגיבן אן אררעי A וואס רעפרעזענטירט א רייע אפערעישאנס/אינסטרוקשנס צו אויספירן אויף די קאונטערס. אויב איז A[K] = X אוואו X >= 1 און X<= N טוט עס אנדייטן דו זאלסט אינקריסן קאונטער אויף פאזישען X-1 מיט איינס. אויב איז X>N מיינט עס אז אלע קאונטערס ברויכן ווערן סעט צו די מאקסימום קאונטער. ד.ה. צו די וואליו פון די העכסטע קאונטער פון צווישן אלע קאונטערס.

צום ביישפיל, לו יצוייר N איז 5 און A איז:
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

וועלן די וואליוס פון די קאונטערס נאך יעדע קאנזעקיוטיוו אפעראציע, אויסקוקן אזוי:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

די גאול פון די פונקשן וואס דו דארפסט שרייבן איז אויסצורעכענען די וואליוס פון אלע קאונטערס נאכ'ן אויספירן אלע אפעראציעס פון אררעי A. שרייב א פונקשן int[] solution(int N, int[] A) וואס טוט דאס.

סאוי לדוגמה פאר די אינפוט אויבן, זאל די פונקשן צוריקגעבן [3, 2, 2, 4, 2]. (די רון טיים זאל נישט זיין לענגער ווי (n)0)

📎 Screenshot 2020-11-13 072705 - Copy.png

יוניווערסיטי_בחור » פרייטאג נאוועמבער 13, 2020 7:54 am

· #462553

Solution #5

כ'האב מיך סאפיסטיקירט.
[code=PHP] using System.Collections; using System.Linq; Console.WriteLine(string.Join(",", solution(5, new int[] { 3, 4, 4, 6, 1, 4, 4 })));//-> [3, 2, 2, 4, 2] public static int[] solution(int N, int[] A) { var max = 0; int[] counters = new int[N];//we're going to store here the results of the Increase(X) (or 'bumpup') operations; ignoring the MaxCounter(all Xs) operations for now. Hashtable indexesChanged = new Hashtable(); if (A.Where(i => i <= counters.Length).Count() < 1) return counters; else { for (int i = 0; i < A.Length; i++) { if (A[i] <= counters.Length) { counters[A[i] - 1]++; if (!indexesChanged.ContainsKey(A[i] - 1))//stores how many changes (Increase ops) we've made to this index in 'counters' in between MaxCounter operations indexesChanged.Add(A[i] - 1, 1); else indexesChanged[A[i] - 1] = ((int)indexesChanged[A[i] - 1]) + 1; } else { if (indexesChanged.Count > 0)//each time we have an MaxCounter operation, if any bumpups were made in between, we're adding to max //the biggest new change (since the last MaxCounter operation) we've made to a single index in 'countres' { max += indexesChanged.Values.Cast<int>().Max(); indexesChanged.Clear();//we're clearing the hashtable in order to start a new 'bumpup series' } } } for (int j = 0; j < counters.Length; j++) { if (indexesChanged.Contains(j) && counters[j] < max)//if we've changed this index in 'counters' since the last MaxCounter we need this index to be 'max' plus the last changes/bumpups //except if it's the same index that was the max at the last MaxCounter operation in which case it will already have the additional changes as well as max.. counters[j] = max + (int)indexesChanged[j]; else if (counters[j] < max)//if this index had no changes done to it the last time round (or also if the last instruction was a MaxCounter) or if it had increasements but is already >=max, we don't want to override it with a lower number. counters[j] = max; } return counters; } }[/code]

יוניווערסיטי_בחור » זונטאג נאוועמבער 15, 2020 3:49 am

· #462575

Problem #6

Problem #6

שרייב א פונקשן וואס קריגט א 2D אררעי מיט קערעקטערס (אדער סטרינג קערעקטערס) אינעווענדיג און קאנקעטענעיטס די קערעקטערס שורה'ווייז אבער אין דיאגאנעלס. (דו מעגסט אננעמען אז די נומבער פון ראוס איז די זעלבע ווי די נומבער פון קאלומס.) אסיין צו יעדע שורה אן אינדעקס פון איינס ביז וויפיל דיאגאנעלס עס זענען פארהאן אין די אררעי, אנגעהויבן פון די באטעם לינקס קארנער פון די אררעי. נאכדעם, רי-ארדער די סטרינגס אקארדינג צו לעקסיאגראפיק ארדערינג און געב צוריק א 1D אררעי, ווייזענדיג די אלטע אינדעקסעס (די דיאגענאלס) ווי אזוי זיי (די סטרינגס) ליגן אין די נייע סדר. ד.ה. אנשטאט צו ווייזן די עקשועל סטרינגס אין די נייע סדר, ווייז בלויז די פון-פריער אסיינד אינדעקסעס. למשל, אויב דו באקומסט א 2D אררעי וואס קוקט אויס אזוי:

זאל די רעזאלץ זיין: {5,3,2,1,4}.

פשט איז: עס זענען דא 5 דייאגענאלס (אויב n איז די נומבער פון ראוס (און קאלומס) איז פארהאן n*2-1 דייאגענאלס). זיי זענען: c, bc, abd, ca, a

און די לעקסיאגראפיק ארדערינג איז: a, abd, bc, c, ca

📎 Screenshot 2020-11-15 081443 - Copy.png

יוניווערסיטי_בחור » מאנטאג נאוועמבער 16, 2020 5:26 am

· #462621

Solution #6

[code=php] static int[] diagonalsArranging(string[,] a) { int diagonals = (a.GetLength(0) * 2) - 1;//GetLength(0) gets the length of rows (GetLength(1) the length of columns and so on for each dimension) Dictionary<int, string> concatenatedStrs = new Dictionary<int, string>();//we're using a dictionary where the index of each diagonal is the key for (int r = a.GetLength(0) - 1; r >= 0; r--)//starts off with row equaling to bottom left corner, decreasing row (until row = 0) after every inner traversal of columns (to the right) { string concat = ""; int row = r; for (int c = 0; c < a.GetLength(0) - r; c++)//number of columns to traverse to the right gets ever so more as we decrease row (or is proportional to row reduction) { concat += a[row, c]; row++; } concatenatedStrs.Add((a.GetLength(0) * 2) - diagonals, concat);//the first index should be 1; not 0. Since we're not on row 1 (nor col 1) we have to do this trick) diagonals--; } for (int c = 1; c < a.GetLength(1); c++)//now we do the second half diagonals (top right corner) { string concat = ""; int col = c; for (int r = 0; r < a.GetLength(0) - c; r++)//number of rows left to traverse to the right gets ever so diminished as we increase col number (or is proportional to column increase) { concat += a[r, col]; col++; } concatenatedStrs.Add((a.GetLength(0) * 2) - diagonals, concat); diagonals--; } var ordered = concatenatedStrs.OrderBy(i => i.Value);//re-order return ordered.Select(i => i.Key).ToArray();//a map function to extract keys only from dictionary and transform to array which is the returned value }[/code]

יוניווערסיטי_בחור » מאנטאג נאוועמבער 16, 2020 4:45 pm

· #462654

#7

שרייב א פונקשן וואס באקריגט א נומבער A און א נומבער B אנצודייטן א רעינדזש פון A ביז B אינקלוסיוו; און א נומבער K צווישן 1 און B. (A און B קענען זיין פון 0 ביז 2 ביליאן (מעקס int) אינקלוסיוו.)

די פונקשן זאל צוריקקערן די נומבער פון וויפיהל נומבערס אין די רעינדזש צווישן A און B לאזן זיך דיוויידן פונקטליך ביי K. ד.ה. { i : A ≤ i ≤ B, i mod K = 0 }

סאוי למשל פאר A = 6, B = 11 and K = 2 זאל די פונקשן צוריקגעבן 3 ווייל אין די רעינדזש פון [11..6] זענען פארהאן דריי נומבערס וואס זענען דיוויזיבעל ביי 2. דהיינו, 6,8 און 10.
📎 Screenshot 2020-11-16 213751 - Copy.png
#8

שרייב א פונקשן וואס באקומט אן אררעי מיט נומבערס (מעגליך דופליקעיטס) און געבט צוריק די נידריגסטע פאזעטיווע נומבער (נומבער העכער זיראו) וואס פעהלט אין די אררעי. אויב איז נישטא אזא נומבער (למשל אלע נעגעטיוו) זאל די פונקשן צוריקקערן 1.

📎 Screenshot 2020-11-16 214348 - Copy.png

יוניווערסיטי_בחור » דינסטאג נאוועמבער 17, 2020 8:12 am

· #462685

Solution 7 & 8

Solution #7

[code=php] public static int solution(int A, int B, int K) { if (K > B && A > 0) return 0; else if (K > B)//return 1 for 0 as explained below return 1; long count = 0;//we need to handle when B is 2 billion for (int i = B; i >= A; i--)//start of from the highest number { if (i % K == 0)//else it maybe a prime { count = (((long)(i - A)) + K) / K; //if A is 0, add one multiple of K for 0 is divisible by all numbers. if not, still add one multiple of K for the number you’re subtracting (A). break; } } return (int)count; } [/code]

Solution #8

[code=php] public static int solution(int[] A) { HashSet<int> hs = new HashSet<int>(); var B = A.OrderBy(i => i).ToArray(); var startInd = Array.IndexOf(B, B.Where(i => i > 0).Count() > 0 ? B.First(i => i > 0) : 1);//if the array contains positive values, get the index of the first and lowest positive item if (startInd < 0)//if there are no positive numbers, 1 will also not be found and will set startInd to -1. return 1; ; for (int j = startInd; j < A.Length; j++) hs.Add(B[j]);//deals with dups int e = 1; while (hs.Contains(e)) { e++; } return e; }[/code]

יוניווערסיטי_בחור » זונטאג נאוועמבער 29, 2020 2:00 pm

· #463353

Problem #9

Problem #9

נאך איינס פון די שווערערע.

א דנ"א סיקווענס קען ווערן רעפרעזענטירט דורך א סטרינג פון א סיקווענס פון איינע, עטליכע אדער אלע פון די פאלגנדע לעטטערס A, C, G און T. יעדע פון די לעטטערס זענען אסאציאירט מיט אן אימפאקט פאקטאר פון 1,2,3,4 רעספעקטיוולי. דו וועסט שרייבן א פונקשן וואס וועט ענטפערן א רייע פראגן/קוועריס, אלע פון די פארעם פון, וואס איז די נידריגסטע אימפאקט פאקטאר וואס דו קענסט טרעפן אין א געוויסע פארשן (פארציע) אין די דנ"א סיקווענס.

שרייב א פונקשן public int[] solution(String S, int[] P, int[] Q) וואס באקומט א סטרינג S אלס די דנ"א סיקווענס, אנטהאלטנדיג די לעטטערס S[0] S[1]...S[N-1]. די פונקשן וועט אויך באקומען צוויי אררעיס P און Q פון M אינטעדזשערס, וואס צוזאמען רעפרעזענטירן די קוועריס וואס מ'ברויך ענטפערן אויף S. פאר יעדע Kth אינדעקס אין P[K] און Q[K], די ציהל איז צו ענטפערן וואס איז די מינימאל אימפאקט פאקטאר אין די דנ"א סטרינג S צווישן פאזיציעס Q[K] און P[K] אינקלוסיוו. ד.ה. צווישן S[Q[K]] און S[P[K]]. מ' ועד בכלל. די פונקשן זאל צוריקגעבן אן אררעי מיט א ליסט פון די פאזיציעס צו יעדע פון די קוועריס. למשל:

אז דו באקומסט די סטרינג CAGCCTA און אררעיס P און Q אזוי אז:
P[0] = 2 Q[0] = 4
P[1] = 5 Q[1] = 5
P[2] = 0 Q[2] = 6

וועט די ענטפער זיין אין דער ארדער:
- צווישן פאזיציע 2 און 4, געפינט זיך די סטרינג GCC, איז די ענטפער 2.
- צווישן פאזיציע 5 און 5 געפינט זיך בלויז T, וועמענס אימפאקט פאקטאר איז 4, אלזא איז די ענטפער 4.
- צווישן פאזיציע 0 און 6, געפינט זיך די גאנצע סטרינג, איז די ענטפער 1.

סאוי, די פונקשן געבט צוריק [2,4,1].

די פונקשן זאל נישט האבן א ראן טיים לענגער פון (n)0.

📎 GenomicRangeQuery - Copy.png

יוניווערסיטי_בחור » מאנטאג נאוועמבער 30, 2020 1:07 pm

· #463409

Solution #9

איך האב שוין געטראפן א דזשאב במילא ווייס איך נישט וויפיהל צייט איך וועל האבן צו ווייטער ממשיך זיין און ס'זעט אויך נישט אויס אז איינער חוץ @מי אני איז אינטרעסירט אבער פאר מיין אייגענע טובה, צו בלייבן שארף, וועל איך פרובירן פון צייט צו צייט צו פאוסטן.

Solution #9

באזירט אויף Prefix sums method, א קאנצעפט דעסקרייבד דא: <a class="postlink" href="https://codility.com/media/train/3-PrefixSums.pdf">https://codility.com/media/train/3-PrefixSums.pdf</a>

די עקשועל [עפישענט] סעלושן האב איך נישט געקענט אויספיגערן ביז איך האב געקוקט דא: <a class="postlink" href="https://stackoverflow.com/questions/19552754/java-codility-training-genomic-range-query">https://stackoverflow.com/questions/195 ... ange-query</a>

מיין סעלושן איז בעיסיקלי די ערשטע ענטפער אין דער טרעד^ נאר כ'האב גענוצט א צווייטע דאטא סטרוקטור און מיט א סלייטלי דיפערענט צוגאנג.

[code=php] public static int[] solution(string S, int[] P, int[] Q) { //Foreach character in S, we're going to add an element/tuple of 3 entries to 'prefixSums'. The elements in 'prefixSums' will indicate how many As, Cs, Gs and Ts we found in the string, // with each entry in the tuple indicating a different letter, A, C and G respectively. (See later what we do about T). // So, for 3 of these 4 different characters, A C G and T, we have counters that we'll bump up each time we encounter one. One counter for each character. (0, 1, 2) = (A, C, G). // By bumping up the relevant counter for each occurrence of the letter it is associated with, they'll in the end serve as accumulators for how many times we encountered the relevant character in the string. // Every letter we move forward, we add a new element to 'prefixSums' and have all the counters in the new element take on (we assign to them) the values of the previous counter at their respective positions, // as well as adding a 1 if the letter that's associated with 'this' counter is found at the current position and a 0 if not. //To answer the queries, we find out for a given S[P[K]] to S[Q[K]] the minimal factor within this boundary, by subtracting the counter at element P[K] in 'prefixSums' // [for the relevant factor/letter - i.e. starting from lowest to highest, that is index (firstIndex, second, third)] // from the counter at the same position in element Q[K] in 'prefixSums', to see if we're left with a number more or equal to 1. This will tell us, that in between these two positions in S, a letter associated with the factor of this value [i.e. 1, 2, or 3] was found //For the forth character T (i.e. factor 4), we don't need a separate counter as we can indicate its occurrence by merely adding a new element to 'prefixSums' where all the counters remain unchanged from the previous element in 'prefixSums'. List<Tuple<int, int, int>> prefixSums = new List<Tuple<int, int, int>>() { Tuple.Create(0, 0, 0) }; int[] minimalIF = new int[P.Length]; var i = 0; foreach (var ch in S) { Console.WriteLine(prefixSums.Count()); switch (ch)//here the string is traversed, and the counters are set accordingly { case 'A': prefixSums.Add(Tuple.Create(1 + prefixSums.ElementAt(i).Item1, prefixSums.ElementAt(i).Item2, prefixSums.ElementAt(i).Item3)); break; case 'C': prefixSums.Add(Tuple.Create(prefixSums.ElementAt(i).Item1, 1 + prefixSums.ElementAt(i).Item2, prefixSums.ElementAt(i).Item3)); break; case 'G': prefixSums.Add(Tuple.Create(prefixSums.ElementAt(i).Item1, prefixSums.ElementAt(i).Item2, 1 + prefixSums.ElementAt(i).Item3)); break; default: prefixSums.Add(Tuple.Create(prefixSums.ElementAt(i).Item1, prefixSums.ElementAt(i).Item2, prefixSums.ElementAt(i).Item3)); break; } i++; } foreach (var p in prefixSums) Console.WriteLine(p); for (int j = 0; j < P.Length; j++)//here we answer the queries { if (prefixSums.ElementAt(Q[j] + 1).Item1 - prefixSums.ElementAt(P[j]).Item1 > 0) minimalIF[j] = 1; else if (prefixSums.ElementAt(Q[j] + 1).Item2 - prefixSums.ElementAt(P[j]).Item2 > 0) minimalIF[j] = 2; else if (prefixSums.ElementAt(Q[j] + 1).Item3 - prefixSums.ElementAt(P[j]).Item3 > 0) minimalIF[j] = 3; else minimalIF[j] = 4; } return minimalIF; } [/code]

יוניווערסיטי_בחור » מיטוואך דעצעמבער 2, 2020 4:52 am

· #463527

Problem #10

דו באקומסט אן אררעי A מיט N אינטעדזשערס. א פארל (pair) פון אינטעדזשערס (P,Q) אזוי אז P>=0, Q>P, N>Q, ווערט אנגערופן א סלייס פון אררעי A. (א סלייס קען נישט האבן ווינציגער פון צוויי עלעמענטס.) די עווערידזש פון א סלייס איז די סומע פון די סלייס A[P] + A[P + 1] + ... + A[Q] דעוויידעד ביי די לענג פון די סלייס. סאוי, (Q − P + 1) / (A[P] + A[P + 1] + ... + A[Q]) (היות אין קאמפיוטינג גייען מיר אייביג לויט די 0 בעיסד אינדעקס). לדוגמה, אויב אררעי A זעהט אויס אזוי:

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

זענען דא אין אררעי A, צווישן אנדערע, די פאלגענדע סלייסעס:
סלייס (2, 1) וועמענס עווערידזש איז -> 2 = 2 / (2 + 2)
סלייס (4, 3) וועמענס עווערידזש איז -> 3 = 2 /(5 + 1)
סלייס (4, 1) וועמענס עווערידזש איז -> 2.5 = 4 / (2 + 2 + 5 + 1)

די גאול איז צו טרעפן די ערשטע (אדער אנהויבענדיגע) פאזיציע פון א סלייס וועמענס עווערידזש איז די קלענסטע פון צווישן אלע מעגליכע סלייסעס אין די אררעי. סאוי טרעף א סלייס וועמענס עווערידזש איז מינימאל און פון דעם, געב צוריק די סטארטינג פאזישען פון דער סלייס. שרייב א פונקשן public int solution(int[] A) וואס גיבענדיג אים א נישט-ליידיגע אררעי פון N אינטעדזשערס, קערט אום די בעגינינג/סטארטינג פאזישען פון א סלייס מיט די מינימאל עווערידזש אין אררעי A. אויב איז דא מער פון איינס אזא סלייס, זאל די פונקשן אומקערן די נידריגסטע סטארטינג פאזישען פון אזא סלייס (דהיינו, פון די ערשטע אזא סלייס). למשל, פאר די אויבנדערמאנטע עקזעמפל פון אררעי A, די ענטפערן זאל זיין 1 ווייל די די ערשטע פאזישען פון די סלייס וואס פארמאגט די מינימעל עווערידזש איז סלייס (2, 1) וועמענס עווערידזש איז -> 2 = 2 / (2 + 2), ווי שוין אויבן ערקלערט.

די פונקשן זאל נישט האבן א ראן טיים לענגער פון (n)0.

📎 MinAvgTwoSlice - Copy.png

יוניווערסיטי_בחור » מיטוואך דעצעמבער 9, 2020 5:02 pm

· #463933

Solution 10

[code=php]//The way we do this is by first realizing that for each element in array A, you only need to check //all two and three sub arrays of the original array and not more (that is, for each element in array A, starting from the left, its combination with the element next to it once, and then again its combination //with the next element, + the element next to that one. eg. {1 2 3 4} -> (1, 2), (1,2,3), (2,3),(2,3,4), (3,4)), and keep comparing, all the while resetting //the smallest subarray to the smallest found so far. //The reason being that as soon as you find subarray s that contains the MA, ( minimal/smallest avg), a bigger subarray ss that includes the smaller one s will //'also' contain the smallest avg (You need at least two elements as two is the minimum definition of a subarray as per the problem description.). //So, more concretely, take an example of a comparison of a subarray a of size 2 to a subarray b of size 3 (that also includes the subarray a of size 2), if the avg of subarray a is smaller, than the avg of subarray b - that's simple - as we can then say/know //two things: 1) subarray b as it is, has a higher MA than subarray a without b and hence the starting index remains in a. (All we have left to do is check which index in a causes the MA, by checking element 2 in A in combination with element 3 in A; something which we'll do anyway since we check all contiguous subarrays of 2.) //and 2) even if we were to add further elements to b, i.e. create a subarray c that also includes b, and their content rate of increase will be lower than the rate of increase of the number of elements reached, they'll still never cause the MA to move over from subarray a to b //because the minimal avg in c will still be b, which is more than a; and out of A, a is still the minimal avg. And so on it goes..) //On the other hand, if b is shown to contain the MA and not a (that is, the starting index of the subarray that contains the MA is the third element in A), then we know that however more elements we would extended b to, its starting index will never move from the position it is now //because even if further indexes' contents cause the MA to decrease (if they cause to increase, it's simple to see that the starting index remains where it is) that can only happen because //of the same concept described earlier, that is, the rate of content increase [i.e. the integers/content you're getting by each added subsequent index] is smaller compared to the divisor increase [i.e. the index numbers that are constantly increasing by 1 because of extending b] //and so, as long this is true, the starting index cannot move. Note, if the avg of subarray of 2 is equal to avg of subarray of 3, which is certainly possible, the question specification outline that in such scenario, the starting index of the first 'minimal avg subarray' is returned and so we're good anyway. public static int solution(int[] A) { int[] B = new int[A.Length + 1]; int i = 0; int j = 1; int copiedVal = A[1]; A[1] = A[1] + A[0]; double min = (double)A[1] / 2; int pos = 0; while (j < A.Length - 1 || (j < A.Length && i == 0))//a refactored version of a previous solution which had n*n-1/2 run time and was done with just one While loop and a bit of trickery. //so this still uses one while loop and knows when to change inner loop by checking if there's still 2s or 3s left in A to check. { B[i + 1] = B[i] + A[i + j];//uses prefix sums to get subarrays of 2s and 3s if ((double)B[i + 1] / (i + 2) < min)//calculating and comparing the MA subarrays { min = (double)B[i + 1] / (i + 2); pos = j - 1; } if (i == 1)//check for exiting the inner loop { A[j] = copiedVal; j++; copiedVal = A[j]; A[j] = A[j] + A[(j - 1)]; i = -1; } i++; } return pos; } [/code]