Here is one I have been playing with.

Factorials and Fibonacci numbers are traditionally used as examples of recursive functions.

Let's see them done without recursion with reasonable timing.

I apologize for not coming up with a new one this week, but I will post a few freebies.

I discovered discord, and I spent too much free time helping 8th graders do their home work :) Or so it would appear.

Okay, so my solution didn't meet the O(n+m) complexity. But Iound the correct algorithm, and both are in place and the code is updated. @freemo this was kind of interesting, reminds me of an old card trick I used to do.

@hot9cups Welcome!!

Second Freebie!!! This one is marked as "easy"

Given two singly linked lists that intersect at some point, find the intersecting node. The lists are non-cyclical.

For example, given A = 3 -> 7 -> 8 -> 10 and B = 99 -> 1 -> 8 -> 10, return the node with value 8.

In this example, assume nodes with the same value are the exact same node objects.

Do this in O(M + N) time (where M and N are the lengths of the lists) and constant space.

Freebie!! Here you go!

A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighboring houses are of the same color.

Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color, return the minimum cost which achieves this goal.

Here's a freebie. They labeled it as "Hard"

Suppose we represent our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
subdir1
subdir2
file.ext
The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext
The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

Note:

The name of a file contains at least a period and an extension.

The name of a directory or sub-directory will not contain a period.

@sptnkmmnt privet, kak dela?

Okay, this is a big one (description-wise) but basically the idea is to build a Monte Carlo simulation craps simulator to observe strategic differences between "Pass", "Don't Pass", with and without odds.

Here is a description of the necessary craps rules. Ask whatever questions that I haven't made clear.
git.qoto.org/Absinthe/crapssim

This one is super free! It is not a programming problem so much as a BASH problem.

Using bash parameter expansion only gnu.org/software/bash/manual/h

Given an arbitrarily long path, such as "/head/shoulders/knees/and/toes/eyes/ears/mouth" stored in a variable $TEMP construct a parameter expansion to render only the last two subdirectory and filename like "eyes/ears/mouth" such that you can simply offer the command "echo${TEMP<stuff goes in here>}"

And yes I do know how much easier it is to do with grep, sed, python, perl, awk <insert your favorite alternate solution here> can do it better and easier. This is a real world problem, and someone on Reddit pointed me in the right direction.

I think I may have an idea for the problem this week. Who likes "Craps?" I will work on the specifics, and think of some additional what-ifs as well.

Here us my attempt in python:

git.qoto.org/Absinthe/randchoi

Here is my attempt in python

git.qoto.org/Absinthe/montecar

I tried it basing on a sample size of attempts, and also trying until I got so many successful points in circle.

c++ solution

Here's another freebie, but I am not really sure how to solve it. Guess I wouldn't be getting that job at 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 :)

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".

QOTO: Question Others to Teach Ourselves. A STEM-oriented instance.

No hate, No censorship. Be kind, be respectful

We federate with all servers: we don't block any servers.