ishantagarwal1986
Yes, in knapsack every possible case gets covered, so this case will also get covered. Just some memorization is done in knapsack.
 ishantagarwal1986 November 21, 20111 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Clearly for this case the median = (8 + 9)/2 doesn't lie on the secondary diagonal, so medians of matrix = median of scndry diagonal is completely wrong.
 ishantagarwal1986 November 13, 2011Another possible algo could be if we are talking only of integer values then straight away check for the time slots of 1 hour i.e 89 so on so forth, this way we will not need to sort. and it can be done in O(10 * n) i.e O(n) complexity, also without using any extra memory to save anything, else pallavis soln seems to be fine.
 ishantagarwal1986 November 12, 2011If either all characters are present odd no of times or all are present even number of times, in tht case the result will be 2 and in any other case the result will be 1. Please suggest a case where this does not hold true.
 ishantagarwal1986 November 12, 2011Well it appears to be that it is going to be either 1 or 2 but with a b c as unequal also the min value will come to 2 for e.g. try acbcc > aacc > abc > cc
 ishantagarwal1986 November 12, 2011Should be straight forward as below
public void output(String abc, List delims){
int len = abc.length();
StringBuilder stb = new StringBuilder(abc);
StringBuilder newWord = new StringBuilder();
int i = 0;
while(i<len){
while(i<len && delims.contains(stb.charAt(i)))
i++;
while(i<len && !delims.contains(stb.charAt(i)))
{newWord.append(stb.charAt(i));
i++;
}
if(i<len && delims.contains(stb.charAt(i)))
newWord.append('');
}
return newWord.toString();
}

ishantagarwal1986
November 12, 2011 Leave it, infact the last nodes pointer will also be poinitng to null so its fine, ur code will work fine with complexity O(nlogn).
 ishantagarwal1986 November 03, 2011yes dude, I wrongly calculated it, the complexity is going to be of the order of O(nlogn) in the second case, but just one minute edge case is missing that the last node's right pointer should be pointing to null.
 ishantagarwal1986 November 02, 2011Dude, i m not sure if ur code is correct, but atleast the complexity is O(n*n).
 ishantagarwal1986 November 02, 2011Hey dude I do know that using local variables is preferable as compared to global variables but I am just curious to know that did the i/wer explicitly asked that u shd not use global variables, anyhow the answer without global variables is and in complexity O(n)
public Node bstToList(Node current, Node lastPrintedPointer){
if(current.getRight() != null){
lastPrintedPointer = bstToList(current.getRight(), lastPrintedPointer);
}
current.setRight(lastPrintedPointer);
lastPrintedPointer = current;
if(current.getLeft()!=null)
lastPrintedPointer = bstToList(current.getLeft(), lastPrintedPointer);
return lastPrintedPointer;
}

ishantagarwal1986
November 01, 2011 Node head = null, lastNode = null;
public void bstToList(Node current){
if(current == null)
return;
if(current.getLeft()!=null)
bstToList(current.getLeft());
Node right = current.getRight();
if(head == null){
head = current;
}
if(lastNode != null)
lastNode.setRight(current);
lastNode = current;
lastNode.setRight(null);
if(right!=null)
bstToList(right);
}

ishantagarwal1986
November 01, 2011 I am pretty sure that following soln will work. The concept is simple, if at any point we find that the current petrol used is less than the distance traveled then just start again from the very next point considering it as the first point.
public int petrolPump(int[] petrol, int[] distance){
int i = 0, start = 0, tot = 0;
while(true){
tot++;
if(count == 0){
start = i;
}
cp = cp + petrol[i];
dist = dist + distance[i];
count++;
if(cp < dist){
count = 0;
cp=0;
dist = 0;
}
if(count == len)
break;
i++;
if(i>len1)
i = 0;
if(tot >= 2*len)
return 1;
}
return start;
}
 ishantagarwal1986 October 30, 2011Following should be O(N) where N is the total number that we want to check for. We can use DP here to make sure that we don't traverse the same values again.
public boolean packets(List pckt, int currentVal, int reqVal, HashMap check){
Iterator itr = pckt.iterator();
while(itr.hasNext()){
int val = (Integer)(itr.next()).intValue();
if(currentVal + val == reqVal)
return true;
else{
if(!(check.contains(currentVal + val)) && currentVal + val < reqVal){
check.add(currentVal + val);
if(packets(pckt,currentVal + val,reqVal,check))
return true;
}
}
}
return false;
}

ishantagarwal1986
October 29, 2011 This one will be a little better than the earlier solns. because here we are not using "String" instead we are using "StringBuffer" which is mutable, hence lesser number of objects will get created, so little improvement in terms of time complexity as well as space complexity.
 ishantagarwal1986 October 29, 2011public void printString(List chars, int reqLength, int currentLength, StringBuilder stbd){
if(reqLength == currentLength)
{
System.out.println(stbd);
return;
}
Iterator itr = chars.iterator();
while(itr.hasNext()){
stbd.append(((Character)itr.next()).charValue());
printString(chars, reqLength, currentLength+1, stbd);
stbd.delete(stbd.length()1);
}
}

