java - How is Reservoir Sampling being used here? -


i solving question on leetcode, based on concept of reservoir sampling (rs). question is:

given array (that may contain duplicates), randomly output index of given target number. target number guaranteed exist in array. e.g., if input is: {1,2,3,3,3} , target 3, of indices 2, 3 , 4 must returned equal probability. similarly, if target 1, index 0 should returned (obviously probability of 1).

the upvoted code follows:

public class solution {      int[] nums;     random rnd;      public solution(int[] nums) {         this.nums = nums;         this.rnd = new random();     }      public int pick(int target) {         int result = -1;         int count = 0;         (int = 0; < nums.length; i++) {             if (nums[i] != target)                 continue;             if (rnd.nextint(++count) == 0)                 result = i;         }          return result;     } }

as understand rs, first select, n numbers. then, when select next number, need select probability, 1/(n+1). how does:

rnd.nextint(++count) == 0

select number probability of 1/(n+1)? understand ++count make n+1, happened numerator? why rnd.nextint() instead of simple 1?

edit: question link here.

okay, have statement rnd.nextint(++count) == 0

the first time hit target, count increments 1 , statement evaluates to

rnd.nextint(1) == 0

which returns true, because argument 1 exclusive upper bound , possible value may return 0. @ point, current index set result, because not know if there more targets in array.

the second time encounter target, count becomes 2 , statement evaluates to

rnd.nextint(2) == 0

and 1 returns either 0 or 1. hence, index has 50% chance selected result.

so there 2 known targets in array , both had 50% chance set result. second target had chance obvious, first target can small calculation. had 100% percent chance chosen first time code hit if-statement , second time there 50% chance second target did not become result (leaving 50% chance first target remained result). these chances combined results in

first target result = 100% x 50% = 50%

these steps can repeated more 2 targets, makes explanation lot more complex. in end, n targets in array have 1/n chance of being result.


Comments

Post a Comment

Popular posts from this blog

What is happening when Matlab is starting a "parallel pool"? -

running parallel cpu processes in matlab starts command parpool() according documentation , function: [creates] special job on pool of workers, , [connects] matlab client parallel pool. this function takes bit of time execute, on order of 30 seconds. in other multi-cpu paradigms openmp, parallel execution seems totally transparent -- i've never noticed behavior analogous matlab (granted i'm not experienced parallel programming). so, happening between time parpool() called , when finishes executing? takes long? parallel computing toolbox enables run matlab code in parallel using several different paradigms (e.g. jobs , tasks, parfor , spmd , parfeval , batch processing), , run either locally (parallelised across cores in local machine) or remotely (parallelised across machines in cluster - either 1 own, or 1 in cloud). in of these cases, code run on matlab workers , copies of matlab without interactive desktop. if you're intending run on remo...
Read more

angular - DownloadURL return null in below code -

when change file updated in firebase storage when try downloadurl show null. filechange(event: any) { const imagefolder: string = this.employee.id; const filelist: filelist = event.target.files; const file: file = filelist[0]; const storageref = firebase.storage().ref().child(`${imagefolder}/profile.jpg`).put(file); console.log(storageref.snapshot.downloadurl); } the put() asynchronous. if want url after file uploaded have this: firebase.storage().ref().child(`${imagefolder}/profile.jpg`).put(file).then((snapshot) => { storageref = snapshot.downloadurl: console.log(snapshot.downloadurl); });
Read more

php - Cannot override Laravel Spark authentication with own implementation -

during login process of laravel spark need request token of remote api. api stores exact same users , passwords laravel spark application. therefore need username , non hashed password of user during authentication process. i thought overriding authenticated method solution problem. in routes/web.php override post /login endpoint , pointing endpoint own logincontroller: <?php namespace app\http\controllers\auth; use illuminate\support\facades\log; use illuminate\http\request; use laravel\spark\http\controllers\auth\logincontroller sparklogincontroller; class logincontroller extends sparklogincontroller { /** * create new login controller instance. * * @return void */ public function __construct() { parent::__construct(); } /** * handle successful authentication attempt. * * @param request $request * @param \illuminate\contracts\auth\authenticatable $user * @return response */ public fu...
Read more