Note: me telling you up front that these are trick questions rather gives the answers away in most cases, but oh well.
What's the fastest way to sort a jumbled array, given that the array has length N and contains all the integers from 1 to N inclusive?
What's the fastest way to test whether a 32-bit integer is a perfect number?
How do you reverse a Unicode string?
Just repopulate the array with integers from 1 to N. Running time is O(N).
return x == 6 || x == 28 || x == 496 || x == 8128 || x == 33550336;
For 64-bit integers you need only three additional terms.
You can't. The Unicode standard does not have a concept of string reversal.
There are numerous semi-obvious ways in which a programmer could rapidly/spontaneously define "string reversal", but all of them run into serious problems when presented with arbitrary Unicode strings which may contain non-ASCII characters, combining characters, ligatures, joined "words", bidirectional text in multiple languages, surrogate pairs and so on. As the problem becomes more complex, we discover that defining reversal on an arbitrary Unicode string in a meaningful, practical way is, though probably not completely impossible, extremely difficult. The algorithm we would eventually define would be complex and highly non-obvious, taking months of work to create. Additionally, it would have to be created by the same sort of highly informed language specialists who came up with Unicode's character-combining, normalization or bidirectionality algorithms — namely, the Unicode Consortium. And then, suitable metadata might need to be added to all 100,000+ Unicode characters to facilitate the algorithm.
This has not been done, because there is no genuine real-world need for such a thing. The algorithm doesn't exist. You can't reverse a Unicode string.
A corollary is that Unicode also has no concept of palindromes (strings which read the same after being "reversed"). When encountering programming questions relating to palindromes, it's important to ascertain exactly what a "string" is considered to be, and what "reversed" is considered to mean.
Discussion (31)
2019-12-16 00:45:47 by DanielLC:
2019-12-16 00:52:03 by qntm:
2019-12-16 02:31:15 by njo:
2019-12-16 02:50:04 by yaloi:
2019-12-16 06:18:08 by white_len:
2019-12-16 06:40:08 by Coda:
2019-12-16 14:43:54 by t:
2019-12-20 20:45:51 by gordy:
2019-12-20 20:50:24 by qntm:
2019-12-21 16:44:05 by John F:
2019-12-21 16:44:07 by John F:
2019-12-23 15:49:49 by AGM:
2019-12-23 15:55:44 by qntm:
2019-12-24 09:23:57 by Ingvar:
2019-12-24 10:57:08 by qntm:
2019-12-30 14:07:06 by ingvar:
2020-02-29 15:25:06 by IggleSniggle:
2020-02-29 15:27:05 by IggleSniggle:
2020-02-29 16:51:56 by Jeff:
2020-02-29 17:20:41 by remover:
2020-02-29 17:23:26 by qntm:
2020-02-29 21:41:50 by aconite:
2020-03-01 11:32:03 by qntm:
2020-03-01 14:47:53 by FalkH:
2020-03-02 18:03:54 by inad:
2020-03-02 22:15:02 by qntm:
2020-03-03 11:29:17 by inad:
2020-03-05 09:06:54 by enes:
2020-03-06 08:03:27 by justno:
2020-03-08 04:08:50 by siquod:
2020-03-14 22:48:22 by qntm:
This discussion is closed.