code_monkey
BAN USER- 1of 1 vote
AnswersWord Wrap / String Justification algorithm.
- code_monkey in United States
Given a set of words and a length.
You are required to print the words such that the words on each line end almost on the same column and the number of trailing spaces at the end is minimized.
Given aaa bb cc ddddd and length is 5 print the following output.
aaa
bb cc
ddddd| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm
------------------------------
Storing binaries <<< done
Listing build files... done
Checking for application data... done
Running:
------------------------------
***********************************
012
345
************* START ***************
013
014
015
023
024
025
034
035
045
123
124
125
134
135
145
234
235
245
345
#include<stdio.h>
#include<stdlib.h>
int *last_combo;
int* next_combo(int *src, int* combo, int maxsize, int combosize)
/*
* 0 1 2 3 4 5
* 0 1 2
*/
{
if (combosize == 1)
{
if (combo[0] == maxsize-1)
return NULL;
else {
combo[0]++;
return combo;
}
}
if(combo[combosize-1] < maxsize-1)
{
combo[combosize-1] = combo[combosize-1] + 1;
} else if (memcmp(combo,last_combo,combosize)){
combo = next_combo(src,combo,maxsize-1,combosize-1);
combo[combosize-1] = combo[combosize-2] + 1;
}
return combo;
}
int main()
{
int *a;
int *combo;
int size = 3;
int src_size=6;
int i,j;
combo = (int*)malloc(sizeof(int)*size);
last_combo = (int*)malloc(sizeof(int)*size);
a = (int*)malloc(sizeof(int)*src_size);
memset(a,0,src_size);
memset(combo,0,size);
memset(last_combo,0,size);
for(i=0; i<src_size;i++)
{
a[i] = i;
}
for(i=0; i<size;i++)
{
combo[i] = a[i];
}
for(i=src_size-1,j=size-1; j>=0;i--,j--)
{
last_combo[j] = a[i];
}
printf("\n***********************************\n");
for(i=0; i<size;i++)
{
printf("%d",combo[i]);
}
for(i=0; i<size;i++)
{
printf("%d",last_combo[i]);
}
printf("\n************* START ***************\n");
printf("\n");
while (memcmp(combo,last_combo,size))
{
combo = next_combo(a, combo, src_size, size);
printf("\n");
for(i=0; i<size;i++)
{
printf("%d",combo[i]);
}
}
return 0;
}
As some one suggested, the answer for this problem is to use a suffix trie!
<i'm assuming that the strings given doesnt contain spaces (albeit it doesnt really matter, let me downcomplicate this problem)>
So basically, collect all the suffixes of string 1, and put them in a trie.
Trie *TR;
Add all suffixes of the first string into the trie
mainfunction()
{
for(i=0; i<strlen(s1) i++)
{
// adding every suffix into the trie, we dont care what is return is.
insertIntoTrie(&TR, getstring(s1, i, strlen(s1)-1));
}
// do the same for second string
For every suffix of the second string, check if that suffix is present in the trie until the required length
for(i=0; i<strlen(s2) i++)
{
if (CheckTrie(TR, getstring(s2, i, strlen(s2)-1), N))
{
// adding every suffix into the trie, while doing this keep checking
// if the current substring is present in the trie
return true;
}
}
return False;
}
bool CheckTrie(Trie * TR, char *suffix, int RequiredLength)
{
// Contains() simply walks through the branches of the tree for Required length depth
// and checks if there is a match until the required length
if (strlen(suffix) >= RequiredLength &&
Contains(TR, suffix, RequiredLength))
{
return true;
}
}
insertIntoTrie(Trie **TR, char* suffix)
{
if(TR == null)
{
newnode = makenode[suffix[0]];
if (suffix[0] == '\0')
{
newNode->endOfWord = 1;
} else {
insertIntoTrie(&newNode->child[word[0] - 'a'], suffix+1);
}
*TR = newNode;
} else {
insertIntoTrie(&TR->child[word[0] - 'a'], suffix+1);
}
}
// something along these lines!, I have not executed this code so there can be a lot of syntactical errors!, but I've written the code to explain the approach.
- code_monkey April 12, 2014Ahha!
This is a good question.
And what you asked above is just a cherry of an entire dessert.
for what you asked, is simple enough to split the strings using strtok or tokenizer and add stuff into a hashmap.
Now these are the follow up questions I thought of asking you
What if I need only what the K largest statuses are?
How would you implement them if there are some millions of machines?
How would you implement the same if there are millions of processors on a single machine(virtual machines with same address space)
:)
this question is way more interesting that you think, and is hugely open ended, and I can go very deep asking this to a person :)
@VladP :
Corrected. Thanks :)
I think it is a linear solution!!
- code_monkey November 21, 2012enum {
FALSE,
TRUE
};
/*
* Pass 12345 as array, index = 2, size = 2
* result of this function would be 34.
* Pass 12345 as array, index = 2, size = 3
* result of this function would be 345.
* Pass 12345 as array, index = 1, size = 3
* result of this function would be 234.
*/
int make (int *A, int index, int n)
{
// n is the size
int iterator = index + size - 1;
int sum = 0;
while (iterator >= index)
{
sum = sum * 10 + A[iterator];
iterator--;
}
return sum;
}
int is_Aggregated(int *Array, int size)
{
int factor = 1;
// used to move the indexes through the locations.
int i = 0, j, k;
while (i < n)
{
j = i + factor;
k = j + factor;
if (k >= n )
{
break;
}
if(make(A,i,factor) + make(A,j,factor) !=
make (A,k,factor))
{
i = 0;
factor++;
} else {
if ( k + factor == n){
/*
* The last position is matched, therefore
* the array is a aggregate;
*/
return TRUE;
}
i = i + factor;
}
}
return FALSE;
}
example 1
pass a: 0 1 1 2 3 5 8
i j k
pass b: 0 1 1 2 3 5 8
i j k
pass c: 0 1 1 2 3 5 8
i j k
pass d: 0 1 1 2 3 5 8
i j k
pass e: 0 1 1 2 3 5 8
i j k ==> true
Example 2
pass a: 1 2 3 4 4 6 8 0
i j k
pass b: 1 2 3 4 4 6 8 0
i j k ==> i = 0, factor = 2
pass c: 1 2 3 4 4 6 8 0
i j k
pass d: 1 2 3 4 4 6 8 0
i j k ==> true
Example 3
pass a: 1 2 3 4 5 6 5 7 9
i j k
pass b: 1 2 3 4 5 6 5 7 9
i j k ==> i = 0, factor = 2
pass c: 1 2 3 4 5 6 5 7 9
i j k ==> i = 0, factor = 3
pass d: 1 2 3 4 5 6 5 7 9
i j k ==> true
---
A mistake is a crash course in learning.
Please comment on its correctness.
---
Good one!
- code_monkey November 08, 2012Why do you need count and changed?
- code_monkey November 08, 2012Hey Noobie,
Where do I read more on playing with data present externally like in discs. like I wanna know more about the logistics of disc seek time, and time taken to transfer from disc to main memory and stuff
Please help.
Hadoop?
- code_monkey October 21, 2012Oops! Dint pay much attention to them :)
Nevertheless corrected.
Thnx.
int add (int a, int b)
{
int carry, sum;
if (b == 0)
{
return a;
}
sum = a ^ b; // xor takes sum
carry = a & b; // collect carry;
carry = carry << 1;
return ( add (sum, carry) );
}
Like the way I learnt adding numbers when I'm a kid. Additionally, no math operator is used
- code_monkey October 17, 2012int ancestors(tree *root, tree *node)
{
// how do I call a root an ancestor of the child,
// it can either be a direct parent or a children
// of its children.
if( !root || !node)
{
return 0;
}
if (root->left == node ||
root->right == node ||
ancestors(root->right) ||
ancestors(root->left))
// if I'm the direct ancestor of that node
// or if any of my children is the ancestor
// I print myself.
{
printf("\n %d", root->data);
return 1;
}
return 0;
}
@loler!!
#Respect!!
A rustic approach:
1. imagine x is the array with more elements and y with less elements [x > y]
so we have to add zeros to y.
Step 1: Add zeroes to y such that sizeof(x) = sizeof(y).
Step 2: sort x in ascending order, xlogx;
Step 3: sort y in descending order. xlogx (since at this point sizes of x,y will be the same).
step 4: go multiply everything and return the value. (x) complexity.
examples:
x=> 1,5,8,4,0,-1,9,2
y=> -2, -1, 5, -3,2.
after step2, y=>-2,-1,5,-3,2,0,0,0.
x sorted in ascending; -1,0,1,2,4, 5, 8 ,9
y sorted in descending: 5,2,0,0,0,-1,-2,-3
Product of them and find.
I agree this is very rustic than a good DP solution, but this has a complexity xlogx+x.
Comments are appreciated.
--
A mistake is a crash course in learning.
--
int remove_dup(int *array, int len)
{
int i,j=0;
for ( i = 1; i < len; i++ )
{
if ( array[i] != array[j] )
{
array[j] = array[i];
j++;
}
}
}
Corrections are appreciated :)
--
“A mistake is a crash-course in learning.”
--
I see this as a double linked list.
Every interval can be stored as a node in a double linked list.
When a node gets deleted , inaddition to modifying the pointers, modify the values too.
typedef struct node_t {
struct node_t prev;
int prev_data;
struct node_t next;
int next_data;
}node;
12 <==> 24 <==> 45.
[illustration only, not this problem]
lets imagine we need to insert 23,
we need to insert a node called 23
with node->next_data = 3;
and node->prev_data = 2;
traverse the node and find a node with next_data = 2.
let it be p;
newnode->next_data = 3;
newnode->prev_data = 2;
newnode->next = p->next;
newnode->prev = p;
p->next = newnode;
p->next_data = newnode->prev_data; //3;
newnode->prev_data = newnode->next_data;
newnode->next_data = newnode->next->prev_data; // newnode becomes 34
so totally the nodes will now become
12 <==> 23 <===>34 <==> 45.
now to delete 23, which is our node, we refer it by 'del'
let del point to 23.
12 <==> 23 <===>34 <==> 45.
//del->prev_data = 2;
//del->next_data = 3;
//del->prev = 12;
//del->next = 34;
void delete (node *del)
{
node *after;
node *before;
before = del->prev;
after = del->next; //34
after->prev_data = del->prev_data; // 34 becomes 24;
before->next = after;
after->prev = before;
free(del);
}
12 <=====> 24 <========> 45
Corrections are appreciated :)
--
“A mistake is a crash-course in learning.”
--
C implementation
int* add(int *src, int len, int data)
{
int *res;
int carry = data;
int i;
for (i = len-1; i > = 0; i-- )
{
if ( carry == 0 )
{
break;
}
src[i] = ( src[i] + carry ) % 10;
carry = ( src[i] + carry ) / 10;
}
if ( carry == 0 )
{
return src;
} else {
res = (int *)malloc(sizeof(int) * (len + 1));
res[0] = carry;
memcpy(res[1],src,len);
free(src);
return res;
}
}
Corrections are appreciated :)
--
“A mistake is a crash-course in learning.”
--
what is a uni - value subtree?
is that a leaf node?
bool present_in_dict(char* source)
{
// have a trie.
// walk it and return true or
// false if the string is present in the trie
}
int make (char *source, char s)
{
// insert a char s into source such
// that the resulting string is in the output.
// GrEeDy :)
int i;
char ch;
for (i = 0; i < strlen(source); i++)
{
ch = source[i];
source[i] = s;
if (present_in_dict(source))
{
printf("%s",source);
return 1;
}
source[i] = ch;
}
retirn 0;
}
int Table[26];
void process (char *s)
{
for (i = 0; i < 26; i++)
{
Table[s[i]-'a']++;
}
}
void insert (char *s, char *d)
{
int i;
for (i = 0; i < 26; i++)
{
Table[i] = 0;
}
process(d);
for (i = 0; i < 26; i++)
{
if (Table[i] > 0 )
{
// if the charecter is yet to be taken
if( make (s, i + 'a') > 0 )
// 0 + a = a, 1 + a = b..
{
// this charecter got in.
Table[i]--;
// so again start from the beginning
// to see if you can insert any
// charecters.
i = 0;
}
}
}
// when all charecters are inserted this returns
}
Corrections are highly appreciated. :)
--
“A mistake is a crash-course in learning.”
--
A trie
- code_monkey September 28, 2012int* add( int *src, int len, int data)
{
int *res;
int i;
for ( i = len - 1; i > = 0; i-- )
{
if ( data == 0)
{
break;
}
data = (src[i] + data) / 10;
src[i] = (src[i] + data) % 10;
}
if ( data == 0 )
return src;
else
{
res = (int*)malloc(sizeof(int)*(len+1));
memset(res, 0, len+1);
res[0] = data;
memcpy(res[1], src, len);
free(src);
return res;
}
}
Corrections are appreciated :)
- code_monkey September 28, 2012I think I can propose something and for N > 3, it can be generalized.
// y = mx+c notation
Struct line_t
{
int x;
int y;
int slope;
};
We have to create 3 lines which pass through each of the three given positions and are perpendicular to the other two.
like, Line 1: passes through A, and is perpendicular to BC.
Line 2: passes through B, and is perpendicular to AC.
and line 3 similarly.
these lines can be got by just finding the line y = mx+c, where m is the perpendicular slope of the other two lines. ( if m1 is the slope of BC, then the line through A should have slope -1/(m1).)
After your get two lines find thier intersection.
Now we gotta retrieve these two lines in our structs.
have a function similar to this.
void (int &x, int &y, struct line *line1, struct line *line2)
{
// just do the mathematical equivalent of finding the intersection of two lines..
multiply(line1, line2->y);
multiply(line2, line1->y);
// Im equating the mx + c with each of the y cordinate.
// now two lines will have equal y cordinate.
// *x = solve (line1, line2); // simply equate mx+c term and retrieve x;
// now use *x, line to get y.
// x , y is the required solution
}
Now every N greater than 3, break it down into triangles, find the point and again find the nearest of the respective points which are obtained. (corner case: if you get two points, find its midpoint and return it) eg: 6 people, 2 triangles, 2 points ==> mid point of these gives the reqd solution.
this is just on top of my mind, and would appreciate if someone has any thoughts to improve this.
I feel a Trie serves Better than a Suffix Tree.
We wont need to store the prefixes at all, only the number in its entirety should be stored.
Taking advantage of the common prefix, I think a trie is a better go.
int rangesum(tree *root, int max, int min)
{
if(!root)
return 0;
if (max < min)
return 0;
if(min == root->data && max == root->data)
return root->data;
if(min<=root->data && root->data <=max)
return (root->data + rangesum(root->left) + rangesum(root->right));
if(min < root->data && max < root->data)
return (rangesum(root->left));
if(min>root->data && max>root->data)
return (rangesum(root->right));
return 0;
}
Repsusanaminick, Research Scientist at CapitalIQ
I am Susan from Dallas, I am working as a Property manager in Kohl's Food Stores company. I love ...
Repannavhedge4, AT&T Customer service email at ABC TECH SUPPORT
Hi everyone, I am from Worcester,USA. I currently work in the Argus Tapes & Records as Scientific illustrator . I love ...
logncomplexity.wordpress.com/2013/01/10/48/
- code_monkey April 20, 2014