Populate next higher in a singly linked list

Problem

/*
   Algo:  This is similar to insertion sort algorithm
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct node {

int data;
struct node *next;
struct node *next_higher;

}Node;


typedef Node *List;


List populateNextHigher(List l) {

if(!l) return NULL;

Node *start = l; //starting of the sorted list
l = l->next;

while(l){ //iterate through the list

if(l->data < start->data){

l->next_higher = start;
start = l;

} else {

Node *p = start;

while(p->next_higher && l->data >= p->next_higher->data) //find the position of l
p = p->next_higher;

l->next_higher = p->next_higher; //insert l
p->next_higher = l;

}
l = l->next;
}

return start;
}


//Utilities

Node *makeNode(int n) {
Node *node = calloc(1, sizeof(Node));

node->data = n;
}

List array2List(int a[], int n){

List l = NULL;

if(n > 0) {
Node *end = l = makeNode(a[0]);
int i;

for(i = 1; i < n; ++i) {

end->next = makeNode(a[i]);
end = end->next;
}
}

return l;

}


void printList(List l) {

while(l){
printf("%d ", l->data);
l = l->next_higher;
}

printf("\n");
}

int main(){

int a[] = {90, 80, 60, 70, 50, 40,100};

List l = array2List(a, sizeof(a)/sizeof(int));

List h = populateNextHigher(l);
printList(h);

return 0;
}
Advertisements

To find minimum distance of two sorted lists where distance is the absolute difference of pair of elements

Problem
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int minDist(int a[], int m, int b[], int n){

int i = 0,
j = 0,
min = INT_MAX,
cur;

while(i < m && j < n) {

cur = abs(a[i] - b[j]);

min = min < cur ? min : cur;

if(a[i] < b[j])
i++;
else
j++;
}

return min;
}

int main() {

int a[] = {2, 3, 5, 11, 18, 19, 20};
int b[]= {15, 24, 27, 29};


printf("%d\n", minDist(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int)));

return 0;
}

reorder linked list as even elements followed by odd elements

#include <stdio.h>
#include <stdlib.h>


typedef struct node {
int data;
struct node *next;
}Node;

typedef Node * List;


/*
arranges the list as event elements followed by odd elements in single pass
*/
void evenOddList(List l){

if(!l) return;

Node *even = NULL,
*odd = NULL,
*start = NULL;

if(l->data & 1)
odd = l;
else
even = l;

l = l->next;

while(l) {

if(l->data & 1) {//odd

if(odd)
odd->next = l;
else
start = l;

odd = l;

}else { //even

if(even)
even->next = l;
else
start = l;

even = l;
}

l = l->next;
}

if(start) {
if(start->data & 1) {//odd

even->next = start;
odd->next = NULL;

}else {//even

odd->next = start;
even->next = NULL;
}
}

}


List append(List l, int e) {

static Node *end = NULL;

Node *n = calloc(sizeof(Node), 1);

n->data = e;

if(end) {
end->next = n;
}else {
l = n;
}

end = n;

return l;

}


void printList(List l) {

Node *n = l;

while(l) {

printf("%d ", l->data);

l = l->next;
}

printf("\n");
}


int main() {

int a[]= {13, 11, 28, 45, 58, 69, 34, 23, 86};


List l = NULL;

int i;

for(i = 0; i < sizeof(a)/sizeof(int); ++i) {

l = append(l, a[i]);

}


printList(l);

evenOddList(l);

printList(l);
return 0;
}

Max breadth of a binary tree

#include <stdio.h>
#include <stdlib.h>
#include <list>

typedef struct TreeNode {
struct TreeNode *left, *right;
int data;

}TreeNode;


typedef TreeNode * Tree;

/*
*Function which returns maximum width of a binary tree without recursion

We are using level order traversal
*/

int Width(Tree t) {

int width = -1;

if(t != NULL) {

std::list<Tree> q; //Queue to store tree nodes

q.push_back(t);
q.push_back(NULL); //null is the delimeter to show end of the level

int cur = 0;

while(!q.empty()) {

TreeNode *node = q.front();
q.pop_front();

if(node == NULL) {//delimeter encountered, compare width with cur width and push NULL if q not empty

if(width < cur)
width = cur;

cur = 0;

if(!q.empty())
q.push_back(NULL);

}
else {

cur++;

if(node->left)
q.push_back(node->left);

if(node->right)
q.push_back(node->right);
}
}

}

return width;
}


/*Utilities*/

inline TreeNode * makeTreeNode(int data) {

TreeNode *n = (TreeNode *)calloc(sizeof(TreeNode), 1);
n->data = data;

return n;
}


int main() {

/*level 0*/
Tree t = makeTreeNode(10);

/*level 1*/
t->left = makeTreeNode(20);
t->right = makeTreeNode(30);


/*level 2*/
t->left->left = makeTreeNode(40);
t->left->right = makeTreeNode(70);
t->right->left = makeTreeNode(50);
t->right->right = makeTreeNode(60);

/*level 3*/
t->left->left->left = makeTreeNode(70);
t->left->left->right = makeTreeNode(70);
t->left->right->left = makeTreeNode(70);
t->left->right->right = makeTreeNode(70);
t->right->left->left = makeTreeNode(60);
t->right->left->right = makeTreeNode(160);
t->right->right->left = makeTreeNode(60);
t->right->right->right = makeTreeNode(160);

/*level 4*/
t->left->left->left->left = makeTreeNode(70);

printf("%d\n", Width(t));

return 0;
}

