InMobi Interview Question for SDE1s


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

import java.util.Scanner;

public class Solution{
	public long  getValue(long  a, long  b, long  c, long  d, long n){
		return a * n * n * n + b * n * n + c  * n + d;
	}
	public long  findT(long  a, long  b, long c, long d, long k){
		long  result = 1;
		long  right = 1000000;
		long  left = 1;
		long  mid = left;
		long shouldReturn = 1;
		while(left < right){
			mid = left + (right - left) / 2;
			result = getValue(a ,b, c , d, mid);
			if(result == k){
				break;
			}
			if(result < k){
				shouldReturn = mid;
				left = mid + 1;
			}else{
				right = mid - 1;
			}
		}
		return shouldReturn;
	}
	public static void main(String[] args){
		Solution s = new Solution();
		int T, K, a, b, c, d;
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int i  = 0; i < T; ++i){
			a = scanner.nextInt();
			b = scanner.nextInt();
			c = scanner.nextInt();
			d = scanner.nextInt();
			K = scanner.nextInt();
			System.out.println(s.findT(a, b, c, d, K));
		}
	}
}

- ravio June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))

- Blahfoo June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- balaji June 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@balaji

Read up on Newton raphson method which is a fast method of finding zeros of a polynomial. Of course, one can do it in a more usual bisection method similar to binary search, but this is probably faster.

- Blahfoo June 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Anonymous June 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Blahfoo June 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My bad,
You are right, t > 0 and A,B,C,D all positive.
F(t) is monotonic for t > 0

F'(t) is always positive for t>0

- Anonymous June 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Abhijit October 06, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More