Programming trick questions @ Things Of Interest

Note: me telling you up front that these are trick questions rather gives the answers away in most cases, but oh well.

Questions

Question 1

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?

Question 2

What's the fastest way to test whether a 32-bit integer is a perfect number?

Question 3

How do you reverse a Unicode string?

Answers

Answer 1

Just repopulate the array with integers from 1 to N. Running time is O(N).

Answer 2

return x == 6 || x == 28 || x == 496 || x == 8128 || x == 33550336;

For 64-bit integers you need only three additional terms.

Answer 3

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.

Back to Code

Back to Things Of Interest

Discussion (31)

2019-12-16 00:45:47 by DanielLC:

x = 33550336 should be x == 33550336. I was expecting reversing the string was going to be adding the right-to-left mark.

2019-12-16 00:52:03 by qntm:

Fixed.

2019-12-16 02:31:15 by njo:

>You can't. The Unicode standard does not have a concept of string reversal. That doesn't make it an unsolvable problem. The ASCII specification doesn't have a concept of string reversal either, but I would claim that it is possible to reverse an ASCII string. There would be a lot of hairy edge cases, but that could make it an interesting question.

2019-12-16 02:50:04 by yaloi:

>>You can't. The Unicode standard does not have a concept of string reversal. >That doesn't make it an unsolvable problem. The ASCII specification doesn't have a concept of string reversal either, but I would claim that it is possible to reverse an ASCII string. How would you reverse ab<backspace>ab? Is it baa, which visually reverses the displayed characters, or bba, which renders each character in reverse order?

2019-12-16 06:18:08 by white_len:

>How would you reverse ab<backspace>ab? Is it baa, which visually reverses the displayed characters, or bba, which renders each character in reverse order? That might not be the best example to use, considering that the backspace character also exists in ASCII.

2019-12-16 06:40:08 by Coda:

> reversing Unicode There are only two sane interpretations of this requirement: 1. Reverse the code points. 2. Reverse the rendered glyphs. The first is trivial, but also potentially nonsensical, as it would mean combining characters get combined in different ways. The second is what most laypeople would interpret "reverse" to mean. This is absurdly complicated, to be fair, as it essentially requires reimplementing the whole rendering stack in order to figure out the intent. It's certainly POSSIBLE, but it's not EASY in the slightest.

2019-12-16 14:43:54 by t:

I was hoping the answer to "How to reverse a unicode string?" was to get a mirror.

2019-12-20 20:45:51 by gordy:

your answer for 1 only works if there are no duplicates

2019-12-20 20:50:24 by qntm:

How could there be duplicates?

2019-12-21 16:44:05 by John F:

For 2) when I was in high school, we had a programming assignment to calculate perfect numbers on Apple II machines in Basic. Only 16 bit math there. But I realized that every perfect number is a Mersenne Prime multiplied by the previous power of two weeks than the prime was based on. Not a new insight there, Euclid proved it. But it meant I was able to calculate the 5th number indirectly, and compute all of the first five dramatically faster than the brute force testing everybody else did. Long-winded way of saying that I knew there were very few such numbers and I could just enumerate them.

2019-12-21 16:44:07 by John F:

2019-12-23 15:49:49 by AGM:

Actually, you can reverse a string of Unicode characters. Input them into a C-language array, then printf(...); said array backwards with a for(...) loop.

2019-12-23 15:55:44 by qntm:

That results in complete gibberish. The output isn't even Unicode text anymore in many cases.

2019-12-24 09:23:57 by Ingvar:

If someone asked me to "reverse a Unicode string", in an interview context, I would start by saying "do you mean emit the codepoints in reverse oredr to what htey originally occur?" That being as close as I can think to "reverse the Unicode string" to mean. Further discussions on how to deal with combining characters might lead into "pick codepoints out of the private use area to represent each fully-combined characet we've seen, then uncombine them when generating the reversed string". There's also the fun htat we'd (probably) need to decode whatever storage representation was being used, as we're unlikely to have it in UCS-4 (or is it UTF-32, I can't remember).

2019-12-24 10:57:08 by qntm:

Then there's bidirectional text, ligatures...

