Darida
BAN USERalmost 3 years of work experience, including programming experience in C++, Java and C#. Strong OOP skills. Coding skills in JavaScript and AJAX. Database design and SQL experience. Strong background in computer science, with core competencies in efficient data structures, algorithms, and software design.
IPv4 is X1.X2.X3.X4 where X can be from 0 to 255, that's mean it can take 2^8 values.
4*X  is 4*8 bit and is it 4 byte.
1. we can use 4 byte as key for one element. In this case we will never have collisions.
2. we can use less then 4 byte, then the best way to impliment hash function will be to ignore first numbers, and use last (X4, X3.X4 or X2.X3.X4 dependence of how many memory we want to use) as hashkey.
We use only end of id address, because in real life ip addresses usually in one area have same first 3 digits, more over in one (home/work) network they usually have same 3*3 digits.
So collisions will be more evenly distributed if we skip first part.
Obviously, this is reqursion/dynamic problem. So we need formula.
Let's say, that F(i, j)  is max possible coins that 'first' player can collect on board with packets from i to j. And by 'first' player I mean player whos turn now.
F(0, n1)  will be the answer.
Ok, now for F(i, j), first player can take v[i] or v[j].
x = v[i] + (Sum[i+1, j ]  F(i+1, j ) );
y = v[j] + (Sum[ i , j1]  F( i, j1) );
And he will collent x or y coints. Of course he will choose the maximum option:
F(i, j) = MAX(x, y);
Why (Sum[i+1, j ]  F(i+1, j ) )? Thats simply. After the first player took the coins, the turn passes to the second. And he also wnat to win. And now he is the first player but on the board (i+1, j) or (i, j1). The Sum is fixed, so all that he will not take  is our coins.
_________________________________________________
But do we really need to calculate Sum? No!
Lets go deeper! in recursion : ) I skip here computing. In two words:
If we 'open' F(i+1, j ) and F( i, j1)  sum will be reduced and using that
Max[a, b] == Min[a, b]
and we will get:
a = F(i+2, j); b = F(i+1, j1); c = F(i, j2);
x = v[i] + MIN(a, b); y = v[j] + MIN(b, c);
F(i, j) = MAX(x, y);
On each iteration size of board will be reduced on 2.
_________________________________________________
To avoid recomputation, we need to store all done computation:
ArrayInfo optimal_subset_sum; //optimal_subset_sum( i, j ) = F(i, j)
ArrayInfo can be simply int[n][n]. if you don't care about the amount of memory used.
But we'll get to that later.
First, we need to initialize the smallest boards answers. There are two different situation.
If N is odd, then F(i, j) = F(i, i) = v[i]
for(int i=0; i+1<n; ++i)
optimal_subset_sum(i, i+1) = data[i];
If N is even, then F(i, j) = F(i, i+1) = MAX(v[i], v[i+1])
for(int i=0; i+1<n; ++i)
optimal_subset_sum(i, i+1) = MAX(data[i], data[i+1]);
And now, we increasing the size of the board for 2 and calculate answers for all possible boards:
for(int k = smallest_lenght + 2; k<=n; k+=2)
for(int i=0, j=k1; j<n; ++i, ++j)
{
int a = optimal_subset_sum( i+2, j );
int b = optimal_subset_sum( i+1, j1 );
int c = optimal_subset_sum( i, j2 );
int x = data[i] + MIN(a, b); int y = data[j] + MIN(b, c);
optimal_subset_sum(i, j) = MAX(x, y);
}
_________________________________________________
Returning to the ArrayInfo.
There is only 1 subboard starting fron i=n1. (n1, n1)
There are only 2 subboard starting fron i=n2. (n2, n2) and (n2, n1)
...
Additionaly, we have only odd or only even lenght subboards, because we reduce it on 2 each time.
So we don't need N*N space. We can impliment ArrayInfo such way:
class ArrayInfo
{
public:
ArrayInfo(size_t n)
{
data = new int*[n]();
for(int i=0; i<n; ++i)
{
data[i] = new int[(n1i)/2+1]();
for(int j=i; j<n; ++j)
data[i][j] = 1;
}
}
int& operator() (int i, int j)
{
return data[i][(ji)/2];
}
private:
int** data;
};
And it will used
Sum[(Ni1)/2 + 1, { i, 0, N1 } ] = N*(3+N)/4 = n^2/4 + 3*n/4
that's in 4 time less.
working code: http://ideone.com/ZzbMRt
sum array will be: 0 1 1 1 1
longest subset is from 1 to 4
you can find an explanation by looking closely at the function Range::add
first time we will set both  first && last positions to the current. and the lenght of array will be 0.
then we will set only last position.
So, we want to find subset [i, j], such that
( a[i]+a[i+1]+ ... a[j] ) % k = 0
with k == 7, that really does not matter
________________________________________________
Let's calculate the sum of elements from 1 to i by mod k for each i:
s[i] = (a[1] + a[2] + ... + a[i]) % k
And we can note that, if there is such [i, j] that we are looking for, then:
s[j]s[i] == (a[1]+...+a[j])  (a[1]+...+a[i]) == (a[i]+...+a[j]) == 0
So, for each s[i] == s[j], sum of subset [i, j] is divisible by k.
Now we need to find the most appropriate range.
If we are looking for the longest set, then
struct Range
{
int first_position = 1;
int last_position = 1;
void add(int position)
{
if(first_position == 1)
last_position=first_position = position;
else
last_position = position;
}
friend bool operator<(const Range& r1, const Range& r2)
{
int r1_lenght = r1.last_positionr1.first_position;
int r2_lenght = r2.last_positionr2.first_position;
return r1_lenght < r2_lenght ;
}
};
for each modulo of k: we need find first and last position (in sumarray), and select the largest range from them.
Range searchRange[k];
int sum = 0, max_range_id = 0;
for(int i=0; i<n; ++i)
{
sum=(sum+data[i])%k;
searchRange[sum].add(i);
if(searchRange[max_range_id] < searchRange[sum])
max_range_id = sum;
}
Here is working full code: http://ideone.com/VvWSkT
 Darida October 28, 2013Well, we have sorted Matrix M*N.
