InMobi Interview Question
SDE1sCountry: India
Interview Type: Written Test
Foo_function is monotonically increasing for t in [0, 10^18] because all coefficients are positive. Therefore there is at most one solution to the equation F(t) - K = 0 for t in [0, 10^18]
import sys
import math
file = open('input')
n = int(file.readline())
def polyvalAt(x):
return a*x*x*x + b*x*x + c*x + d
def dbydx_polyvalAt(x):
return 3*a*x*x + 2*b*x + c
for line in file:
if n == 0:
break
n = n - 1
a, b, c, d, k = map(float, line.split())
# transform F(t) = K to F(t) - K = 0
d = d - k
# if d > 0 then no solution exists
if d > 0:
print('Inv')
continue
mid = 0
while (1):
if abs(polyvalAt(mid)) > 0.000001:
mid = mid - polyvalAt(mid)/dbydx_polyvalAt(mid)
else:
break
print(int(mid))
How did you arrive at the condition
x = x - (a x^3+ bx^2+cx+d) / (dy/dx ( a x^3+ bx^2+cx+d ) ) can be used for narrowing down the value of x.
The derivative of F(t) is a quadratic function.
with coefficients 3A, 2B, C.
You cannot conclude that F(t) is monotonic.
You have to solve the F'(t), find the 2 stationary points p1, p2 if they exist.
Say F(p1) < F(p2).
If F(p1) < K < F(p2), the locate t after p2.
If F(p2) > K, then locate t before p1.
In those 2 cases, the parts of F(t) on those intervals is monotonic
If p1, p2 don't exist, F(t) is monotonic so you just locate t the normal way.
Using numerical method. (Or Cardano formula to find solution of cubic equation)
It says A, B ,C, D are prime numbers hence they are all positive.
At³ + Bt² + Ct + D must be monotonically increasing for t > 0 and all co-efficients positive.
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;++i)
#define repr(i,a,n) for(int i=n-1;i>=a;--i) // reverse order
#define cube(x) ceil(exp(float(log(x)/3)));
using namespace std;
int main()
{
long a=3,b=5,c=7,d=11,k=123498761234,f;
long t = cube(k); // t must be less than equal to cuberoot(k)
long temp;
//cout << t << endl;
repr(i,0,t)
{
temp = a*i*i*i + b*i*i + c*i + d;
if(temp <= k)
{
cout << i << endl;
break;
}
}
return 0;
}
Just do binary search and use a variable to track the most recent value that can have the equation less than k. Here is the java code for this.
- ravio June 01, 2014