2019-12-30 14:07:06 by ingvar:

"Bi-directional text" sounds like a presentation problem, not a data representation problem, and "reverse a string" sounds like a data representation problem. Off-hand, I don't know how ligatures are represented in Unicode (to me, ligatures sound like a type-setting problem, so again a presentation problem), but it seems that some ligatures actually have code points, although in at least a few locales, at least some of those ligatures are considered single characters (æ being one of them, in at least Danish, Norwegian, Icelandic, and Faroese). I think the closest we could possibly get to "reverse a Unicode string" is "emit all the code points in reverse order". But, I don't think there is a correct answer, and the best we could possibly do is argue about what edge cases to observe, including our old friend "locale", which makes even printing numbers hard.

2020-02-29 15:25:06 by IggleSniggle:

This response found on HN to #3 seems quite reasonable to me (in the spirit of trick questions at least): if the string is left-to-right, prepend the right-to-left code https://www.codetable.net/decimal/8207 Voilá, a Unicode string, in reverse direction.

2020-02-29 15:27:05 by IggleSniggle:

(I'm not at my computer or else I would check what happens when you use two rtl codes in the same string)

2020-02-29 16:51:56 by Jeff:

gnirts edocinU a

2020-02-29 17:20:41 by remover:

for 1 it would be good to specify that the integers are consecutive :)

2020-02-29 17:23:26 by qntm:

How could they not be consecutive?

2020-02-29 21:41:50 by aconite:

#1 is wrong unless the problem statement is changed to say "all the integers 1 to ...".

2020-03-01 11:32:03 by qntm:

A bizarre number of people seem not to understand that the integers from 1 to 5 means 1, 2, 3, 4 and 5 .

2020-03-01 14:47:53 by FalkH:

At least for 64 bits, the following test for perfect numbers might be faster: bool isPerfect(uint64_t x) { int ctz = __builtin_ctzll(x); return ((0x40051056 >> ctz) & 1) && ((x >> ctz) + 1) == (uint64_t(1) << (ctz + 1)); }

2020-03-02 18:03:54 by inad:

The unicode answer is a bit far fetched... It is easy to reverse 99% of any english text you will find on the web, or even any other latin languages, and this is the context of the question. If you expect the answer to take into account corner cases for an english speaker, you need to specify it in the question ("...taking into account all characters of Unicode vX.Y encoded in UTF-xx"). If I ask the usual probability riddles regarding the sex of children in a family, this would be very unfair of me to point out afterwards that the answer do not take into account non binary genders.

2020-03-02 22:15:02 by qntm:

Tell me more about the context of my own question.

2020-03-03 11:29:17 by inad:

The context of the question is just the usual cases, not the corner ones, unless specified. For instance, you are saying "the array has length N and contains ... 1". Well this is impossible. You never said that N is a strictly positive integer, so the answer must be able to handle an array of length 0 including 1, which is of course impossible, therefore you are falling in same pitfall that you setup for question 3. In question 2, you just say 32 bits integer, but you do not specify the encoding... which could be a compressing one based on LZW and store much bigger perfect numbers. When I read the question 3, I am thinking for instance of managing non ASCII UTF-8 characters. This question has been asked for years for ASCII / ISO-8859-x in schools and interviews, and I never saw somebody coming up saying : "Tadam ! you are wrong, you do not manage strings containing NUL or CRLF !".

2020-03-05 09:06:54 by enes:

For Unicode question, you need to know what's a 'readable' character set that we want to be able to reverse. For ASCII it's the same story, just reverse the readable string. Please don't make it dramatic.

2020-03-06 08:03:27 by justno:

@inad 'The context of the question is just the usual cases, not the corner ones, unless specified. For instance, you are saying "the array has length N and contains ... 1". ' No, it says "contains [...] 1 to N". That handles the case N=0.

2020-03-08 04:08:50 by siquod:

I understood question 1 so that the referential identities of the integers had to be preserved, seeing as you said "integers" and not "ints".

2020-03-14 22:48:22 by qntm:

Seems like a whole bunch of folks did not correctly answer the trick questions!

This discussion is closed.