Laiq Ahmed
BAN USERFollowing is the algorithm to check whether the singly link-list is palindrome or not in O(N) time and O(1) space.
Algorithm is as follows:
1. find the length of the link-list in O(n) time..
2. loop through half of the length.. floor(length(list)/2)...
2.1 extract the node from the list and push it to stack (in-place).
2.2 advance the current node pointer.
3.0 if length of list is Odd advance the current list pointer by 1.
4.0 loop till both the stack list pointer & current pointer is not NULL
4.1 compare the elements to see if they don't match return false.
5.0 return true;
following is the code snippet of the idea. Please suggest improvements
Note: the sub-list are not merged into single list but it can be easily done
using the same logic as create_stack method.
int length(node* h) {
int l = 0;
while (h) {
++l;
h = h->next;
}
return l;
}
node* create_stack(node*& h, node* n) {
node* t = n->next;
n->next = h;
h = n;
return t;
}
bool is_palindrome(node* h) {
int len = length(h);
node* l = h;
node* r = NULL;
for(int i=1; i<=len/2; ++i)
l = create_stack(r, l);
if (len % 2 != 0)
l = l->next;
while (l != NULL && r != NULL) {
if (l->x != r->x)
return false;
l = l->next;
r = r->next;
}
return true;
}
// following is the O(N) time algorithm for constructing Cartesian tree from in-order traversal of the binary search tree (i.e. sorted sequence).
Please suggest improvement
static Node cTree(int[] a, int start, int end) {
// let's construct 1...
// for the remaining array...
// construct the left child... 2n + 1
// construct the right child...2n + 2.
if (start > end)
return null;
int key = a[start];
Node n = new Node(key);
n.left = cTree(a, 2*start + 1, end);
n.right = cTree(a, 2*start + 2, end);
return n;
}
This is sort of interpolation search with average/best case complexity of O(lg(lgn)) iff elements are uniformly distributed. but in worst case the complexity meets O(n). I come up with the following code to solve this problem.
Editing it to mention the test-cast where the complexity meets O(n)
in the following array search for 7.
int[] a = {5,6,5,6,5,6,5,6,5,6,5,6,5,6,7};
Algorithm
static int first_occurance(int key, int[] a) {
int start = 0;
while (start < a.length) {
int v = Math.abs(key - a[start]);
if (v == 0)
return start;
start += v;
}
return -1;
}
Updated the algorithm...
node* add_list(node* list1, node* list2, int& carry) {
if (list1 == NULL && list2 == NULL)
return NULL;
node* t = add_list(list1->next, list2->next, carry);
int sum = list1->item + list2->item + carry;
carry = sum / 10;
node* n = new node(sum % 10);
n->next = t;
return n;
}
node* add_list(node* list1, node* list2) {
int carry = 0;
node* l = add_list(list1, list2, carry);
if (carry > 0) {
node* t = new node(carry);
t->next = l;
return t;
}
return l;
}
Have tested on 18 + 99... The algorithm breaks in that case :(.
- Laiq Ahmed May 21, 2013The problem can be solved if you can handle the carry... there are two cases to handle the carry... 1 is if 9 + 9 = 18. in that case we'll receive the carry as the head of the list.
other cases are 99 + 99 = 198 in which we've to add the carry to the previous node. just little paper and pencil will ensure that we'll never have a carry greater than 1 and we'll never have a sum%10 greater 8. therefore we just have to handle two cases only.
Following is the algorithm please suggests any improvement.
node* add_list(node* l1, node* l2, node* prev) {
if (l1 == NULL && l2 == NULL)
return NULL;
node* add = new node(0);
add->item += l1->item;
add->item += l2->item;
int carry = add->item / 10;
add->item = add->item % 10;
if (carry > 0) {
if (prev == NULL) {
prev = new node(carry);
prev->next = add;
add->next = add_list(l1->next, l2->next, add); // case 1
return prev;
} else {
prev->item += carry;
}
}
add->next = add_list(l1->next, l2->next, add); // case-2
return add;
}
This is my efforts for to solve this problem.
void foo(char a[], int n) {
int k = 0;
for (int i=0; i<n; ++i) {
if (a[i] != 'b') {
if (a[i] != 'a') {
a[k++] = a[i];
}
else if ((i + 1) < n && a[i+1] == 'c') {
i += 1;
}
else {
a[k++] = a[i];
}
}
}
if (k < n)
a[k] = '\0';
}
For implementing the Iterator {} for binary_tree....
the choice of Node {} structure would help, if parent pointer is stored
in the Node then we can do it without using extra space, otherwise O(h) space would be required.. where h = height = longest distance
from root to the leaves in worst case it would be O(n) and best/Average it would be O(lgn).
I am not able to find the solution with duplicates.
- Laiq Ahmed May 19, 2013In order to find the rotations in a sorted array we can adopt the solution.
T(n) = T(n/2) + c divide and conquer technique resulting in a O(lgn) solution.
The interesting part of this problem is that whether the array is sorted in
ascending order or descending order... I tried to solve this with ascending and
descending order then I think over the combined solution...
Any improvement and suggestions are highly appreciated.
int find_r(int a[], int start, int end) {
while (start < end) {
int mid = start + (end - start)/2;
// ascending if (a[mid] > a[end])
// descending if (a[mid] < a[end])
// both
if (where_to_go(a, start, mid, end))
start = mid + 1;
else
end = mid;
}
return start;
}
Now the tricky part is decide where to go either on the left or on the right.
for this we've to analyse two arrays...
// A = <8,7,6,5,9,10> -- right rotated, rotations = 2.
// B = <6,7, 1,2,3,4> -- left rotated, rotations = 2.
if we correctly guess the whether it's ascending or descending sequence this would solve
the problem.
bool where_to_go(int a[], int start, int mid, int end) {
if (a[mid] < a[start] && a[mid] < a[end]) { // descending
if (a[mid] < a[end]) // go to right.
return true;
else
return false;
} else { // ascending.
if (a[mid] > a[end]) // go to right.
return true;
else
return false;
}
}
Absolutely correct Prithvi square_root is redundant here... and second and the most critical mistake I've made pointed out by Nitin is using the Max Priority Queue (as I was thinking kth closest point). For Farthest we've to use Min Priority Queue thank you guys.
- Laiq Ahmed May 16, 2013Using a max priority queue of k items.
1. Create a function which gives the distance (square_root( square(x1) + square(y1)). The complexity of function square_root is Olog(n). where n = sum of square or x1 and y1
1. Initially the queue is empty insert k items directly into the priority queue O(klogk). k distances.
2. Now for remaining entries you can simply check with the max element if the new item is less than max remove max and insert that item. Do this for every remaining item in the file. O(nlogk).
3. At the end you'll have k smallest items remaining in the priority queue. The space complexity for this solution is O(k)
Please correct me if anything is wrong.
In order to merge K-sorted arrays, we can simply merge the sorted sub-arrays at the back of the
bigger array.
I've added comments in the code. just to give the idea how it works, it is not the optimized version and also make
some assumption but overall gives the clear idea of the algorithm.
// A little modified form of merge algorithm, it just keep track of the start position
// in the bigger array.
void merge(int left[], int right[], int n, int m, int a[], int start) {
int i = 0;
int j = 0;
while (i <n && j < m) {
if (left[i] < right[j]){
a[start++] = left[i++];
}
else {
a[start++] = right[j++];
}
}
while (i < n) a[start++] = left[i++];
while (j < m) a[start++] = right[j++];
}
// The algorithm is based on the merge-sort merge algorithm.
// what it actually does is simple it simply picks up the list and
// merge it at the end of the bigger array.
// a little arithematic for indexing is required.
// I've assume size of each sub-list to be 10 it can easily extends to different size lists.
// the logic is simple every time you perform the merge start from size of already merged list + size of new sub-list to be merged.
// The you need to remember two things at every iteration.
// first = size of array 'a', (i.e. elements that are present in array a)
// second = the starting index from where to start merging the new list to the existing list.
void merge_lists(int* lists[], int sz, int a[], int n)
{
// assume size of every sub-list = 10.
int m = 10;
// flag to keep track whether it's a first pass
// if yes then it simply
bool isFirstPass = false;
int iListIter = 0;
// copy the array directly to a.
while (sz > 0) {
// pick the list and merge it
int* left = lists[iListIter];
if (isFirstPass == false) { // no elements are present in the main array.
iListIter++;
isFirstPass = true;
// merge two lists in the bigger array.
int* right = lists[iListIter];
merge(left, right, m, m, a, n - (iListIter + 1)* m); // start merging the arrays at the end.
sz--;
}
else {
merge(left, a + n - (iListIter * m), m, (iListIter * m), a, n - ((iListIter + 1)* m));
}
iListIter++;
sz--;
}
}
In order to merge K-sorted arrays, we can simply merge the sorted sub-arrays at the back of the
bigger array.
I've added comments in the code. just to give the idea how it works, it is not the optimized version and also make
some assumption but overall gives the clear idea of the algorithm.
// A little modified form of merge algorithm, it just keep track of the start position
// in the bigger array.
void merge(int left[], int right[], int n, int m, int a[], int start) {
int i = 0;
int j = 0;
while (i <n && j < m) {
if (left[i] < right[j]){
a[start++] = left[i++];
}
else {
a[start++] = right[j++];
}
}
while (i < n) a[start++] = left[i++];
while (j < m) a[start++] = right[j++];
}
// The algorithm is based on the merge-sort merge algorithm.
// what it actually does is simple it simply picks up the list and
// merge it at the end of the bigger array.
// a little arithematic for indexing is required.
// I've assume size of each sub-list to be 10 it can easily extends to different size lists.
// the logic is simple every time you perform the merge start from size of already merged list + size of new sub-list to be merged.
// The you need to remember two things at every iteration.
// first = size of array 'a', (i.e. elements that are present in array a)
// second = the starting index from where to start merging the new list to the existing list.
void merge_lists(int* lists[], int sz, int a[], int n)
{
// assume size of every sub-list = 10.
int m = 10;
// flag to keep track whether it's a first pass
// if yes then it simply
bool isFirstPass = false;
int iListIter = 0;
// copy the array directly to a.
while (sz > 0) {
// pick the list and merge it
int* left = lists[iListIter];
if (isFirstPass == false) {
iListIter++;
isFirstPass = true;
// merge two lists in the bigger array.
int* right = lists[iListIter];
merge(left, right, m, m, a, n - (iListIter + 1)* m);
sz--;
}
else {
merge(left, a + n - (iListIter * m), m, (iListIter * m), a, n - ((iListIter + 1)* m));
}
iListIter++;
sz--;
}
}
It's simply a merge_sort algorithm on link-list, I don't suggests to merge the list initially. It will just increase the traversing of break_list algorithm eventually you've to break the list into two.
So here it what should be done.
- 1. Perform MergeSort on List1. (mlogm) assuming size of list m.
- 2. Perform MergeSort on List2. (nlogn) assuming size of list n.
- 3. Merge two sorted List O(m+n).
MergeSort on Link-List can be performed as follows:
- 1. If size of list is one no need to sort.
- 2. break the list into two (say left, right).
- 3. recursively sort the left & right sub-lists.
- 4. merge the two sub-lists into sorted one.
Here is the sample code in C/C++
class Node {
public:
int value;
Node* next;
Node(int v, Node* n) : value(v), next(n) {}
};
Node* merge(Node* left, Node* right) {
Node* head = NULL, *tail = NULL;
while (left != NULL && right != NULL) {
if (left->value < right->value) {
Node* t = left->next;
if (head == NULL) {
head = tail = left;
}
else {
tail->next = left;
tail = tail->next;
}
left = t;
}
else {
Node* t = right->next;
if (head == NULL) {
head = tail = right;
}
else {
tail->next = right;
tail = tail->next;
}
right = t;
}
}
if (left != NULL) {
if (head == NULL) {
head = tail = left;
}
else {
tail->next = left;
}
}
if (right != NULL) {
if (head == NULL) {
head = tail = right;
}
else {
tail->next = right;
}
}
return head;
}
void break_list(Node* head, Node*& left, Node*& right) {
if (head == NULL)
return;
Node* slow = head, *fast = head;
Node* tailSlow = NULL;
while (fast) {
tailSlow = slow;
slow = slow->next;
fast = (fast->next) ? fast->next->next: NULL;
}
tailSlow->next = NULL;
left = head;
right = slow;
}
void printList(Node* h) {
while (h) {
cout << h->value;
h = h->next;
}
cout << endl;
}
Node* merge_sort(Node* head) {
printList(head);
// if the list has only one element, it's already sorted.
if (head == NULL || head->next == NULL)
return head;
Node* left = NULL, *right = NULL;
break_list(head, left, right);
Node* l = merge_sort(left);
Node* r = merge_sort(right);
head = merge(l, r);
printList(head);
return head;
}
Node* merge_two_lists(Node* head, Node* head2) {
Node* h = merge_sort(head);
printList(h);
Node* h2 = merge_sort(head2);
printList(h2);
Node* r = merge(h, h2);
printList(r);
return r;
}
Following is my efforts to solve the problem. The solution is written in java.
- Laiq Ahmed June 26, 2013