Laiq Ahmed
BAN USERFollowing is the algorithm to check whether the singly linklist is palindrome or not in O(N) time and O(1) space.
Algorithm is as follows:
1. find the length of the linklist 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 (inplace).
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 sublist 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;
}

Laiq Ahmed
June 21, 2013 // following is the O(N) time algorithm for constructing Cartesian tree from inorder 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;
}

Laiq Ahmed
June 19, 2013 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 testcast 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;
}

Laiq Ahmed
June 05, 2013 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;
}

Laiq Ahmed
May 21, 2013 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); // case2
return add;
}

Laiq Ahmed
May 20, 2013 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';
}

Laiq Ahmed
May 19, 2013 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;
}
}

Laiq Ahmed
May 19, 2013 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 Ksorted arrays, we can simply merge the sorted subarrays 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 mergesort 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 sublist 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 sublist 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 sublist = 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;
}
}

Laiq Ahmed
March 18, 2013 In order to merge Ksorted arrays, we can simply merge the sorted subarrays 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 mergesort 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 sublist 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 sublist 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 sublist = 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;
}
}

Laiq Ahmed
March 18, 2013 It's simply a merge_sort algorithm on linklist, 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 LinkList 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 sublists.
 4. merge the two sublists 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;
}

Laiq Ahmed
March 18, 2013 Open Chat in New Window
Following is my efforts to solve the problem. The solution is written in java.
 Laiq Ahmed June 26, 2013