La Fée Verte @Absinthe@qoto.org
The green faerie
Joined Aug 2019
Here is my attempt in python
https://git.qoto.org/Absinthe/montecarlopi
I tried it basing on a sample size of attempts, and also trying until I got so many successful points in circle.
La Fée Verte
boosted
c++ solution
@Absinthe Even worse overengineering than previously: https://gitlab.com/tymorl/warmups/blob/master/MCPie/sol.cpp .
I think the most interesting part is the stopping condition. I arrived at it by a mix of trial-and-error and intuition. The intuition was just "the square is needed, because something something statistics", so pretty bad. If anyone knows what the stopping condition should be I am all ears.
Here's another freebie, but I am not really sure how to solve it. Guess I wouldn't be getting that job at Google :)
This problem was asked by Google.
The area of a circle is defined as πr^2. Estimate π to 3 decimal places using a Monte Carlo method.
Hint: The basic equation of a circle is x2 + y2 = r2.
Here's a fun freebie! Only because I just recently saw a problem similar :)
This problem was asked by Facebook.
Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.
Here's another freebie:
This problem was asked by Amazon.
Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.
For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".
discussion of solution
@freemo I understand that the solution is the nth fib for any n when the choice is 1 or two at a time. And my guess is that it goes with a similar function for other numbers of stairs. I also know that for n stairs there is a summation of each number of permutations with repetition n , 1, 0 + n-1, 2,8 8 + n-2 , 3, 4 and so forth. But I don't understand why the fib() works?
Okay, here is another freebie.
This problem was asked by Amazon.
There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.
For example, if N is 4, then there are 5 unique ways:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.
La Fée Verte
boosted
Python solution
@Absinthe #toyprogrammingchallenge
https://git.qoto.org/zingbretsen/nonadjacent_sums/blob/master/main.py
This solution modifies the list as we loop over it. It ensures that at each step, we have the maximum possible sum at each step.
The possibility of having negative numbers necessitates checking at each step.
O(N) time, and repurposes the original list for calculations, so adds no space overhead. This could also be done with a separate 2-item register if the original list should not be modified. This would also be constant space.
La Fée Verte
boosted
c++ solution
@Absinthe C++ is clearly not the appropriate tool, but I need to refamiliarize myself with it, so thanks for the excercise. Solution: https://gitlab.com/tymorl/warmups/blob/master/nonadjecentSum/sol.cpp .
La Fée Verte
boosted
@Absinthe
I think I understand this discussion, I'm admittedly out of my element though so specific implementation ideas aren't coming to mind (which is exciting for me!). Let me see if I have some basic problem constraints:
a n-letter word W is used for encoding pricesbase(s) are open field, ideally base 10 with a 10-letter word
an anagram of W can be used for decoding to deterministically apply a specific markup or discount
Am I following?
La Fée Verte
boosted
@Absinthe #toyprogrammingchallenge I did this with recursion (plus caching). Will create a repo tomorrow, but the lru_cache in Python is pretty awesome. The recursive solution starts to slow down significantly as the input strong gets longer, but caching the intermediate results keeps it super fast.
Here's a freebie,
This problem was asked by Airbnb.
Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.
For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.
Follow-up: Can you do this in O(N) time and constant space?
@freemo When I was interviewing candidates for jobs in SQL my idea was to have them solve a problem like how to design a database to manage WIlly Loman's missionary book.
However, when I would get some of these young guys in, they will have never seen or read the play. Or never done old school sales where they used a "missionary book."
So for a 15 minute interview I ended up trying to explain the Play or Sales techniques to someone instead of moving forward with questions about table design and so forth. I had to learn to make much simpler examples. Because things you assume are common knowledge, aren't always so common.
Shabbat shalom y'all
Okay, maybe you can help me come up with a problem. I can feel it coming on, so here is where I am going:
A trick for pricing things for negotiation is to hide the price encoded. One of the ways of doing this is using a 10 letter isogram such as "upholstery" to convert 0=u, 1=p, 2=h...9=y. So then you could mark a tag or sticker with Tly for $6.49 (with the capitols for dollars and the lower case for cents) Alternatively, you could have an asking price and hide a lowest taking price TlyLuu Meaning that you could ask 6.49 but settle for 4.00. This way someone else could negotiate with the customers, from the person that set the prices.
So writing a program should be unnecessary, the reason for using the isogram is to make it easy to remember and figure it out simply.
So how hard would a program to do this be? Ideas?
This is not a programming question per-se. It, was however, quite interesting and fun to figure out. I am still looking for a new program for this weekend. Unfortunately, no one seemed too interested in last weekend's one, so I may let it float. But I am still looking for one anyway.
An evil warden holds you prisoner, but offers you a chance to escape. There are 3 doors A, B, and C. Two of the doors lead to freedom and the third door leads to lifetime imprisonment, but you do not which door is what type. You are allowed to point to a door and ask a single yes-no question to the warden. If you point to a door that leads to freedom, the warden does answer your question truthfully. But if you point to the door that leads to imprisonment, the warden answers your question randomly, either saying "yes" or "no" by chance. Can you think of a question and figure out a way to escape for sure?
La Fée Verte
boosted
Octave solution
Linear in time and space by taking advantage of the Fibonacci numbers.
function count = interpretations(string)
ambig = string(1:end-1) == '1' | (string(1:end-1) == '2' & string(2:end) <= '6');
ambig &= string(1:end-1) ~= '0' & string(2:end) ~= '0' & [string(3:end) '1'] ~= '0';
ambig = [false ambig false];
consec = find(ambig(1:end-1) & !ambig(2:end)) - find(!ambig(1:end-1) & ambig(2:end));
fibo = zeros(max(consec), 1);
fibo(1:2) = [2 3];
for i = 3:max(consec)
fibo(i) = fibo(i - 1) + fibo(i - 2); end;
count = prod(arrayfun(@(x)fibo(x), consec)); end;
La Fée Verte
boosted
🇳🇱
This was a really fun programming challenge originally proposed by @Absinthe I want to paste it here, along with my solution, so everyone who is interested can check it out.
Here is the link to his original post: https://qoto.org/@Absinthe/102895801091007015
#toyprogrammingchallenge
Another Freebie...
This problem was asked by Facebook.
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is not allowed.
Here is the link to my solution: https://qoto.org/@freemo/102898629821739556
My solution. This should be a somewhat space-optimized solution in ruby based off the modified concept of a Trie.
https://git.qoto.org/snippets/4
If i made this into a Radix Trie by compressing nodes with single children down I could reduce this further.
But since it does work I thought I'd share it as is. I'll update everyone if i decide to finish optimizing this particular solution.
It does however do a fairly decent job at compressing the tree by making sure no subtree is a duplicate of any other part of the tree (a node of any specific length/id will be the only node with that length.
For clarity I attached a picture from my notes of what the Trie would look like for the encoded string "12345" where the value inside each circle/node is the "length" value of that node, and the value attached to an arrow/vector/edge is the "chunk" associated with that link. The end result is any path from the minimum node (0) to the maximum node (5). This diagram does not include incomplete paths which my program does right now.
Incomplete paths can also be trimmed to further reduce the space. But since incomplete paths each add only a single leaf node to the tree, and might be useful for various use cases I decided to keep it.
#toyprogrammingchallenge
Another Freebie...
This problem was asked by Facebook.
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.
You can assume that the messages are decodable. For example, '001' is not allowed.
La Fée Verte
boosted
@Absinthe got a new challenge soon, been a bit busy but ready for the next!
