24 ms·
Programming trick questions
- vortico 7y ago#1 got me and I had a good laugh. I wonder if there's a faster method for #2 using AVX and bit tiddling, or if the optimizer is smart enough to find the most efficient code for a particular architecture.
- leni536 7y agoThese are the five numbers in binary, to give some inspiration for a bit twiddling algorithm: 110 11100 111110000 1111111000000 1111111111111000000000000
- leni536 7y agoOne things that comes to mind: popcnt(x^(x>>1))==2 for all 5 numbers. Maybe the checking function could start with that condition, then fall back to the slower one-by-one check when that evaluates to two. For most numbers the popcnt check would fail. edit: Not to mention that all 5 numbers are even, so a parity check could also help for odd number inputs (but it makes it slower for even numbers). I do not think that AVX has anything to offer here though.
- zzo38computer 7y agoIt might matter then what cases you need to optimize for, which statistics are most important, and what instruction set you are using.
- leni536 7y agoSure, my tricks are mostly aimed for improving the average performance for uniform inputs between 0 and 2^32-1. Edit: And yeah, you need a fast popcnt here.
- amptorn 7y agoThe even perfect numbers all have the formula 2^(p - 1)(2^p - 1) for some prime `p`. In code that's ((1 << p) - 1) << (p - 1) for `p` = 2, 3, 5, 7 and 13, which is why you're seeing that interesting pattern of bits. (There are no odd perfect numbers in the range under consideration.)
- pmiller2 7y agoYou should also note that there are no known odd perfect numbers, period. Any that do exist must exceed 10^1500.
- vortico 7y agoHmm, I can't think of a way to use the mathematical structure of those numbers to speed up checking. However, the reason I said AVX is because it can be used for checking equality of 5 (well, 8) numbers simultaneously. This solution requires AVX2 and is probably faster than the optimized reference code. // Copy x to all 8 elements. __m256i a = _mm256_set1_epi32(x); // Duplicate 6 because we need to fill all 8 elements. __m256i b = _mm256_set_epi32(6, 28, 496, 8128, 33550336, 6, 6, 6); // Check for element-wise equality. __m256i c = _mm256_cmpeq_epi32(a, b); // Check if any bytes are nonzero. return _mm256_movemask_epi8(c) != 0; https://godbolt.org/z/6W8rZy https://godbolt.org/z/6W8rZy
- saagarjha 7y agoI’d benchmark that before being sure.
- vortico 7y agoIt might not be faster, but unfortunately the computer I'm typing this on doesn't support AVX2. :(
- deleted 7y ago[deleted]
- x0 7y agoSeems to be faster, did a crappy shell benchmark. It takes 5.7 seconds to run that SIMD function INT_MAX times, compared to 6.6 seconds for the original. MacBook Air, late 2014, clang, -O3 -mavx2
- OskarS 7y agoI have a hunch that the actually fastest version is to change all those "||" to "|" in the original version. Short-circuiting and adding branches probably just slows the whole thing down compared to just running the comparisons, which will probably pipeline really well. Interestingly the compiler doesn't do this optimization, even though it could. So maybe I'm wrong. No real way to know without benchmarking, though.
- abnry 7y agoGot me to laugh too! I thought I was clever with my O(n) solution. Let A be the original array and let B be the sorted array. Just loop through A and assign B[A[i]] = A[i]. But this is still dumb! lol.
- BubRoss 7y agoIt says from 1 to N inclusive, so each offset would need to have 1 subtracted from it. (Yes I realize it would just be an iota function in c++)
- Someone 7y agoAssuming arguments will be uniformly picked an extra check would speed things up on many architectures: return (x & 0xFE0000001 == 0) && (x == 6 || x == 28 || x == 496 || x == 8128 || x == 33550336): The original code does about 5 comparisons in each call. The improvement always does a binary ‘and’ and 1 comparison, and only does the original 5 in 1/256 of the calls.
- contravariant 7y agoAlthough unlike the original code it will be trickier to refactor for >5000 bit architectures once we encounter an odd perfect number.
- hairtuq 7y agoHere's a version that at least for 64 bit 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)); }
- sethammons 7y agoDecent examples. I'd like to toss another in that, years ago, a colleague gave a candidate. He thought of the question that morning in the shower. Morse Code. All letters are combinations of one or more dashes and/or dots. Here is a sentence of Morse Code where the spaces are stripped. Decode it to get the original ASCII sentence. He gave it and failed the candidate. Sounding like an interesting problem, some of us in the office tried it. Turns out that it is a very hard problem. You have to make a tree of possibilities and it is easy to accidentally make your solution O(n!). Moral of the story is never give out a coding question that have not personally solved. Second moral: be open to out of the box solutions.
- egdod 7y agoIs the answer even well-defined? Seems like without spaces, there could be strings that decode to multiple possible (possibly nonsense) “sentences.”
- hnkain 7y agoIn particular, E is . and T is -, so you can trivially decode any sequence of dots and dashes to strings containing only E and T.
- pbhjpbhj 7y agoSurely "decoding" means returning the text that was encoded. You can't trivially decode it, you can provide a candidate solution, that's entirely different; the point of sharing this was it's not possible to decode because there's no unique solution. ...---... you can guess it's EEETTTEEE, but the decoding is SOS, that was the plaintext I started with.
- rdlw 7y agoYes, and even a simple string like "...---..." has 200 possible solutions, including "VTTIE", "3NI", and "SMB". Especially for longer inputs, there's no way to guess which one is right.
- whatshisface 7y agoI disagree with the answer to #3, you can reverse a Unicode string with "". ;) https://en.m.wikipedia.org/wiki/Right-to-left_mark https://en.m.wikipedia.org/wiki/Right-to-left_mark
- zyx321 7y agoWill not reverse languages that are right-to-left by default, such as Arabic or Hebrew. Will not reverse composed ligatures, e.g. ﷺ is synonymous to صَلَّىٰ ٱللَّٰهُ عَلَيْهِ وَسَلَّمَ, but صَلَّىٰ ٱللَّٰهُ عَلَيْهِ وَسَلَّمَ with a LTR directional override is صَلَّىٰ ٱللَّٰهُ عَلَيْهِ وَسَلَّمَ while ﷺ remains as ﷺ. Will not reverse 겁 into 벅.
- enriquto 7y agowow, these symbols are awesome! Is it regular arabic or fancy calligraphy stuff? Are there two lines of characters?
- BubRoss 7y agoYou can copy and paste the text
- blattimwind 7y agoSince these are ligatures (though really complex ones) most software consider these as one "character" (try selecting part of the ligature; you can't).
- zyx321 7y agoIt's a fancy calligraphy version of "Peace Be Upon Him" used specifically when referring to the prophet Muhammad. There are a handful similar phrases, mostly religious in nature. The most notable one would be ﷽ "In the name of Allah the merciful and compassionate" AKA the widest single codepoint in all of Unicode.
- seiferteric 7y agoMakes me wonder if we should not have tried to make a single "unicode" and instead had distinct types for each language like EnglishString ArabicString etc. and programmers can handle each case as needed.
- ddevault 7y agoqntm.org is a website worth browsing, if you've never been here before. Some of my personal favorites: https://qntm.org/destroy https://qntm.org/destroy https://qntm.org/excellent https://qntm.org/excellent
- zzo38computer 7y agoThe first question is easily enough; I figured it out. I knew the third question also, but not the second question. (Unicode is not suitable for all uses, anyways. Unicode is very messy.)
- testplzignore 7y agoFor #1, it really depends on what you mean by "array" and what you need to use it for. Sounds like an XY problem. If you take it to mean a more abstract concept of a list of things that can be iterated and accessed by index, then the fastest implementation is O(1): build no data structure at all - just implement the iterator and index functions. If you take it to mean physically manipulating atoms on a chip to be in a certain state, then you'll actually have to do something :)
- zyx321 7y agoAn array is a data structure that can be accessed using the Array operator `[]`. C# will allow overloading the operator, Java will not.
- mgamache 7y agoThese are fun brain candy and a reminder of the value of lateral thinking, but I hope no one actually uses these as employment screening.
- seanmcdirmid 7y agoAren’t these really just the same thing as the brain teasers that have already been disavowed by most companies? Anyways, even many Leetcode questions involve “tricks” that we just have to deal with.
- techslave 7y agowhy not? they are trivial. not “trick” in the sense of poor questions which are easy enough once you’ve studied the problem for 20 years and know some trivia that is rare knowledge, but are otherwise insanely difficult. i think these are good. TELL the candidate they are trick questions. again, they are trivial. i was actually disappointed.
- barrkel 7y agoBetter questions are those that more closely simulate a work sample, being aware that an interview is high stress and time boxed and thus not actually like work. I like an hour or more pair programming in a language the candidate is comfortable with on a simplified problem with some relevance to work. For more senior candidates, you definitely wouldn't want to waste everyone's time with brain teasers because if the high risk of a hasty rejection - a deeper probing into systems they've built and and designed in the past, with an angle on relevant problems for the business, along with the pair programming.
- weego 7y agoSo what insight do you think this is actually giving into someone interviewing? Surprise trivia / trick questions do not select for anything meaningful in respect to the day to day practices of any developer
- remmargorp64 7y agoI'm of the opinion that the only valid type of coding question in an interview is one that tests the candidate's ability to perform the actual type of work they are being hired to do. If you were trying to hire a mechanic, would you first give them a sudoku puzzle to measure his "cleverness" (and then use that as a predictor of their car repair abilities)?
- scythe 7y agoI wonder if this would be faster on average (most numbers fail all five comparisons) for #2? int y = x ^ (x-1); return x == y * (y+1) / 2 && ([comparison list]);
- jks 7y agoHere's a similar one: What's the best possible time complexity of a program that plays perfect chess, assuming we could write such a program? Answer: O(1), since it could be written as one big lookup table from game state to optimal move. To get a nontrivial complexity class, you have to have some parameter that can vary, so e.g. the question "what's the time complexity of a program that plays perfect chess on an n-by-n board?" (assuming a suitable generalization of the chess rules is given) is much harder to answer.
- clarry 7y agoI think that works only if n-by-n can vary to infinity. Otherwise I'll just have a lut for every possible board size. By the same method, you can sort any finite sequence in O(1).. but then you don't really sort infinite sequences, do you? So I'm not sure this is a good trick question.
- draw_down 7y agoWhy are people talking about this in context of employment interviews? The article doesn’t go there, and neither should anyone else. Trick questions do not “show you how the candidate thinks” or whatever. Judging candidates on them is not acceptable.
- ajross 7y agoI dunno, these aren't very interesting to me. Question one is good. Question two relies on the answerer knowing specific details about the distribution of perfect numbers, which isn't a "trick" in any meaningful sense. Either you know it or you don't. Contrast with "Are the arguments to memcmp() declared const in ISO C99?". Is that a "trick" question? And question three is just senseless pedantry. It says that unicode symbols don't make "real" strings if you reverse their orders. Which is true, but not really what the question was asking. ASCII strings aren't "real" if you reverse their order either, because "real" is a human distinction that doesn't live at the data layer. It is certainly true that a reversed unicode string containing ligatures and combining characters is a VALID string per the unicode standard, which seems to meet the phrasing of the question as asked.
- misiti3780 7y agoHow can one get better at questions like these (im horrible at them)?
- nebulous1 7y agoExperience. You "should" have been able to get the first one, I think the other two are pretty debatable as they require knowledge you might have to research first if you didn't already know about perfect numbers or at least some of the complexities of unicode. As far as the first one goes, you could go through some of the questions on https://codesignal.com/ https://codesignal.com/ . They're geared towards interview practice, but ignoring that they provide reasonable problems, a decent environment to write code in and after you get your solution accepted you'll be able to access other solutions to get new ideas. The aim here is just to learn how to think through a problem and allow your brain start to make connections that it wasn't making before.
- misiti3780 7y agoyes, the first one was not hard.
- misiti3780 7y agothanks!
- pmiller2 7y agoFor the perfect number question, you can always just argue that precomputing a 512 MiB bit array that has 1 in position n if n is a perfect number, then indexing into that bit array is O(1). Because the range is constrained, you don't need to know anything about perfect numbers to come up with this.
- amptorn 7y agoRealistically, this is for fun and games. Nobody should actually be asking you trick questions in a real scenario. It's okay not to be able to catch the trick.
- lojack 7y agoThey’re trick questions, so I think it’s fair to be pedantic. It’s asking for fastest method not the one with least complexity. I would argue the fastest method would be to pick a random location in memory and get lucky.
- whoopdedo 7y agoRender string to canvas. Use glyph width to divide into characters. Rearrange the characters. OCR back into Unicode.
- acangiano 7y agoMy favorite trick is to not ask trick questions.
- TrumpMyGuns 7y agoOne of the biggest red flags is when a company starts throwing you these trick questions. Run away, fast.
- baron816 7y agoI think “problem solving” questions are pretty much useless. Engineers need to solve problems, but they don’t have to do it in under an hour and under stress. Plus, solving tricky problems is not something you do everyday, or maybe even every week. What I care about when I do interviews is how they organize their code. I want to see what people’s instincts and habits are, because that’s what’s going to determine the quality of 99% of the code they write. I’d rather have someone who can come up with objectively good abstractions instead of writing one giant, unintelligible block of code than someone who can come up with something very clever on the spot to a totally esoteric problem.
- yters 7y agoWhile I know it is common practice to dismiss problem solving questions, a good problem solution can be the difference between intractable NP complete or worse, and a solution that is O(lg N). Additionally, a good solution is elegant and easily maintainable, while a bad solution is bloated and has large code debt.
- ameixaseca 7y agoInterview questions should be trivial examples so you can see if the candidate know what programming is or how to program on the language, not what libraries he/she knows. Ideally nothing that depends on any particular OS std libraries as well. Of course this does not apply if you are hiring someone for a position where knowledge on a particular library is a requirement, but in my experience that is usually not the case for either junior nor senior positions, maybe only for in-between. If you need anything more advanced you should do an assignment to allow time for proper design and reasoning, otherwise you'll never be able to fully evaluate what the candidate really can do and how he/she approaches problems.
- masswerk 7y agoRegarding reversing Unicode strings: This is simple, just render the string in a purposefully crafted mono-space font using distinct, non-overlapping bit patterns for glyphs (this will be a rather huge font, we may suggest a 0xFFFF x 0xFFFF matrix for glyphs to be on the safe side), slice the resulting bitmap image, detect and recompose. ;-) (Obviously, this is a trick answer.)
- chapium 7y agoI know next to nothing about unicode. If I took the bits and arranged them in reverse order would I be asked to leave the building? It didn't state the output should also be unicode.
- masswerk 7y agoThis is much like the practical paper tape answer: punch it on a 8-bit tape (ASR-33 TeleType) and flip the tape. :-)
- kolbe 7y agoDoes everyone understand something I don’t about #1? It never said they were unique integers.
- kmill 7y agoThe array is length N, and it says it contains the integers 1 through N inclusive, as in, all of them. If there were any repeats, then you'd have an array of length greater than N.
- kolbe 7y agoSeems like somewhat ambiguous semantic garbage to me. Especially when there is a much clearer three letter word to use (all) that would actually communicate the the point of the question.
- bobblywobbles 7y agoThis is what I can't understand about hiring interviews, and I thank 1/2 of my interviews haven't involved such trickery. Sure - it's "easy" to say "Oh you've solved this great puzzle, you'd be perfect since you are smart on your feet", but you can be great at writing UI's, but struggle on the backend. This culture needs to end. I don't spend my time at work solving puzzles, I spend time at work meeting with stakeholders, organizing meetings, discussing options and timelines. I spend my time coding and iterating, not wasting my time at puzzles. I hate puzzles, because I like to do work that actually produces results (and isn't a measure of how smart one might be). Puzzles are a waste of time in my opinion, a much better proof of pudding would be a programming portfolio of things you've written (ie. Github).
- hermanschaaf 7y agoHere is another one I thought of the other day. Q: Given V (the number of vertices), E (the number of edges) and L (a list of the edges) for a connected undirected graph, determine whether the graph is a tree. ---- A: It can be done in O(1) by: return V == E + 1 The number of vertices in a tree is always one more than the number of edges. We also know that the graph is connected, so it has to be a tree.
- stephc_int13 7y agoI've tried trick programming questions when I started interviewing coders, the SNR was simply awful and it was frustrating for me and the candidates. Any evaluation system have to be calibrated on a large enough pool of candidates, when you're building a company and start interviewing you don't really have the luxury of wasting the first dozens applications. Today I tend to completely avoid programming questions, except to reject complete newbies.
- tasty_freeze 7y agoSince I work from home, I haven't had to do interviews in a long time, but back when I did, I did always ask one programming question, but it would be only one step harder than trivial. I'd say use whatever language you want, even make one up, so long as you can explain parts where I might have questions. I didn't care about syntax, or performance, or cleverness -- just does it work. If they can't do that, you don't want them for a coding position.
- ape4 7y agoI like that its impossible to do "string reversal" until "string" and "reversal" are defined. Oh you want me to sort an array... how do you define "sort" and "array".
- bmn__ 7y agoConcerning Unicode reversal, the author's statements "This has not been done", "there is no genuine real-world need", "The algorithm doesn't exist" are wrong (see UAX #29 §6.4), "suitable metadata might need to be added" has already been done, and "what a 'string' is considered to be" is well-defined and requires no deliberation or reinterpretation. His text is surprising to me because I know the author programs in Perl, JS, Python, so he should really be knowledgeable about this topic. With the following code samples, all the edge cases written about in the article are taken care of. https://docs.raku.org/routine/flip https://docs.raku.org/routine/flip $some-str.flip https://p3rl.org/unicook#℞-32:-Reverse-string-by-grapheme https://p3rl.org/unicook#℞-32:-Reverse-string-by-grapheme join '', reverse $some_str =~ /\X/g https://php.net/grapheme_extract https://php.net/grapheme_extract ... https://github.com/dart-lang/characters https://github.com/dart-lang/characters ... https://grapheme.readthedocs.io/en/latest/grapheme.html#grapheme.graphemes https://grapheme.readthedocs.io/en/latest/grapheme.html#grap... from grapheme import graphemes "".join(reversed(list(graphemes(some_str)))) https://npmjs.com/package/grapheme-splitter https://npmjs.com/package/grapheme-splitter const gs = new(require('grapheme-splitter')); gs.splitGraphemes(some_str).reverse().join(''); Rust deserve special mention because the language implementers did the correct thing and put it in the language: https://doc.rust-lang.org/1.3.0/std/str/struct.Graphemes.html https://doc.rust-lang.org/1.3.0/std/str/struct.Graphemes.htm... … only to take it out again for no good reason, thus rendering the programming language not Unicode compliant in the process. Talk about snatching defeat from the jaws of victory! m-( Other languages: try to find a binding for libpcre or libicu. http://www.pcre.org/current/doc/html/pcre2pattern.html#Extended%20grapheme%20clusters http://www.pcre.org/current/doc/html/pcre2pattern.html#Exten... http://userguide.icu-project.org/boundaryanalysis#TOC-Character-Boundary http://userguide.icu-project.org/boundaryanalysis#TOC-Charac...
- llarsson 7y agoAre other professionals subjected to the same scepticism during interviews? Are lawyers given tough questions and expected to come up with a clever response on the spot? Doctors given a list of symptoms? Teachers given a difficult student and told to teach them some concept from physics? Serious question (albeit a bit facetious in my examples).
- dahfizz 7y agoLawyers, doctors, and teachers are all positions that have some form of certification. Potential employers can be guaranteed that all potential employees meet the basic knowledge and skills requirements. Nothing of the sort exists in the programming field. That, coupled with the high salaries, means fraud is a real problem when trying to hire programmers.
- hwayne 7y agoI like these a lot! I'm seeing them less as "interview questions", which they'd be terrible as, but as "annoy your friends questions" after you've all had a couple drinks. One I heard a while back: "You have a list consisting of every college student in the US. What's the fastest way to sort them by age in years?"
- amptorn 7y agoOther than sorting by birth date, what's your intended solution to this?
- hwayne 7y agoAlmost all of the students are going to be somewhere between 17 and 23 years old, so you first do one pass as a bucket sort for each of those seven values. Then sort the remaining students however you want. While it's technically still O(n log n), almost everyone is sorted in that first pass, so it's practically indistinguishable from O(n).
- sethammons 7y agoThat is actually a decent optimization. If you know the final cardinality, you just create that many buckets, and drop records in it. Not unlike how histograms work.