JustCoding
BAN USERI guess by distance you mean "length of the path from n1 to n2"...
so the idea is to do a special case on the diameter of the tree rooted at the given root, but only till nodes n1 and n2...
see here for more: geeksforgeeks.org/archives/5687
What is the runtime of this? Looks like O(n^2)?
- JustCoding October 27, 2012yeah but never mind... it will become complicated if we try this... your solution appears to work fine...
actually @yakku should check and comment on the expected answer and compare against your solution... that will give better picture...
you will note that 1 has 3 levels of nodes below it... so 1 should output 1, 3, 3
also, by the definition I have given above, 8 should output 8, 4, 0 since it is the 4th cardinal in the inorder traversal, and has 0 levels below it...
so I think you first need to find the height of the tree, and then use that value while giving the y-coordinate...
does this make sense?
@CodeSpace: here is the tree I am constructing:
struct node* root = newNode (1);
root->left = newNode (2);
root->right = newNode (3);
root->left->left = newNode (4);
root->left->right = newNode (5);
root->right->left = newNode (6);
root->right->right = newNode (7);
root->right->left->left = newNode (8);
so it if of the form:
------------------------- 1---------------------------------
---------------------2----------3--------------------------
----------------4-------5----6------7--------------------
-----------------------------8-----------------------------
does the tree make sense?
Tested this. does not work.
it is printing incorrect x, y values
You can do it in 3 measurements (since we don't know if it is heavy or light, else it can be done in 2 measurements):
If we know that the fake ball is heavy or light:
first keep any 2 balls aside, and weigh the other 6 balls by placing 3 on each pan...
Case 1: if these balls weight equal (the scale is balanced), you know all 6 of these balls are identical and none is fake. If so, weigh the other 2 balls and find out whichever one is fake (using the knowledge of heavy/light).
Case 2: if the pans don't balance, you know one set of 3 balls being weighed currently contains the fake ball. Again, using the knowledge of heavy/light, weigh any 2 out of the 3 balls which are not weighing properly and you know your answer.
So that's 2 measurements.
If we DON'T know heavy or light, after weighing the 6 balls,
Case 1: if Case 1 above holds, use any one of those 6 balls (since they are all identical) and use it to weight against any one of the remaining 2 balls. If it weighs equal, the remaining ball (so this is still 2 weighings)
Case 2: NOW we need to know if it is heavier or lighter to proceed IMO... OR... again weigh like in Case 2 above... but just to make sure if the fake one is lighter or heavier, weigh of these balls with the remaining 3rd ball you will know...
let me know if this makes sense or I can give examples with numbered balls or so...
the 2nd declaration (char *str) declares a pointer to a char... this pointer is placed on the current memory stack but the data itself ("/root//foo/bar") is stored elsewhere, not on the current stack and not at that same location. So you cannot (should not) change the value using str[in1] = str[in2]. It will lead to seg fault as you have rightly noticed.
But if you have to change the value, you use double indirection (using ** or &) and make the change.
is this circular doubly linked list?
- JustCoding October 22, 2012Use counting sort: space is O(k) which is O(2) here so constant...
or you can use 3 counters to count the number of occurrence of 0, 1, 2 in the given collection, then overwrite the array with those many 0s, 1s, and 2s...
or you can use a hashmap to maintain the counts and basically do the same as above...
Constant space usage and O(N) runtime...
You can easily note here that for any given node:
the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;
Using these 2 pieces you can easily get the output shown above...
makes sense?
Also change count += (mark(arr, i, j) > 1) ? 1 : 0; to check >= 1
- JustCoding October 18, 2012DFS will help... count the node "value" at every step... sum of those counts along a path will be the sum of that path...
- JustCoding October 17, 2012diagonal not considered?
in this example:
1 1 0 0
0 0 1 1
0 0 0 0
1 1 1 1
what is the answer? 2 groups? or 3 groups?
Well Archimedes' principle has to do with the "weight of the liquid" and not so much with the volume displaced... but his famous "Eureka" story showed why the crown sunk in the bathtub... and that's the only explanation I can think of...
- JustCoding October 16, 2012It will still be L1 according to Archimedes principle.
- JustCoding October 16, 2012@bluseky: why specifically 3 characters only?
- JustCoding October 15, 2012read the amount of the file that can fit into memory, and create an in-memory map or heap to count the occurrence for each word... print the top "N" values from the map once the entire file has been read...
O(n) time and O(n) space...
what is your complexity going to be? Mergesort is O(n log n) so
- JustCoding October 12, 2012could you explain/give your logic instead?
- JustCoding October 11, 2012a) O(n^2)
b) O(n)
c) O(n) if no sort order maintained; O(log n) if it is BST or sorted tree
d) O(1)
e) O(n) if it is unsorted; O(log n) if sorted
correction- Assuming that the array is sorted in increasing order:
if start+end > given sum, then end-- else start++...
if start + end == sum, return/print those 2 numbers and continue to find more such pairs...
Ya now it is making so much more sense... Now you can follow @Ben's method above ^^.
- JustCoding October 09, 201220 + 21 + ..
this is an increasing series.. so how can we reach 2n which will be 2*1 for n=1? Am I missing something?
is the given array sorted?
define "adjacency"... in the array 1 3 2 4 5, are 2 and 3 adjacent or 3 and 4 in the conventional sense?
yes but you can do it in-place as well...
- JustCoding October 07, 2012@pradegup: you should also maintain a count of how many times that value occurs in the array. for example, in the given array, 4 appears twice so when you look up 4, you will try to find if k-4 = 8-4 = 4 exists... and this returns true...
but consider an array where 4 appears only once... and when you do a search on 4, you will return true... but that's not solution...
does this make sense?
@Manish: this solution assumes the numbers are in a range I think? say the array is of size 10.. and the elements are 1 3 5 7 9 20 18 35 40 100...
arr[arr[i]] will be arr[100] for the last element... and then you'll get out of bounds since your arr size will be 10 and not 100.. right?
@Anonymous is right... you see that the second array already has 3 blank spaces that can be used to record the final sorted array... you can merge sort each array in-place... and then merge the sorted arrays into the bigger array... this will be in-place and without using extra space
- JustCoding October 06, 2012^^ this has been discussed in an earlier comment... the assumption is that array B is sorted... if not, it can be sorted in O(n log n)... the other assumption is that B does not contain duplicates... if it does, then multiple elements will be deleted for the same index value...
one possible solution is to just MARK the array elements as "to be deleted"... and in another run delete those actually...
that's an assumption we need to check with the interviewer... but yes "sorted" on B is expected... if not tats O(n log n) for sorting it...
- JustCoding October 04, 2012Start removing from the "last" position of B... so remove A[3] first.. and then remove A[1]... going in reverse order on B... that won't change the preceding positions...
- JustCoding October 04, 2012This one does not remove the spaces in the source string... it just prints the string without printing the spaces... not the complete solution...
- JustCoding October 04, 2012This one does not work... throwing "System.AccessViolationException" error.
- JustCoding October 04, 2012A very nice explanation given here along with full working code:
geeksforgeeks.org/archives/5687
Source: cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html
your code won't work entirely because you are incrementing i inside the while loop twice so after p[i] is handled, the next character handled will not be s[i] but instead s[i+1]..
otherwise the logic works fine...
hmmm... you mean 1, 2, 4, 8, 3, 5, 6 , 9, 10, 7
- JustCoding September 29, 2012@Anonymous... that sounds similar to using a map/hashset... is it?
- JustCoding September 29, 2012Traverse the numbers from 1 to n... whenever you see a number that is a power of 2 (including 2^0 = 1), output it... now traverse again, and print all the numbers that are not powers of 2, in the same order...
for example, if n = 8, the output would be 1, 2, 4, 8, 3, 5, 6, 7
Any algorithm/explanation to help pls?
- JustCoding September 28, 2012what do you mean by precision value? can you give and example and explain?
- JustCoding September 28, 2012I think the time complexity with solution is O(n) because you have to traverse the entire array to print out all the duplicates. Space is your bitvector size.
- JustCoding September 28, 2012if it is a BST, then sorting the given traversal will give you inorder.. and then use the 2 traversals to construct the BST...
- JustCoding September 28, 2012N should be the maximum positive number in the array not the number of elements in the array.
also... if N*(N+1)/2 == S, then the number is N+1;
for example.. in the array, 3, 4, 2, 1, the answer is 5...
Start from the last index of the array and add 1... if that sum is == 10, make that number = 0, and carry "1" to the preceding num... exactly like you would add a number..
// assume a is the array
i = a.length() - 1;
while (i >= 0)
{
int sum = a[i] + 1;
if (sum == 10) /* sum cannot be > 10 since you're adding only 1, max will be 9 + 1 = 10 */
{
a[i] = 0;
i --;
}
else
{
a[i] = sum;
break;
}
}
it becomes tricky when the number is such that adding 1 increases the number of elements by 1... for example, the number is 999... then adding 1 will make it 1000 which is 1 digit more than that of the given number...
in that case, you could check the value of i after the while loop...
if (i < 0)
{
/* create a new array b with size = a.length + 1) */
b[0] = 1;
for (j = 1; j < b.length; j++)
{
b[j] = 0;
}
}
This does not take care of the case where the list might containt duplicate elements...
consider the case: 1-> 2->3 -> 4 -> 3' (a new 3)
this list does not contain a loop
consider the case: 1-> 2-> 3 -> 4 -> 3' (new 3) -> 5-> 3 (first 3)
this list does contain a loop.
Using a bitset of size n, initialized to 0.
As you traverse the array, set the particular bit in the bitset. If you see any bit already set, that's the duplicate. To find the missing number, you will need to traverse the bitset, and any number set to 0 is the missing integer.
O(n) time and O(n) space...
If the array is sorted, then a single traversal will do... without needing a bitset... O(n) time and constant space..
An n-ary tree structure with the root being "/"?
- JustCoding September 27, 2012You can use the Cycle Detection Algorithm (in particular, I like the Tortoise and Hare Algorithm). Look it up on Wikipedia.
The basic idea is to have 2 pointers: one slow and one fast... both start at the head of the list. The slow pointer moves one step at a time and the fast pointer moves 2 steps at a time. If they meet at any time ie.,e if slow == fast, there is a loop in the list...
The question says you don't know if the fake ball is heavy or light... so you will need at least one more weighing..
- JustCoding November 02, 2012