int data[N][M] = ...;
The idea is to start sorting matrix using Megre Sort algo and stop when we find Kth element.
_____________________________________________
That's the interface for our class.
class IMegreSort2D
{
MegreSort2D(const int** data, int n, int m);
int next(size_t count = 1);
};
We can use it such:
int k_sorted_element = MegreSort2D(data, N, M).next(k);
or such (to sort all matrix):
MegreSort2D sort(data, N, M);
for(int i=0; i<N*M; ++i)
cout<<sort.next()<<endl;
_____________________________________________
Now we need to impliment function "next".
Let's create support structure Link. It will store position and value from this position. Also we will override operator< for them to compate 2 Link by values.
struct Link
{
int i, j;
const T& value;
Link(const int** data, int i, int j) : i(i), j(j), value(data[i][j]) {}
friend bool operator<(const Link& l1, const Link& l2) { return l1.value > l2.value; }
};
Of course, we can use str::pair<int,int> and get value from data. But, as for me, this version is more readable.
_____________________________________________
Now, our MergeSord need Min/Max Heap. In c++ we can use std::priority_queue.
priority_queue<Link> min_heap;
Firstly, we put there only smallest/biggest element:
min_heap.push(Link(data, 0,0));
Then, on each call 'next', we will take smallest/biggest element from this heap, and put next element from the same row to them:
int next()
{
const Link& link = min_heap.top(); //get smallest/biggest element from heap
T value = link.value; //save to return
if(link.i<(N1)) //if it is not the last element of the row
min_heap.push(Link(data, link.i+1,link.j)); //add next value from this row
if(link.i==0 && link.j<(M1)) //if it was first element from the row
min_heap.push(Link(data, 0,link.j+1)); //add first value from next row
min_heap.pop();
return value;
}
Also we put first element from the next row, when take first element from previouse row.
Here is full working code: ideone.com/xZqt51
The task is not clear, but i guess, that we are speaking about finding Kth sum from a[i]+b[j] for ANY {i, j}. Becouse if i==j, it is simply binary search, and there is no reason to complicate the task description.
___________________________
This task reduced to another popular task, which has been discussed here many times:
Find Kth element in Sorted Matrix.
Let's imagine that we have N*M Matrix: S[i][j] = a[i]+b[j];
a[0]+b[0] a[0]+b[1] ... a[0]+b[m]
a[1]+b[0] a[1]+b[1] ... a[1]+b[m]
...
a[n]+b[0] a[n]+b[1] ... a[n]+b[m]
A and B was sorted list. So each column and each row is sorted too.
Here is the link to solution:
question?id=6335704
or you can find it, as the most commented question from Google's interview.
I use word 'imagine', becouse we don't need to build it for real.
To solve derivative problem, all numbers from matrix are needed only once, so we can calculate sum in runtime, without saving to matrix.
Well, we have
int input[n] = {7, 5, 6, 3, 4, 1, 2, 9, 11};
we want to get
int answer[n]; // = {9, 6, 9, 4, 9, 2, 9, 11, 1}
for(int i=0; i<n; ++i)
answer[i] = 1;
I mark numbers that doesn't have bigger at right side as 1.
We can replace 1 with anything we need later.
We will save all positions, for which we still didn't find answers in stack.
At the start, stack is empty.
stack<int> still_without_answer;
Now, we are going to iterate throw the array.
for(int i=0; i<n; ++i)
For each number, we will find all numbers on the left sife, that less then current.
We will delete them from the stack.
So after that, all numbers in the stack will be bigger then current.
That mean that our stack is decreasing order and we can check only the top value, instead of iteration throw stack.
int smallest_without_answer = still_without_answer.top();
while(!still_without_answer.empty()&&input[smallest_without_answer]<input[i])
{
answer[smallest_without_answer ] = input[i];
still_without_answer.pop();
}
int smallest_number_without_answer = still_without_answer.top();
After setting current number as answer for smaller numbers, we push them to stack. Now it is the smallest number without answer.
still_without_answer.push(i);
This is O(n), becouse we iterate 1 time throw each elements, 1 time put each element to the stack for O(1), and 1 time delete from the stack for O(1).
 Darida October 23, 2013You solution will fail on something like this:
