airfang613
BAN USERTo be honest I did not understand the question...
But anyway, if the problem is what you thought it is, there is an assumption that the array is already sorted in order to apply your method.
Now if assuming the array contains only single positive integer bits (0-9), a recursive solution can be given:
Let's see within N positions from index START, is there any digit larger than A[START]. If there is, move that digit to A[START]. If there are still remaining steps, recurse from START+1 and the remaining steps as new N.
The code is available here: ideone.com/v7Se6 (you can try different steps)
I think my solution is essentially the same as Tulley's (didn't check thoroughly). But I believe there are faster ways if additional space is used, as linearly scanning for maximum every time is definitely not smart.
I also wonder that if the array elements are only single digits or can be any integer (positive? negative?)
- airfang613 April 18, 2011I stand corrected.
Thank you very much for the suggestion.
Thanks for your verification, I have described above the problem that causes my program to behave improperly. In short, according to my understanding of the problem, the number of elements in the array and the number of elements to be extracted are the same (it was the same notation k).
So I still believe my solution is correct. Also I have already mentioned above that this is indeed not an efficient solution. It is merely A solution.
I am sorry, but perhaps either you or me understand the problem wrong.
According to my understanding the number of values in the original array EQUALS to the number of values that need to be extracted.
So my first loop only expects exact same numbers from the original array.
Please see next comment for the code.
I don't think this is the elegant solution as a lot of space and time is wasted in computing and storing the pairwise and triplet sums, there should be a smarter (or lazier) way to generate the result vector. Nonetheless, it is a working solution.
int main() {
int A[7] = {3,4,5,15,19,20,25};
vector<int> original(A,A+7);
vector<int> first;
vector<int> second;
vector<int> third;
// now assume k = 7
int k = 7;
for (int i = 0; i < k; ++i) {
for (int j = 0; j < second.size(); ++j)
third.push_back(original[i]+second[j]);
for (int j = 0; j < first.size(); ++j)
second.push_back(original[i]+first[j]);
first.push_back(original[i]);
}
vector<int> result;
while (k > 0) {
while (!first.empty() && first[0] <= second[0] && first[0] <= third[0] && k > 0) {
result.push_back(first[0]);
first.erase(first.begin());
k--;
}
while (!second.empty() && second[0] < first[0] && second[0] <= third[0] && k > 0) {
result.push_back(second[0]);
second.erase(second.begin());
k--;
}
while (!third.empty() && third[0] < first[0] && third[0] < second[0] && k > 0) {
result.push_back(third[0]);
third.erase(third.begin());
k--;
}
}
k = result.size();
for (int i = 0; i < k; ++i)
cout << result[i] << " ";
cout << endl;
return 0;
}
In fact, I don't really like the idea of simply posting code here (especially without proper indentation). You might just make others spending half an hour figuring out that you got it wrong!
I think getting the idea correct is more important than its implementation.
With that said, I will post code later on. Stay tuned.
Maintain 3 vectors, the first one contains the element themselves, second one contains the sums of two, and the third one contains the sums of three, here's how to update these 3 vectors:
1. We get the numbers from the original array one by one.
2. It will first be appended to the first list
3. For each element in the first list, add the current number and append to second list
4. For each element in the second list, add the current number and append to third list
Now we have 3 sorted vector, we can just perform some lazy evaluation (extract the min of the first elements of each one) once we have extracted k numbers from the original array (when we can guarantee that the top k numbers we need are all in the 3 vectors).
In support of @Kishore answer:
bool GreaterCombined(const int& a, const int& b) {
stringstream ssab, ssba;
ssab << a << b;
ssba << b << a;
int ab, ba;
ssab >> ab;
ssba >> ba;
return ab > ba;
}
int main(int argc, char** argv) {
int array[5] = {4, 94, 9, 14, 1};
vector<int> input(array, array+5);
sort(input.begin(), input.end(), GreaterCombined);
for (int i = 0; i < 5; ++i)
cout << input[i] << " ";
cout << endl;
}
The median minimizes the average absolute deviation.
- airfang613 March 19, 2011+1
only that it seems too easy to be a Google interview question
I don't understand how you get str3, can you please explain?
- airfang613 March 17, 2011Since everything insertion wouldn't change the median by more than one position, it is not necessary to keep all elements in order. We simply scan N/2 elements for max or min (or sometimes do nothing), that'd be an O(N) solution
if input is larger than current median && N is odd:
update the array O(1)
median stays the same
if input is smaller than current median && N is odd:
update the array
find the max element in the left subarray O(N) to be the median
if input is larger than current median && N is even:
update the array
find the min element in the right subarray to be the median
if input is smaller than current median && N is even:
update the array
median stays the same
"Like" this comment
- airfang613 March 17, 2011+1, utilize the fact that the two arrays are SORTED.
- airfang613 March 17, 2011int A[5] = {1,3,8,9};
int B[9] = {2,4,5,6,7,0,0,0,0}; // last four as place holders for the merge
// start from the end of the larger array;
int idx = 8;
// we also need the indices of the largest elements in both arrays
int idx_a = 3, idx_b = 4;
while (idx_a >= 0) { // done when A has been traversed
if (idx_b < 0 || A[idx_a] > B[idx_b]) { // if elements of b are exhausted
B[idx] = A[idx_a];
idx_a--;
}
else {
B[idx] = B[idx_b];
idx_b--;
}
idx--;
}
1. Build a hashset as Jike described, maintain a var LONGEST storing the length of the current longest prefix
2. For each subsequent string, work backwards. If longer than the current longest prefix, "chop off" the extra part. Query the hashset
3. If it is not in the hashset, remove the prefixes of its length and up to the length of the current longest prefix, update LONGEST
4. chop off one more char at the end and query again
5. continue until the hashset is empty or all strings have been processed.
This algorithm would run O(m+n) for both cases when all strings are the same and when all strings are different except for the first character
I don't understand your solution. From what I read, you will need at most M comparisons for each string, if all the strings only have their first char as the common prefix, that'd still be N*M.
- airfang613 March 15, 2011What you are describing seems to be the median of medians method, but can you please explain how you decide the relationship between median_exp and true_median?
And how you handle the reduced search space, I understand using median of medians can reduce the search space, but how do you plan to index and search in the remaining partitions?
@memo I think Tulley's solution works
The example you give would yield 2 correctly, since the extract-min will be called (3*3)/2+1 = 5 times
I think this is the best solution for this problem (if we are allowed to alter the list)
Otherwise, using a hash table is equivalently good
+1
create a bit vector of size 1 million, iterate through the phone numbers and set the corresponding bit (O(n))
then output the nonzero elements of the bit vector in order (O(n))
the sign bit of the signed integer will become the most significant bit for the unsigned int, hence it changes into a very big number
- airfang613 March 09, 2011nugarp is correct, scan the char array from left to right, check for the first negative sign, then for the rest of characters, sum = sum * 10 + (array[i] - '0'), negate at the end if the first char is '-'
- airfang613 March 05, 2011bob you forgot to increment the depth as you travel down the tree
plus, I think the question was meant to ask the height of a tree. Depth is usually for some node in the tree.
bingo
- airfang613 March 05, 2011Here is an iterative version based on Xu's comment, also would it be a little faster if mod-based GCD computation is used instead of subtraction-based?
int GetGCD(int a, int b) {
int aa = a;
int bb = b;
while (bb != 0) {
int tmp = bb;
bb = aa % bb;
aa = tmp;
}
return aa;
}
int main(int argc, char** argv) {
int array[3] = {10,9,15};
vector<int> A(array, array+3);
int n = A.size();
int lcm;
int left_operand = A[0];
for (int i = 1; i < n; ++i) {
int prod = left_operand * A[i];
int gcd = GetGCD(left_operand, A[i]);
lcm = prod / gcd;
left_operand = lcm;
}
return lcm;
}
I think either CareerCup 150 or Programming Interviews Exposed has this exact problem and the solution is as described by Tulley.
- airfang613 February 25, 2011In the second case you also need to delete the next node.
Furthermore, you need to make a note to the interviewer that the 2nd approach would not work if the node to be deleted is the last node.
888 + 88 + 8 + 8 + 8 = 1000, but doesn't it look to simple?
- airfang613 October 16, 2010888 + 88 + 8 + 8 + 8 = 1000, but doesn't it look to simple?
- airfang613 October 16, 2010How is 7*7 different from 3*3 in principal? I chose 3*3 to explain the solution so it I don't have to write too many numbers.
- airfang613 October 16, 2010By sorting by row I meant, race once and reposition the cars (in the matrix) based on their ranking. Maybe I should use a concrete example to explain better:
Suppose you have 9 cars, 3 tracks, and we want to find out the 5th fastest car (the median), considering such random matrix:
9 8 5
7 2 6
3 1 4
We first race the cars row-by-row (so 1st round 9 8 5, 2nd round 7 2 6 and 3rd round 3 1 4), after sorting/repositioning we have
5 8 9
2 6 7
1 3 4
Now we race the cars column-by-column (1st round 5 2 1, 2nd round 8 6 3 and 3rd round 9 7 4), sort/reposition the cars again we get
1 3 4
2 6 7
5 8 9
To get the 5th fastest car, we simply race one more time the cars lie on the minor diagonal and see which car comes in the middle. All I did was 3 + 3 + 1 = 7 races.
This can be generalized to the case with 49 cars, 7 tracks and looking to find 25th fastest car.
I agree, I have the same answer.
Of course this is under the assumption that it is an odd matrix (otherwise how would one choose a median)
I think we just need to view the problem differently. To find the 25th fastest car in 49 cars is essentially a median-searching problem. Utilizing the method to find median in a sorted matrix (iirc someone posted a few days ago), I think it will take 7+7+1=15 races.
Imagine a 7 x 7 matrix, each with a different number representing the speed of a particular race car. It will take 7 races to sort them row-by-row (reposition the cars from slowest to fastest, say). Use the current matrix to start 7 more races, this time column-by-column, sort/reposition the cars again based on the results. Then it becomes clear that the median must lie on the diagonal from lower-left to upper-right, hence 1 more race is needed to find the median.
I, too, would like to see the method adapted to rectangular regions.
- airfang613 April 21, 2011