a MSVS q(solution)imt a folder of MSVS projects

label: IDE, book

I agree the project is a more important development concept, but the solution also has unique, important functionalities. I found many of these functionalities from [[MSVS 2010 unleashed]].

* project dependency is described in the sln file.

* you can build an entire solution, according to the predefined build order

* a solution can contain so-called non-project items such as documentation. All such files are by default put into the “Solution Items” virtual folder.

Advertisements

locate a pair whose diff=55

http://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/ has a nice algo for “sum=55”

This technique becomes more interesting when the problem is modified to “find a pair whose difference is 55”. Without loss of generality, let’s keep everything positive.

–my solution:

  1. sort the original integers
  2. duplicate the array, flip the signs and reverse it
  3. append positive array to get a combined, sorted array, whose left half are all negavie
  4. now start the 2 pointers, but each constrained within its half.
//Requirement: find all pairs in the array whose difference = D
//
//If there are negative numbers, then the simplest solution is
//to shift everything up to positive

vector<int> v{3,1,1,7,4,9};
int const SZ = v.size();
int const D = 2;

void dump(){
  for(int i=0; i<v.size(); ++i) cout<<setw(3)<<v[i];
  cout<<endl;
  for(int i=0; i<v.size(); ++i) cout<<setw(3)<<i;
  cout<<endl;
}
int main(){
  sort(v.rbegin(), v.rend());
  for (int i=SZ-1; i>=0; --i) v.push_back(-1 * v[i]);
  dump();
  for(int left=0, right=v.size()-1; left < SZ && right>=SZ;){
        int diff = v[left] + v[right];
        if (diff == D) {
                cout<<v[left]<<" - "<<-1*v[right]<<endl;
                if (v[left+1] == v[left]) ++left;
                else --right;
        }
        else if (diff < D) --right;
        else ++left;
  }
}

locate a pair whose sum=55 #bbg IV #Morris

Q: From an unsorted array of positive integers, is it possible to find a pair of integers that sum up to a given sum?

Constraints: This should be done in O(n) and in-place without any external storage like arrays, hash-maps, but you can use extra variables/pointers.

If this is not possible, can there be a proof given for the same?

—–Initial analysis—-
I wish I were allowed to use a hash table of “wanted ” values. (iterate once and build hashtable. For Each new value encountered, check if it is in the “wanted” list…)

I feel this is typical of west coast algorithm quiz.

I feel it’s technically impossible, but proof?  I don’t know the standard procedure to prove O(n) is impossible. Here’s my feeble attempt:

Worst case — the pair happens to be the 1st and last in the array. Without external storage, how do we remember the 1st element?  We can only use a small number of variables, even if the array size is 99999999. As we iterate the array, I guess there would be no clue  that 1st element is worth remembering. Obviously if we forget the 1st element, then when we see the last element we won’t recognize they are the pair.
—–2nd analysis—-
If we can find a O(n) sort then problem is solvable. Let’s look at Radix sort, one of the most promising candidates.

Assumption 1: the integers all have a maximum “size” in terms of digits. Let’s say 32-bit. then yes radix is O(n). Now, with any big-O analysis we impose no limit on the sample size. For example we could have 999888777666555444333 integers. Now, 32-bit gives about 4 billion distinct “pigeon-holes”, so by the pigeon-hole principle most integers in our sample have to be duplicates! Sounds artificial and unreasonable.

Therefore, Assumption 1 is questionable. In fact, some programming languages impose no limit on integer size. One integer, be it 32 thousand bits or 32 billion bits, could use up as much memory as there is in the system. Therefore, Assumption 1 is actually superfluous.

Without Assumption 1, and if we allow our sample to be freely distributed, we must assume nothing about the maximum number of digits. I would simply use

Assumption 2: maximum number of digits is about log(n). In that case radix sort is O(n log(n)), not linear time:(

—– new analysis as of Jun 2017 —-
Use Morris algo to sort the array (external storage). Then use the 2-moving-pointer algo in locate a pair whose diff=55

However, Morris needs a tree not an array.

 

keyboard accelerator to open c:/temp/a

Easy in win-xp- – Create an item on the start menu. The item is a link to the tmp file

–solution 1:
On win7, I had to name the file something like c:/temp/tmppp.txt. Then place a shortcut on Desktop outside any myShortcuts\ folder. Then right-click -> properties -> shortcut.

Ineffective when notepad++ is already running (possibly minimized to tray…) So the workaround is Alt-F4 to kill notepad++ then use the shortcut key

–Solution 2: drag shortcut “pin to start menu”

1. Open mswe and locate the file
2. Drag the file towards the start button until “pin to start menu”
3. Pin it to top of the list
4. From now on, we can wake up the start menu then arrow-down, blindfold