Magento2 REST API Error 'Class does not exist'

A DocBlock is required in app/code/Test/Calculator/Api/CalculatorInterface.php as described here: http://devdocs.magento.com/guides/v2.0/coding-standards/docblock-standard-general.html

<?php

namespace Test\Calculator\Api;

interface CalculatorInterface
{
    /**
     * Add two numbers.
     *
     * @param int $num1
     * @param int $num2
     * @return int
     */
    public function add($num1, $num2);
}

In my case problem was that I used "use" clausule in interface. Magento DocBlockReflection could not handle that and was searching for interface without full namespace. So for example in bellow code:

use My\Namespace\ExampleObjectInterface
interface ExampleObjectRepositoryInterface
{
/**
 * xyz
 * @param int $id
 * @return ExampleObjectInterface
 * @throws \Magento\Framework\Exception\NoSuchEntityException
 * @throws \Magento\Framework\Exception\LocalizedException
 */
public function getById($id);
}

I needed to remove "use" clausule:

interface ExampleObjectRepositoryInterface
{
/**
 * xyz
 * @param int $id
 * @return \My\Namespace\ExampleObjectInterface
 * @throws \Magento\Framework\Exception\NoSuchEntityException
 * @throws \Magento\Framework\Exception\LocalizedException
 */
public function getById($id);
}

Make sure below command executed successfully. Don't interrupt or hit any API call. After execution your issue will be resolved. Worked for me.

php bin/magento setup:di:compile