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.

Advertisements

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