Question

Question:

The function predictAnswer should be made based on the following. Your answer must be able to run in LESS than quadratic time. Either NLogN or linear time is expected.

In the prediction game, the first player gives the second player some stock market data for some consecutive days. The data contains a company's stock price on each day. The rules for the game are:

1. Player 1 will tell player 2 a day number
2. Player 2 has to find the nearest day on which stock price is smaller than the given day
3. If there are two results, then player 2 finds the day number which is smaller
4. If no such day exits, then the answer is -1.

Example 1

stockData size n =10;

stockData = [5,6,8,4,9,10,8,3,6,4]

queries = [6,5,4]

Result is [5,4,8]

On day 6, the stock price is 10. Both 9 and 8 are lower prices one day away. Choose 9 (day 5) because it is before day 6. On day 5, the stock price is 9. 4 is the closest lower price on day 4. On day 4, the stock price is 4. The only lower price is on day 8. The return array is [5,4,8]

Example - 2

stockData size n = 10

stockData = [5,6,8,4,9,10,8,3,6,4]

queries = [3,1,8]

Result is [2,4,-1]

If the day number is 3.both days 2 and 4 are smaller.choose the earlier day,day 2.

If the day number is 1,day 4 is the closet day with a smaller price.

If the day number is 8,there is no day where the price is less than 3.

The return array is [2,4,-1]

Code Snippet:

/*

     * Complete the 'predictAnswer' function below.

     *

     * The function is expected to return an INTEGER_ARRAY.

     * The function accepts following parameters:

     *  1. INTEGER_ARRAY stockData

     *  2. INTEGER_ARRAY queries

     */

def predictAnswer(stockData, queries):

Answer 1

Python code for above problem

def predictAnswers(stockData,queries):
   result=[]
   for day in queries:
       left_index=day-2
       while(left_index>=0):
           if(stockData[left_index]<stockData[day-1]):
               break
           left_index-=1
      
       right_index=day
       while(right_index<len(stockData)):
           if(stockData[right_index]<stockData[day-1]):
               break
           right_index+=1
          
       min_val_1=99999999
       min_val_2=99999999
      
       if(left_index>=0):
           min_val_1=abs(left_index-day+1)
      
       if(right_index<len(stockData)):
           min_val_2=abs(right_index-day+1)
          
       min_val=min([min_val_1,min_val_2])
      
       if(min_val==99999999):
           result.append(-1)
       elif(min_val_1<=min_val_2):
           result.append(left_index+1)
       else:
           result.append(right_index+1)  
      
   return result
  
print(predictAnswers([5,6,8,4,9,10,8,3,6,4],[6,5,4]))   # prints [5,4,8]
print(predictAnswers([5,6,8,4,9,10,8,3,6,4],[3,1,8]))   # prints [2,4,-1]

Mention in comments if any mistakes or errors are found. Thank you.