saumils1987
BAN USERbecause i have good logic and coding skills.have a good hand on coding in java and C,C++.
just try out with this solution..
if lenght ,breadth and height is given as 4,6,8 then make a three digit number out of it i.e 468.
do this with all the dimensions given and put that three digit number into an array.
sort this array using radix sort starting from the left most digit of that number and proceeding to the rightmost number.
after getting the sorted array traverse from largest to smallest thereby checking if any of the dimensions of lower one is not equal to its own corresponding dimension. if they are found to be equal just leave that block and proceed to next block down the array and keep on adding them and finally one would get largest subset required.
if we are permitted to use an extra space of order 'k' then the following solution works. declare an array of length 'k'.now traverse thru the original array and copy first 'k' elements as it is in the new array(at the same time keep a note of max and min elements of this array in some variable named max,min). for the further elements check if they lie in the max and min range if yes the replace the max with that element else do nothing.now after the original array is traversed completely ,traverse thru the new array and print the max of it. thus the solution is dere in the given time complexity...
- saumils1987 October 19, 2010i think it would work .. it seems to be more or less like a breadth first search traversal (BFS) with a little modification where the dummy node acts as a marker for a level. i think this is the most optimized approach...
- saumils1987 October 19, 2010sure the order wont be preserved in any case if you use quicksort with pivot as 0...
- saumils1987 October 07, 2010we can start from the left end of the string and gradually move towards right end checking at every step its neighbors(both cases for odd and even length palimdrome) and if criteria for a palindrome if met then spread further in left and right direction to check if they also meet the criteria ,keep speading at each step until criteria fails(then record the start and end index of this palindrome string).. keep doin this till u reach the right end of the string.
hope my logic is convincing for most of the people who have posted the solution or the comments and in case u find any flaw then just let me know ...
since we have large set of data ,so can be done is using the concept of external merge sort i.e bring a chunk of data into the memory and sort it ...
i had read bout this logic sumtime back.. plz reply u find anything wrong in this ..
what more can be done using stacks which are required three in number.
read a node push it in stack say s1 and at the same time push its children into another stack say s2. now read read by popping frm s2 and printing left child of popped node value until s2 gets empty simultaneously push this node to s1 and its children to stack s3.now do the same for s3 using s2 untile one reaches the end of the tree. this way as we move down the tree we keep on printing the left of every node. and after we have traversed the full tree we have all the node ordered in s1. just pop from s1 and print their rhith children and at last print the root which is lowest in the stack s1...
hope this logic makes sense to u guys..
if ne of u finds ne loop hole in dis plz do comment ..
how about about applying the banker's algorithm for resource allocation to each process...
if anyone finds any problem to this approach then just post it here....
lets assume (x1,y1) be bottom left and (x2,y2) as top right .. all we need to check for non intersection is that either of the co-ordinates(x,y) of other rectangle should follow :
x should not be in region [x1,x2] and y should not be in [y1,y2] for each pair of co-ordinates...
dude thats relative velocity question.
lets assume velocity of band as u and dat of dog as v.
let total time be T.
uT=50; and 50/(v+u)+50(v-u)=T
so we get 50/(v+u)+50(v-u)=50/u
solve it to get (v-u)^2=2(u^2) i.e v=(sqrt(2)+1)u
den we know uT=50 so vT=(sqrt(2)+1)uT i.e (sqrt(2)+1)*50 =120.7
@cool: Ur solution is not convincing ,coz there mi8 be a possibility that majority element's all the occurrences are in first and last quarter of array and some other element at A[n/2].. so it need not be necessary that majority element if accurs will be surely at A[n/2] position....
- saumils1987 September 20, 2010start from the lowest left in left sub-tree. make it the root and make its parent its right child and its sibling if any its right grand child.. do this as u move up on tree .... hope this does the required job .. if sum1 has a bettr solution do post it ..
- saumils1987 September 20, 2010yeah
dice 1: 012678
dice 2: 012345 if we use 6.9 by inversion of them by 180 degrees...
it is 120.7 metres... for dog because speed of dog is (sqrt(2)+1) times that of band. and band travel 50 metre in overall time so dog would travel more by a factor of srt(2) time the distance traveled by band ..
- saumils1987 September 20, 2010global static is like that nobody can change it rather i can be used by many.whereas synchronised method makes variable to be accessed by only one computation at a time like semaphores in operating system,so tha data remains protected. no i dnt think that such methods are there in C++;
- saumils1987 September 15, 2010define a static variable that holds initially the product of all the numbers.
den traverse thru the list of number and make the set of (product/a[i]) where 'a' is array of numbers of list of numbers and 'i' is the index while travellin thru the list.
this questions seems to bear a lot of ambiguity.. plz clear the procedure of promoting the odd i.e 9th team in upper levels.if the promotion is to the level right above it then the answer is 11.
gullu do reply to this post ..
yeah suffix tree would do the job..
create a suffix tree of the string of length N.then for each of M small strings of length L ,do the search in this tree and if the small string gets exhausted while reaching the leaf of suffix tree,then it means that the small string is present in the larger string..
right 2(2(2(2x-y)-y)-y)=y
gives x=(15/16)y;
put y =16 to makes x least integer as 15;
the case where K is comparable to n can be solved using counting sort and hence omittin the duplicate counts.the case where k<<n degrades the performance of the counting algo.in that case we can use hash table to map the numbers using an appropriate hash function.do not map the elements in table if they have been already mapped before.
- saumils1987 September 13, 2010initialize sum=0;
for the first and second bit check if they are set and add 1 to sum if first bits is set and add 2 to sum if second bit is set. then proceed on remaining stream from 3rd bit onwards.for every odd bit set add 1 to sum and for evry even bit set substract 1 from sum and meanwhile also make it sure that when sum exceeds 3 den set sum as sum%3.thus at any point of time the value of sum would tell u the divisibily.if sum=0,3 then its divisible else not..
what can be done here is that we need to maintain a stack.at every turn we need to create an object that stores the possible turns that can be taken at that point and also marks which turn we have selected and push that object onto the stack.also at every move forward we need to push move to stack.at a dead end turn around with two right turns and move forward with every pop of move object.as soon as we encounter a turn object,we need to analyse it and start moving it the direction not taken by us before and mark that direction also as taken. continue this until u find a cheeze .
if anyone has beter idea then do post it here and do comment on the idea suggested.
start with finding the max and min of the array and check if min is at beginning or max is at the end .if either of them occurs to be true then accordingly change the start and end of array.recurse it until the max and min within the array boundaries(start and end) dont happen to be at the either extremities.at that point sort the array in length start and end.
- saumils1987 September 13, 2010i think the naswer is 274.66hm
- saumils1987 September 06, 2010i didnt refresh the page for long hence couldn't see that mattj777 has posted the same solution as mine . i saw mattj777's solution after the page got refreshed when i submitted my answer.
nice one frm mattj777...
a better solution would some what similar in the beginning as mentioned by annonymous. but the later part could be done by retracing the path from the node in list(of nodes) having only one leaf(and such nodes won't be more than 2) and then finding the presence of that node in all the leaves(whose nodes are not visited) and wherever we find it use that node to trace back in the similar procedure until we have all the nodes marked as visited.
i think this would be the most optimized approach in terms of time and space. time complexity would be less than O(n2).
sorting by any means other tha counting sort cannot be less than O(nlogn)..
whereas counting sort give it in O(n) at the cost of space.\
this sorting technique is applicable when we know the range of data.
i hope i have explained it well now.
what we can do is that we can make entry of these interval objects in a priority queue that implements the interface comparable and hence give the definition of method compareTo in a way that sorts these objects according to the the lower bound of the interval.
next we can fetch head object from the queue(until head not equal to null and increment head each time) and merge our intervals and create a new object(when next object cannot be merged) for this interval and insert the object in an ArayList.
perform counting sort and create an integer array of length 50.
that would surely do the job..
preorder(root)
{
print(root.element);
if(leftchild!=null)
{
preorder(leftchild);
}
if(leftchild!=null)
{
preorder(rightchild);
}
}
yeah one can easily do and preorder traversal adn get all the nodes printed;
preorder(root)
{
if(leftchild!=null)
{
preorder(leftchild);
}
if(leftchild!=null)
{
preorder(rightchild);
}
}
interoper ur solution is wrong as well ..
only ahj's solution si correct..
here M=3
so ur solution is wrong..
improve the quality of questions :P
- saumils1987 August 28, 2010it can be solved in O(n) time ..
first find two extreme zero's and check if the number of ones's inside them are less than the total number of zero's.if yes them find extra number of ones's on either side to equate the number of 0's and 1's,else start pruning the string frm one side until u encounter the numbers to be equal.
my code below has done the same all what is needed to be appended is that pruning from left side as well so as to get the longest string with same number of 1's and 0's.
import java.io.*;
import java.lang.reflect.*;
import java.lang.*;
class substring{
public static void main(String args[])
{
//System.out.println("code wrks fr string with number of one's more than number of zero's");
String s=args[0];
char[] str=s.toCharArray();
//System.out.println(Array.getLength(str));
//int len=str.length();
int i,c=0,so=0,sz=0,ls,zf,zl,alfa=0,ss,se,ss1,se1;
//while(str[i]!=null){i++;}
int len=Array.getLength(str);
int z=0,o=0,omz=0;
for(i=0;i<len;i++)
{
if (str[i]=='0')
{
z++;
}
else
{
o++;
}
}
i=0;
while(str[i]!='0')
{
i++;
}
zf=i;ss=i;
i=len-1;
while(str[i]!='0')
{
i--;
}
zl=i;se=i;
ls=zl-zf+1;
if(o>z)
{
omz=o-z;
//System.out.println("no is 1's "+zf);
//System.out.println("no is 0's "+zl);
//System.out.println("no is 1's minus no. of 0's "+omz);
for(i=zf;i<=zl;i++)
{
if(str[i]=='1')
so++;
}
sz=ls-so;
//System.out.println("no of ones inside extreme zero's"+so);
if(so<=sz)
{
alfa=sz-so;
if(((len-1)-se)>=alfa)
{
se=se+alfa;
}
else
{
se=len-1;ss=ss-(alfa-((len)-se));
}
for(i=ss;i<=se;i++)
System.out.print(str[i]);
}
else
{
//System.out.print(so+" ");
//System.out.println(sz);
int i1;
i=len-1; alfa=o-z;
//System.out.print(o+"is 1's");
//System.out.println(z+"is 0's");
//System.out.print(alfa+" is alfa ");//System.out.println(sz);
while((alfa!=0))
{
if(str[i]=='1')
{
alfa--;i--;
}
else {alfa++;i--;}
}
if(i==-1){System.out.println("full string exhausted");}else{se=i;}
for(i1=ss;i1<=se;i1++)
System.out.print(str[i1]);
}
}
else return;
}
}
note:one thing more can be appended is if string has just one 0 or one 1.then answer can be given too easily so a check can be put ri8 in the start.
i had coded fr this sumtime back so have just put my code here in a partial cumplete manner acording to the demand of the question but i hope i have made my idea clear to do this question in O(n) time and O(1) space... if sum1 has any prob then let me knw ,i can explain the logic a bit more vividly .
full code :further optimised in terms of computations
import java.io.*;
import java.lang.reflect.Array;
class X
{
static int len;
public static int[] unionMinusIntersect(int[] arr1, int[] arr2) {
int i = 0; // index for arr1
int j = 0; // index for arr2
int k = 0; // index for result
int[] result = new int[arr1.length+arr2.length];
while(i<arr1.length && j<arr2.length) {
if(arr1[i]<arr2[j])
{
result[k++] = arr1[i++];
len++;
}
else if(arr1[i]>arr2[j])
{
result[k++] = arr2[j++];
len++;
}
else {//arr1[i]==arr2[j]
i++;
j++;
}
}
while(i<arr1.length) { //get the leftovers
result[k++] = arr1[i++];
len++;
}
while(j<arr2.length) { //get the leftovers
result[k++] = arr2[j++];
len++;
}
return result;
}
public static void main(String args[])
{
int[] a={1,2,4,7,13,14,15};//user can have inputs as he/she wishes to .
int[] b={2,3,5,8,10,12,13,16,18,19};
int l=a.length+b.length;
int c[]=new int[l];
c=unionMinusIntersect(a,b);
for(int i=0;i<len;i++)
System.out.println(c[i]);
}
}
mayank's code can be modified at the cost of space complexity.
the way in dat code we are looking for all the substrings present in dictionary ,we must save the start and end index(in a 2-D array or arraylist<T>) of all the found words in a dictionary as we process the string.later we can print them with invarient that start index of next words must be one more than end index of previous word. how about this idea?? the time compexity still remains O(n2).
your code fails for the dictionary:
mam
am
ample
pleased
ease
lease
leased
and sentence as:mampleased
output given by your code is: am pleased
which is wrong and rather it should have been:mam pleased.
static data can be protected by using it inside a synchronized method.here at a time only one can use the data since locks are put on it exactly like mutex in semaphores.
- saumils1987 August 25, 2010how bout trying with merge sort and den gettin index 3 frm it..
it will take 11 comparision in all the cases even if its best ,average or worst case..
there can be methods which can use lesser number of comparision but they would be dependent on the type of case.
i think your answer complicates the question even more...
- saumils1987 August 25, 2010even i agree to u Hinax.. make the cuts on the positions which are nearest to the mid of that section of block and continue doin the same. it a sort of binary appraoch as u can say ..
- saumils1987 August 25, 2010one(List) is raw type declared and the other (List<String>) is parameterized...
latter can hold only object of class String wheras the former can hold objects of class Object.
t will be the sum of this series
1+C(n-1,1)+C(n-2,2)+C(n-3,3)+......C(n-x,x) where x<n/2;
exaplanation:
there is 1 way when only one step is taken each time for n times to climb up.
next we take a double(2) step and all other single(1) steps, in dis case total number of times i need to take steps will be n-1.
do this recusively increasing the number of double steps taken and arraging those.
this is code that answers for all possible test cases.
import java.io.*;
class X
{
static int max=Integer.MIN_VALUE;
public static void main(String args[])throws Exception
{
int f1=0,t1=0,frm=0,to,i,j,len,sum;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("enter length of array");
len=Integer.parseInt(br.readLine());int[] arr=new int[len];
for(i=0;i<len;i++)
{
arr[i]=Integer.parseInt(br.readLine());
}
for(to=2;to<len;to++)
{
for(i=0;i<(len-to);i++)
{
sum=0;
for(j=(i+frm);j<(i+to);j++)
{
sum+=arr[j];
}
if(sum>max)
{
max=sum;
f1=frm+i;
t1=to+i-1;
}
}
}
System.out.println("max is "+max);
System.out.println("start index"+f1);
System.out.println("end index"+t1);
}
}
what can be done is start from the max element i.e rightmost lowest.
- saumils1987 November 25, 20101.push its neighbors into a max heap.
2.chose the max of this heap and include it into our move and then delete it from the heap.
3.also add its neighbors into the heap thereby maintaining the max property.
4.goto step 2 until we have done it for k times.
i hope this algo might work out.
complexity is is < nlogn.