Delete N nodes after M nodes of a linked list

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

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

typedef Node* List;

void deleteNafterM(List l, int n, int m) {

	int count = 0;
	Node *prev = NULL, *next;

	while (l) {

		count++;
		next = l->next;

		if (prev) {
			if (count == n) {
				prev->next = next;
				prev = NULL;
				count = 0;
			} 

			free(l);

		} else if (count == m) {
			prev = l;
			prev->next = NULL;
			count = 0;
		} 

		l = next;
	}
}

void printList(List l) {
	while (l) {
		printf("%d", l->el);
		l = l->next;
	}

	printf("\n");
}

inline Node* newNode(int el) {
	Node *node = (Node *)malloc(sizeof(Node));
	node->el = el;
	node->next = NULL;

	return node;
}

List createList(int n) {
	List l = newNode(1);

	Node *curr = l;
	int i;

	for (i = 2; i <= n; i++) {
		curr->next = newNode(i);
		curr = curr->next;
	}

	return l;
}

int  main(int argc, char const *argv[])
{
	List l = createList(10);

	deleteNafterM(l, 2, 3);

	printList(l);

	return 0;
}
Advertisements

Merge Overlapping Intervals

#!/usr/bin/env mocha

function m(intervals) {

//Sort the intervals
  intervals.sort(function(a, b) {
    return a[0] - b[0];
  });

//Merged intervals
  var r = [];

//Iterate over the intervals
  for (var i = 0, len = intervals.length; i < len; ) {

    var end = intervals[i][1];

//Now find the interval end
    for (var j = i + 1; j < len && end >= intervals[j][0]; j++) {
      if (intervals[j][1] > end) {
        end = intervals[j][1];
      }
    }

    r.push([intervals[i][0], end]);

    i = j;
  } 

  return r;
}

var assert = require("assert");

describe('mergeIntervals', function(){
    it('should merge all the contigous intervals', function() {
      assert.deepEqual([ [1, 9] ], m([ [6,8], [1,9], [2,4], [4,7] ]));
      assert.deepEqual([ [1, 8] ], m([ [6,8],[1,3],[2,4],[4,7] ]));
      assert.deepEqual(
       [ [1, 3], [4, 6], [7, 9], [10, 13] ], m([ [1,3],[7,9],[4,6],[10,13]]
      ));
      assert.deepEqual(
       [ [1,4], [5, 8]], m([[1,3], [2,4], [5,7], [6,8] ]
      ));
    })
})

Find the largest multiple of 3, given an array of n digits

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;
typedef vector<int> Container;

/*
 * Algorithm:
 * a . Sort the array
 * b . find the sum of the array
 * c. find rem = sum % 3
 * c1. if rem == 0 return 0;
 * else
 * find first digit whose remainder == rem
 * if found
 * erase it from the array and return 0
 * else
 * find first two digits whose remainder != 0 and != rem
 * if found
 * erase them and return 0
 * else
 * return -1
 */

/**
 * Return:
 * 0 success
 * -1 failure
 */

int largestDivBy3(Container &v) {

sort(v.begin(), v.end());

int s = accumulate(v.begin(), v.end(), 0),
rem = s % 3,
tmp;

if (rem == 0) return 0;

int pos1 = -1,
pos2 = -1;

for (auto i = v.begin(); i != v.end(); ++i ) {
tmp = *i % 3;
if (tmp == rem) {
v.erase(i);
return 0;
} else if(tmp) {
if (pos1 == -1) {
pos1 = i - v.begin();
} else if(pos2 == -1) {
pos2 = i - v.begin();
}
}
}

if (pos2 != -1) {
v.erase(v.begin() + pos1);
v.erase(v.begin() + pos2 - 1);
return 0;
}
return -1;
}


int main() {
Container v = {9, 7, 6, 6, 6 };

int n = largestDivBy3(v);

if (n == 0) {
for(auto i = v.rbegin(); i < v.rend(); ++i) {
printf("%d", *i);
}

printf("\n");
} else {
printf("Not possible");
}
}

Given two BST print the elements in sorted form

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


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

typedef TreeNode* Tree;

class InorderTraversal {
  public:

InorderTraversal(TreeNode *t):t_(t), cursor_(t) {}


/**
     * Returns NULL at the end of the traversal
     *
     **/

TreeNode* next() {
while (cursor_) {
s_.push(cursor_);
cursor_ = cursor_->left;
}

if (!s_.empty()) {
TreeNode* ret = s_.top();
s_.pop();
cursor_ = ret->right;
return ret;
}

return NULL;
}

void reset() {
cursor_ = t_;
s_ = std::stack<TreeNode*>();
}

