developer.2020
BAN USERThe algorithm is working perfectly for "34900543205000" but Prabhakar is right. Please add :
if (flag==2)
base-=flag;
after while body
- developer.2020 September 04, 2012is it possible to revisit a visited location again? (loop)
- developer.2020 August 29, 2012this is one approach, but I am looking for something better. the complexity for this algorithm is O(m+n) in best case and O(nm) worst case
simply try to trace the string, as soon as found the first match character start comparing with pattern. If matched report the start character position, otherwise continue from next character of first start matched in last step.
int findStr(char *str, char *pattern)
{
int i=0, j=0, ptr=0;
for(; i<strlen(str)-strlen(pattern);)
{
while(*(pattern+j)==*(str+i))
{
i++;
j++;
}
if(*(pattern+j)=='\0')
return ptr;
j=0;
i=++ptr;
}
return -1;
}
it does not work! because it is possible a word has repeated in all buckets in for example rank 11, and you do not report it as a frequent word! but in total might be the most frequent word.
Notice in each bucket different word sets might be dominant in terms of frequency.
of course I can store it. Because I do not store the terabyte string! I just need one place for each word in this long string.
The number of words in a long text are not unlimited!
The space needed for this algorithm is O(n) which n is the total number of words that is used in the text. notice if a word is used 100,000 times in the text we need just one place in the memory to keeping track of that word
Create a hash table, the key is word, and value is a counter. Trace all words, if is not existed in hash, add it with value 1, otherwise, increment the value.
In the same time using a list of pair key value, can hold the most ten frequent repeated words, and if a word after increment has a value of more than the minimum in this list, replace with that and remove the minimum in list.
Notice the total English words! The Second Edition of the 20-volume Oxford English Dictionary contains full entries for 171,476 words in current use, and 47,156 obsolete words. To this may be added around 9,500 derivative words included as subentries.
anyways, this is a simple code to handle this case:
Dictionary<string, int> lookup = new Dictionary<string, int>();
string word = getNextWord();
int maxFrequent = 0;
Dictionary<string, int> topTen = new Dictionary<string,int>();
while (!String.IsNullOrEmpty(word))
{
if (lookup.ContainsKey(word))
lookup[word]++;
else
lookup.Add(word, 1);
if (lookup[word] > maxFrequent)
{
if (topTen.ContainsKey(word))
topTen[word] = lookup[word];
else
{
topTen.Add(word, lookup[word]);
if (topTen.Count() > 10)
{
string lessFrequent = findMinTopTen();
topTen.Remove(lessFrequent);
}
}
maxFrequent = findMinTopTen();
}
word = getNextWord();
}
At the end, topTen contains the most ten frequent words items.
findMinTopTen() return the word with less frequent repeat in a list of 10 items. This algorithm is linear and run in O(N) which N is total words in the text and needs O(m) space which m is the number of items in the word set used in the text
This solution is O(n). The logic is start tracing two string consequently until the end.
bool interleaveTest(char *a, char *b, char *c)
{
int seta=0, setb=0;
while(*c!='\0')
{
if(*c!=*a && *c!=*b) {
if(*c==*(a-seta)) {
a-=seta;
seta=setb=0;
}
else if(*c==*(b-setb)) {
b-=setb;
seta=setb=0;
}
else
return false;
}
if(*c==*a) {
seta++;
a++;
}
else {
a-=seta;
setb=seta=0;
}
if(*c==*b) {
setb++;
b++;
}
else {
b-=setb;
seta=setb=0;
}
c++;
}
return true;
}
int A[]={10, 5, 2, 3 , 7, 8};
int X=15;
int findSum(int idx, int sum, int totalMatches)
{
int n=sizeof(A)/sizeof(int);
if(idx==n)
return totalMatches;
if(sum+A[idx]>X)
return findSum(idx+1, sum, totalMatches);
else if(sum+A[idx]==X)
return totalMatches+1;
else
{
int tot=0;
for(int j=idx+1; j<n; j++)
tot+=findSum(j, sum+A[idx], 0);
return totalMatches+tot;
}
}
and for computing the total subsets call the above function as :
int tot = 0;
for(int i=0; i<sizeof(A)/sizeof(int); i++)
tot+=findSum(i, 0, 0);
The solution has the complexity of O(nm) while n is the digit number of the first number and m is the second one.
#define toAscii(A,len) for(int i=0; i<len; A[i++]+='0');
#define fromAscii(A,len) for(int i=0; i<len; A[i++]-='0');
char * multiply(char *A, char*B)
{
int n= strlen(A);
int m = strlen(B);
char * res = (char*) malloc (sizeof(char)*n+m+1);
memset(res, 0, sizeof(char)*n+m+1);
fromAscii(A,n);
fromAscii(B,m);
for(int i=n-1; i>=0; i--)
for(int j=m-1; j>=0; j--)
{
res[i+j+1]+=(A[i] * B[j]);
res[i+j]+=res[i+j+1]/10;
res[i+j+1] = res[i+j+1]%10;
}
toAscii(res, n+m+1);
res[n+m]='\0';
return res;
}
This is a C function that the parameter is called by reference. The logic is so simple, start copying the characters from pointer to the base pointer. When two 0 have seen by prt and then a none 0 appear decrement base pointer by 2. At the end close the string.
because this is a call by reference function the string in caller method will change. Easily you cn convert to a call by value function and return the result as a return value.
void remove2zeros(char *str)
{
int flag = 0;
char *p,*base;
p=base=str;
while(*p!='\0')
{
if(*p=='0')
flag++;
else {
if(flag==2)
base-=2;
flag=0;
}
*base=*p;
base++;
p++;
}
*base='\0';
return;
}
There is a way to do the job in place.
Start from root,
1- go to the right node, lets say setPoint node,
2- if there is any node in left, move this node to the most right node of setPoint
3- if there is NULL in setPoint->left, point to the setPoint's parent (we are going to make a double link list)
4- continue from step 1 with Setpoint->right until the end of chain
now with the same logic apply the algorithm with root->left
at the end we have a double linked list
here is the code in C
of course the complexity of this method is o(n^2) while for each node is needed to trace all left or right nodes.
Any suggestion? better idea?
/* Flatten BST*/
node * flattenBST(node* head)
{
node *h=head;
while(h->right!=NULL)
{
if(h->right->left!=NULL)
{
node *mostRight, *setPoint;
setPoint=mostRight=h->right;
while(mostRight->right!=NULL)
mostRight=mostRight->right;
mostRight->right=setPoint->left;
setPoint->left=h;
}
else
h->right->left=h;
h=h->right;
}
h=head;
while(h->left!=NULL)
{
if(h->left->right!=NULL)
{
node *mostLeft, *setPoint;
setPoint=mostLeft=h->left;
while(mostLeft->left!=NULL)
mostLeft=mostLeft->left;
mostLeft->left=setPoint->right;
setPoint->right=h;
}
else
h->left->right=h;
h=h->left;
}
return h;
}
when you are using recursion in fact you are using stack and based on the requirement you are not allowed to use stack! the question asked to do the job in place!
- developer.2020 August 26, 2012no extra memory ! using Queue is not allowed
- developer.2020 August 26, 2012stop posting your homeworks here
- developer.2020 August 26, 2012Still is possible to delete item with O(1) in middle of Queue!!!
Honestly, you do not need to delete item from queue when you perform Delete operation. It is enough to delete from hash table which is O(1)
For Enqueue perform the following steps:
1. look if the Enqueue item is existed in hash table
2. if Yes, Enqueue and delete item from hash
3. if Not, remove item from queue ( O(1) ) and go to step 1
in this case delete item is O(1) and all other operation are in O(1) too
In class con there is just one data definition. As long as there is no data value, and there is just a data type, so no memory space is needed. Data type is just a definition for a data value in compile time and no keeping space in run time.
Therefore, class con has kept no space.
In class con there is just one data definition. As long as there is no data value, and there is just a data type, so no memory space is needed. Data type is just a definition for a data value in compile type and no keeping space in run time.
Therefore, class con has kept no space.
The assumption is that the input is a valid Json string.
In this case, simply we can convert all ',' to break line and all '{' or '}' to <br>{<br> or <br>}<br>
all other characters remain unchanged.
Here is a simple function in C/C++
#define Indent(x) for(int i=0;i<x;i++)printf("\t");
void intentJson(char * json)
{
int indent = 0;
char ch = *json;
while(ch!='\0')
{
switch(ch)
{
case ',':
printf("\n");
Indent(indent);
break;
case '{':
printf("\n");
Indent(indent);
printf("%c\n",ch);
Indent(indent++);
break;
case '}':
printf("\n");
Indent(--indent);
printf("%c\n",ch);
Indent(indent);
break;
default:
printf("%c",ch);
}
ch=*(++json);
}
return;
}
what if some word removed from the text? the provided solutions can't handle this situation
- developer.2020 August 24, 2012the complexity for this solution is O(N) because each node will be visited at most twice! the best case is (n) and the worst case is (2n-1) which is O(n)
- developer.2020 August 23, 2012what about space complexity? they prefer O(1) I guess
- developer.2020 August 23, 2012start from head, if child is existed make a link to the child, and trace until the end of child's chain and link to the next node of the current pointer. move to the next node until the end.
Node * FlattenNodes(Node *head)
{
Node * p = head;
while (p!=NULL)
{
if(p->child!=NULL)
{
Node *ch=p->child;
while(ch->next!=NULL)
ch=ch->next;
p->child->last=p;
ch->next=p->next;
if(p->next!=NULL)
p->next->last=ch;
p->next=p->child;
p->child=NULL;
}
p=p->next;
}
return head;
}
-swipe the registered finger backward
-what if the finger is greasy
-what if the sensor is greasy
-is it work in all temperatures ? minus zero or +40 C
-how about the swipe speed? how will react in this case and how fast detection can be handled?
-how if the registered finger is scratched? or partially is covered by a band?
-how if the registered finger is wet?
....
The answer is correct now! I had to just stop the pointer when I swap the positive numbers.
Sorry about that, I didn't run the code, just start writing here in time.
1.get two pointer for head and tail,
2.trace the array from the beginning,
3.if the pointer see a negative number swap with head and if is positive swap with tail
4. move to next item until hit the tail
int[] sortArray(int[] T)
{
int i=0, head = 0;
int tail=T.length()-1;
while(i<=tail)
{
if(T[i]<0) {
int tmp=T[head];
T[head++]=T[i];
T[i]=tmp;
}
else if (T[i]>0) {
int tmp = T[tail];
T[tail--]=T[i];
T[i--]=tmp;
}
i++;
}
return T;
}
easily you can call the function like this:
printf("%s", number2alpha(x));
char *number2alpha(long long int x)
{
char *s;
s=(char *)malloc(sizeof(char) * (x/26)+2 );
int i=0;
while(x>0)
{
x--;
int k=x%26;
x/=26;
s[i++]=k+'A';
}
s[i]='\0';
return strrev(s);
}
The method is fine, but the only problem is you print out the alpha string in reverse! because the first iteration computes the lowest digit, and next iteration second, and so on!
you need to reverse the direction of output report.
In this case I suggest Insertion Sort, However, Bubble Sort is a good idea as well. Bubble sort for a list with n=10000 which is almost sorted and has just 50 unsorted items gives a complexity of about O(n) in the best case. I think it is the best algorithm for this problem.
- developer.2020 August 17, 2012This is my code:
int[] findPath(int N)
{
int[] path = new int[N * N];
int x, y, x1, y1, i;
int direction = 1;
i=x = y = 0;
while (x != N - 1 || y != N - 1)
{
path[i++] = x + y * N + 1;
x1 = x += direction;
y1 = y -= direction;
if (x >= N) {
y += 2;
x = N - 1;
}
if (y >= N) {
x += 2;
y = N - 1;
}
if (x < 0) x = 0;
if (y < 0) y = 0;
if (x != x1 || y != y1) direction = -direction;
}
path[i] = N * N;
return path;
}
int [] incrementList(int[] list)
{
int carry = 1;
int flag=1;
for(int i = list.length()-1; i>0; i--)
{
flag*=carry;
list[i]+=carry;
carry=(int) list[i]/10;
list[i]=(int) list[i]%10;
}
if(flag*carry==1)
list[0]=1;
return list;
}
You assumed that list is sorted, but lets extend the question for the case that list is not sorted!
Using partitioning would be a potential answer with O(n) and another solution is using Hash Map, count the items in array using item as a key.
even it can be done without any extra data structure! just do search for both N and M in the same time. As long as we traverse in the same manner is fine. The last common node in search is the 1st common ancestor, so space complexity would be O(1) and time complexity O(log n)
- developer.2020 March 27, 2012I guess it can be solved with log(n) if we are allow to use an array in size at most n or a queue.
Easily find the first number, say N, and keep the track of traverse to N in an array or queue.
Then start finding the next number, and check the saved track for the first one, as soon as we could not see the same number of the saved sequence we stop searching and report the last common item as ancestor
Take a hash map, start from both list A, and B. In each list check if the current node is existed in hash (using address of the node as a key). If a node exists in hash table, so this node is the connection point, otherwise add the node to the hash and go to the next one.
- developer.2020 March 26, 2012I guess I have a good solution to this problem!
income liquid to each cup is sum up the overflow of two cups above. let's say cup(h,k) =o(cup(h-1, k-1)) + o(cup(h-1, k)) , here o(x) means overflow cup x.
so we have :
f(h, k) = 0 for k<0 ,
f(h-1, k-1)+f(h-1,k) for k>=0, k<=h ,
0 for k>h
now we can easily write a recursive relation and resolve the problem based on a recursive program. The run time would be just O(log n)
float max(float a, float b) { return (a<b)?b:a; }
float d(int h, int k)
{
if(k<0 || k>h)
return 0;
if(h<=0)
return N;
else if(h==1)
return max((N-capacity)/2, 0);
float income = max( (d(h-1, k-1)-capacity)/2, 0) +
max((d(h-1, k)-capacity)/2, 0);
return income;
}
suppose we have two global float variables, capacity and N, as capacity of each cup and total liquid
I would appreciate any comment or suggestion.
static uint G2B(uint x, uint r, int n)
{
if (n<0)
return r;
return G2B(x, (uint)(r | (((r ^ (x << 1)) & (1 << n)))>>1), n- 1);
}
static uint Gray2Binary(uint x)
{
int NumBits=32;
return G2B(x, (uint)(x & (1<<NumBits-1), NumBits-1);
}
goal is the number that the sum of subset items should be equal
in this question goal is 10
Assume we have a partition function which is the same as used in quick sort.
int find(A, n, k)
{
int t;
t = partition(A, n);
if (t == k)
return A[k];
else if (t < k)
return find (A + t, n - t, k - t);
else
return find (A, t - 1, k);
}
on average it works on O(n)
- developer.2020 March 04, 2012The time complexity for this solution is O(nlogn) which is not acceptable based on the question.
- developer.2020 March 04, 2012Create a Hash table, and trace all items in first array, increment hash value using array items as key.
Trace the second array, but this time decrements the hash value using items as key.
At the end, if there is any non-zero item in hash table two arrays are not equivalent .
This is a very simple approach based on dynamic programming method :
the function could be launch by calling : findNumbers(list, 0, 0, goal, "");
static void findNumbers(int[] list, int index, int current, int goal, string result)
{
if (list.Length < index || current>goal)
return;
for (int i = index; i < list.Length; i++) {
if (current + list[i] == goal) {
Console.WriteLine(result + " " + list[i].ToString());
}
else if (current + list[i] < goal) {
findNumbers(list, i + 1, current + list[i], goal, result + " " + list[i].ToString());
}
}
}
Agree with pc, not a solution for this problem. Does not work for this input:
- developer.2020 June 09, 2015{ (1,2) (1,2) (3,5) }