PUdayakumar
BAN USERThis solves only a possible solution. Not the shortest possible solution.
We need to use a back tracking + BFS combination to find the shortest path.
I think the algorithm didn't handle the nearest gaurd points case. Your algorithm might return the longest routes to all the 0 from a given set of gaurds. What if the gaurd point you are starting is not the right candidate for a '0' zero node. There is a possibility that this '0' node can be reached from another gaurd point which is much close.
So we need to correct the logic to take the min( existing a[i][j] and new a[i][j])
The only integer which goes by all rule is 1234 (not 1023 as mentioned by the author of this question).
- PUdayakumar July 13, 2014This could be further optimized by making few changes.
- Instead of maintaining the items in a separate arraylist and have the positions as the value of the TreeMap, we could actually have the LinkedList/ArrayList of items as the value the TreeMap, so that way, you don't need to readjust the positions every time something changes within the ArrayList, especially delete.
So it will be something like,
TreeMap<Key, ArrayList<items>>
HashMap<KeyType, TreeMap<Key, ArrayList<items>>
This problem is more like having an index on the keys - This is how it is done is databases.
Sounds reasonable!
Except the condition of one node as the child of another node. I guess that case needs to be exempted or else the given question cannot be solved.
I doubt you can take median of smaller list and apply it to a bigger list. Your approach doesn't work.
Consider the below example:
[5,6,9,1] ==> Sorted ==> [1,5,6,9] ==> Median is 5,6
[5,2,2,2,2,2,3] ==> Sorted ==> [2,2,2,2,2,3,5] ==> Median is 2
[9,6,8] ==> Sorted ==> [6,8,9] ==> Median is 8
Resulting list after removing all items greater than & less than the median
[5,6]
[2]
[8]
Merging & Sorting them ==> [2,5,6,8]
Median (as per your algorithm) is (5+6)/2 ==> 5.5
Actual Median Algorithm:
[1,2,2,2,2,2,3,5,5,6,6,8,9,9] ==> 14 elements
7th element is '3'
8th element is '5'
Median is (3+5)/2 ==> 4
This is the typical sort-merge technique which is used the map-reduce paradigms - It also uses the external sorting technique.
- Sort the individual set of integers within each of the server (using standard sorting techniques) - This can happen parallely in each of the N servers.
- Once the we have sorted buckets of data in each server, the shuffle stage (or essentially the sort-merge stage), brings in data from all the N servers by doing a multi-way merge sort of these sorted buckets.
- In the final reducer (or machine or on disk) the full sorted list is available. Assume we have also calculated the length of this list during the map-reduce while doing sorting, each mapper throws the length of its individual list. The reducer then merges these individual counts and forms the total list size.
- After this we can calculate the median by the following simple rule. Lets say list size is 'X'.
- If X is odd, median is list[(X+1)/2]
- If X is even, median is (list[X/2] + list[(X/2)+1])/2
Please refer to some map-reduce techniques or external sorting techniques which pretty much forms the basis of most distributed computing.
Node* CopyLinkedList(Node* head) {
Node* n = head;
// First pass, insert a copy next to the code.
while (n) {
Node* n1 = new Node();
n1->data = n->data;
n1->next = n->next;
n->next = n1;
n = n->next->next;
}
// Second pass, set random pointer.
n = head;
while (n) {
n->next->random = n->random->next;
n = n->next->next;
}
// Third pass, detach two lists.
n = head;
Node* head1 = n->next;
while (n) {
Node* temp = n->next->next;
n->next->next = temp ? temp->next : nullptr;
n->next = temp;
n = temp;
}
return head1;
}
Where is the link between result & curr_result.
I see you are assigning the result to curr_result. But where is result updated to curr_result?
+1 for the funny solution - But 0 marks in terms of actual solution
- PUdayakumar July 03, 2014What is the time complexity & space complexity of this algorithm?
- PUdayakumar July 03, 2014Your space complexity is pretty high - You are using stack and then a String[] etc. Can we do better?
- PUdayakumar July 03, 2014Small correction - Sorry it is O(n + k*m), where k is number of words and m is the average size of each word.
- PUdayakumar July 03, 2014Small correction - Sorry it is O(n + k*m)
- PUdayakumar July 03, 2014O(n + klogm) solution with the use of Stack, where k is number of words and m is the average size of each word.
public static void reverseWords(String str){
char[] a = str.toCharArray();
int start = 0;
int end = 0;
char prevChar = ' ';
for(int i = 0; i < a.length; i++){
if(i == a.length -1){
reverse(a, start, end);
}
if(prevChar == ' ' && a[i] == ' '){
start++;
end++;
continue;
}
if(a[i] == ' '){
reverse(a, start, end-1);
end++;
start = end;
}
else
end++;
prevChar = a[i];
}
System.out.println("\nReversed: " + new String(a));
}
public static void reverse(char[] a, int start, int end){
Stack<Character> s = new Stack<Character>();
for(int i = start; i <= end; i++){
s.push(a[i]);
}
for(int i = start; i <= end; i++){
a[i] = s.pop();
}
}
O(n) solution with the use of Stack and no extra loops
public static void reverseWords(String str){
char[] a = str.toCharArray();
int start = 0;
int end = 0;
char prevChar = ' ';
for(int i = 0; i < a.length; i++){
if(i == a.length -1){
reverse(a, start, end);
}
if(prevChar == ' ' && a[i] == ' '){
start++;
end++;
continue;
}
if(a[i] == ' '){
reverse(a, start, end-1);
end++;
start = end;
}
else
end++;
prevChar = a[i];
}
System.out.println("\nReversed: " + new String(a));
}
public static void reverse(char[] a, int start, int end){
Stack<Character> s = new Stack<Character>();
for(int i = start; i <= end; i++){
s.push(a[i]);
}
for(int i = start; i <= end; i++){
a[i] = s.pop();
}
}
RepShastri Ji is well known hindi and tamil vashikaran specialist. He will give you effective and simple totke to control ...
Guy is a posting questions from all random places ... I see Guy's question every page at-least 8-10 of them from him.
- PUdayakumar July 13, 2014Can't a GUY attend so many questions and still not get a job in google ;)