Knowledge Systems Interview Report
- 0of 0 votes
AnswersProblem Statement for SortEstimate (Binary Search)
- Algorist April 15, 2011
You have implemented a sorting algorithm that requires exactly c*n*lg(n) nanoseconds to sort n integers. Here lg denotes the base-2 logarithm. Given time nanoseconds, return the largest double n such that c*n*lg(n) <= time.
Definition
Class: SortEstimate
Method: howMany
Parameters: int, int
Returns: double
Method signature: double howMany(int c, int time)
(be sure your method is public)
Notes
- lg(n) = ln(n)/ln(2) where ln denotes the natural log.
- Your return value must have a relative or absolute error less than 1e-9.
Constraints
- c will be between 1 and 100 inclusive.
- time will be between 1 and 2000000000 inclusive.
Examples
0)
1
8
Returns: 4.0
Given 8 nanoseconds we can sort 4 integers since
1*4*lg(4) = 4*2 = 8
1)
2
16
Returns: 4.0
Now that c = 2 we need twice as many nanoseconds to sort 4 integers.
2)
37
12392342
Returns: 23104.999312341137
We can almost sort 23105 integers, but not quite.
3)
1
2000000000
Returns: 7.637495090348122E7
Largest possible return.| Report Duplicate | Flag | PURGE
Knowledge Systems Software Engineer / Developer Algorithm - 0of 0 votes
AnswersProblem Statement for AutoLoan (Problem on Binary Search)
- Algorist April 15, 2011
Auto dealerships frequently advertise tempting loan offers in order to make it easier for people to afford the "car of their dreams". A typical sales tactic is to show you various cars, and then talk in terms of what your monthly payment would be, to say nothing of how much you are actually paying for the car, how much interest you pay, or how long you have to make payments.
A typical auto loan is calculated using a fixed interest rate, and is set up so that you make the same monthly payment for a set period of time in order to fully pay off the balance. The balance of your loan starts out as the sticker price of the car. Each month, the monthly interest is added to your balance, and the amount of your payment is subtracted from your balance. (The payment is subtracted after the interest is added.) The monthly interest rate is 1/12 of the yearly interest rate. Thus, if your annual percentage rate is 12%, then 1% of the remaining balance would be charged as interest each month.
You have been checking out some of the cars at your local dealership, TopAuto. An excited salesman has just approached you, shouting about how you can have the car you are looking at for a payment of only monthlyPayment for only loanTerm months! You are to return a double indicating the annual percentage rate of the loan, assuming that the initial balance of the loan is price.
Definition
Class: AutoLoan
Method: interestRate
Parameters: double, double, int
Returns: double
Method signature: double interestRate(double price, double monthlyPayment, int loanTerm)
(be sure your method is public)
Notes
- Because of the way interest is compounded monthly, the actual interest accrued over the course of a year is not necessarily the same as (balance * yearly interest rate). In fact, it's usually more.
- In a real situation, information like this would typically need to be disclosed, but since you aren't at a point of signing any paperwork, the salesman has no legal obligation to tell you anything.
- The return value must be within 1e-9 absolute or relative error of the actual result.
Constraints
- price will be between 1 and 1000000, inclusive.
- monthlyPayment will be between 0 and price / 2, inclusive.
- loanTerm will be between 1 and 600, inclusive.
- The resulting interest rate will be between 0 and 100, inclusive.
Examples
0)
6800
100
68
Returns: 1.3322616182218813E-13
Noting that 68 payments of 100 equals the total price of 6800, so there is no interest.
1)
2000
510
4
Returns: 9.56205462458368
Here, we do pay a little interest. At 9.562% annual interest, that means each month we pay 0.7968% of the balance in interest. Our payment schedule looks like this:
Month | + Interest | - Payment | = Balance
------------------------------------------
| | | 2000.00
1 | 15.94 | 510.00 | 1505.94
2 | 12.00 | 510.00 | 1007.94
3 | 8.03 | 510.00 | 505.97
4 | 4.03 | 510.00 | 0.00
2)
15000
364
48
Returns: 7.687856394581649
This is similar to what purchasing a new car with no money down might look like, if you make payments for 4 years.| Report Duplicate | Flag | PURGE
Knowledge Systems Software Engineer / Developer Algorithm - 0of 0 votes
AnswerProblem Statement
- Algorist April 15, 2011
Given a list of integers, find the n-th smallest number, i.e., the number that appears at index n (0-based) when they are sorted in non-descending order. The numbers will be given in intervals. For example, the intervals (1, 3) and (5, 7) represent the list of numbers { 1, 2, 3, 5, 6, 7 }. A number may be present in more than one interval, and it appears in the list once for each interval it is in. For example, the intervals (1, 4) and (3, 5) represent the list of numbers { 1, 2, 3, 3, 4, 4, 5 }.
The intervals will be given as two int[]s, lowerBound and upperBound. The i-th elements of these int[]s represent the smallest and largest numbers in the i-th interval, inclusive.
Definition
Class: UnionOfIntervals
Method: nthElement
Parameters: int[], int[], int
Returns: int
Method signature: int nthElement(int[] lowerBound, int[] upperBound, int n)
(be sure your method is public)
Notes
- n is 0-based, meaning that the first element is indexed 0.
- A sequence is sorted in non-descending order if and only if for each pair of indices i and j, where i is smaller than j, the element at position i is less than or equal to the element at position j.
Constraints
- lowerBound will contain between 1 and 50 elements, inclusive.
- upperBound will contain the same number of elements as lowerBound.
- Each element of lowerBound and upperBound will be between -2,000,000,000 and 2,000,000,000, inclusive.
- The i-th element of lowerBound will be less than or equal to the i-th element of upperBound.
- n will be a non-negative integer less than the total number of elements in the list, but no greater than 2,000,000,000.
Examples
0)
{ 1, 5 }
{ 3, 7 }
4
Returns: 6
The numbers are 1, 2, 3, 5, 6 and 7. The number at index 4 is 6.
1)
{ 1, 3 }
{ 4, 5 }
3
Returns: 3
2)
{ -1500000000 }
{ 1500000000 }
1500000091
Returns: 91
Watch out for overflow errors.| Report Duplicate | Flag | PURGE
Knowledge Systems Software Engineer / Developer Algorithm