Anurag Singh
BAN USERI believe step 4(a) will take (n^2) for each element search and searching is needed for each array element in worst case so it becomes O(n^3). My others two comments I gave already where I said the same.
If a pair of number (a,b) can be found such that a+b = -c for a given c in O(n) time, we are good.
But I don't see how can we find a pair in O(n).
If you don't mind, could you please explain if you have any thought on that (You may want to look at my other two comments 1st on top)
Above may not work in worst case..
e.g. -6, 0 , 1, 2, 4
answer is: -6, 2, 4
To start with -6, we need to find a pair with sum 6
and probably search pair pattern would be:
(0,1), (0,2), (0,4) -- not found
(1,2), (1,4) -- not found
(2,4) -- found
And this search doesn't seem to be O(n). In worst case it will be:
(n-1) + (n-2) + (n-3) + .... + 1 = O(n^2) times
1. Sort the given array (say sorted array is a). O(n log n)
2. Create a n x n matrix (say sum) where sum[i][j] = a[i] + a[j]
This matrix is sum of all possible pairs in given array where sum value is sorted
left to right and top to bottom. O(n^2)
Here diagonal elements can be ignored and also upper and lower triangular are same,
We need only upper or lower, so we may calculate only upper triangular portion of the
matrix.
3. Now for each element c in the array, search for -c in the sum array as below:
a) start from sum[0][0]
b) if current element in sum is equal to -c, you got the answer (a[i] + a[j] + c = 0)
c) if current matrix element is less than -c, go right in the same row
d) if current matrix element is more than -c OR you reached at the end of the row
,go down in the same column
e) If you reached at the last element of matrix (bottom right) and -c not yet found,
-c is not in the matrix
Step 3 will take at most 2n search for any -c (if your search happens to be
right, down, right, down, right, ..........), so total O(n^2)
Overall complexity: O(n log n) + O(n^2) + O(n^2) = O(n^2)
This seems to be O(n^3) algorithm.
For a given c, finding (a,b) pair such that a+b = -c would take n^2.
and in worst case, you need to try all possible c, i.e. and so
n* O(n^2) = O(n^3)
bool symmetric(node)
{
if(root == null)
return true;
else
return symmetric(node->left) && symmetric(node->right);
}
I guess following will work:
Here k should be some given no say, 5 or 10 and this is the difference of the length of two linked lists. So both lists will make a Y shape where one list has K node more than the other one. Here traversing complete list is not allowed so we can't find which list is longer one (If allowed, traverse K node 1st one longer list, then traverse both list together node by node and keep checking if they are same which will be the merged node)
So we need to try this on both list together where we can have two pairs of pointers say P1, P2 and Q1, Q2 (P1, Q1 pointing to one list and P2, Q2 pointing two another).
1. Move P1 and P2 upto K nodes
2. Now move all 4 pointers node by node, keep comparing equality on P1, Q2 and P2, Q1. One pair will point to merged node when they reach node p and that will give the answer.
Yes, True. My above solution will violate the property of BST.
Following should do:
If BSTs are A and B then:
Merge(A,B)
{
If A has only one node, insert into B.
If rootA < rootB then
rightA = A.right
A.right = NULL
Merge(A,B.left)
Merge(rightA,B)
Else
leftA = A.left
A.left = NULL
Merge(A,B.right)
Merge(leftA,B)
}
--- REMOVED ---
- Anurag Singh March 26, 2011Well, if you read the algorithm above given before the code, things should be little easy to understand. Here is the deal (per above code):
1. s is an array of structure (size is length of input string)
2. we store each character in input string in structure one by one. character at index i is stored in s[i].
3. s[i] could be a numeric or non-numeric and it's next pointer has address of same type of character which comes next.
e.g. in input ze5s1d3q
s[0] will have z (i.e. s[0].data) and s[0].next points to e (next non-numerix character)
s[1] will have e and s[1].next points to s
s[2] will have 5 and s[2].next points to 1 (next numerix character)
s[3] will have s and s[3].next points to d
and so on
so at this point, input string is just stored in array so if we print all s[i].data from 0 to len-1, input string will be printed. Also in this array, each character knows the next character of it's own type. So just by following the next pointers, we can print only numeric sequence (513) or non-numeric sequence (zesdq)
Now we are sorting numeric and non-numeric sequences so after sorting, numeric sequence becomes 135 and non-numeric sequence becomes deqsz. while sorting numeric sequence, character movement happens only at numeric locations in structure s (non-numeric locations in structure s are not affected) and vice-versa (for non-numeric). This was possible with help of next pointer of each character in structure s.
So after sorting, character type index is maintained in structure s i.e. 1st two index has non-numeric, then, 3rd is numeric etc.
so after sorting, structure s will have
s[0]=d, s[1]=e, s[2]=1, s[3]=q, s[4]=3 and so on.
and same is printed at the end.
A little optimization in above (It's NEVER required to move elements from s2 to s1. Also move from s1 to s2 is needed only when s2 is EMPTY)
1. Have two stacks, s1 and s2.
2. If Enqueue, push into s1
3. If Dequeue, pop from s2 (if s2 is not empty). If s2 is empty, move all elements from s1 to s2 (pop from s1 and push in s2). Now pop from s2.
Enqueue Cost: O(1)
Dequeue Cost: O(1) -- Amortized
Scan the given string and check each character if it is any of the given punctuation.
Hash can be used to store punctuation characters for faster search.
OR we can consider ascii values of characters and use binary search.
I guess it should be:
(Taking total array size as n)
if(i<n/2)
j=2*i;
else
j=n+1-2*(n-i);
Apart from that above algorithm will require O(n) space where requirement is to solve it without space.
Already lots of discussion went on this at:
careercup.com/question?id=7528760
height(BST) = 1 + min(height(BST->left),height(BST->right));
- Anurag Singh February 11, 2011This is probably the most efficient solution.
- Anurag Singh February 09, 20111. Create a node struct (which has data and pointer to next node)
2. Scan the given string, create a node for each character and store that in a new array. Here next pointer of any node SHOULD point to next node of same type (i.e. a numeric node should point to next numeric node, and non-numeric node should point to non-numeric node)
3. Also have two pointers pointing to the head of numeric and non-numeric linked list.
4. At this point, we have a new array, having two linked list (numeric and non-numeric) inside it and order of nodes are exactly same as input string.
5. Now sort both linked list separately.
6. Print the new array and this is the desired output.
A working C code (used bubble sort here, should be replaced with better sorting code.... tested on cygwin):
#include<stdio.h>
#include<string.h>
struct node
{
char data;
struct node *next;
};
void llist_bubble_sort(struct node *head);
int main()
{
char str[]="ffdf45dfdf23hhnnnabd543";
printf("input string: %s\n",str);
int len=strlen(str);
struct node s[len];
struct node *num_head=NULL, *num_tail=NULL, *str_head=NULL, *str_tail=NULL, *tmp;
int i;
int j=0,k=0;
for(i=0;i<len;i++)
{
if(str[i]-'0' >= 0 && str[i]-'0' <= 9)
{
s[i].data=str[i];
s[i].next=NULL;
if(j==0)
{
num_head=num_tail=&s[i];
j++;
}
else
num_tail=num_tail->next=&s[i];
}
else
{
s[i].data=str[i];
s[i].next=NULL;
if(k==0)
{
str_head=str_tail=&s[i];
k++;
}
else
str_tail=str_tail->next=&s[i];
}
}
llist_bubble_sort(num_head);
llist_bubble_sort(str_head);
i=0;
printf("Sorted String: ");
while(i<len)
{
printf("%c",s[i].data);
i++;
}
printf("\n");
return 0;
}
void llist_bubble_sort(struct node *head)
{
struct node *i,*j;
for(i = head; i != NULL; i=i->next)
{
char c;
for(j = head; j != NULL; j=j->next)
{
if(i->data < j->data)
{
c=i->data;
i->data=j->data;
j->data=c;
}
}
}
}
Merging in oposite way.
Merge A and B from back to front. Get max values from A and B and put in B from back side.
for(i=X-1,j=Y-1;i>=0 && j>=0;)
{
if(A[i] >= B[j])
{
B[i+j+1]=A[i];
i--;
}
else
{
B[i+j+1]=B[j];
j--;
}
if(i>0)
{
for(k=0;k<=i;k++)
B[k]=A[k];
}
}
Both above are good and have same logic. 1st one if list is not editable, 2nd if editing allowed.
- Anurag Singh February 08, 2011Yes. Look like k-d tree is the right answer.
- Anurag Singh February 08, 2011A little addition:
Finding Closest Point for a given (x,y):
1. Look for x JUST smaller then given x, look for y JUST smaller than given y, calculate the distance (say d1)
2. Look for x JUST smaller then given x, look for y JUST greater than given y, calculate the distance (say d2)
3. Look for x JUST greater then given x, look for y JUST smaller than given y, calculate the distance (say d3)
4. Look for x JUST greater then given x, look for y JUST greater than given y, calculate the distance (say d4)
5. Look for same x, look for y JUST greater than given y, calculate the distance (say d5)
6. Look for same x, look for y JUST smaller than given y, calculate the distance (say d6)
7. Look for same y, look for x JUST greater than given x, calculate the distance (say d7)
8. Look for same y, look for x JUST smaller than given x, calculate the distance (say d8)
9. point of MIN(d1,d2,d3,d4,d5,d6,d7,d8) is the closest point.
If no space issue, we can just use index array (say idx), initialize it to ZERO.
then for each element in array (Say a), increment index array. At the end, index with ZERO value is missing (And index with value 2 is repeated).
idx[n]={0};
for(i=0;i<n;i++)
idx[a[i]]++;
for(i=0;i<n;i++)
{
if(idx[i]==0) printf("%d is missing",i);
else if(idx[i]==2) printf("%d is repeated",i);
}
Nested loop (for loop inside outer while) ONLY runs when we find an element already shuffled in the shuffling process. And depending on input size, either this case will not arise OR may arise some some time say 4 OR 5 times but this doesn't depend on n, So I take this as constant. And so I say this soln is O(n).
I found following while testing it for input size upto 40
No for loop execution for input sizes:
2,4,6,12,14,20,30,38
for loop executes one time for input sizes:
8,10,18,24,26
for loop executes two times for input sizes:
28
for loop executes three times for input sizes:
16,34,40
for loop executes four times for input sizes:
22,36
for loop executes five times for input sizes:
32
1. Get count of each word.
2. Create a MIN heap of word counts with 1st 100 elements.
3. Now for all other word counts , if count is smaller (OR equal) than root (of max heap), ignore it, otherwise replace the root with new greater count and heapify.
At the end, elements in heap will be the 100 most frequently occurring words.
1. Calculate distance of all points. O(n)
2. Build a max heap for 1st 10 distances
3. Now for all other distances, if distance is greater (OR equal) than root (of max heap), ignore it, otherwise
replace the root with new smaller distance and heapify.
At the end, elements in heap will be the 10 smallest distances.
Level Order traversal for both trees and keep checking corresponding elements in both.
Stop as soon as they don't match. This looks most efficient and works for n-ary trees.
9 will be ON, I corrected in my previous example.
- Anurag Singh February 07, 2011Right. I should say wrapper classes and String are immutable.
- Anurag Singh February 07, 2011OK, I didn't test my previous code for many inputs and there were some issues.
Corrected the above code I gave and following is working well for input size 2-30 like:
1,10
1,2,10,20
1,2,3,10,20,30
1,2,3,4,10,20,30,40
etc..
I made few small change in the code to track what elements has been shuffled already and should not be shuffled again.
Logic still remains the same [ONLY tricky part is to track which element is shuffled alrerady and which one is yet to shuffle. Looks like this is the best soln. Time: O(n), Space: O(1)
Please verify it and see if it looks good.
If not, pls post the error/issues you see with following:
public class Shuffle {
public static void main(String args[]){
int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,10,20,30,40,50,60,70,80,90,100,110,120,130};
for(int i=1;i<a.length-1;i++)
a[i]=-1*a[i];
ShuffleArray(a);
for(int i=0;i<a.length;i++)
System.out.print(a[i]+ " ");
}
public static void ShuffleArray(int[] a){
int n = a.length;
int cnt=1;
int i=1;
int hold;
int curr,c;
curr=a[i];
while(cnt<n-1 && i<n)
{
if(i<n/2)
hold=2*i;
else
hold=n+1-2*(n-i);
if(a[hold] < 0)
{
c=a[hold];
a[hold]=-1*curr;
i=hold;
curr=c;
cnt++;
}
else
curr=a[hold];
if(cnt<n && curr > 0)
{
for(i=2;i<n && a[i]>0;i++);
curr=a[i];
}
}
}
}
annoy soln will work in O(n2), will be too slow on large arrays. I guess the soln given in above 2 posts (working java code for array of positive numbers in my 2nd post) by me is O(n) and much much faster. Comment on that pls..
Also I'm not getting the idea in Adiser soln. Can anyone pls explain it on array:
a0,a1,a2,a3,a4,a5,a6,a7,b0,b1,b2,b3,b4,b5,b6,b7
Here expected output is:
a0,b0,a1,b1,a2,b2,a3,b3,a4,b4,a5,b5,a6,b6,a7,b7
This XOR will work if and only if ONE number appears in array ODD no of times, and all other appear EVEN no of times. And this is what said in the question. So this XOR soln assumes that ONLY one number appears ODD times.
- Anurag Singh February 07, 2011Here shuffling is happening as per two rules (On current index):
If current_index is < array_size/2
move current_index to 2*current_index
else
move current_index to (array_size+1)-2*(array_size-current_index)
Here 1st element(a[0]) and last element(a[n-1]) will not move at all.
From index 1st, move current element as per above rule, wherever this element goes, that will be the next element to be moved (per above rules).
Keep doing this until ALL elements are moved.
Now here the tricky part is to tracked moved element (OR yet to move element). While moving elements, we may come to an element (as current element) which has been moved already. So we have to check if there is any more element yet to move, if so, start from there OR stop shuffling.
In following, I just negated all numbers 1st (Assuming array elements are positive). For other possible inputs, I mentioned some ways in my very 1st post.
This is IN PLACE and O(n). [It may look like O(n2) but I guess it's not (I may be wrong) because we have to RELOOK(when current_element is positive, that means moved already) into array for negative element for few times only, not n times, so its not nxn but constant X n.)
If we are allowed to use extra space, we may do the tracking by using hash (OR something else) easily. Put all in hash 1st, then keep removing moved elements from hash.
public class Shuffle {
public static void main(String args[]){
int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,10,20,30,40,50,60,70,80,90,100,110,120,130};
for(int i=1;i<a.length-1;i++)
a[i]=-1*a[i];
ShuffleArray(a);
for(int i=0;i<a.length;i++)
System.out.print(a[i]+ " ");
}
public static void ShuffleArray(int[] a){
int n = a.length;
int cnt=1;
int i=1;
int hold;
int curr,c;
curr=a[i];
while(cnt<=n && i<n)
{
if(i<n/2)
hold=2*i;
else
hold=n+1-2*(n-i);
c=a[hold];
a[hold]=-1*curr;
i=hold;
curr=c;
cnt++;
if(cnt<n && curr > 0)
{
for(i=2;i<n && a[i]>0;i++);
curr=a[i];
}
}
}
}
I believe that we want to run only one instance of a GIVEN exe. Say if is is abc.exe then if abc.exe is running, we can't run one more abc.exe in parallel, but we can run other exe like def.exe, dff.exe etc.
If this is the question then, we can use following check before executing the exe.
<< UNIX Script>>
if[ $(ps -ef | grep abc.exe | grep -v grep | wc -l) -eq 0 ]; then
execute abc.exe
fi
Input:
a1,a2,a3,a4,.....an,b1,b2,b3,b4,.....,bn
Output:
a1,b1,a2,b2,a3,b3,a4,b4,..........an,bn.
If we notice, there is a pattern for all elements while shuffling.
For all elements from 1st half portion (a1 to aN)
a[i] is moved to a[2*i] where 0<= i <= n [say array name is a]
i.e.
a[0] is moved to a[0] (for i=0, i = 2*i =0)
a[1] is moved to a[2]
a[2] is moved to a[4]
a[3] is moved to a[6]
......
....
For 2nd half, same is true from opposite (OR if we see array
inverted,b1 to bN behaves same as a's)
In other words, keeping array as is, 2nd half of the array (b1 to bN)
goes like this
a[i] is moved to a[(n+1)-2*(n-i)] where n/2 < i < 2n
i.e. (Assuming 2nd half array starting with index i=7, so total array
size 12)
a[7] moved to a[1]
a[8] moved to a[3]
a[9] moved to a[5]
overall as example:
Input
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11]
Output:
a[0], a[6], a[1], a[7], a[2], a[8], a[3], a[9], a[4], a[10], a[5], a[11]
And I believe it's pretty straightforward to implement this. using
only few extra variables [not dependent on array size](Based on
implementation).
So, O(n) time and O(1) space [IN PLACE].
Alg: [assuming all elements are > 0)
Negate all elements (a[i] = -1 * a[i];)
current_index = 0;
current_element=A[0];
do
if current_index <= n/2 then
to_index = 2*current_index
else
to_index = (size + 1) - 2*(size - current_index)
end if
current_element = A[to_index];
A[to_index] = -1 * A[current_index];
if current_element > 0 then
to_index = index of next negative element.
current_index = to_index;
while A[current_index] < 0
Algo can be modified to check in other cases like when elements can be
negative also, OR elements are characters, strings.
There can be different ways to track if all elements are processed or
not, depending on problem.
e.g. if negative elements are also in input then,
Add some very very negative no to all elements say -50000 and while
assigning it to to_index, adding 50000
If element are characters, string then attach some keyword (prefix or
suffix) to each element,
while assigning it to to_index, remove the attachment.
With hash, it doesn't look as simple. One thing can done is:
Have some identifier which should imply duplicate (This identifier should not be a line in file) then
1.Read lines in file and store it in hash IF line is not already in hash. If line already there, put DUPLICATE identifier in hash.
2.Once complete file is read, scan the hash and print values (lines) which are not DUPLICATE identifier.
But this doesn't seem to be a good soln due to following:
1. DUPLICATE identifier may be a line in file
2. Size of file, If too big, memory issue. External Hashing ???
Say given string is: "My name is Anurag Singh"
1. reverse given string: "hgniS garunA si eman yM"
2. Now reverse each word: "Singh Anurag is name My"
#include <stdio.h>
#include <string.h>
void reverseString(char *s,int start, int end);
int main(int argc, char *argv[])
{
char *s="My name is Anurag Singh";
printf("%s\n",s);
int len=strlen(s);
reverseString(s,0,len-1);
printf("reverse by charater: %s\n",s);
int i=0,start=0;
while(i<=len)
{
if(s[i] && s[i] != ' ')
i++;
else
{
reverseString(s,start,i-1);
start=++i;
}
}
printf("Reverse by Word: %s\n",s);
return 0;
}
void reverseString(char *s,int start, int end)
{
int i=0,j=0;
char c;
for(i=start,j=end;i<j;i++,j--)
{
c=s[i];
s[i]=s[j];
s[j]=c;
}
}
Basic bit manipulation problem:
Just XOR all the elements in the given array, output will be the no which appeared in array an odd number of times.
answer=a[0];
for(i=1;i<array.length;i++)
answer ^= a[i];
printf("answer=%d\n",answer);
^v and Ajay Singh.. Yes, hashing looks much better option here (instead of sorting and then printing unique)
- Anurag Singh February 04, 2011At high level, sort file data then print unique lines.
Sorting is the real problem here.Since it is a file which can be too big and memory overflow may occur if we put complete file in main memory and try to sort it.
I believe we need to use external R way merge sorting here. The way unix sort works.
Look like "sort -u" unix implementation would be the right solution here.
--
- Anurag Singh February 03, 2011e.g. for 10 switches:
after 1st round: ALL are ON
after 2nd round: 1,3,5,7,9 are ON
after 3rd round: 1,5,6,7 are ON (3,9 were ON, TOGGLE them)
after 4th round: 1,4,5,6,7,8 are ON (4,8 were was OFF, TOGGLE them)
after 5th round: 1,4,6,7,8,10 are ON (5 was ON, TOGGLE it, 10 was OFF, TOGGLE it)
after 6th round: 1,4,7,8,10 are ON
after 7th round: 1,4,8,10 are ON
after 8th round: 1,4,10 are ON
after 9th round: 1,4,9,10 are ON
after 10th round: 1,4,9 are ON
So for 10 switches, after 10 rounds, switch no 1,4 and 9 (SQUARED No) will be ON, others OFF.
Actually question is not provided correctly. It is ctrying to say following:
While every round, TOGGLE the switches (If OFF, switch it ON, if ON, switch is OFF) which no is divisible by round No.
This is a little tricky. Say switches nos are 1 to 100.
Here
after 1st round, all switches are ON (All were OFF, so toggling will make all ON)
after 2nd round, all switches divisible by 2 (switch no divisible by 2) are TOGGLED
after 3rd round, all switches divisible by 3 (switch no divisible by 3) are TOGGLED
after 4th round, all switches divisible by 4 (switch no divisible by 4) are TOGGLED
.......
In other way, we can see that all switches having ODD no of divisors are going on be ON, and all switches with EVEN no of Divisors are going to be OFF.
e.g. Switch No
1 == >> divisor is 1 (ODD count), will be ON
2 == >> divisors are 1, 2 (EVEN count), will be OFF
3 == >> divisors are 1,3 (EVEN count), will be OFF
4 == >> divisors are 1, 2, 4 (ODD count), will be ON
Now how to find out all nos from 1 to 100 having ODD no of divisors. This is again tricky. Only SQUARE Nos will have ODD no of divisors :-) so simple.
So nos with ODD divisor count are: 1,4,9,16,25,36,49,64,81,100
So answer is: Switches with SQUARED no will be ON after 100 rounds (All other will be OFF).
This will not work for
1,2,3,4,2,3,3
Answer should be: 2 (1 and 4 are unique)
But above will give 1.
Right soln will be as I said, put in hash with array element as key and it's count as value (value 1 if inserted 1st time, increment later on while duplicate).
At the end, just count the hash element having value 1.
I guess storing element in hash and increment/decrement counter will not do here.
e.g. for input 1,2,3,4,3,5,2,2,7
Answer should be: 4 (1,4,5,7 are unique, others repeated).
So one soln would be to use index array (as told above) given that input range is known and input is not sparse (Else space wastage will be there).
Other soln would be to use hash where key is given input no and value will be count of that no (i.e. index array concept only but use hash instead of array to avoid space wastage). At the end, count the keys in hash having value ONE which will be the answer.
Here idea is same as in above program using array.
Use of Hash Map doesn't add anything good here (May save a little but space where array value is blank). Also array is faster than the Hash Map.
We can use some parser generator like Lex & Yacc OR JavaCC to generate a parser program for any given grammar. If it is allowed to use any of the available parser generators, this is very very simple job But writing parser code from scratch without help of any tool will not be easy which involves lexical analysis, syntax and semantic analysis (symbol table, parse tree etc)
- Anurag Singh January 29, 2011Both, Anil and anonymouS, good one !!!
- Anurag Singh January 29, 2011I believe you are trying to avoid some equality check but we need to add some extra boundary check and also if characters doesn't match, check the previous characters.
- Anurag Singh January 29, 2011Question says: bitwise reverse a very long character string
If it is bytewise, then we may do following:
1.Scan string characters from both side (front and end) using two variable say i and j.
2.Swap str[i] and str[j]
3.increment i and decrement j
4.Repeat 2 and 3 until i>=j
for(i=0,j=strlen(str);i<j;i++,j--)
swap(str[i],str[j]);
I can't think of any better soln. Other ideas pls.
Normally when we say, two or more link lists intersect, we mean that they share a SAME node at the point of intersection.
If this is what we mean here, then for two lists, shape will look like Y. It can't be of shape X OR /\ (As suggested by M) because one node can't have two different next pointers. With this assumption, v and rosh above are good and saying same thing.
If we mean intersection of list if two nodes a different (at two different memory addresses) but have same value, then we can think of X ot /\ scenarios. But I believe this is not the case here.
Find LCA of 3 pairs - (a, b), (b, c) and (c, a)
- Anurag Singh August 14, 2014LCA of at-least 2 pairs will be same.
If all 3 LCAs are same, remove that LCA node.
If only 2 LCAs are same, then we have two distinct LCA node here. One LCA node will be parent and other LCA node will be child. Remove the Child LCA Node (We may calculate height of the two LCA nodes here. The LCA node with lesser height will be the Child of the other and this lesser height node should be deleted).