0 0 0 0 0
0 1 0 1 0
0 1 x 1 0
0 0 0 1 0
in both case  whether we can go to 4 direction or 8.
Because, when you find path from A to X it will be:
p p p 0 0
0 1 p 1 0
0 1 x 1 0
0 0 0 1 0
and where is no path from X to B not including first path.
 Darida October 22, 2013Two words are anagrams IF AND ONLY IF they have the same set of letters.
Let's create a class representing a collection of letters. We can implement it several ways: by sorting set of letters, or by array or some another way. Here is implementation by array:
class CharSet
{
private:
static const int alphabet_lenght = 'z'  'a' + 1;
size_t letters[alphabet_lenght];
public:
void add(char letter)
{
++letters[letter  'a'];
}
class Comparer; class Hasher;
};
We need to define Comparer and Hasher for this class to effectively use later.
Comparer should simply iterate over array and check whether they equal;
Here is sample of Hasher:
class CharSet::Hasher
{
private:
const size_t PRIME = 31;
public:
size_t operator()(const CharSet& word) const
{
size_t hash=0;
for(size_t i=0; i<alphabet_lenght; ++i)
hash= hash * PRIME + word.letters[i];
return hash;
}
};
Now, we can say, that if two words have equal CharSet then they are anagrams.
But it is a too long to compare CharSet completely each time.
The two CharSet NEVER equal if
a. they contain different number of chars
b. or their hash doesn't equal.
It is much faster to compate two numbers (lenght and hash) instead of 2 arrays.
Lets create class AnagramPatern, that can faster compare CharSets:
class AnagramPatern
{
private:
size_t hash, lenght;
CharSet letters;
public:
AnagramPatern(const string& word) : lenght(word.size())
{
for(const char& letter : word)
letters.add(letter);
hash=CharSet::Hash()(letters);
}
class Comparer; class Hasher;
};
We will count hash only 1 time  on creating, and save it. Hasher will simply return it.
And Comparer will first compare length and hash, and only if they equal, that compare full CharSet. Actually, for small alphabet we can implement hash without collision, and comparing arrays will be not needed.
class AnagramPatern::Comparer
{
public:
bool operator() (const AnagramPatern& first, const AnagramPatern& second) const
{
if(first.lenght != second.lenght  first.hash != second.hash)
return false;
return CharSet::Comparer()(first.letters, second.letters);
}
};
Now we need HashTable. Words will be values, and AnagramPatern will be th key.
class AnagrammGrouper
{
private:
typedef unordered_map<AnagramPatern, list<string>, AnagramPatern::Hasher, AnagramPatern::Comparer> Collection;
Collection groups;
public:
void add(const string& word)
{
AnagramPatern format(word);
auto it = groups.find(format);
if(it == groups.end()) //first time for such pattern we need to create list
it = groups.emplace(format, list<string>()).first;
it>second.push_back(word);
}
Collection::const_iterator begin() { return groups.begin(); }
Collection::const_iterator end() { return groups.end(); }
};
Here is full code with test:
http://ideone.com/buzjGP
First check whether number is power of 2:
x = 2^k
x == 0...010...0
x1 == 0...001...1
x & (x1) == 0...000...0
x != 2^k
x == 0...1...010...0
x1 == 0...1...001...1
x & (x1) == 0...1...000...0
If it is not power of 2  then it is not power of 4.
If it power of 2  then it have exactly one 1 in binary record.
1 = 000000001
4 = 000000100
16 = 000010000
64 = 001000000
256 = 100000000
If it is power of 4  position of this single 1 will be odd.
bool isPowerOfTwo = x && !(x & (x  1));
//101010100 = 0x5...554
int mask = 0x5...554; //(or 0x5...555 is 1 should be included as 4^0)
return isPowerOfTwo && (x & mask );

