Programming trick questions @ Things Of Interest

Programming trick questions

2019-12-15 by qntm

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 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 (16)

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.