geliang2008
BAN USERThe problem seems to fresh. If the integers are all positive, we can have the following solution:
unsigned int find_odd(vector<int>& v){
for(unsigned int i=0;i<v.size();i++){
if(v[abs(v[i])]>0)
v[abs(v[i])]=-v[abs(v[i])];
}
for(unsigned int i=0;i<v.size();i++){
if(v[i]<0) return i;
}
O(n) time, O(1) space
Test: 2,2,1,1,3,3,3
first round the array becomes: 2,2,-1,1,3,3,3
second round output 3
The code works on an assumption that the linked list contains no cycle.
- geliang2008 December 04, 2011The code is nice. It seems to have a bug or constraint that the length of linklist n and the interval k must have a GCD bigger than 1. For example, I test n=10, k=3, the program has an error. I fix the code as the following:
LinkNode* linkedlist::Reverse_Interval(LinkNode* head, int n){
if(!head) return NULL;
LinkNode* p, *q=NULL, *temp=head;
int k=n;
while(k--){
p=q;
q=temp;
temp=temp->next;
if(!temp) break;
q->next=p;
}
head->next=Reverse_Interval(temp,n);
return q;
}
Input: {75 191 176 175 155 151 143 128 118 98}
Output: {176 191 75 151 155 175 118 128 143 98}
here n=10, k=3
The time complexity is O(nlogn) and space is O(n), most of time is spent in sorting
- geliang2008 December 04, 2011Let's start from the naive solution. Suppose we have a helper function is_Consequence(vector<int>& v) to tell if the vector v is the consecutive sequence or not. It takes O(n) to finish the test. Then we iterate all n^2 subarray to find the longest subarray that is a sequence. That will take O(n^3) time and O(1) space.
Now we take the general strategy of space for time. Also we notice that the question doesn't ask for the index of the elements of the array rather the actual value. I come up the following solution:
vector<int> Array::Longest_Subarray_Sequence(vector<int>& v){
sort(v.begin(),v.end());
std::map<int,int> map;
int n=v.size(),max_len=0,start=0;
for(int i=0;i<n;i++){
int left=(map.find(v[i]-1)==map.end()?0:map[v[i]-1]);
int right=(map.find(v[i]+1)==map.end()?0:map[v[i]+1]);
int len=left+right+1;
map[v[i]]=len;
if(len>max_len){
max_len=len;
start=v[i]-left;
}
}
vector<int> result;
for(int i=0;i<max_len;i++) result.push_back(start+i);
return result;
}
Input: {4,5,1,5,7,4,3,6,3,1,9}, Output: {3,4,5,6,7}
The ideas are:
1) first sort the array
2) build a hashmap which counts the current length of consecutive sequence
3) for each element, we check its left element-1 and right element+1 to see if they are in the array, if not, len=0 otherwise len=current length
4) mark the max_len and start point on the fly
The code is tested and welcome bug finding
@Anony: My code is fine, otherwise I won't get the result. 1) Pearl is the namespace, you should omit it if you use global space or use your own namespace. 2) the input should similar to vector's begin() and end() function, in you case this should be (a13,a13+12).
- geliang2008 November 17, 2011The problem is we have to know the exact start and end index of the answer. Using arr[i]<RMAX[i] won'd give you this. I think the running philosophy behind such kind of problem is "Space for Time". If you want a faster alg., usually setting up auxiliary data structure is wanted. You can check on "Programming Pearl" about Maximal Sub Vector Problem. I learnt a lot from this problem and its exercises
- geliang2008 November 11, 2011Yeah, Eugene, Bitmap is one of solutions in certain conditions. That's why we ask assumptions. Treat the integers as string and apply trie is another a brilliant idea
- geliang2008 November 10, 2011Sure, The radix_test class wraps an operation () which performs the test in std::stable_partition. stable_partition performs partition according to the test function which is implemented by radix_test. lsd stands for least significant digit. The algorithm works like this: first we partition the array such that the first half contains elements whose lsd is 0 and second half contains elements whose lsd is 1. By this, we implement eugene idea of separating odd number and even number. We recursively doing this in each half by partitioning by the next lsd.
the stop condition 1) first==last is trivial 2) lsd=32 because the type is int, it only contains 32 bit. Therefore, we stop there. Hope it helps
Sure, The radix_test class wraps an operation () which performs the test in std::stable_partition. stable_partition performs partition according to the test function which is implemented by radix_test. lsd stands for least significant digit. The algorithm works like this: first we partition the array such that the first half contains elements whose lsd is 0 and second half contains elements whose lsd is 1. By this, we implement eugene idea of separating odd number and even number. We recursively doing this in each half by partitioning by the next lsd.
the stop condition 1) first==last is trivial 2) lsd=32 because the type is int, it only contains 32 bit. Therefore, we stop there. Hope it helps
Sure, I've thought this before. I think in interview one is about if you are smart enough, the other is about if you are experienced enough. We don't need to re-invent the wheel every time. The problem has an variant: instead of maximize (j-i), we maximize (arr[j]-arr[i]). This variant is stemmed from stock price problem: given a month of stock price, you find the two days that you buy and sell such that your profit is maximized
- geliang2008 November 10, 2011Read the problem again: we want to maximize (j-i) or test your code
- geliang2008 November 09, 2011The naive solution is inspired from bubble sort. If we find "bad" happens, i.e. a[k]=b, i<=k<=j, we swap a[k] and a[j]. For each element in the array, we run such test. The process ends when all the elements are tested. I guess the time complexity is O(n^2)
- geliang2008 November 09, 2011std::vector is implemented by array. My most concerns is how to deal with function like resize, and size increase in push_back and insert
- geliang2008 November 09, 2011If I am the interviewee, I will ask the question what is the integer? telephone number, IDs? temperature? The questions are intended to find out the following key issues:
1) if the numbers have duplicates
2) what's the lower and upper bound of the number
3) the format of the number, for example, for telephone number you expect to be 10 digit and never starts with 0 or 1 (in us)
If you know enough details, you can go bitmap(no duplicate, known uppbound). Better refers to "Programming Pearl Column 1 "
I think the problem is intended to test you about the time complexity of operations when you implement it with different data structures: vector, linkedlist, binary tree, heap, set, bins. If you can compare different time complexity, I believe that is what the interviewer has in mind. The best example come from "Programming Pearl 2nd edition Column Search", where the author implements a search structure containing insert, find, size, using the above data structures. And the author compare the time complexity in details
- geliang2008 November 09, 2011int Array::MaxDiff(vector<int> arr){
if(arr.size()==0) return 0;
int n=arr.size(),i,j;
vector<int> Lmin(n,0);
vector<int> Rmax(n,0);
Lmin[0]=arr[0];
for(i=1;i<n;i++)
Lmin[i]=min(arr[i],Lmin[i-1]);
Rmax[n-1]=arr[n-1];
for(i=n-2;i>=0;i--)
Rmax[i]=max(arr[i],Rmax[i+1]);
int maxdiff=0;
i=0,j=0;
while(i<n&&j<n){
if(Lmin[i]<Rmax[j]){
maxdiff=max(maxdiff,j-i);
j++;
}
else i++;
}
return maxdiff;
}
O(n) time and O(n) space solution. Tested! The key observation is the two auxiliary arrays LMin and RMax which saves the smallest value left of i and biggest value right of i
1) For each key word, extract the vector of the document-id, the vector is sorted
2) for k list extracted, perform modified k-way merge algorithm
3) k-way merge is recursive like merge sort: you find the result in the first half and in the second half, you merge them into final result
It is straightforward to use map-reduce to solve. Extracted lists are distributed across n nodes. In each node, perform map operation to emit pair<value, list_id>. In the reduce node, it collects all the pair with the same value and count the number of list it receives. If it equals to k, output the value, i.e. document-id
The general idea is right, but code is full of errors. The working code is as follows:
Tree is the namespace I use.
- geliang2008 December 22, 2011Test example: 2,7,10,13,11,9,16,20,17,15 (CLRS Binary Tree Chapter Example)