mag
BAN USER- 0of 0 votes
AnswersYou are given a binary search tree T of finite (means can fit in memory) size n in which each node N contains
- mag in India
- integer data element
- pointer to left child
- pointer to right child
- pointer to in order successor (which is set null for each node)
Set all in order successor pointers of the given binary search tree.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures
@:E have you run my code on your example? or have you performed a dry run at least on your input?
Let me walk though:
1. your input is already sorted
2. find total sum = 30
3. start at 9:
min_sum = 30 - 2 * 9 = 12
a[i] = 9 * -1 = -9
total_sum = min_sum = 12
at 6:
min_sum = 12 - 2 * 6 = 0
a[i] = 6 * -1 = -6
total_sum = min_sum = 0
break;
you got 1,2,3,4,5,-6,-9
let me know which part you didn't get?!
Algorithm:
1. Sort given array (say, in ascending order) ( Time: nlogn )
2. Loop once through array and find total sum - ( Time: n )
3. Start from right most element - ( Time: n )
4. See if current element can be made negative (for i = n - 1 to 0, both inclusive )
curr = a[i];
min_sum = total_sum - 2 * curr;
if ( min_sum >= 0 )
{
a[i] = curr * -1;
total_sum = min_sum; // update sum
}
if ( min_sum == 0 ) break; // because you can't minimize than that
5. When you reach first element, you would have made sufficient elements negative or you would have broke out from the loop.
TC: O(n log n)
SC: O(1)
Advantages:
1. Time complexity is nlogn
Disadvantages:
1. Modifies the input array
Here is the working C function (tested for all inputs in other answers):
int ModifyArray( int * a, int n )
{
int i, sum = 0;
if (!a) return -1;
if ( n <= 0 ) return -1;
// sort the input array in increasing order
qsort( &a[0], n, sizeof(int), compare );
// find total sum in one loop
for ( i = 0; i < n; ++i )
sum += a[i];
// actual algorithm
// scan from right to left
// see if each element's twice can be subtracted from total sum
for ( i = n - 1; i >= 0; --i ) {
int element = a[i];
int min_sum = sum - 2 * element;
if ( min_sum >= 0 ) {
a[i] = element * -1;
sum = min_sum;
}
if ( min_sum == 0 ) break; // early termination
}
return sum;
}
@AP: as I said, if you take constant amount of storage and that size does not depend your input size, its constant extra space. so if you get string of length 100 or of length 1 million, you are always going to reserve 128 int's.
So we are not increasing time complexity. Taking 2-3 temporary variables as extra space in your code is just a myth about using constant extra space!
1. Take 128 int array, initialized as all 0
2. In first pass: increment character count in array
3. In second pass: keep two pointers at first character
4. loop until j reaches end
5. keep copying characters at position j to characters at position i if char count at position j is 1
6. if char count at j is > 1 ignore this j and go ahead.
7. finally put null at i+1 position.
8. you are done.
TC: O(n) because you traversed string twice, so O(n) + O(n) = O(2n) = O(n)
SC: O(1)
because constant extra space requirements says that size of extra space should not depend upon size of input just as in our case, no matter how large your input string is going to be, you will always need 128 int's
Here is my post on rotating a given 2D matrix by a given angle (+90, -90, +180, -180):
rajendrauppal.blogspot.in/2011/12/rotating-2d-array-of-integers-matrix-by.html
Summary:
Input: n by n matrix M, where n >= 2
Rotate by +90 (clock-wise):
Step 1: Transpose M
Step 2: Reverse each row
Rotation by -90 degree (anticlockwise once):
Step 1: Transpose
Step 2: Reverse each column
Rotation by +180 degree (clockwise twice):
Two methods follows
First:
Rotate input matrix +90 degree twice, if routine for which is available to you
Second: (You'll be amazed!)
Step 1: Reverse each row
Step 2: Reverse each column
Rotation by -180 degree (anticlockwise twice): Three(!!!) methods follows
First:
Rotate input matrix -90 degree twice, if routine for which is available to you
Second: (You'll be amazed again!)
Step 1: Reverse each column
Step 2: Reverse each row
Third: (Aha!)
Because rotating a matrix +180 degree or -180 should produce same result. So you can rotate it by +180 degree using one of above methods.
What is the actual question here?
1. If the actual question is to generate a random number in a range but not in a blacklist without using rand function of a particular programming language then its a different question altogether.
( You have to write your own random number generator in this case. )
2. If actual question is to generate the random numbers uniformly which are not in the blacklist and you can use built-in rand function of programming language of your choice then many algorithms discusses here can achieve this.
( Any algorithm you devise to achieve this depends upon the uniformity of build-in rand function you chose to use. )
3. If the question is to do it efficiently then none of the above answers talk about doing it in linear or sub-linear time.
( Need to optimize any methods discussed above. )
I was presented this question at Amazon, it was like this:
Given a 2D array, in how many ways you can go from cell (0, 0) to cell (m-1, n-1). The constraint is that you can only move below and right from a given cell. I solved it.
The answer:
(m + n - 2) , if m = n
(m + n -1), if m != n
@nihaldps: Your answer in comments is correct. But you original question doesn't mention the constraint.
- mag February 24, 2012With O(n) extra space it is trivial.
Without extra space, you need recursion to hold values. You can ask the interviewer that if I have source code of given stack, if I have the information on how the stack is implemented, then reverse that internal data structure of stack for example, array and linked lists can be reversed using constant extra space.
Suppose ABC is triangle and P is given point.
Step 1. Find Area(PAB), Area(PBC), Area(PCA)
Step 2. If all three areas are of same sign (irrespective of positive or negative), then P lies inside ABC, otherwise outside
Note: Better than Sanjay's approach because it doesn't calculate area of whole triangle
To see how it works:
1. When you find area of PAB, and if it is positive, it means you are standing at P and A, B are clockwise from P.
2. Similar argument holds for PBC and PCA.
3. If all three areas are positive then you are standing at P and looking at A, B and C in clockwise direction, if all are negative then anti-clockwise.
4. If there is a sign change, you (P) are outside triangle ABC.
5. If any of the area is zero, then P is one of the edges AB, BC or CA
/* Returns 1 if successful, 0 otherwise */
int sort01( int * a, int n )
{
int i, j, temp;
i = j = 0;
if ( !a ) {
printf("Invalid array parameter\n");
return 0;
}
if ( n < 0 ) {
printf("Invalid array size\n");
return 0;
}
while ( j < n ) {
if ( 0 == a[j] ) {
temp = a[j];
a[j] = a[i];
a[i] = temp;
++i;
}
++j;
}
return 1;
}
1. Time complexity O(N)
2. Space complexity O(1)
3. Tested code till n = 50 million, results correctly in less than 1 second
4. Single pass algorithm
5. Clean and solid
In addition to default ctor, default copy ctor, default copy assignment operator and destructor, non-const address of (&) and const address of operators would also be generated. (I would imagine the interviewer wanted this answer!)
@michael: sizeof(e) = 1, because C++ differentiates between two objects of same kind.
O(N) time, O(1) space: recursive
1. Traverse till middle
2. One pointer at start, second half of the string will recurse till end
3. Keep matching, at first unmatch, break and report false
4. Return true if all matches
(Somewhat tricky to write but optimal)
O(N) time O(1) space:
1. Find length (if not given)
2. Traverse till middle of list
3. Reverse second half of list
4. Keep two pointers, one at start, other at middle
5. Keep comparing until you match them all (i.e., reach till end of second half)
6. If at any point characters don't match break and report false, else true
7. Reverse the second half again to restore or if there is a specification that you can't modify the input.
O(N) time, O(N) space:
If you are asked not to reverse the list then following can be brute force idea:
1. Traverse the list once
2. Make string out of it
3. Check if the string is palindrome
Reference: Wikipedia:
"An expression is said to be referentially transparent if it can be replaced with its value without changing the behavior of a program (in other words, yielding a program that has the same effects and output on the same input). The opposite term is referentially opaque."
So log(x) is referentially transparent, rest are referentially opaque.
Because for given x, log(x) has a certain value. But in case of:
now(): time changes so you can't possibly replace it with an exact value.
strcat(str1, gets()): result depends upon input string received from gets.
rand(0, 1): random number between 0 and 1, cannot have certain value, it will be different each time it is called.
Probably we are looking for something like this:
- mag December 07, 2012stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string