milota@mindgrip.com
BAN USER 0of 0 votes
AnswersCreate a stack for bools. it will have these functions
 milota@mindgrip.com in United States
void push(bool input)
bool pop() // no one will ever try to pop if it is empty
bool empty() const // returns true if the stack is empty
void clear() // cleans out the data and recovers the memory
This stack should not be limited in size but grow as needed.
hard part
save space, it is ok if it is slow from time to time but should generally be fast
98% of the time we will push false and 2% of the time we will push true
edge conditions
the first push may be true or false
there may be long runs of just pushing true or long runs of just pushing true
second part
how would you change it to if it was 80 / 20 and there were long runs of an average length of 15 trues in a row?
third part
How would you change it if there were different ratios and different average length runs. Report Duplicate  Flag  PURGE
Software Engineer / Developer Data Structures
sort
match every other one
{w[0], w[1]}
{w[2], w[3]}
...
If x+y1 is odd you can make any pattern with row/column flips.
Else
If the exor of all cells is 0 then this is a valid pattern
However if it is 1 then you cannot make that pattern
Label all cells in the grid with capital letters
ABC
DEF
Let the lower case letter be true if it was the center of a flip
a= true
111
100
Write the equation for each cell
A = a exor b exor c exor d
B = a exor b exor c exor e
C…
Exor all capital letters
Simplify
z exor z > 0
0 exor z > z
…
When you flip a row / column you change x+y1 cells
If(x+y1) is even then the exor of all bits will = 0
If(x+y1) is odd then exor of A….. = exor a…. so that does not matter
If someone can write a better explanation please do. It took me a long time to figure this out and I want to move on. It seems like a induction proof would be good for this.
#include "stdafx.h"
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
int count_crossings_after_sort(vector<int> in) // no depes aloud !
{
unordered_map<int, int> value_to_old_index;
for (int i = 0; i < in.size(); i++)
{
value_to_old_index[in[i]] = i;
}
sort(in.begin(), in.end());
int c = 0;
for (int i = 0; i < in.size()  1; i++)
{
for (int j = i + 1; j < in.size(); j++)
{
if (value_to_old_index[in[i]] > value_to_old_index[in[j]])
{
c++;
}
}
}
return c;
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> in = { 3, 5, 2, 1 };
int r = count_crossings_after_sort(in);
return 0;
}

milota@mindgrip.com
November 21, 2017
 milota@mindgrip.com December 18, 2017