ishantagarwal1986
October 29, 2011 I guess it is that simple only, i.e. all that is needed to be done is to reverse the pointers of the node from root to the node that is being held in the right hand, that's all. And important thing is that the condn of nary tree will not break because for each node whose pointer is being reversed is actually loosing one child is also gaining one child as well. But yes for that one particular node i.e. the one being held in right hand, it could be an issue is if it is already having n children.
 ishantagarwal1986 October 26, 2011I guess this should work. But this is O(n*n) soln. but I guess there has to exist a O(nlogn) soln.
for(i=len/2;i<len;i++){
j=i;
while(j>2*(i(len/2))){
int swap = arr[j];
arr[j]=arr[j1];
arr[j1] = swap;
j;
}
}

ishantagarwal1986
October 25, 2011 Can be solved, by first calculating for tree with 1 node, then tree with 2 nodes, then tree with 3 nodes, so on so forth. Like for tree with 3 nodes it can be calculated by assuming first node as root node so there will be 0 node on left side and 2 nodes on right side, then 1 on left and 1 on right , other being 2 nodes on left side and 0 node on right side and adding all.
 ishantagarwal1986 October 24, 2011Complexity will be O(n*n). We have to reverse element by element. Kindly suggest if you know a way to do this with lesser complexity.
public static void main(String[] args){
for(int i=1;i<stackSize;i++){
Object obj = reversestack(stack,i,0);
stack.push(obj);
}
}
public Object reverseStack(Stack stack, int toBeReversed, int current){
Object obj = stack.pop();
if(current == toBeReversed){
return obj;
}else{
Object obj2 = reverseStack(stack, toBeReversed, current+1);
stack.push(obj);
return obj2;
}
}

ishantagarwal1986
October 23, 2011 if the numbers can be repetitive and can have ve values, ur method isn't gonna work, and in case, if numbers are not repetitive or say the nos are unique then, the best way would be to just deduct first number from K, and apply binary search on the array with length = resulting value, starting from zero..
 ishantagarwal1986 October 23, 2011Infact according to me, either one demon will live or everbody including will live. Lets say 1st demon will eat the man thinking that if he eats the man than no demon will eat this demon, as the second demon will become the target. If all demons will think this way then no demon will stay will alive but one.
In other case lets assume that all demons think the other way round that if it eats and then sleeps, then it will get eaten, so no one will get eaten.
mng soln seems to be appropriate
 ishantagarwal1986 October 22, 2011Kindly consider the time complexity also.
 ishantagarwal1986 October 22, 2011int minLevel = 100000;
public void calc(Node nd, int level){
if(level!=0 && nd.left() == null && nd.right() == null && level<minLevel ){
minLevel = level;
return;
}
if(nd.left()!=null)
calc(nd.left(),level+1);
if(nd.right()!=null)
calc(nd.right(),level+1);
}
HashSet set = new HashSet();
StringBuilder str = new StringBuilder();
while(i<string.length){
while(i<string.length&&string.charAt(i)!=' '){
str.append(string.charAt(i++));
}
set.add(str.toString());
while(i<string.length() && string.charAt(i)==' '){
i++;
}
str.delete(0,str.length());
}
Simple take two arrays and keep on incrementing the index values corresponding to the ASCII values of the characters in two strings, if arrays match completely the strings are anagrams.
 ishantagarwal1986 October 16, 2011I could think of this soln only, kindly suggest a smaller soln. if possible, in terms of time complexity.
 ishantagarwal1986 October 16, 2011I guess this can be or should be done using DP. assume that we have kept the left parts of all the parentheses now we are suppose to place the right part of the n parentheses,
therefore we start by placing ) at the last and keeping all the entries or strings in a hashmap, for checking if we have already made/visited a particular combination. Now the second ")" can be placed at 3 positions i.e. last, 2nd last, 3rd last out of which last and second last will be same so only one entry will go in the map. Similarly we will keep doing this for all other remaining ")" parantheses, and at the end count/print all Strings in the hashmap which have length 2n.
Dude bit operations are anyways faster, and more importantly, in any soln. other than the XOR one u will have to travel thru all values and parse them. So I don't think that any other soln will be extremely less in time complexity than the XOR one.
 ishantagarwal1986 October 04, 2011The above soln. is O(n) only in time complexity , although the space complexity is O(n)!
 ishantagarwal1986 September 28, 2011Please correct me if I am wrong. Keep a variable max for updating it and a variable sum to keep the current sum, now start with any value on the circle, and add it to sum, if value of sum becomes less than to zero because of addition of any new element, make sum = 0 else continue, and again start adding elements to sum , while doing this just keep updating the "max" value. We will need to do this nearly 2 times on the circle, also make sure that the same element doesn't get added twice.
 ishantagarwal1986 September 28, 2011and by "orignial String" I mean the other string, which we have NOT appended.
 ishantagarwal1986 August 23, 2011It's simple, I guess wats intended is that the relative distance or displacement of characters should remain the same. So the soln for this would be to append the same string in itself and now start checking if the original string is present in this String or not.
 ishantagarwal1986 August 23, 2011Open Chat in New Window
yes u r right, if given is ab or ac or bc in tht case too it will be 1. looks like what i wrote is true for strings greater or equal to of length 3
 ishantagarwal1986 December 05, 2011