Anshul
BAN USER1. Do an inorder and post order traversal
2. find position of both elements in inorder array and note the range.
3. now find rank of all elements from this range in post order array.
4. last ranked element in post order is lowest common ancestor.
an O(N) solution wrt time complexity.
Well searching time in a max heap can be optimized upto N/2 at max, so according to me a regular max heap won't help. You can either choose an
1. Skip list: Which on average take O(log n) time for inserting,searching and replacing. You can keep a pointer to the last node always for LRU entry, updation of which will O(1) time if Skip list is implemented using a Quad node.
2. Heap structured search trees (HSST) looks another good option. But skip list being a standard and more evolved DS, I would like to give it a shot at first.
An easy and iterative way....just keep on swapping nodes while you reach the end....
static ListNode swapAdjacentNodes(ListNode head) {
if(head==null || head.next==null) {
return head;
}else {
ListNode current=head;
head=current.next;
current.next=head.next;
head.next=current;
while(current.next!=null && current.next.next!=null) {
ListNode temp=current.next;
current.next=current.next.next;
temp.next=current.next.next;
current.next.next=temp;
current=current.next.next;
}
return head;
}
}
@AlgoFreek...
Appreciate your work but it is not working in any case....:(
1. You have written ( random!=start ) in both cases as random will be always equal to start in the beginning it will never enter your loop.
2. You always need to return the same node as you were passed on the first place.
Did you test this code? :P
Yeah...forgot about that.....
I got a nice solution for it....But u'll need to use RandomAccessFile in place of inputstream...
1. Set seek() method at the end of input file and read a character...
2. Read and store the character in a StringBuilder and decrease the seek() position of input file by 1.
3. Repeat steps 1-2 until you encounter a space or a newline character.
4. Call reverse() function of String builder object and write it to an output file.
5. Repeat steps 2-3-4 until you reach start of input file...
Well I won't say its too easy unless you are allowed to traverse once and get the head aka minimum element....Three cases will arrive in this case...
1. value is less than givenNode.data.
2. value is greater than givenNode.data.
3. value is equal to given givenNode.data.
Implementation won't be much complex...but yes it will take time...if you consider all the cases like largest element and only 1 node in the list etc..
Java implementation...
docs.google.com/open?id=0Bw6L8Yy5eLJ3WGhpRENTcHNlekk
Well I won't say its too easy unless you are allowed to traverse once and get the head aka minimum element....Three cases will arrive in this case...
1. value is less than givenNode.data.
2. value is greater than givenNode.data.
3. value is equal to given givenNode.data.
Implementation won't be much complex...but yes it will take time...if you consider all the cases like largest element and only 1 node in the list etc..
Java implementation...
docs.google.com/open?id=0Bw6L8Yy5eLJ3WGhpRENTcHNlekk
Or if you want to do it using only 1-2 more files....
1. Read character by character and keep writing it at the start of the new file using RandomAccessFIle class from java....
2. You can change the writing position of temp file using RandomAccessFile class in java and use its seek method to set the pointer to start of the file each time...
3. When finished reading the file...take each word at a time from the temp file...reverse it and write it to the result file...
I agree with Eugene...Here is an implementation in java...I did not reverse the list back....u might not wanna use it if other threads are using the same list as well....if not...you can call the method again to reverse the list back...algo it still O(n)
docs.google.com/open?id=0Bw6L8Yy5eLJ3T3JZNDRYbTBQbmM
1. Just keep track of max_sum, max_start and max_end so far.
2. Keep storing new sum in temp_sum and new start in new_start new end will be "i".
3. If temp_sum is greater than max_sum update all max variables.
O(n) and done in place....
Here is an implementation in java...
docs.google.com/open?id=0Bw6L8Yy5eLJ3MUQxM3B2MVNEMkE
Here is the algorithm...
1. Assuming that we have memory for only 1-2 lines...read first line.
2. Split the string with given seprator and write it to a temp file e.g 1.tmp, 2.tmp,3.tmp....
3. Repeat steps 1 and 2 until input data is finished.
4. Now make an output file and write data to it from temp files in reverse order.3.tmp,2.tmp..
Here is an implementation in java...
docs.google.com/open?id=0Bw6L8Yy5eLJ3dm1KSEx5bkV1a0E
Can be done in O(n) without additional memory... Just modify quick select(selection problem) a bit...here is an tested implementation in java:
public static int getMinDist(Point[] arr, int num) {
int k = 0;
int start = 0;
int end = arr.length - 1;
while (k != num - 1) {
k = quickSelect(arr, start, end);
if ((start + k) < (num - 1))
start = k + 1 + start;
else if ((start + k) > num - 1)
end = start + k - 1;
else
k = num - 1;
}
return k;
}
static int quickSelect(Point[] arr, int start, int end) {
int pivot = (end - start) / 2;
swap(arr, pivot, end);
int i = start, j = end - 1;
while (i <= j) {
if (getDist(arr[i]) > getDist(arr[end])
&& getDist(arr[j]) < getDist(arr[end])) {
swap(arr, i, j);
i++;
j--;
} else {
if (getDist(arr[i]) < getDist(arr[end]))
i++;
if (getDist(arr[j]) > getDist(arr[end]))
j--;
}
}
swap(arr, i, end);
return i;
}
static int getDist(Point p) {
return (int) Math.sqrt(p.x * p.x + p.y * p.y);
}
1.Use array if you know size of tree else use arraylist
2.Keep adding right and left child until you reach at the end of tree.
3.Print elements of arraylist in revese order.
Time:O(n)
Space:O(n)
Here is a sample implementation in java:
public static void printReverseLevelOrder(TreeNode root) {
if (root == null)
return;
ArrayList<TreeNode> deque = new ArrayList<TreeNode>();
deque.add(root);
for (int i = 0; i < deque.size(); i++) {
TreeNode node = deque.get(i);
if (node.right != null) {
deque.add(node.right);
}
if (node.left != null) {
deque.add(node.left);
}
}
for (int i = deque.size() - 1; i >= 0; i--) {
System.out.print(deque.get(i).data);
}
}
1.If you know n.
Use this formula to get the missing number:
num=n-(n2-n1)
where:
sum of elements after replacing=n2
sum before replacing=n1
P.S: I am assuming all numbers are present from 1 to 1000 before replacing.
2.If n is not known:
while iterating through the array for calculating sum with replaced number just check which number is greater than thousand and that will be your n. Then follow step 1.
Here is the working code....I tried to test all the test cases....please let me know if it breaks somewhere
import java.util.*;
public class Test {
public static void main(String[] args) {
String[] A = { "apple", "banana", "mango", "potato","apple","potato" };
String[] B= { "apple", "brinjal", "mango", "Raadish","onion","banana","apple" };
String [] C=getIntersection(A,B);
for(String s: C)
System.out.println(s);
}
public static String[] getIntersection(String[] A,String[] B){
int len;
len=A.length>B.length?A.length:B.length; //get the upper bound of length
Map<Mark,Integer> map=new HashMap<Mark,Integer>();
for(int i=0;i<len;i++){
if(i<A.length){
if(map.containsKey(new Mark(A[i],1))) //if map has entry with same string from B add one to it
map.put(new Mark(A[i],1),(map.get(new Mark(A[i],1))+1));
else if (!map.containsKey(new Mark(A[i],0))) //else add the string as A's entry
map.put(new Mark(A[i],0),1);
}
if(i<B.length){
if(map.containsKey(new Mark(B[i],0))) //if map has entry with same string from A add one to it
map.put(new Mark(B[i],0),(map.get(new Mark(B[i],0))+1));
else if (!map.containsKey(new Mark(B[i],1))) //else add the string as A's entry
map.put(new Mark(B[i],1),1);
}
}
ArrayList<String> arr=new ArrayList<String>();
for(Mark m: map.keySet()){
if(map.get(m)>1)
arr.add(m.s); //add in arraylist as we are not sure how much strings are there, creating bigger array may be a bad idea
}
String[] strarr=new String[arr.size()];
arr.toArray(strarr);
return strarr;
}
}
//class Mark used as key in map, No fancy error checking, no optimization done for hashcode.
class Mark{
String s;
int flag;
Mark(String s1,int b){
s=s1;
flag=b; //Here flag=1 represents String B arrays entry and flag=0 represents String A arrays entry
}
public boolean equals(Object o){
Mark m=(Mark)o;
return (this.s).equals(m.s) && this.flag==m.flag;
}
public int hashCode(){
return 5;
}
}
RepHi, I’m Jamie from the Portsmouth USA and I am working as an account manager. I work for a ...
@Rinku..
- Anshul February 25, 2013since we are not allowed to return the head pointer of resulting list...caller has to himself take care of the resulting node's head pointer by storing the last node...or we can create a wrapper function calling this one and setting the last node as head in a static variable when we reach the end of recursion in this function...no need to pass it with every recursive call.
@abhishek
when you reach 2nd last node...you want to point last node to 2nd last and 2nd last to 3rd last....
so at 2nd last recursive call root will have 2nd last node....now you are doing root.next.next that means last node's next pointer and you are pointing it to root, that means 2nd last node i.e
1->2->3->4 becomes 1->2->3<-4 in last call then
1->2<-3<-4 and so on...