Sum Of Perfect Powers

August 31, 2018

I think this must be somebody’s homework:

Write a program to determine if a number x can be written as the sum of two perfect powers. This is, given x determine if there exist non-negative integers a, b, m and n such that am + bn = x where 1 ≤ x ≤ 106 and m > 1 and n > 1.

Your task is to write a program that determines if a number is a sum of two perfect powers. 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.

Advertisements

Pages: 1 2

Array Of Integers

August 28, 2018

Today’s exercise is an interview question from Amazon:

You are given an array of integers, not necessarily unique. Your goal is to transform the array of integers so that the smallest number does not differ from the largest number by more than two times by removing integers from the array; thus, if x is the smallest element in the array, and y is the largest, then y ≤ 2x. You need only find the number of items to be removed from the array, not make a list of the items. As an example, given the array [4,5,3,8,3,7], you can remove the 2 smallest integers, leaving [4,5,7,8], so that 8 ≤ 2 × 4, or you can remove the 2 largest integers, leaving [3,4,5,6], so that 5 ≤ 2 × 3.

Your task is to write a function to determine how many items to remove from the array. 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

Data Structures Homework

August 24, 2018

Today’s exercise is from a programming student taking a Data Structures course, using Java.

Given a text file, print a list of the ten most common words in the file, along with their frequency of occurrence. You may not use a HashMap or ArrayList, but you may use regular expressions.

Your task is to write a program to find the ten most common words in an input file. 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

Mars Rover

August 21, 2018

Today’s exercise is a Microsoft interview question:

Write code using the commands below for two rovers to meet. Two rovers are dropped on Mars. Imagine Mars to be a straight infinite plane. When the rovers are dropped on Mars they are dropped with a parachute, so their initial position on Mars is on the parachute:

The only commands available are:

  1. Go left.
  2. Go right.
  3. No operation.
  4. If on parachute go to label.

A label points to a piece of code with a name where it is possible to transfer execution.

Using ONLY the commands above, write code to enable the rovers to meet.

Your task is to write a program to help the Mars rovers meet. 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

Matrix Search

August 17, 2018

Today’s exercise is a simple task in matrix manipulation. Given a matrix in which the rows are ordered but the columns or not, efficiently search for a specific item in the matrix. For instance, given the matrix

2 5 8
1 4 7
3 6 9

 

a search for 6 finds it in row 2 column 1, a search for 8 finds it in row 0 column 2, and a search for 0 fails.

Your task is to write a program that searches a matrix. 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 interview question comes from Apple:

Write a program to add two integers. You may not use the + (addition) operator, but may use the ++ (increment by 1) or -- (decrement by 1) operators. Be sure your solution works for both positive and negative inputs.

Your task is to write a program to add two integers. 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

Penniless Pilgrim

August 10, 2018

Today’s exercise comes to us courtesy of long-time reader and contributor Ben Simon; you might like to look at his version of the task:

You must travel from the top-left corner of a five-by-five grid of points to the bottom-right corner, stepping from one point to another without retracing any edge. The first two steps must be eastward through the grid. Each step has a cost. An eastward step adds 2 to the current accumulated cost (so you start with an accumulated cost of 4), a westward step subtracts 2 from the current accumulated cost, a northward step halves the current accumulated cost, and a southward step doubles the current accumulated cost. It is possible to reach the bottom-right corner with an accumulated cost of zero.

Ben’s version of the task has a pretty map of Duonia, and a story about a penniless pilgrim who longs to visit the temple.

Your task is to write a program to find the zero-cost path through the grid. 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 3

Odometer

August 3, 2018

Today’s exercise is an Amazon interview question:

An odometer variously uses letters and digits in its reading; for instance, an odometer might have a reading of G7TS39. Incrementing the odometer means adding 1 to a digit or increasing to the next letter to the next letter, with a carry to the next column when appropriate. Thus, G7TS39 increments to G7TS40 and G7TZ99 increments to G7UA00. As a special case, the odometer never increases in size, but rolls over, so the next odometer reading after Z9ZZ99 is A0AA00. An odometer position that initially contains a digit always contains a digit, and an odometer position that initially contains a letter always contains a letter, so 1Z9 increments to 2A0.

Your task is to write a program to increment an odometer. 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