coding.arya
BAN USERCode:
void SwapNodes(Node** start)
{
if (start == NULL || *start == NULL)
return;
Node* temp = *start;
if (temp ->next != null)
{
*start = temp->next;
while (temp && temp->next)
{
Node* next = temp->next->next;
Node* temp2 = temp->next;
temp2->next = temp;
temp->next = next;
temp = next;
}
}
}
Virtual memory concept virtualizes the main storage available to a process or task, as a contiguous address space which is unique to each running process, or virtualizes the main storage available to all processes or tasks on the system as a contiguous global address space. Whereas main memory is amount of physical memory (usually RAM) allocated to the system.
For more info:
en . wikipedia . org /wiki/Virtual_memory
Correct but start that grouping from right to left...
- coding.arya August 03, 2013We can use a hash function to generate a hash value for a string url...
create a hashmap using this hash function for the original URL to store...
www . tinyurl . com / hashvalue
as tiny url for the web URL...
Assuming all integers are unique... we have to find a
right = -1;
loop:
Let left = right + 1;
step: Let diff = a - arr[left];
if diff < 0
if left == 0
a is not in the array;
else
a will be into 0 to left - 1; use binarysearch(arr[], 0, left - 1, a);
else
right = left + diff;
goto loop:
vector<string> lines;
string newString;
int max = 0;
while (cin >> newString)
{
if (max < newString.length())
{
max = newString.length();
}
lines.push_back(newString);
}
for (int i = 0; i < max; ++i)
{
for (int j = 0; j < lines.size(); ++j)
{
if (i < lines[j].length())
{
cout << lines[i];
}
}
count << endl;
}
a vector is usually considered to represent contiguous storage, and a linked list is considered to be represented by individual cells linked together. Vectors provide fast constant time random-access read and write operations, but inserting and deleting vector elements take linear time. Lists have linear lookup performance to find an element to read and write, but given an element location, have constant time insertion and deletion. You can also add items to the start and to the end of a list in constant time (if the ADT implementation caches the location of the last element in the list)
- coding.arya June 19, 2013map mymap;
int givenarr[n];
int otherarr[n];
j = 0
for i = 0 to n - 1
if not mymap.containskey(givenarr[i])
otherarr[j++] = givenarr[i]
mymap[givenarr[i]] = something
while j < n
otherarr[j++] = Nothing
O(nlogn)
- coding.arya June 19, 2013Assuming the array has non-negative numbers:
startIndex = 0
sum = 0
arr[n]
givenSum //already given
for i = 0 to n - 1
sum = sum + arr[i]
if sum == givenSum
print "from index " startIndex " to " i
return
else if sum > givenSum
sum = sum - arr[startIndex]
++startIndex
--i
print "No sequence found!"
Complexity: O(n)
- coding.arya June 19, 2013In an rough and simplified sketch, assuming the simplest possible HTTP request, no proxies and IPv4:
1. Checks link's URL part. If not empty take that URL to be feteched.
2. browser checks cache; if requested object is in cache and is fresh, skip to #9
3. browser asks OS for server's IP address
4. OS makes a DNS lookup and replies the IP address to the browser
5. browser opens a TCP connection to server (this step is much more complex with HTTPS)
6. browser sends the HTTP request through TCP connection
7. browser receives HTTP response and may close the TCP connection, or reuse it for another request
8. browser checks if the response is a redirect (3xx result status codes), authorization request (401), error (4xx and 5xx), etc.; these are handled differently from normal responses (2xx)
9. if cacheable, response is stored in cache
10. browser decodes response (e.g. if it's gzipped)
11. browser determines what to do with response (e.g. is it a HTML page, is it an image, is it a sound clip?)
12. browser renders response, or offers a download dialog for unrecognized types
There are many other things happening in parallel to this (processing typed-in address, adding page to browser history, displaying progress to user, notifying plugins and extensions, rendering the page while it's downloading, pipelining, connection tracking for keep-alive, etc.).
map mymap;
int givenarr[n];
j = 0
for i = 0 to n - 1
if not mymap.containskey(givenarr[i])
givenarr[j++] = givenarr[i]
mymap[givenarr[i]] = something
while j < n
givenarr[j++] = Nothing
if n == 1
print 0
else if n == 2
print 1
else if n > 2
first = 0
second = 1
n = n - 2
print first and second
while (n-- > 0)
third = first + second
print third
first = second
second = third
1. Use a map and insert all the elements one by one avoiding duplicate. 0(nlogn)
2. Use HashTable.
Assume given tree is BST:
Steps:
for lineN to 1:
if treeExists
insert nodes one by one in this tree in BST form.
else
create root node with given element
//you will have a complete BST now...
//Use preorder() to draw preorder string of BST
If the array are sorted then it
Median (R) = Median (A) + Median(B)
If arrays are not sorted then,
Input new element in sorted order and you will found the median... O(n*m)
A snippet from stackoverflow(by Anurag):
Here's an attempt at an informal proof.
The shape of the cycle doesn't matter. It can have a long tail, and a loop towards the end, or just a loop from the beginning to the end without a tail. Irrespective of the shape of the cycle, one thing is clear - that the tortoise pointer can not catch up to the hare pointer. If the two were ever to meet, the hare pointer has to catch up the to tortoise pointer from behind.
With that established, consider the two possibilites:
hare pointer is one step behind the tortoise pointer.
hare pointer is two steps behind the tortoise pointer.
All greater distances will reduce to one or two eventually.
Assuming the tortoise pointer always moves first (can be the other way around too), then in the first case, the tortoise pointer takes one step forward. Now the distance between them is 2. When the hare pointer takes 2 steps now, they will land on the same node. Here's the same thing illustrated for easier understanding. Too much text can get in the way.
♛ = hare
♙ = tortoise
X = both meet
..♛♙... #1 - Initially, the hare is one step behind the tortoise.
..♛.♙.. #2 - Now the tortoise takes one step. now hare is two steps behind.
....X.. #3 - Next, the hare takes two steps and they meet!
Now let's consider the second case where the distance between them is 2. The slow pointer moves one step forward and the distance between them becomes 3. Next, the fast pointer moves forward two steps and the distance between them reduces to 1 which is identical to the first case in which we have already proved that they will meet in one more step. Again, illustrated for easier understanding.
.♛.♙... #1 - Initially, the hare is two steps behind the tortoise.
.♛..♙.. #2 - Now the tortoise takes one step and they become three steps apart.
...♛♙.. #3 - Next, the hare takes two steps which is identical to previous case.
Now, as to why this algorithm is guaranteed to be in O(n), use what we've already established that the hare will meet the tortoise before it moves ahead. Which means that once both are inside the loop, before the tortoise completes another round, it will meet the hare since the hare moves twice as fast. In the worst case, the loop will be a circle with n nodes. While the tortoise can only complete one round in n steps, the hare can complete two rounds in that time. Even if the hare missed the tortoise in its first round (which it will), it's definitely going to catch up to the tortoise in its second round.
for i = 1 to n
S += A[i];
for i = 1 to n
S[i] = S + (-A[i]); //Just Kidding
S[i] = S + (~A[i] + 1);
Why it should wait infinitely???
And Nbob is right! main() is not reentrant method.
Use merge sorting
- coding.arya June 01, 2013pit, pat, mat, map
- coding.arya May 25, 2013@Rakesh: The question doesn't say not to print duplicate values... It says that it should synchronize printing if the threads are going to print same value..
- coding.arya May 15, 2013I think you are right... :)
I took wrong input...
1^2^...^n^k ^ 1^2^...^n = k
Is this solution take care of missing number also? No!
Correct One... :)
- coding.arya May 13, 2013This would modify the given array... :P
- coding.arya May 13, 2013Check this out:
int FindDup(int arr[], int n)
{
for (int i = 1; i <= n; ++i)
{
if (arr[i - 1] != i)
{
int temp = arr[i - 1];
arr[i - 1] = arr[arr[i - 1] - 1];
arr[arr[i - 1] - 1] = temp;
}
}
for (int i = 1; i <= n; ++i)
{
if (arr[i - 1] != i)
{
return arr[i - 1];
}
}
return 0;
}
0(n)
- coding.arya May 13, 2013Take 1, 2, 3, 3, 5
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
Now 1 ^ 2 ^ 3 ^ 3 ^ 5
= 001 ^ 010 ^ 011 ^ 011 ^ 101
= 011 ^ 011 ^ 011 ^ 101
= 000 ^ 011 ^ 101
= 011 ^ 101
= 110 = 6
and 1 ^ 2 ^ 3 ^ 4 ^ 5
= 001 ^ 010 ^ 011 ^ 100 ^ 101
= 011 ^ 011 ^ 100 ^ 101
= 000 ^ 100 ^ 101
= 100 ^ 101
= 001 = 1
Now 110 ^ 001 = 111 = 7...
Is this the repeated or missing number???
You can create a linked list of int (or suitable data type like long or long long) which will store 1 integer in parts. If this datatype can store up to some digits say (10^n) then use a single node to store 10^n - 1 digits of this integer.
say if we store 5 digits in a node.
if the two big numbers are 403433232 and 4380200
then there will be two linked list...
First: 33232->4034->null
and second: 80200->434->null
then addition will be like...
33232 + 80200 = 113432 this exceed 5 digits limit so we will take 1 as carry and will store
13432 in first node of result and
then addition of second nodes will be
4034+434+1(carry from previous node) = 4469
so the result list will be
result: 13432->4469->null
i.e. 446913432
check this out::
int MaxTripleProduct(int arr[], unsigned int len)
{
switch(len)
{
case 0:
ASSERT(false);
break;
case 1:
return arr[0];
break;
case 2:
return arr[0] * arr[1];
break;
case 3:
return arr[0] * arr[1] * arr[2];
break;
default:
//sort array with 0(n) sorting algorigthm
countingSort(arr, len);
if (arr[len - 1] < 0)
{
return arr[0] * arr[1] * arr[2];
}
else
{
return max(arr[0] * arr[1], arr[len-3] * arr[len-2]) * arr[len - 1];
}
}
}
Approach is correct...
But I think you have not used the correct variables at correct places... :P
Check this out:
void PairWiseSwap(Node** mainlist)
{
if (mainlist && *mainlist)
{
Node* list = *mainlist;
Node* temp = list->next;
if (temp)
{
*mainlist = temp;
while(temp)
{
list->next = temp->next;
temp->next = list;
temp->prev = list->prev;
list->prev = temp;
if (temp->prev)
temp->prev->next = temp;
if (list ->next)
list ->next->prev = list ;
list = temp->next;
if (list)
temp = list->next;
else
temp = 0;
}
}
}
}
My solution would be:
1. first create a function (synchronized) to convert an integer to corresponding integer object using a map/hashtable such that this map returns same object with same integer value.
2. then print function should be like:
public void print (Integer value){
synchronized(value){
System.out.println(value);
}
}
I hope this would work.. :)
- coding.arya May 12, 2013I tried to shorten LargestEvenPalin()...
int LargestEvenPalin(char str[], int* startIndex)
{
int len = strlen(str);
bool bEven = (len % 2 == 0);
int lenResult = 0;
int j = len - (bEven ? 1 : 2);
for(int i = 0; (j - i > lenResult); ++i)
{
for(; (j - i > lenResult); j -= 2)
{
if (IsPalindrome(str, i, j))
{
*startIndex = i;
lenResult = j - i;
}
}
bEven = !bEven;
j = len - (bEven ? 1 : 2);
}
return lenResult + 1;
}
Let me know if there is any issue in this code... :)
- coding.arya May 12, 2013Check this out:
bool IsPalindrome(char str[], int startIndex, int endIndex)
{
while (startIndex < endIndex)
{
if (str[startIndex] != str[endIndex])
{
return false;
}
++startIndex;
--endIndex;
}
return true;
}
int LargestEvenPalin(char str[], int* startIndex)
{
int len = strlen(str);
bool bEven = (len % 2 == 0);
int j = 0;
int lenResult = 0;
for(int i = 0; i < len - 1; ++i)
{
j = len - (bEven ? 1 : 2);
if (j - i > lenResult)
{
for(; i < j; j -= 2)
{
if (j - i > lenResult)
{
if (IsPalindrome(str, i, j))
{
if ((j - i) > lenResult)
{
*startIndex = i;
lenResult = j - i;
}
}
}
else
{
break;
}
}
}
else
{
break;
}
bEven = !bEven;
}
return lenResult + 1;
}
void RunDriver()
{
//input
char str[1000];
int startIndex = -1;
cin.getline(str, 1000);
int resLen = LargestEvenPalin(str, &startIndex);
if (resLen > 1)
{
char* resultString = str + startIndex;
resultString[resLen] = '\0';
cout << endl << "Longest possible even palindrome is: " << resultString << endl;
}
else
{
cout << endl << "No Longest possible even palindrome exists." << endl;
}
}
0(n^2) if no palindrome exists... :)
- coding.arya May 12, 2013This solution is a tweak of Subset Sum Problem(Dynamic Programming) solution and As per I know this is best known solution for it.
O(sum*len)
Consider the following bit pattern:
ABCDEFGHIJKLMNOP
How to reverse it??
First reverse a group of 1 bit with adjacent group of 1 bit...
BADCFEHGJILKNMPO
Then reverse a group of 2 bits with adjacent group of 2 bits...
DCBAHGFELKJIPONM
Then reverse a group of 4 bits with adjacent group of 4 bits...
HGFEDCBAPONMLKJI
Then reverse a group of 8 bits with adjacent group of 8 bits...
PONMLKJIHGFEDCBA
Keep doing this till group size becomes sizeof(bit pattern) / 2... :)
Well this's a easy question to ask..
Algorithm is:
1. Reverse the whole string.
2. Reverse the individual words.
For example:
Welcome to India
after step 1 => aidnI ot emocleW
after step 2 => India to Welcome
...
0(n) and not extra memory... :)
You are right... my code doesn't work for 0... but it can be modified slightly to resolve that problem as well.. :)
- coding.arya May 11, 2013bool HasOddSum(int arr[], int len, int count, int sum)
{
if ((sum == 0) && (count % 2 == 1))
return true;
else if (sum < 0 || len < 0)
return false;
else if (sum < arr[len - 1])
return HasOddSum(arr, len - 1, count, sum);
else
return HasOddSum(arr, len - 1, count + 1, sum - arr[len - 1]) || HasOddSum(arr, len - 1, count, sum);
}
void RunDriver()
{
//input
int arr[] = {3, 23, 44, 2, 11};
int sum = 16;
cout << endl << "Array " << (HasOddSum(arr, sizeof(arr) / sizeof(arr[0]), 0, sum) ? "has" : "has't") << " sum " << sum << " with odd number of elements" << endl;
}
void SortString(char data[])
{
if (data != 0)
{
int len = strlen(data);
if (len > 1)
{
int i = 0;
int j = len - 1;
while (i < j)
{
while(data[i] == '0')
++i;
while((i < j) && (data[j] == '1'))
--j;
if (i < j)
{
data[i++] = '0';
data[j--] = '1';
}
}
}
}
}
void RunDriver()
{
//input
char data[1000];
cin.getline(data, 1000);
SortString(data);
cout << endl << "the sorted string is: " << data << endl;
} //RunDriver
First sort you string...
Find anagrams of this string (using permutation) ( ;) they will be generated in sorted order) (I think permutation algorithms do like this)
Then finding them in order in the dictionary will be easier...
And this problem is also known as diameter of a tree... :)
- coding.arya May 11, 2013Solution would be:
Run Postorder on binary tree...
take a static variable...
for each node :
if it is leaf node return 0 + 1(for branch connecting to parent)
else maximum of {left tree value, right tree value} + 1
(if either of child tree is not present take it as 0)......
at each node calculate current_max = left tree value + right tree value
if this is bigger than our static variable update our static varaible = current_max....
At end of the process our static variable will contain maximum distance between any of two nodes in our binary tree... :)
Minimum will be if only one thread gets the CPU time...
minimum: variable_currentValue + 100
Maximum will be if both threads get the CPU time for themselves...
maximum: variable_currentValue + 100 + 100 = variable_currentValue + 200
- coding.arya August 07, 2013