Little problem(s) July 2022
|
07-04-2022, 06:04 PM
(This post was last modified: 07-07-2022 05:31 PM by pier4r.)
Post: #1
|
|||
|
|||
Little problem(s) July 2022
#1 Sum of two integers in a list
Input: L2: a list (or an array) of positive integers values L1: an integer Int1 Output: L1: the positions of the two different (!) elements in the list in input whose sum is equal to Int1 Constraints: - Assume the input list to have only one couple of values that equals to Int1 or none. No duplicates. #2 Sum of two integers in a list bonus No1 Like the problem in #1 but try to get less than O(n^2) #3 Sum of integers in a list bonus No2 Input: L2: a list (or an array) of positive integers values L1: an integer Int1 Output: L1: the positions of the different (!) elements in the list in input whose sum is equal to Int1, so that the number of elements that produce the sum is maximum (if it is possible to equal Int1). If multiple options are possible, one is to be picked. Example inputs: { 1 2 3 2 2 1 } 6 output: { 1 2 4 6 } @1 2 2 1 @alternative { 1 2 5 6 } Wikis are great, Contribute :) |
|||
07-04-2022, 08:20 PM
Post: #2
|
|||
|
|||
RE: Little problem(s) July 2022
Klick at your own risk: Spoiler
|
|||
07-04-2022, 11:11 PM
Post: #3
|
|||
|
|||
RE: Little problem(s) July 2022
I am not sure if this match the requirements.
Here is Lua's solution, which should be trivial to convert to Python Note: Lua index is 1-based; Python 0-based. Code: function f(lst, x) For index permutations instead of combinations, remove if prev > y then ... line lua> L1, L2 = {1,2,3,2,2,1}, 6 lua> f(L1, L2) -- L1 index combinations that sum to L2 1 2 3 1 2 4 6 1 2 5 6 1 3 4 1 3 5 1 4 5 6 2 3 6 2 4 5 3 4 6 3 5 6 |
|||
07-05-2022, 01:01 AM
Post: #4
|
|||
|
|||
RE: Little problem(s) July 2022
Actually, question #2 happens to be a very standard question in technical interviews these days.
Candidates are supposed to solve a couple of questions of that kind in the typical 45' interview. The difficulty is to do this in "real time" without significant bugs, in the language of your choice. |
|||
07-05-2022, 03:31 AM
(This post was last modified: 07-05-2022 03:54 AM by Thomas Klemm.)
Post: #5
|
|||
|
|||
RE: Little problem(s) July 2022
Here's my solution of #2 for the HP-48:
Code: \<< OVER - \-> ns ms Example { 2 7 11 15 } 17 (4,1) (1,4) Add a final DROP if you are only interested in one solution. Addendum: Under the hood the implementation of POS is probably \(\mathcal{O}(n)\). This makes my solution \(\mathcal{O}(n^2)\) and thus rather a solution for #1. But we don't have to tell that the interviewer, do we? |
|||
07-05-2022, 04:06 AM
Post: #6
|
|||
|
|||
RE: Little problem(s) July 2022
(07-05-2022 01:01 AM)pauln Wrote: a very standard question in technical interviews these days. Cf. Technical Interviews |
|||
07-05-2022, 10:00 AM
(This post was last modified: 07-05-2022 10:08 AM by pier4r.)
Post: #7
|
|||
|
|||
RE: Little problem(s) July 2022
(07-05-2022 01:01 AM)pauln Wrote: Actually, question #2 happens to be a very standard question in technical interviews these days. yes I saw the problem in a post online that mentioned careercup. I found it nonetheless a nice challenge for list processing ( see here ) and thus I wanted to share plus adding some variants (#3, that may likely be an already posed question but I was simply trying to expand on #1). Further I am pretty sure that is unlikely that such problems were solved (with shared solution) within the realm of calculators capabilities (especially older ones), unless they were already discussed here on on other calculator forums. Wikis are great, Contribute :) |
|||
07-05-2022, 01:56 PM
(This post was last modified: 07-05-2022 01:57 PM by pier4r.)
Post: #8
|
|||
|
|||
RE: Little problem(s) July 2022
(07-05-2022 03:31 AM)Thomas Klemm Wrote: Addendum: Why is POS \(\mathcal{O}(n)\) in userRPL? Is there no direct access to the position in a list, does the system have to iterate through the elements every time? (is DOSUBS the only way to avoid it?) Wikis are great, Contribute :) |
|||
07-05-2022, 02:03 PM
(This post was last modified: 07-05-2022 02:11 PM by John Keith.)
Post: #9
|
|||
|
|||
RE: Little problem(s) July 2022
(07-05-2022 03:31 AM)Thomas Klemm Wrote: Here's my solution of #2 for the HP-48: Very nice program, as usual. ![]() This is not really an improvement, but I couldn't resist a functional version of your program for the 48G: Code:
Unfortunately it is not a well-behaved function because, due to what I consider to be a bug in DOLIST, it returns nothing if no pair of numbers in the list sums to the level 1 argument. The ListExt function LMAP does not have this problem (it returns an empty list) but that is limited to the 49g and 50g. As an addendum to your addendum, your program is technically O(n^2) but since built-in functions like POS are many times faster than any UserRPL equivalent, it comes out much closer to O(n) in practice. |
|||
07-05-2022, 03:41 PM
Post: #10
|
|||
|
|||
RE: Little problem(s) July 2022
(07-05-2022 01:56 PM)pier4r Wrote: Why is POS \(\mathcal{O}(n)\) in userRPL? I must admit that I don't know the details, but I assume that POS has to check every entry to find the position. The worst case is if we search for an entry that is absent. This program measures the time of POS for an increasing list: Code: \<< 1 SWAP Example { 1 1 1 1 1 1 1 1 } 10 This produced the following values: 8 14 29 74 93 181 245 343 430 580 It looks like an exponential curve to me: Since the length of the list is doubled in each iteration this gives a linear relationship. At least it is not logarithmic and definitely not constant. |
|||
07-05-2022, 04:28 PM
Post: #11
|
|||
|
|||
RE: Little problem(s) July 2022
(07-05-2022 02:03 PM)John Keith Wrote: Very nice program, as usual. Thank you! Quote:This is not really an improvement, but I couldn't resist a functional version of your program for the 48G You should know by now that I prefer functional programming. It's really a very nice solution. Quote:As an addendum to your addendum, your program is technically O(n^2) but since built-in functions like POS are many times faster than any UserRPL equivalent, it comes out much closer to O(n) in practice. This reminds me of Clojure’s persistent vectors, which gives practically O(1) runtime for appends, updates, lookups and subvec. Because each node has 32 leaves, the tree becomes very flat. Thus, access is constant for most practical use cases. |
|||
07-05-2022, 09:41 PM
Post: #12
|
|||
|
|||
RE: Little problem(s) July 2022
(07-05-2022 01:56 PM)pier4r Wrote: Why is POS \(\mathcal{O}(n)\) in userRPL? Is there no direct access to the position in a list, does the system have to iterate through the elements every time? (is DOSUBS the only way to avoid it?) POS first need to match the object, then return its position. With unsorted list, linear search is O(n) Sorted list can use binary search, time complexity O(log(n)) BTW, if the list were sorted, there is no need for POS at all. We just repeatedly shorten the 2 tails ... Code: function f2(lst, x) -- lst sorted, no duplicates lua> f2({2,7,11,15}, 17) 1 4 lua> f2({2,5,7,8,10,11,15}, 15) 2 5 3 4 |
|||
07-06-2022, 06:16 AM
Post: #13
|
|||
|
|||
RE: Little problem(s) July 2022
This is a solution for #1 for the HP-42S:
Code: 00 { 38-Byte Prgm } But it should work with the HP-41C as well after minor adjustments. The \(\text{target}\) and the values of the list \(\{a_1, a_2, \cdots, a_n\}\) are expected in the registers: R00: \(\text{target}\) R01: \(a_1\) R02: \(a_2\) … Rnn: \(a_n\) Example 17 STO 00 2 STO 01 7 STO 02 11 STO 03 15 STO 04 4 XEQ "FIND" 4 1 |
|||
07-06-2022, 06:35 AM
Post: #14
|
|||
|
|||
RE: Little problem(s) July 2022
This is my attempt of a solution for #2 for the HP-42S:
Code: 00 { 41-Byte Prgm } I tried to use the undocumented function [FIND] with John's idea. Example [ 4x1 Matrix ] 17 XEQ "FIND" But alas it fails when using the Free42 simulator. It appears that [FIND] is not using the indexed matrix N but the matrix that is currently edited. Therefore all elements are found. I've tried to index the matrix N within the loop but that gives me an error: Restricted Operation Interestingly I can do that manually while editing the matrix. But that exits the edit mode. I can't check this with my HP-42S right now. But maybe someone else can confirm that this is the same behaviour. |
|||
07-06-2022, 07:48 AM
Post: #15
|
|||
|
|||
RE: Little problem(s) July 2022
It is the same in the real 42S.
You cannot EDIT a matrix and INDEX another one at the same time - EDITing implies INDEXing, and there can be only one matrix indexed at any one time. The only way to access two matrices at the same time is to store one in REGS and EDIT/INDEX the other. Cheers, Werner 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE |
|||
07-06-2022, 08:29 AM
Post: #16
|
|||
|
|||
RE: Little problem(s) July 2022
(07-06-2022 07:48 AM)Werner Wrote: store one in REGS and EDIT/INDEX the other Thanks a lot for the hint. This appears to work: Code: 00 { 49-Byte Prgm } Example 17 [ 4x1 Matrix ] XEQ "FIND" Y: 4 X: 1 |
|||
07-06-2022, 01:29 PM
Post: #17
|
|||
|
|||
RE: Little problem(s) July 2022
(07-05-2022 09:41 PM)Albert Chan Wrote: BTW, if the list were sorted, there is no need for POS at all. This is a very good solution, especially for languages that have sets or binary trees as data types. On the HP48, unfortunately, a UserRPL implementation would be slower than one using POS. |
|||
07-07-2022, 05:56 AM
Post: #18
|
|||
|
|||
RE: Little problem(s) July 2022 | |||
07-07-2022, 10:51 AM
Post: #19
|
|||
|
|||
RE: Little problem(s) July 2022
(07-05-2022 03:41 PM)Thomas Klemm Wrote:(07-05-2022 01:56 PM)pier4r Wrote: Why is POS \(\mathcal{O}(n)\) in userRPL? Yes somehow I managed to mix POS with GET in my mind (I hope GET is O(1) with lists in userRPL, now I start to have doubts). (thank you to Albert Chan as well!) But then we cannot really lie to the interviewer can we? That is also the interesting part of those problems solved with the calculator capabilities, one doesn't exactly have all the tools (data structures or methods) needed. Wikis are great, Contribute :) |
|||
07-07-2022, 11:15 AM
Post: #20
|
|||
|
|||
RE: Little problem(s) July 2022
(07-07-2022 10:51 AM)pier4r Wrote: one doesn't exactly have all the tools (data structures or methods) needed That's why we should use MIX (or nowadays rather MMIX) in job interviews. Cf. MMIX Home Page |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 2 Guest(s)