ashot madatyan
BAN USERint height(node* pnode)
{
if (NULL == pnode)
return 0;
int lh = height(pnode->left);
int rh = height(pnode->right);
return (1 + max(lh, rh));
}
void print_nodes(node* pnode)
{
node* pcurnode = pnode;
while(pcurnode)
{
print_node(pcurnode);
int lh = height(pcurnode->left);
int rh = height(pcurnode->right);
pcurnode = lh > rh ? pcurnode->left : pcurnode->right;
}
}
pseudo code below
s = "some string with repeated characters"
map<char, int> m
for each c in some
m[c]++
for each e in m
print e.value
O(N) implementation
// Shift all the zero's to the right of the array
void shift_zeros_right(int arr[], const int& sz)
{
int i = 0, j = sz;
while(i < j)
{
// Skip if the current element is a not zero
if (arr[i] != 0)
{
++i;
continue;
}
if (arr[j] != 0)
{
swap(arr, i, j);
++i;
}
--j;
}
}
Solution at O(n) complexity w/o even an additional tmp variable.
- Start at the first position of the index array
- While the element at the current position is not in its proper slot
-- swap the elements in both the index and data arrays, thus putting the current element into its proper slot
-- if the element is in its proper slot, then increment the counter and continue
void sort_data(char A[], int B[], const int& size)
{
int i = 0;
while(i < size)
{
if (B[i] == i)
{
++i;
continue;
}
// swap the elements in both arrays
swap(A, B[i], i);
swap(B, B[i], i);
}
}
Scan each row and create a 1-dimensional array of count of 1's in each row. This will result in something like below:
1 2 11 0 4 5 2 8 0 1 9 7 9 0 16
The size of this array is the number of rows in the matrix and the index of each item is the row index of the original MxN matrix. Now, the problem boils down to finding the "Maximum subarray problem" with one restriction - the subarray should not be the whole array itself.
@Ramesh N: I believe the
class Logger
is a C++ code, then its
message
function has to be virtual.
- ashot madatyan January 09, 2014If it has to be thread safe and provide high performance, then the first thing to do is to decouple the serialization into the file with the rest of the logic, since file I/O is much slower than memory operations.This knowledge inherently yields a dedicated thread for the logger to serialize its FIFO cache of messages, which can be implemented with the command pattern, as mentioned by the poster. Anyway, access to the shared resources has to be protected with some type of OS-specific locks or similar mechanisms. On Windows platforms, you can use the QueueUserAPC, which will shift the locking from the user-space to the OS's kernel, while on Linux platforms, you will eventually come to mutices and the like.
- ashot madatyan January 09, 2014Do a single scan of the string and collect and print the data as below. Space complexity is constant, time is linear:
#include <stdio.h>
void enc(const char* buf, int size)
{
if (NULL == buf)
return;
int cnt = 0;
char pc = 0;
for (int i = 0; i < size; i++)
{
if (pc == buf[i])
{
cnt++;
}
else
{
// process the previous char
if(pc)
printf("%c%d", pc, cnt);
pc = buf[i];
cnt = 1;
}
}
// process the final char(s)
if (cnt)
printf("%c%d", pc, cnt);
}
int main(int argc, char* argv[])
{
char buf[] = "aaaabbccdd";
int size = strlen(buf);
enc(buf, size);
return 0;
}
Hi Gosham. This is exactly what I have come to when implementing a timer queue in Linux (it's missing the " CreateTimerQueue" functionality analog of Windows). But I have a small (but very important) correction - do not use periodic polling per ce since it is very-very resource consuming. Instead use the "pthread_cond_timedwait" function, that can be released by either explicitly signalling it (signal the wait condition) or when the timeout period expires. It works like a charm even with nanosecond precision - the timer thread wakes up and invokes the callback function of the object stored in the priority queue.
So, voting up your suggestion.
The below implementation does it with O(n) time and O(n) space complexity. Algorithm is in comments.
/**
TASK: Given an n X n matrix, find all elements which are zero, when found
set all the elements in that row and column to zero.
ALGORITHM:
1. Do a single table traversal and collect the information on the rows
and columns to be zero'ed
2. Do another traversal of the table to zero the cells
*/
void zero_cells(int arr[5][5])
{
int cols[5] = {0};
int rows[5] = {0};
// collect table statistics
for (int j = 0; j < 5; ++j){
for (int i = 0; i < 5; ++i)
if (arr[j][i] == 0){
cols[i] = 1;
rows[j] = 1;
}
// zero out cells and rows
for (int j = 0; j < 5; ++j){
for (int i = 0; i < 5; ++i){
if (cols[i] == 1 || rows[j] == 1)
arr[j][i] = 0;
}
Do it in-place and w/o using any additional storage. Actual one-pass implementation presented below does not use strlen, so allowing us to do it in a single pass:
void subst_all_chars(char* a)
{
int fill_pos = -1;
char subst = 'f';
while (a[i++]){
char chcur = a[i];
if (chcur == subst){ // if the current is the sought char
a[i] = 0;
if (-1 == fill_pos)
fill_pos = i;
}
else { // char that is OK to stay
if (-1 == fill_pos)
continue;
else { // we have previous gap, so copy the current char to this position
a[fill_pos] = chcur;
a[i] = 0;
++fill_pos;
}
}
}
}
Split the input file into the "N" chunks (in this case, 2Gb each) that total to size "K" bytes (10Gb in this case). Load the chunks per request. When the memory is full, unload the oldest chunk/chunks to make space for new ones. Among other possible scenarios, You can unload a chunk based on the reference count of the given chunk (i.e., ref = 0).
- ashot madatyan September 04, 2013@gonzo: The binary heap has two properties: heap and shape. Here, we are using its shape property, i.e. inserting items (nodes) from left to right. This yields us the shape of the binary heap when we insert the original values from highest to lowest into the binheap.
Excerpt from wiki:
Shape property
The tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
BTW, another advantage of the binary heap is that it is an in-place algorithm abd does not require any additional storage as a scratch space.
- ashot madatyan August 10, 2013This is the solution that I came up with too. To minimize the tree weight, we have to minimize the two its contributing factors - the level and the product of a number and its level. To achieve this, we need a binary heap (yielding the minimum tree height), while the numbers have to be entered into the heap from highest to lowest. This approach leads us the the max binary heap.
- ashot madatyan August 07, 2013@Chiu.Chiu You have two arrays, each containing non-repeating integers. The second array is the same as the first except the second array is missing two integers from the first array. How would you find in O(N) time and O(1) space those two integers that are missing in the second array?
- ashot madatyan July 26, 2013Do it in O(N) time, simulating the merge stage of the merge sort algo and keeping track of the absolute difference between any current elements of the array. Below is the s/c and the test driver:
#include <stdio.h>
int absdiff(int a, int b)
{
if (a == b)
return 0;
if (a > b)
return (a - b);
return (b - a);
}
int min_diff_els(int a[], int b[], int size, int& idx1, int& idx2)
{
int i = 0, j = 0;
idx1 = 0;
idx2 = 0;
int mindiff;
mindiff = absdiff(a[0], b[0]);
// special case when there is no better solution,
// since absdiff(a, b) can't be < 0
if (0 == mindiff)
return 0;
++i; ++j;
while (i < size && j < size){
int cv = absdiff(a[i], b[j]);
if (cv < mindiff) {
idx1 = i;
idx2 = j;
mindiff = cv;
}
if (a[i] < b[j])
++i;
else
++j;
}
return mindiff;
}
int main()
{
//
int a[] = {5, 9, 12, 15, 18, 25};
int b[] = {1, 3, 6, 10, 17, 22};
int size = sizeof(a)/sizeof(a[0]);
int idx1, idx2, val;
val = min_diff_els(a, b, size, idx1, idx2);
printf("Min Abs Diff: %-3d Idx1: %-3d Idx2: %-3d\n",
val, idx1, idx2);
return 0;
}
The algorithm works using elimination of rows and columns and its worst case complexity is O(n+m), where <n> is the count of rows and <m> is the count of columns.
Solution:
When moving left we eliminate all the values below that column.
Similarly, when moving down we eliminate all the elements to the left
of that cell in the current row.
bool find_int(int mat[][], int rows, int cols, int val)
{
int n = 0; // row index
int m = cols - 1; // column index
while(m >= 0 && n < rows){
int curval = mat[n][m];
if (curval == val) {
printf("found at: %-3d %-3d\n", n, m);
return true;
}
else if (curval > val)
--m;
else
++n;
}
return false;
}
Moreover, this technique can be used to find even two missing elements from the original array. But this is already a different problem :)
- ashot madatyan July 26, 2013@oOZz This should work only for the given range of numbers [1 ... 100], but what I suggested will work for any range, even with the numbers that would overflow should they be summed up. Consider input values as follows [ INT_MAX - 2, INT_MAX - 5, INT_MAX - 20, ...] Will your suggested algo work for this series of numbers ? I believe the answer is "No".
- ashot madatyan July 26, 2013This is Boyer && Moore's the majority vote algorithm, you can find the description at ht tp:// ww w.cs.utexas.edu/~moore/best-ideas/mjrty/.
- ashot madatyan July 26, 2013Summing up the numbers might very easily overflow, in which case you will surely lose the end result.
- ashot madatyan July 26, 2013There is a very elegant solution using bitwise operations with integers.
The following solution has O(n) time and O(1) space:
INPUT: arr[N] = min_val, i.e. min_val + 1, min_val + 2, .... max_val
MISSING: min_val < missing_val < min_val + N
ASSUMPTION: There are no duplicates in the input array
Solution:
0. Find the minimum and maximum values in the array: min_val, max_val
1. Compute the XOR'ed value of all elements from min_val to max_val inclusive: <xc>
2. Compute the XOR'ed value of all the input array elements: <xarr>
3. XOR the two integers - this will produce the missing element's value
The s/c and the test harness are below:
#include <stdio.h>
int missing_element(int arr[], int size)
{
int min_val, max_val;
int xarr = 0, xacc = 0;
// Find the minimum and maximum values in the array
min_val = arr[0];
max_val = arr[0];
for (int i = 1; i < size; ++i){
if (arr[i] > max_val)
max_val = arr[i];
if (arr[i] < min_val)
min_val = arr[i];
}
// Find the XOR'ed value of all numbers from min_val to max_val inclusive
for (int i = min_val; i <= max_val; ++i) {
xacc ^= i;
}
for (int i = 0; i < size; ++i){
xarr ^= arr[i];
}
return (xacc ^ xarr);
}
int main()
{
// values are 5 - 14, missing is 11
int arr[] = {8, 13, 5, 10, 6, 7, 9, 12, 14};
int size = sizeof(arr) / sizeof(arr[0]);
int miss = missing_element(arr, size);
printf("MISSING VALUE: %-3d\n", miss);
return 0;
}
Voted up cause the solution is almost correct :) Please see note from <vishnuJayvel>, he is pointing out a very important case handling.
- ashot madatyan July 15, 2013I do not know who has downvoted king's answer, but I would try to do it too - use the external merge sort if we are limited in the memory.
- ashot madatyan July 09, 2013This is the "Rank of a permutation" algorithm. It is discussed here:
rosettacode.org/wiki/Permutations/Rank_of_a_permutation
@subahjit
I suppose, you meant to generate all the permutations of the given input word, but not the "anagrams".
The KMP should do the work in O(N). Implemented below with sample output provided.
#include <stdio.h>
#include <string>
#include <vector>
using std::string;
using std::vector;
typedef vector<int> ivec;
void print_fail_func(const ivec& idx)
{
for (ivec::size_type i = 0; i < idx.size(); ++i){
printf("idx: %-2d len: %-2d\n", i, idx[i]);
}
}
vector<int> compute_prefix_function(const string& s)
{
int len = s.length();
vector<int> p(len);
p[0] = 0;
int k = 0;
for(int i = 1; i < len; i++) {
while ( (k > 0) && (s[k] != s[i]) )
k = p[k-1];
if (s[k] == s[i])
k++;
p[i] = k;
}
return p;
}
void do_kmp_search(const string& txt, const string& pat, const ivec& idx)
{
int i = 0, j = 0, m = 0;
int ls = txt.length();
int lp = pat.length();
int cmpcount = 0;
while(i < ls){
if (txt[i] == pat[m]) {
++i;
++m;
++cmpcount;
// check if we have a match here
if (m == lp) {
printf("MATCH at: %d\n", i - lp);
m = 0;
continue;
}
}
else { // the current chars do not match
int shft = 0;
if (m > 0)
shft = idx[m - 1];
if (shft > 0) { // we have previous shorter matching prefix of the pattern
m = shft + 0;
}
else { // no previous prefix of pattern matching the string
++i;
m = 0; // reset the pattern index to its beginning
}
}
}
printf("Count of comparisons: %d\n", cmpcount);
}
int main(int argc, char* argv[])
{
string txt = "abc abcdab abcdabcdabde abcdabdu";
string pat = "abcdabd";
//string txt = "AABAACAADAABAAABAA";
//string pat = "AABA";
ivec idx;
printf("TEXT : %-40s LEN: %d\n", txt.data(), txt.length());
printf("PATTERN: %-40s LEN: %d\n\n", pat.data(), pat.length());
idx = compute_prefix_function(pat);
print_fail_func(idx);
printf("\n");
do_kmp_search(txt, pat, idx);
return 0;
}
OUTPUT:
TEXT : abc abcdab abcdabcdabde abcdabdu LEN: 32
PATTERN: abcdabd LEN: 7
idx: 0 len: 0
idx: 1 len: 0
idx: 2 len: 0
idx: 3 len: 0
idx: 4 len: 1
idx: 5 len: 2
idx: 6 len: 0
MATCH at: 15
MATCH at: 24
Count of comparisons: 27
Since this is a complete binary tree, you can simulate the inorder traversal by noting the following properties:
INPUT:
Array[N] - array of the level-order traversal of a complete binary tree
NOTES:
1. Left child node of the node with index "nidx": lidx = 2*nidx - 1
2. Right child node of the node with index "nidx": ridx = 2*nidx + 2
3. The parent node's index of the node with index "nidx": pidx = (nidx - 1) / 2 // integer division
Below is the iterative version of the suggested approach:
#include <stdio.h>
#include <stack>
using std::stack;
static int N = 15;
int left(const int& nidx)
{
int rv = 2 * nidx + 1;
if (rv >= N)
rv = -1;
return rv;
}
int right(const int& nidx)
{
int rv = 2 * nidx + 2;
if (rv >= N)
rv = -1;
return rv;
}
int parent(const int& nidx)
{
if (0 == nidx)
return -1;
int rv = (nidx - 1) / 2;
if (rv < 0)
rv = -1;
return rv;
}
void iter_inorder()
{
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
stack<int> S;
for (int i = 0; i < N; ++i){
int lidx, ridx, pidx;
lidx = left(i);
ridx = right(i);
pidx = parent(i);
printf("NIDX: %-3d LIDX: %-3d RIDX: %-3d PIDX: %-3d\n",
i, lidx, ridx, pidx);
}
printf("\n\n");
int current = 0;
S.push(current);
while (!S.empty()){
while (current != -1){
current = left(current);
if (-1 != current) {
printf("pushing: %d\n", current);
S.push(current);
}
}
current = S.top();
S.pop();
printf("IDX: %-3d NUM: %-3d\n", current, arr[current]);
current = right(current);
if (-1 != current)
S.push(current);
}
}
int main()
{
iter_inorder();
return 0;
}
And this is the output of the run:
NIDX: 5 LIDX: 11 RIDX: 12 PIDX: 2
NIDX: 6 LIDX: 13 RIDX: 14 PIDX: 2
NIDX: 7 LIDX: -1 RIDX: -1 PIDX: 3
NIDX: 8 LIDX: -1 RIDX: -1 PIDX: 3
NIDX: 9 LIDX: -1 RIDX: -1 PIDX: 4
NIDX: 10 LIDX: -1 RIDX: -1 PIDX: 4
NIDX: 11 LIDX: -1 RIDX: -1 PIDX: 5
NIDX: 12 LIDX: -1 RIDX: -1 PIDX: 5
NIDX: 13 LIDX: -1 RIDX: -1 PIDX: 6
NIDX: 14 LIDX: -1 RIDX: -1 PIDX: 6
pushing: 1
pushing: 3
pushing: 7
IDX: 7 NUM: 7
IDX: 3 NUM: 3
IDX: 8 NUM: 8
IDX: 1 NUM: 1
pushing: 9
IDX: 9 NUM: 9
IDX: 4 NUM: 4
IDX: 10 NUM: 10
IDX: 0 NUM: 0
pushing: 5
pushing: 11
IDX: 11 NUM: 11
IDX: 5 NUM: 5
IDX: 12 NUM: 12
IDX: 2 NUM: 2
pushing: 13
IDX: 13 NUM: 13
IDX: 6 NUM: 6
IDX: 14 NUM: 14
Hi Gevorg.
Have you considered meeting in your suggested solution the constraint
"You dont have RAM to store even k elements."
The K-th order statistics does require at least "K * sizeof(object)" allocated memory. Or you maybe suggesting some implementation that could use file system ?
- ashot madatyan July 05, 2013"How do you differentiate between an edge n1->n2 and n2->n1"
This depends on the type of graph - is it directed or not. If it's a directed graph then something similar to list of adjacent nodes for each node will do. Otherwise, you can use adjacency matrix, implemented as a sparce array to preserve the space to be allocated for the lower part of the main diagonal of the NxN matrix, where N is the count of vertices.
- ashot madatyan July 05, 2013That's the simple flood fill algo, for which the iterative implementation is given below:
#include <stdio.h>
#include <queue>
#include <vector>
using std::queue;
using std::vector;
typedef vector<int> ivec;
typedef vector<ivec> itab;
struct coord {
int x;
int y;
coord(int cx, int cy) : x(cx), y(cy) {};
};
void print(const itab& tab)
{
for (int j = 0; j < tab.size(); ++j){
int cc = tab[j].size();
for (int i = 0; i < cc; ++i){
printf("%-3d ", tab[j][i]);
}
printf("\n");
}
}
void init_table(int* dat, int cy, int cx, itab& tab)
{
tab.resize(cy);
for (int j = 0; j < cy; ++j){
tab[j].resize(cx);
for (int i = 0; i < cx; ++i){
;//tab
int v = dat[j * cx + i];
//printf("%d ", v);
tab[j][i] = v;
}
}
}
void flood_fill(itab& dat, int py, int px, int color)
{
int rc, cc;
if (dat.size() == 0)
return;
if (dat[0].size() == 0)
return;
rc = dat.size();
cc = dat[0].size();
if (px < 0 || px >= cc)
return;
if (py < 0 || py >= rc)
return;
int val = dat[py][px];
std::queue<coord> q;
q.push(coord(px, py));
while(!q.empty()){
coord c = q.front();
q.pop();
dat[c.y][c.x] = color;
// now add the neighbours of this cell to the queue
// if the neighbour has the same color as this cell
if (c.x - 1 > 0 && dat[c.y][c.x - 1] == val)
q.push(coord(c.x - 1, c.y));
if (c.x + 1 < cc && dat[c.y][c.x + 1] == val)
q.push(coord(c.x + 1, c.y));
if (c.y - 1 > 0 && dat[c.y - 1][c.x] == val)
q.push(coord(c.x, c.y - 1));
if (c.y + 1 < rc && dat[c.y + 1][c.x] == val)
q.push(coord(c.x, c.y + 1));
}
}
int main()
{
int dat[] = {
1, 1, 3, 4,
5, 1, 1, 8,
9, 1, 10, 12,
13, 1, 4, 16,
17, 1, 1, 1
};
itab tab;
init_table(dat, 5, 4, tab);
print(tab);
printf("\n===============\n");
flood_fill(tab, 0, 0, 0);
print(tab);
return 0;
}
Output:
1 1 3 4
5 1 1 8
9 1 10 12
13 1 4 16
17 1 1 1
===============
0 0 3 4
5 0 0 8
9 0 10 12
13 0 4 16
17 0 0 0
@Shiva
Yes, you got it right - merge a[0] and b[0] into d[m], then merge c[0] and d[m] into d[0].
Suppose you have the following inputs:
a[]
b[]
c[]
d[] // destination array of size 3*m
m // the size of each small array
1. Merge the two of the arrays and start placing in the destination array at index "m",
thus leaving space for "m" number of elements at the beginning of the array.
2. Now start merging the third array with the larger array in the destination array
located at position "m"
void merge(int a[], int b[], int c[], int d[], int m)
{
int i = 0, j = 0, didx;
// Merge the first two arrays into the largest starting at index "m"
didx = m; // destination index
while (i < m && j < m){
if (a[i] <= b[j]) {
d[didx] = a[i];
++i;
}
else {
d[didx] = b[j];
++j;
}
++didx;
}
if (i < m) {
while(i < m){
d[didx] = a[i];
++didx;
++i;
}
}
else {
while(j < m){
d[didx] = b[j];
++didx;
++j;
}
}
// Now merge the last array into the destination
// [0] .... [m] ...... [3*m - 1]
i = 0;
j = m;
didx = 0;
while (i < m && j < 3 * m) {
if (c[i] <= d[j])
d[didx++] = c[i++];
else
d[didx++] = d[j++];
}
// If there is a tail in first array, then copy it to the destination
// otherwise the rest of the elements are in their proper positions
while (i < m)
d[didx++] = c[i++];
}
As a first thought, I would create a trie of some special type. The terminal nodes of the trie are the nodes with alpha keys (thus making it at most 3 nodes high - "ABC"), each containing a set of numbers ranging from 000-999.
- ashot madatyan June 30, 2013The approach #2 will require Log(N) size additional storage, where N is the count of the original elements. On the other hand, if we are to find ONLY 1 minimum value, the approach #1 should do it quite ok.
- ashot madatyan June 30, 2013Use max-heap of size K, where the K is the count of min values for which the indices have to be stored/found. A slight modification to the max-heap will need to be required to store not only the values but their indices too. Something similar to the structure below:
struct val_stat {
int idx;
int value;
val_stat () : idx(-1) {} // entry not initialized
};
I would use something similar to the pseudocode below:
template <class T>
class maxheap
{
struct val_stat {
int idx;
int value;
val_stat () : idx(-1) {} // entry not initialized
};
//CTOR
maxheap(int size) : maxsize(size), cursize(0) {}
/** Push to the heap if we have enough space.
If the heap is full, then pop the topmost
value first.
*/
void push(T, int idx)
{
if (cursize == maxsize)
pop();
// code to add the incoming value to the heap
....
}
T pop()
{
T retv = heaptop();
// code to remove the topmost value
// and heapify the rest of the entries
....
return retv;
}
private:
T heaptop()
{
// code to return the topmost element of the heap
...
}
private:
int maxsize;
int cursize;
}
Besides the safe allocation and deallocation of the memory chunks within the custom memory manager, we should take care of returning to the caller a set of chunks that are contiguous in the virtual memory. This is of course if we are not to simulate/implement the virtual memory itself.
- ashot madatyan June 30, 2013@SatishM
If there is a storage constraint and we are not interested in a query structure to be used repeatedly, then as Dumbo suggested, you could use the KMP string matching algo of O(N) time complexity. On the other hand, even the KMP does require a fixed length of additional storage (as anartifact of the failure function) equal to the length of the pattern, i.e. the length of the word to be searched in this context.
I would go with that solution too, so voting it up. The trie DS builds a very efficient query structure that can be used repeatedly.
- ashot madatyan June 29, 2013Use min-heap of size "K" or, as suggested by subahjit, the quick selection(aka selection search) algo. The min-heap has the advantage that it can also produce the list of all values starting from element N-K up the the N-th element, where the N is the size of the array.
- ashot madatyan June 28, 2013I would do it in a simple yet very efficient manner:
for each permutation of the set of strings
find out the longest consecutive sequence of the char
Below is the complete working code for the above algorithm:
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
using std::string;
using std::vector;
typedef vector<string> svec;
bool longest_sequence(const string& data, int& count, char& letter)
{
count = 0;
letter = 0;
if (data.length() == 0) {
printf("Data length: 0\n");
return false;
}
int slprev = -1;
char chprev;
int slcurr = -1;
char chrcurr;
for (int i = 1; i < data.length(); ++i){
if (-1 == slcurr) {
slcurr = 1;
chrcurr = data[i];
}
else {
if (data[i] == chrcurr) {
++slcurr;
}
else { // point where the current char differs from the last one
// if the previous is not initialized, then do it now
if (-1 == slprev) {
slprev = slcurr;
chprev = chrcurr;
}
else {
// we got the previous stored already, so compare the
// length and replace the previous with the current
// if the count of the current > previous
if (slprev < slcurr) {
slprev = slcurr;
chprev = chrcurr;
}
}
// Initialize the new current values
chrcurr = data[i];
slcurr = 1;
}
}
}
// Do the final processing of the current and the previous values
if (slcurr > slprev) {
count = slcurr;
letter = chrcurr;
}
else {
count = slprev;
letter = chprev;
}
return true;
}
string join_data(const svec& data)
{
string ret = "";
for(svec::const_iterator it = data.begin(); it != data.end(); ++it){
ret += *it;
}
return ret;
}
void print_longest_perm_string_seq(svec& items)
{
if (items.size() == 0) {
printf("Empty list of strings\n");
return;
}
int lchrs = 0;
char chr;
string strret = "";
string str = join_data(items);
printf("PERM:\t%s\n", str.data());
longest_sequence(str, lchrs, chr);
strret = str;
while(std::next_permutation(&items[0], &items[0] + items.size())){
int lc;
char chrc;
str = join_data(items);
printf("PERM:\t%s\n", str.data());
if (longest_sequence(str, lc, chrc)) {
if (lc > lchrs) {
lchrs = lc;
chr = chrc;
strret = str;
}
}
}
if (lchrs > 0)
printf("STRING: %s LONGEST CHAR SEQUENCE: %c %d\n", strret.data(), chr, lchrs);
}
int main(int argc, char* argv[])
{
svec items;
items.push_back("aac");
items.push_back("ab");
items.push_back("ba");
print_longest_perm_string_seq(items);
return 0;
}
- ashot madatyan June 28, 2013Here's the code to demonstrate the recursive method to find the LCS of two strings.
#include <stdio.h>
#include <string>
using std::string;
#define min(a, b) (a < b)
#define max(a, b) (a > b)
string LCS(const string& X, const string& Y)
{
int lx, ly;
string res;
string sx;
string sy;
lx = X.length();
ly = Y.length();
if (lx == 0 || ly == 0)
return "";
if (X[lx - 1] == Y[ly - 1]) {
sx = X.substr(0, lx - 1);
sy = Y.substr(0, ly - 1);
res = LCS(sx, sy) + X[lx - 1];
return res;
}
sx = LCS(X.substr(0, lx - 1), Y);
sy = LCS(Y.substr(0, ly - 1), X);
lx = sx.length();
ly = sy.length();
res = (lx > ly) ? sx : sy;
return res;
}
int main(int argc, char* argv[])
{
string X = "ZTANBMBLAUCY "; //"CATCG";
string Y = "GABVCBKLAMNC"; //"GTACCGTC";
printf("LX: %d LY: %d\n", X.length(), Y.length());
string res = LCS(X, Y);
printf("LCS: <%s> <%s> is: %s\n", X.data(), Y.data(), res.data());
return 0;
}
And the answer is:
LX: 13 LY: 12
LCS: <ZTANBMBLAUCY > <GABVCBKLAMNC> is: ABBLAC
Yes, that's correct, the answer is: "ABBLAC"
- ashot madatyan June 26, 2013Approach 1: It is not going to produce the correct answer, because as soon as you "merge and sort the two lists", you won't be able to figure out which element was contained in which list, while the task is to find the greatest COMMON integer. See the example below:
Arr 1: 1 2 3 4 5
Arr 2: 2 3 4 6 6
The dups in the above sorted and merged list will be: {2,2}, {3,3}, {4,4}, {6,6}.
As you can see, the values 2, 3 and 4 are actually contained in both lists, while the "6", though being the element with the greatest value, is contained only in the second list.
@JeffD && @Mem: Thanks for noting that, you are absolutely correct. The "bfound" was introduced to track that case too, but somehow I just got it used incorrectly - a clear indication that one should get asleep at nights and not work :) Anyway, I have corrected the pseudo code.
- ashot madatyan June 26, 2013Given lists: L1 and L2, bool bfound = false, int Val = L2[0]
1. Iterate over L1 and add its items to a hash table (hash set)
2. Now, start iterating over second list L2
if the L2[i] is present in the hash table {
if (false == bfound) {
Val = L2[i];
bfound = true;
}
else { // we already got a value stored in the "Val"
if (L2[i] > Val)
Val = L2[i];
}
}
else // // not found in the hash set
continue iterating;
if bfound
print the value
If we are talking about a binary tree shape similarity, then the below code does it (descriptions inlined):
bool issame(node* root, node* root1)
{
// special case when the two nodes are NULL at the same time
if (root == root1)
return true;
// if we have differing shapes at this level
if ((NULL == root && NULL != root1)
|| (NULL == root1 && NULL != root) )
return false;
// recurse into subtrees
return (root->data == root1->data && issame(root->left, root1->left) && issame(root->right, root1->right));
}
#include <stdio.h>
#include <string>
void dectobin(const unsigned int& num)
{
unsigned int n = num;
std::string strout;
while (0 != n) {
if ((1 & n) == 1) {
strout.insert(0, "1");
printf("1\n");
}
else {
strout.insert(0, "0");
printf("0\n");
}
n = n >> 1;
}
printf("Decimal: %u Binary: %s\n", num, strout.data());
}
int main(int argc, char* argv[])
{
int num = 120;
dectobin((unsigned int)num);
return 0;
}
This is the "Majority vote" algorithm.
- ashot madatyan June 20, 2013
Split the total number (240) of bottles into groups of 16 each. This will yield
15 groups total (15*16). Number each group of bottles from 0-14, number the slaves from
0-3. On each group of 16 bottles write its corresponding binary number
Now make the slaves have wine from each group of 16 bottles if that group number
- ashot madatyan June 18, 2018contains binary bits in the same positions as the slave's number (0-3). E.g. if
the salve number is 3 (B0011), he shall have wine from groups numbered 3, 7 and 11.
After 24 hours, we shall get the exact number of the group of bottles that contained
poison. Now we have 4 slaves left. Use them to find out the exact bottles among
the 16 bottles. I hope the idea is clear.