finding minimum number of platforms required if arrival and departure time of trains given in sorted order of arrival time

#include <stdio.h>

typedef struct {

int a, d;
}Train;



int minPlatform(Train a[], int n) {

int platforms[n];

int i, j;
int num = 1;

platforms[0] = a[i].d; //time when plaform 0 will be free

for(i = 1; i < n; ++i) {

for(j = 0; j < num; ++j) {

if(platforms[j] < a[i].a) { //arrival time is after freeing the platform

platforms[j] = a[i].d; //assign platform j to train i

break;
}
}

if(j == num) { //all platforms busy
platforms[num] = a[i].d; //allocate one more platform
num++;
}

}


return num;
}


int main() {


Train a[] = {{1, 10}, {9, 13}, {10, 15}, {17,20}, {20, 22}, {24, 25}};


printf("%d\n", minPlatform(a, sizeof(a)/sizeof(Train)));

return 0;
}

Create a singly linked list of Leaf nodes from a binary tree

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode
{
struct TreeNode *left, *right, *next;
int data;

}TreeNode;

typedef TreeNode * Tree;

void LeafLinked(Tree t, TreeNode **prevLeaf, TreeNode **head)
{
if(t) {

if(t->left == NULL && t->right == NULL) { //leaf

if(*head == NULL)
*head = t;

else if(*prevLeaf)
(*prevLeaf)->next = t;

*prevLeaf = t;
}
else { //at least one child
LeafLinked(t->left, prevLeaf, head);
LeafLinked(t->right, prevLeaf, head);
}
}
}


/*Utilities*/

inline TreeNode * makeTreeNode(int data)
{
TreeNode *n = calloc(sizeof(TreeNode), 1);
n->data = data;

return n;
}

inline void printList(Tree t)
{
while(t)
{
printf("%d ", t->data);
t = t->next;
}
printf("\n");
}

int main()
{
/*level 0*/
Tree t = makeTreeNode(10);

/*level 1*/
t->left = makeTreeNode(20);
t->right = makeTreeNode(30);


/*level 2*/
t->left->left = makeTreeNode(40);
t->left->right = makeTreeNode(70);
t->right->left = makeTreeNode(50);
t->right->right = makeTreeNode(60);

/*level 3*/
t->left->left->left = makeTreeNode(70);
t->right->right->left = makeTreeNode(60);
t->right->right->right = makeTreeNode(160);

/*Empty List head*/
TreeNode *head = NULL, *prevLeaf = NULL;

/*Convert tree to list*/
LeafLinked(t, &prevLeaf, &head);

/*print list*/
printList(head);


return 0;
}

Python Version:

class BinaryTree:

def __init__(self, e):
self.left = self.right = self.next = None
self.data = e


def LinkLeaves(t):

if t:
if t.left or t.right:

for x in LinkLeaves(t.left):
yield x

for x in LinkLeaves(t.right):
yield x
else:
yield t

def printList(t):

while t:
print t.data,
t = t.next
print

def main():

t = BinaryTree(10);

t.left = BinaryTree(20)
t.right = BinaryTree(30)

t.left.left = BinaryTree(40)
t.left.right = BinaryTree(70)
t.right.left = BinaryTree(50)
t.right.right = BinaryTree(60)

t.left.left.left = BinaryTree(70)
t.right.right.left = BinaryTree(60)
t.right.right.right = BinaryTree(160)

head = None
prevLeaf = None

for x in LinkLeaves(t):
if head is None:
head = x
else:
prevLeaf.next = x

prevLeaf = x

printList(head)


if __name__ == '__main__':
main()

find two elements in a binary search tree whose sum is given k

class BinarySearchTree:

def __init__(self, e = None):
self.left = self.right = None
self.data = e

def insert(self, e):

if self.data is None:
self.data = e
else:
if self.data >= e:
if self.left is None:
self.left = BinarySearchTree(e)
else:
self.left.insert(e)
else:
if self.right is None:
self.right = BinarySearchTree(e)
else:
self.right.insert(e)

def nextMin(self):

if self.left:
for x in self.left.nextMin():
yield x

yield self.data

if self.right:
for x in self.right.nextMin():
yield x

def nextMax(self):

if self.right:
for x in self.right.nextMax():
yield x

yield self.data

if self.left:
for x in self.left.nextMax():
yield x

def findxy(self, k):

if self.data:

mn = self.nextMin()
mx = self.nextMax()

m = mn.next()
n = mx.next()

while True:

sm = m + n

try:
if sm == k:
return m,n
elif sm < k :
m = mn.next()
else:
n = mx.next()
except:
return None


def main():
l = [50, 80, 30, 20, 40, 70, 60]

t = BinarySearchTree()

for i in l:
t.insert(i)

print t.findxy(120)


if __name__ == '__main__':
main()