king
BAN USERThis is how I would answer. Not sure if it is right though :)
1) Merge sort: If the data is too big to fit into memory, I will use something like external k-way merge sort. - O(nlogn)
2) Insertion sort: If the data is almost sorted, this is the way to go !
3) Quick sort: If the data is almost unsorted and is small to fit into memory and extra space is not allowed, this is the way to go !
4) Counting sort: If additional O(n) space is allowed, data is almost unsorted and small enough to fit into memory and most importantly, the difference between numbers is much lesser than the number of different numbers, this is the way to go !
5) Bubble sort: if the data is small enough to fit in memory, almost sorted in ascending order, this can be used. But I will still incline to use insertion sort.
I am using modified version of KMP algorithm as follows:
As the border should have 3 non-overlapping occurrences, the maximum length of this border can be len /3.
1) I am computing LPS array for the largest suffix possible.
The last index of suffix_lps array will tell me the longest suffix border found in the given string.
2) if longest suffix border is 0, then return 0 as there is no suffix that matches prefix.
Else compute second_lps array for the 2nd occurence. The 2nd occurence can happen anywhere from index 1 to index len-2.
3) Then I will look in the second_lps to see if there is any border of length same as suffix border and also that there is no over lap in the index of 2nd border and suffix border.
Here is the code:
int len = instr.length();
int suf_start_idx = (len%2) ? 2*len/3 +1 : 2*len/3;
string suffix = instr.substr(suf_start_idx);
int max_suf_len = len - suf_start_idx;
int suffix_lps[max_suf_len];
int second_lps[len - 1];
string prefix = instr.substr(0, len/3);
computeLPSarray(suffix, max_suf_len, prefix, suffix_lps);
if (suffix_lps[max_suf_len-1] == 0)
ret_val = 0;
else
{
computeLPSarray(instr.substr(1), len-1, prefix, second_lps);
int idx_suf_start_match = len - suffix_lps[max_suf_len-1];
for(int i = 0; i < len-1; i++)
if ((second_lps[i] == suffix_lps[max_suf_len-1]) && (i < idx_suf_start_match))
{
ret_val = second_lps[i];
break;
}
}
cout << ret_val << endl;
suf_start_idx = (len%2) ? 2*len/3 +1 : 2*len/3;
string suffix = instr.substr(suf_start_idx);
pattern = instr.substr(0, len/3);
computeLPSarray(suffix, max_suf_len, pattern, suffix_lps);
This is based on the logic of swap using XOR.
if u want to swap a & b using XOR: a = a^b, b=a^b and a = a^b
Just like that, lets assume I want to swap bits of m and n.
((m >> i) ^ (n >> k)) : This is just like first step a^b
((1UL <<l) -1) >> (k-1) : This is 0s followed by 1s of size (l-k+1) Eg: 00000111
This means we are trying to swap bits of length 3 bits.
mask = (((m >> i) ^ (n >> k)) & ( ((1UL <<l) -1) >> (k-1)));
mask will contain 0s followed by XOR of bits of m and n of length l-k+1
n = n^(mask <<k)
This is step 2 of XOR swap that is b = a^ b. In this case a is mask and b is n.
Hope this helps.
void search(int k, int start, int end, int &left, int &right, int a[])
{
if (start <= end)
{
int mid = end - ((end-start)>>1);
if(a[mid] == k)
{
if (left > mid) left = mid;
if (right < mid) right = mid;
search(k, start, mid-1, left, right, a);
search(k, mid+1, end, left, right, a);
}
else if (a[mid] < k)
search(k, mid+1, end, left, right, a);
else
search(k, start, mid-1, left, right, a);
}
return;
}
air traffic control system is a classic example of mediator design pattern.
1) Define an interface for mediator.
2) Define another interface for client.
3) Define concrete impl for the mediator interface
4) Define concrete impl for the flight interface.
Each flight object needs to register with the mediator.
1)For all characters in the left hand set add weight = 2.
- king August 09, 20132) For all characters in the right hand set add weight = 5.
lefthand set is "qwerasdfzxcvtgb "
righthand set is "uiopjklmnhy "
weight[] = {2 or 5 for all of 26 chars};
Foreach word w in dictionary:
1) computer cummulative weight as :
cum_weight = product of weight of all chars in the word.
Eg: cum_weight(cat) = weight[c]*weight[a]*weight[t] = 2*2*2 = 8
2) If (cum_weight % 2 ==0) and (cum_weight %5 !=0)
the word consists of ONLY LEFT HAND set chars.
If (cum_weight %5 ==0) and (cum_weight %2 != 0)
the word consists of ONLY RIGHT HAND set chars.
3) Now u can use max variable to keep track of longest word. Longest word is essentially maximum value in each category.