  private:

Tree t_;
TreeNode* cursor_;
std::stack<TreeNode*> s_;

};

Tree insert(Tree t, int el) {

if (t == NULL) {
t = (TreeNode *)calloc(sizeof(TreeNode), 1);
t->data = el;
} else {
if(el <= t->data) {
if(t->left) {
insert(t->left, el);
} else {
t->left = (TreeNode *)calloc(sizeof(TreeNode), 1);
t->left->data = el;
}
} else {
if(t->right) {
insert(t->right, el);
} else {
t->right = (TreeNode *)calloc(sizeof(TreeNode), 1);
t->right->data = el;
}
}
}

return t;
}


int main() {
int i;
Tree t1 = NULL;
Tree t2 = NULL;

for (i = 10; i >= 6; i--) {
t1 = insert(t1, i);
}

for (i = 12; i >= 6; i--) {
t2 = insert(t2, i);
}

InorderTraversal s1(t1);
InorderTraversal s2(t2);

TreeNode *n1 = s1.next(), *n2 = s2.next();

while (n1 && n2) {
if (n1->data < n2->data) {
printf("%d ", n1->data);
n1 = s1.next();
} else {
printf("%d ", n2->data);
n2 = s2.next();
}
}

while (n1) {
printf("%d ", n1->data);
n1 = s1.next();
}

while (n2) {
printf("%d ", n2->data);
n2 = s2.next();
}

printf("\n");
}

To find the max palindrome in a given string

#include <iostream>
#include <string>
#include <assert.h>

using namespace std;

/*
 * Algo:
 * find the sequence where two equal letters are adjacent or apart by one letter
 * example: "aa", "aba"
 * expand the sequence while the letters at prev and next of the sequence are equal
 *
 * maintain the max palindrome encountered so far
 *
 * Complexity: best O(n) and worst O(n^2)
 */

string largestPalindrome(string s) {

int i, j, k, len = s.length(), m = 0;
string ret(1, s[0]);

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

if (s[i - 1] == s[i]) {

j = i - 2;
k = i + 1;

//expand the sequence
while (j >= 0 && k < len && s[j] == s[k]) {
j--, k++;
}

//compare with prev max
if (m < (k - j - 1) ) {
m = k - j - 1;
ret = s.substr(j + 1, m);
}
}

if ( (i + 1 < len) && s[i - 1] == s[i + 1]) {

j = i - 2;
k = i + 2;

//expand the sequence
while (j >= 0 && k < len && s[j] == s[k]) {
j--, k++;
}

//compare with prev max
if (m < (k - j - 1) ) {
m = k - j - 1;
ret = s.substr(j + 1, m);
}
}
}

return ret;
}

int main() {
assert(largestPalindrome("a") == "a");
assert(largestPalindrome("sa") == "s");
assert(largestPalindrome("aa") == "aa");
assert(largestPalindrome("aaa") == "aaa");
assert(largestPalindrome("aba") == "aba");
assert(largestPalindrome("abba") == "abba");
assert(largestPalindrome("aaaa") == "aaaa");
assert(largestPalindrome("aaaaa") == "aaaaa");
assert(largestPalindrome("aabaa") == "aabaa");
assert(largestPalindrome("sambasiva") == "s");
assert(largestPalindrome("sambabmiv") == "mbabm");
assert(largestPalindrome("saaasr") == "saaas");
assert(largestPalindrome("saasr") == "saas");

cout<< "All tests passed" << endl;
}

To print all the paths the frog can choose to cross the river

Problem
#include <stdio.h>

int frogPaths(int res[], int resIndex, int curRock, int numRocks) {
if (curRock == numRocks) {

int i;

for (i = 0; i < resIndex; ++i) {
printf("%d ", res[i]);
}
printf("%d\n", curRock);

return 1;

} else {
int count = 0;

res[resIndex] = curRock;

if (curRock + 1 <= numRocks)
count += frogPaths(res, resIndex + 1, curRock + 1, numRocks);

if (curRock + 2 <= numRocks)
count += frogPaths(res, resIndex + 1, curRock + 2, numRocks);

return count;
}
}


int main(){
int n;

scanf("%d", &n);

int a[n + 1];

printf("Total num of paths = %d\n",frogPaths(a, 0, 1, n));
}