Darida
October 21, 2013 There are two different situations in unspecified condition:
Whether we should consider duplicate one or more times.
 If the expected result without duplicates:
1. HashSet, not HashTable. Its similar but not identical structures.
2. We should remove elements from HashSet after they was founded  otherwise we can find them a few times.
 If the expected result with countedduplicates
1. HashTable should save as values duplicatescount
This is a simple and intuitive solution.
But we can replace string with bitstorage.
There are (2n)!/(n!(n+1)!) total combination for parentheses and copying string is very timeconsuming operation.
Here is the comparing of work time (in ms) for string and bit implimintation:
n bit string
5 0 2
10 8 869
11 28 3164
12 97 11450
13 358 (< 1 sec) 40892 (40 sec)
14 1300 (1 sec) 146235 (2 min)
15 4788 (5 sec) 537079 (8 min)
I hope, I assure you that it is bad to copy strings
class Parentheses /*save as binary */
{
public:
Parentheses() : parentheses(0), n(0) {}
Parentheses add(bool bracket) //return new object
{
if(bracket) return Parentheses(parentheses  (1 << n), n + 1);
else return Parentheses(parentheses, n + 1);
}
void print()
{
for(size_t i = 0; i<n; ++i)
if(parentheses & (1 << i)) cout<<"("; else cout<<")";
cout<<endl;
}
private:
Parentheses(unsigned long long parentheses, size_t n)
: parentheses(parentheses), n(n) {}
unsigned long long parentheses;
size_t n;
};
void find(int n, int left=0, int right=0, Parentheses s= Parentheses())
{
if(left+right==2*n)
{
s.print(); return;
}
if(left != n)
find(n, left+1, right, s.add(true));
if(right < left)
find(n, left, right+1, s.add(false));
}

Darida
October 20, 2013 The faster solution is merge sort by all rows (or columns) at the same time.
To do this, we need minheap.
Here is how to *use* MinHeap for sorting. MinHeap does not implemented is this code. You can find the implamantation in google if you need.
template<class T> class MegreSort2d
{
struct Link
{
Link(const T** data, int i, int j)
: i(i), j(j), value(data[i][j]) {}
const int i, j;
const T& value;
};
static void sort(const T** data, T* outData, int n)
{
MinHeap<Link> heap;
current_mins.add(Link(data, 0,0));
for(size_t i=0; i<n*n; ++i)
{
const Link& link = heap.getMinValue();
outData[i]=link.value; //save as sorted
if(link.i<(n1))
heap.add(Link(data, link.i+1,link.j)); //add next value from this row
if(link.i==0 && link.j<(n1))
heap.add(Link(data, 0,link.j+1)); //add first value from next row
heap.remove(link);
}
}
};

Darida
October 20, 2013 There is no solution faster that O(n^2 * Log n) where n  is the size of matrix.
Check you solution on something like this:
a a a a b
a a a b c
a a b c c
a b c c c
b c c c c
Where
a  different values in range (x1, x2)
b  different values in range (x2+1, x3  1)
c  different values in range (x3, x4)
I mean, all values upper diagonal is less than diagonal. And all values then down than diagonal  is more than diagonal.
Repsonjamramos45, Graphics Programmer at CGIAMS
I am a strong writer with a passion for storytelling who has extensive experience of writing literary compositions, articles, reports ...
Repsusancmeans, Apple Phone Number available 24/7 for our Customers at Absolute Softech Ltd
I am Susan from Bronx, I am working as a Business management analyst in Brendle's company. I Have a ...
Repammiwilson5, Personnel at BMO Harris Bank
Hi I am Ammy from Served on a research team for improved customer satisfaction survey process,Moderated focus groups to ...
Repomarcdei, Android Engineer at Abs india pvt. ltd.
I'm Omar. I am working as a Mail carrier in Manning's Cafeterias company. I love to learn and ...
Repjoankelly306, Site Manager at EFI
Hi, I am Joan from Fairbanks, in USA. I have been a Food Product Manager in a Food Barn Company ...
Repbrandysolsen, Area Sales Manager at AMD
I am a Social butterflies who enjoy travel.Have fun doing this job and project an atmosphere that reflects Amazon ...
Repkarinkwalton, Backend Developer at Broadsoft
I am working as a Support clerk in an MVP Sports company. I love traveling and exploring facts about technology ...
RepGinaSanchez, Computer Scientist at Autoportal.com
Ginna from New York.Successfully managing a high volume of work assignments without compromising quality to exceed client expectations.Apart ...
Open Chat in New Window
For sorted:
Time: O(N)
Space: O(1)
For unsorted:
Data structure: treap (tree+heap)
sorted tree by value + maxhead by count
 Darida January 03, 2014root will be the answer
Time: O(N Log(N))
Space: O(N)