deadman
BAN USER 2of 2 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[4partsLeft] = i;
printValidIP(str,i+1,end,partsLeft1,dotIndexArray);
}
else{
break;
}
}
return;
}
}

deadman
September 08, 2012 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(nextEmpty1) 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 xaxis location
//y  current yaxis 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<N1 && y<M1) && (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,K1) + 0.25*findProbability(N,M,x,y+1,K1) + 0.25*findProbability(N,M,x1,y,K1) + 0.25*findProbability(N,M,x,y1,K1);
}
return prob;
}

deadman
August 29, 2012 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.
Open Chat in New Window
 deadman June 07, 2015