Lost Boarding Pass

July 21, 2020

We have today a fun little problem from probability:

On a sold-out flight, 100 people line up to board the plane. The first passenger in the line has lost his boarding pass but was allowed in, regardless. He takes a random seat. Each subsequent passenger takes his or her assigned seat if available, or a random unoccupied seat, otherwise. What is the probability that the last passenger to board the plane finds his seat unoccupied?

Your task is to determine the requested probability, either by reasoning mathematically or by writing a program to demonstrate the probability. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Binary Concatenation

July 14, 2020

We have an interview question today:

The concatenation of the first four integers, written in binary, is 11011100; that is, 1 followed by 10 followed by 11 followed by 100. That concatenated number resolves to 220. A similar process can convert the concatenation of the first n binary numbers to a normal decimal number.

Your task is to compute the nth binary concatenation in the manner described above; report the result modulo 109+7, because the result grows so quickly. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Trailing Zero-Bits

July 7, 2020

Today’s exercise indulges in some bit-hackery:

Given a positive integer, count the number of trailing zero-bits in its binary representation. For instance, 1810 = 100102, so it has 1 trailing zero-bit, and 4810 = 1100002, so it has 4 trailing zero-bits.

Your task is to write a program that counts the number of trailing zero-bits in the binary representation of a positive integer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Spelling Numbers

July 3, 2020

Your task is to write a program that lists all of the numbers from zero to one hundred, inclusive, in alphabetical order. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Shuffle An Array

June 30, 2020

Today’s exercise comes to us from Leetcode via Reddit:

Given an array consisting of 2n elements in the form
[x1,x2,…,xn,y1,y2,…,yn], return the array in the form [x1,y1,x2,y2,…,xn,yn].

The Reddit poster claims to be new to Scheme and functional programming, and was thinking of a solution using length and list-ref, but couldn’t solve the problem.

Your task is to show the student how to solve the problem. When you are
finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Summing A String

June 19, 2020

In a string consisting of digits and other non-digit characters, the digits form an embedded series of positive integers. For instance, the string “123abc45def” contains the embedded integers 123 and 45, which sum to 168.

Your task is to write a program that takes a string and writes the sum of the integers embedded in the string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Counting Fingers

June 16, 2020

A little girl counts on her fingers in a curious way. She counts 1 on her thumb, 2 on her index finger, 3 on her middle finger, 4 on her ring finger, and 5 on her pinkie finger, then works back, counting 6 on her ring finger, 7 on her middle finger, 8 on her index finger, and 9 on her thumb, when she again turns around and counts 10 on her index finger, 11 on her middle finger, and so on.

Your task is to write a program that determines which finger the little girl will be on when she reaches a thousand. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

2Max

June 5, 2020

Today’s exercise comes from Stack Overflow:

Given an array A consisting of N integers, return the maximum sum of two numbers whose digits add up to an equal sum. If there are not two numbers whose digits have an equal sum, the function should return -1. For example, A = [51, 71, 17, 42] would output 93 because there are two sets of numbers with the same digit-sum, (51, 42) with a digit-sum of 6 and (17, 71) with a digit-sum of 8, and the first pair has the maximum sum of two numbers of 93.

Your task is to write a program to calculated the requested maximum sum. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Hidden Squares

June 2, 2020

We have a simple task today:

A number n may have squares hidden among its digits. For instance, in the number 1625649, the consecutive digits 1, 4, 9, 16, 25, 49, 64, 256 and 625 are all squares.

Your task is to write a program that takes a positive integer n and finds all of its hidden squares. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Today’s task is somebody’s homework:

Given an array of integers, determine if it is in decreasing-increasing order, with some initial segment of the array in decreasing order and the remainder of the array in increasing order. If the array is in decreasing-increasing order, return the pivot element (the minimum element in the array); otherwise, return an indication the array is not in decreasing-increasing order. Array elements may be duplicated. For example, the array (10 10 10 8 8 6 4 4 3 12 13 22 31 40 59 68) is in decreasing-increasing order, with pivot element 3, but the array (1 2 4 8 12 32 64) is not in decreasing-increasing order.

The student who asked the question suggests a solution using binary search that takes O(log n) time, but can’t get it to work.

Your task is to write a program to determine if an array is in decreasing-increasing order as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2