computational problems

Can you solve this problem?

Given an array, find the largest value in the array.

Is that a computational problem? What is a Computational problem?

The problem above is not a computational problem. 

The array given as the input to the problem above is not well-defined. It could be any of the following

[null, null, null], 

["hello", "Douglas", "world"], 

[1, 3, 4, 5], 

[1, 1, 1, 1],

[],

[2.5, 6.6, 8.9, 10.0]

...... and many more ...

From the examples, since the array is not well-defined, you cannot write a correct algorithm, because depending on the kind of input array it is, your algorithm is going to be completely different. 

In some cases, for example, given an array of nulls, you cannot do a comparison to get the largest value and therefore you cannot write a correct algorithm.

Even in the case where the array is specified as an array of integers, depending on whether the array is sorted or not, you are going to end up writing a completely different algorithm. 

Depending on the kind of input, the solution algorithm is going to be written completely differently

An algorithm, by definition, is a well-defined computational procedure that takes some value as input and produces some value as output. An algorithm is what is used to solve computational problems.

A computational problem should have a well-defined input, including any constraints on the input, (a constraint is just an additional condition on the input), plus a well-defined output, and how the output relates to the input.

bad: Given an array A, find the largest value in A

Good: Given an array of integers A, find the largest integer in A

          input: array of integers

          output: largest integer in A

You can think of a computational problem as a set of inputs and a set of outputs, and there is a relationship between the set of inputs and the set of outputs. Your algorithm is supposed to figure out and establish this relationship so that every element in the set of inputs to mapped correctly to an element in the set of outputs. A particular input to the problem is called an instance of the problem.

An algorithm is correct if it halts for every instance/input to the problem with the correct output

In an interview setting, your first task is to ask questions to determine whether the problem given is a computational problem or not, sometimes interviewers intentionally give you input that is vague and not well-defined, so you have to ask questions to clarify or define the input clearly before attempting to solve the problem.

It is always good to think about the inputs first for the following reasons:

1. Thinking about the input first gives you an idea about how many possible instances/inputs to the problem are there and thus helps with your understanding of the complexity of the problem.
2. Helps you to optimize your code as you can perhaps ignore certain inputs
3. Most importantly the type of input tells you what data structures you can use