Home

Evaluating a polynomial

1,443.8K Views

There is a polynomial and you have access to a function that evaluates that polynomial at a given number.  You don’t know the degree of the polynomial, nor do you know any of the coefficients of its terms.  However, you are told that all coefficients are non-negative integers.  How many times do you need to call the evaluation function in order to identify the polynomial (that is, to figure out the values of its coefficients)?

Share
ronret45 Expert Asked on 1st August 2015 in Microsoft Interview Puzzles.
Add Comment
Cancel

    • 1 Answer(s)

    We can determine the coefficients of the polynomial by making evaluations of the polynomial at specific values.

    First, we can evaluate the polynomial at x = 0. This will give us the constant term of the polynomial.

    Next, we can evaluate the polynomial at x = 1. This will give us the sum of all the coefficients.

    Then, we can evaluate the polynomial at x = 2. This will give us the sum of the squares of all the coefficients.

    We can continue this process and evaluate the polynomial at x = 3, x = 4, and so on, until we have enough equations to solve for all the coefficients.

    Specifically, if the degree of the polynomial is n, we can evaluate the polynomial at n + 1 distinct values of x to obtain a system of n + 1 linear equations in n + 1 unknowns (the coefficients of the polynomial). We can then solve this system of equations to determine the values of the coefficients.

    Therefore, we need to call the evaluation function at least n + 1 times to identify the polynomial. Note that this is a lower bound, and in practice, we may need to call the evaluation function more than n + 1 times to ensure that we have enough independent equations to solve for all the coefficients.

    Cancel
    Moshe Expert Answered on 23rd March 2023.
    Add Comment
    Cancel

    • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.

  • More puzzles to try-

  • Accenture Interview PuzzlesAdobe Interview PuzzlesAge RiddleAkbar Birbal PuzzlesAlgorithm PuzzlesAlphabet riddleAmazon Interview PuzzlesAnalytical MathematicsAptitude PuzzleBank PuzzlesBetting PuzzlesBrain TeasersCalendar PuzzlesCards PuzzlesChess Board PuzzleChess PuzzlesChristmas Puzzlecipher PuzzleCivil Services PuzzleClock time puzzleCognizant Interview PuzzlesCoins PuzzleComputational PuzzleconundrumCoronavirus PuzzleCoupondunia Interview PuzzleCritical Thinking Puzzledata analyticsData Structure Interview QuestionsDecode PuzzleDetective PuzzlesDice PuzzleDictionary Riddlesdifficult riddleEasy Math puzzlesEasy puzzlesEinstein puzzleEnglish RiddleFamily Tree Puzzlefamous puzzleFill in the blanks riddlesFinding Killer RiddlesFlipkart interview puzzlesFunny RiddlesGeneral KnowledgeGeographical PuzzleGoogle Code Jam 2014Google Interview PuzzlesGRE PuzzleHard Puzzle