arrays - Is it possible to do 3-sum/4-sum...k-sum better than O(n^2) with these conditions? - Tech Interview -


this classic problem, curious if possible better these conditions.

problem: suppose have sorted array of length 4*n, is, each element repeated 4 times. note n can natural number. also, each element in array subject constraint 0 < a[i] < 190*n. there 4 elements in array such a[i] + a[j] + a[k] + a[m] = v, v can any positive integer; note must use 4 elements , can repeated. not requirement find 4 elements satisfy condition, rather, showing can done given array , v enough.

ex : = [1,1,1,1,4,4,4,4,5,5,5,5,11,11,11,11] v = 22

this true because, 11 + 5 + 5 + 1 = 22.

my attempt:

instead of "4sum" first tried k-sum, proved pretty difficult instead went variation. first solution came rather naive o(n^2). however, given these constraints, imagine can better. tried dynamic programming methods , divide , conquer, didn't quite me anywhere. specific, not sure how cleverly approach in way can "eliminate" portions of array without having explicitly check values against or permutations.

  1. make vector s0 of length 256n s0[x]=1 if x appears in a.
  2. perform convolution of s0 produce new vector s1 of length 512n. s1[x] nonzero iff x sum of 2 numbers in a.
  3. perform convolution of s1 make new vector s2. s2[x] nonzero iff x sum of 4 numbers in a.
  4. check s2[v] answer.

convolution can performed in o(n log n) time using fft convolution (http://www.dspguide.com/ch18/2.htm) or similar techniques.

since @ 4 such convolutions performed, total complexity o(n log n)


Comments

Post a Comment

Popular posts from this blog

resizing Telegram inline keyboard -

telegram's inline keyboard great feature lots of different use cases. inline buttons added list of items this: inline_keyboard = [[inlinekeyboardbutton(text="button", callback_data="button"), inlinekeyboardbutton(text="reset",callback_data="reset")]] inline_keyboard_markup = inlinekeyboardmarkup(inline_keyboard) update.message.reply_text("hi", reply_markup=inline_keyboard_markup) the above code adds 2 buttons each half width of chat screen. i know the normal keyboard button there resize_keyboard parameter somehow can used. my question is there way resize inline buttons ? example make full width or quarter width. unfortunately, can't now. :( you can suggest @botsupport , might add feature next version.
Read more

command line - How can a Python program background itself? -

consider following python command-line program. doesn't work because incomplete, think illustrates problem: #!/usr/bin/python3 import multiprocessing pool = multiprocessing.pool() task in expensive_iterator_with_user_interaction(): pool.call_async(expensive_computation, (task,)) pool.close() print("dear user, may press ctrl-z , bg script.") pool.join() thus, problem scripts needs user input while it's launching expensive parallel processes. there moment when user interaction not needed anymore. then, ask user background process shell actions. however, can achieved program itself? (side note: core of problem entanglement of user input firing “expensive computations”. therefore, cannot separate both in 2 scripts, , letting 1 spawning other daemon.) the command screen may you. use screen -l create new session , run application. after inputting data, can press " ctrl-a " , press " d " on keyboard detach session. now...
Read more

php - "cURL error 28: Resolving timed out" on Wordpress on Azure App Service on Linux -

Image
my wordpress installation on azure app service on linux using custom docker container has slow response times. pages take around 20-40 seconds load. i have troubleshooting plugin installed indicates problem "curl error 28: resolving timed out after n milliseconds" when making requests following urls https://api.wordpress.org/core/version-check/1.7/ http://api.wordpress.org/core/version-check/1.7/ https://api.wordpress.org/plugins/update-check/1.1/ http://api.wordpress.org/plugins/update-check/1.1/ https://api.wordpress.org/themes/update-check/1.1/ http://api.wordpress.org/themes/update-check/1.1/ curl works fine on scm-site command line. example works ok. curl -x post http://api.wordpress.org/core/version-check/1.7/ edit if ssh container , run php code, works fine. <?php $url = 'http://api.wordpress.org/core/version-check/1.7/'; $fields = array( 'version' => urlencode('4.8.1'), 'php' => urlencode(...
Read more