deadman
BAN USER- 3of 3 votes
AnswersYou are given an external library (lets say a binary search library) which claims to have certain running time complexity. How would you verify that the claim of the rum time complexity is correct.
- deadman in India
I told him give input of different length(1,N,N^2...) and see the differential change in running time. But he said in the shared system resources it wont give the good idea of running time.
Any other way we can do this?| Report Duplicate | Flag | PURGE
A simple backtracking solution. Quite similar to 8 queens problem.
public class ValidIP {
public static void main(String[] args) {
String str = new String("12221222");
System.out.println("All valid combinations are: \n");
int[] arr = new int[3];
printValidIP(str,0,str.length()-1,4,arr);
}
//Utility function
private static long intVal(String str,int start,int end){
String my = new String(str.substring(start,end+1));
return Long.parseLong(my);
}
private static void printValidIP(String str,int start,int end,int partsLeft,int dotIndexArray[]) {
//If at any point start>end, no need to print anything
if(start>end){
return;
}
//The base case when only one last part of IP is remaining
if(partsLeft == 1){
if(intVal(str,start, end) <= 255){
//This is a valid combination, print it
System.out.println("One valid ip is: "+str.substring(0, dotIndexArray[0]+1)+'.'+str.substring(dotIndexArray[0]+1, dotIndexArray[1]+1)+'.'+str.substring(dotIndexArray[1]+1, dotIndexArray[2]+1)+'.'+str.substring(dotIndexArray[2]+1, end+1));
return;
}
return;
}
for(int i = start;i<=end;i++){
if(intVal(str,start,i) <= 255){
dotIndexArray[4-partsLeft] = i;
printValidIP(str,i+1,end,partsLeft-1,dotIndexArray);
}
else{
break;
}
}
return;
}
}
Hi Andy,
Number line was given just to think in terms of that. Implementation wise its very simple. Corresponding to each country you just need to store the min number and max number. If the random number falls in that range, return that country. If you are still not convinced I'll code it for you by tonight.
First of all, sum the population of all countries. Let the sum be N.
Now think of it in terms of a number line. Have a number line from 1 to N. Now allocate proportional part of the number line to corresponding country based on its population (Higher the population more numbers in number line and vice versa). Let say 1 to n1 is for 1st country , n1+1 to n2 to second and so on.
Now generate a random number between 1 to N. Just return the country which owns that number in that number line.
Use two data structures
1. An array of size N, with index nextEmpty, which indicates where the next element should be added.
2. A hashmap with key as the number itself and value as the index of that number in the array.
For add operation - Just add the number at nextEmpty location, update hashmap and do nextEmpty++.
For remove operation - Get the index of the number from hashmap, remove it from hashmap. Then swap last element in the array(nextEmpty-1) with that element. Update the hashmap and do nextEmpty--
Both operations will be O(1)
//N - Total size of grid - x axis
//M - Total size of grid - y axis
//K - Number of moves (Given as 4 in the question)
//x - current x-axis location
//y - current y-axis location
float findProbability(int N, int M, int x, int y,int K){
if(k==0){
if((x<0 || y<0 || x>=N || y>=M){
return 0;
}
if((x<N-1 && y<M-1) && (x>0 && y>0)){
return 1;
}
}
//For higher K - using recursion
float prob;
if((x<N && y<M) && (x>=0 && y>=0) ) {
prob = 0.25*findProbability(N,M,x+1,y,K-1) + 0.25*findProbability(N,M,x,y+1,K-1) + 0.25*findProbability(N,M,x-1,y,K-1) + 0.25*findProbability(N,M,x,y-1,K-1);
}
return prob;
}
This will be a O(n^2) solution. I think in this case O(n) solution is possible.
The approach will be something like this:
Start traversing from left to right keeping a count of number of elements processed. For each of the position, find the element which should be there (like for position 3i, ai should be there, for 3i+1 -> bi and 3i+2 ->ci and so on). Get the position of ai(or bi or ci) which is derivable and swap it with current element. Next try to find the correct position of swapped element and so on. When your counter reaches n, all you elements will be in correct order.
Repdalecronin028, Animator at Pinterest
Hello, I am Dale. I am a Tourist guide who welcomes tourists . Tourist Guides act as ambassadors of the country ...
RepJaninaGilden, Java Experienced at Boeing
I am Janina , a Registered Nurse with 3 years experience providing healthcare to a variety of patients in different institutions ...
Repedenwraye, Photographic spotter at Enrich Garden Services
I'm more of a Photographic spotter than an expert at creating beautiful, functional and personalised products for teachers, mentors ...
- deadman June 07, 2015