algorithm - Integer assignment in range -


i'm looking algorithm assigns , releases integers interval [a,b].

every time request assignment, algorithm produces integer in [a,b] range has not been assigned before. may free integers had been assigned asking algorithm release them. doing makes them available assignment again.

to summarise:

  • after integer assigned, cannot assigned again until released
  • if 1 or more integers not assigned, algorithm must assign 1 of them
  • if , if integers in range assigned, algorithm assigns none

it desired both time , space complexity of algorithm sub-linear (for n = b - a).

as bonus requirement, assume specific integers in [a,b] required assigned.

the first thing comes mind start single "available" range. when user assigns integer, remove range:

        [a,b] <---  [a+1,b]

this o(1) operation in cases. due way return step works, means maximum number assigned when no other number available, , low numbers reused possible.

when user returns integer, binary search figure out range either goes before, or merges into:

[28][30-50]     <---- user going release 29 [28-50] -or- [26][30-50]     <----- user going release 28 [26][28][30-50]

this o(log m) operation m number of ranges, small. starts @ 1, can @ n/2 depending on numbers user releases.

if want tricky, can add second ordering on ranges, moves smaller ranges closer toward "front", , larger ranges closer "end", , when user makes number "available", give them first value in "smallest" range, heuristically lead smaller sets being "consumed", leaving fewer sets total, saving space on average. however, adds lot of complexity, , small amount of space , time, worst cases worse. measure first before trying this.

it's worth mentioning does use linear space, though i'm pretty sure constant <=1, memory overhead less of storing of numbers. it's hard calculate average without making wild assumptions how user assigns , releases integers, i'm pretty sure average memory usage closer logarithmic linear. hard tell though, might optimism.

some dynamic memory dispatches work on similar concepts this, storing "unused" parts linked list inside unused memory. way, there's no additional overhead space required. since you're dealing integer ranges rather heap memory, optimization doesn't you.


Comments

Post a Comment

Popular posts from this blog

commonjs - How to write a typescript definition file for a node module that exports a function? -

consider, toml node module can use: // toml.d.ts declare module toml { export function parse(value:string):any; } declare module "toml" { export = toml; } then: /// <reference path="../../../../../defs/toml/toml.d.ts"/> import toml = require('toml'); toml.parse(...); however, node module export single function, such 'glob' ( https://github.com/isaacs/node-glob ). the node usage of module be: var glob = require("glob") glob("*.js", {}, callback(err, files) { ... }); you'd naively expect this: // glob.d.ts declare function globs(paths:string, options:any, callback:{(err:any, files:string[]):void; ...but because typescripts 'import' semantics bit strange, seems can use 'import .. = require()' statement alias modules . trying call: /// <reference path="../../../../../defs/glob/glob.d.ts"/> import blog = require('glob'); results in: error ts2072: mod
Read more

openid - Okta: Failed to get authorization code through API call -

i'm integrating okta own idp server using okta's api. i'm implementing authorization code flow following steps below: in own server, use /api/v1/authn endpoint sessiontoken. use sessiontoken obtain authorization calling endpoint: /oauth2/v1/authorize?client_id=" + clientid + "&sessiontoken=" + sessiontoken + "&response_type=code&response_mode=query&scope=openid&redirect_uri=" + redirecturl + "&state=evanyang&nonce=" it's supposed return response status code 302 , location header containing redirect url code value. however, keep getting response status code 200 , without location header, html body saying "you using unsupported browser." , "javascript disabled on browser." according api documentation: http://developer.okta.com/docs/api/resources/oidc.html#authentication-request , sessiontoken parameter sufficient this: an okta one-time sessiontoken. allows api-based
Read more

thorough guide for profiling racket code -

did googling ("racket profiling", "racket measure performance"), didn't find , there no examples in docs. did google "profile" search on htdp - no luck. (profile (f ...)) output isn't obvious other small snippets. ideally want python's python -m cprofile usage examples. when search "python profiling", both duckduckgo , google give top result: 26.4. python profilers . (although scanned quickly, seems more of reference "thorough usage guide" examples. if had else in mind, perhaps please link that?) the equivalent racket documentation be: profile: statistical profiler . a usage example: #lang racket (require profile) (profile-thunk (thunk (function-to-profile arg0 arg1) )) here (thunk e) convenience (lambda () e) . bigger example: #lang racket (module mod racket (provide f) (define (f) (for/list ([i 10000]) i))) (require (prefix-in mod: 'mod)) (define (f) (for ([i 10000
Read more