#!/usr/bin/env python def maxkeys(n, table): if n <= 6: table.extend(range(n + 1)) else: maxkeys(n - 1, table) table.append(max([v * (n - x - 1) for x, v in enumerate(table) if x <= n - 3])) t = [] maxkeys(22, t) print(t)
Category Archives: Uncategorized
Reverse level order traversal of a tree given in an array form
Probelm:
One of the many ways of representing a tree is to have an array(of length same as number of nodes), where each element in the node denotes the parent of that node.
Please note –
* An element with parent = -1 is the root element.
* An element with the least index becomes the left most child. (ie. a node with always be on left of all its siblings that have higher index than it)
* When printing a level of tree you need to maintain left to right order.
Eg –
{-1, 0, 0, 1, 1} would represent a tree with –
* 0 as root
* 1 and 2 as children of 0
* 3 and 4 as children of 1
Given a similar representation, you have to print reverse level order traversal of the corresponding tree.
Level order traversal of a tree is where we traverse levels of tree one by one.
Eg –
For the above given tree, level order traversal would be –
0
1 2
3 4
And hence, the reverse level order traversal is –
3 4
1 2
0
Solution:
#!/usr/bin/env python n = raw_input() tree = raw_input().split() #Inverse the tree parent = {} for idx, val in enumerate(tree): if val in parent: parent[val].append(str(idx)) else: parent[val] = [str(idx)] #BFT of the tree def bft (q, t): if len(q) == 0: return ret = q q = [] for node in ret: if node in t: q += t[node] bft(q, t) print " ".join(ret) bft(parent['-1'], parent)
Vertical Order traversal of a tree from the bottom
#include <iostream> #include <vector> #include <memory> #include <map> using namespace std; typedef map<int, vector<int>> Map; class Tree { class TreeNode { public: unique_ptr<TreeNode> left, right; int el; explicit TreeNode(int _el) : el{_el} {} TreeNode() = default; ~TreeNode() = default; TreeNode(TreeNode &&) = default; TreeNode& operator=(TreeNode &&) = default; TreeNode(TreeNode const& ) = delete; TreeNode& operator=(TreeNode const&) = delete; /* Populates Map in vertical order */ void verticalOrder(Map &m, int distance) const { m[distance].push_back(el); if (left != nullptr) { left->verticalOrder(m, distance - 1); } if (right != nullptr) { right->verticalOrder(m, distance + 1); } } }; unique_ptr<TreeNode> root; /* Example Tree: 1 / \ 2 3 / \ / \ 4 5 6 7 \ \ 8 9 */ public: Tree() { root = unique_ptr<TreeNode>{new TreeNode{1}}; root->left = unique_ptr<TreeNode>{new TreeNode{2}}; root->right = unique_ptr<TreeNode>{new TreeNode{3}}; root->left->left = unique_ptr<TreeNode>{new TreeNode{4}}; root->left->right = unique_ptr<TreeNode>{new TreeNode{5}}; root->right->left = unique_ptr<TreeNode>{new TreeNode{6}}; root->right->right = unique_ptr<TreeNode>{new TreeNode{7}}; root->right->left->right = unique_ptr<TreeNode>{new TreeNode{8}}; root->right->right->right = unique_ptr<TreeNode>{new TreeNode{9}}; } Map verticalOrder() { Map m; if (root != nullptr) { root->verticalOrder(m, 0); } return m; } }; int main(int argc, char const *argv[]) { Tree t; Map m {t.verticalOrder()}; for (auto& p : m) { for (auto el : p.second) { cout << el << " "; } cout << endl; } return 0; }
Given a binary tree, defining a term “complete path sum” as sum of values of nodes lying in a path from root to the leaf; Now given a value ‘k’, prune the nodes for whose complete path sum is smaller than k
#include <stdio.h> struct TreeNode { TreeNode *left, *right; int el; explicit TreeNode(int _el) : left(NULL), right(NULL), el(_el) {} ~TreeNode() { delete left; delete right; left = NULL; right = NULL; } private: TreeNode(const TreeNode&); TreeNode operator=(const TreeNode&); }; typedef TreeNode* Tree; bool pruneTree(Tree t, int k, int sum) { if (t == NULL) return sum < k; sum += t->el; bool l = pruneTree(t->left, k, sum); bool r = pruneTree(t->right, k, sum); if (l) { delete(t->left); t->left = NULL; } if (r) { delete(t->right); t->right = NULL; } return l && r; } Tree pruneTree(Tree t, int k) { if (pruneTree(t, k, 0)) { delete t; return NULL; } return t; } void preorder(Tree t) { if (t == NULL) return; printf("%d ", t->el); preorder(t->left); preorder(t->right); } /* Example Tree: 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 */ Tree newTree() { TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); root->left->left->left = new TreeNode(8); root->left->right->right = new TreeNode(9); root->right->right->left = new TreeNode(10); return root; } int main(int argc, char const *argv[]) { Tree t = newTree(); preorder(pruneTree(t, 17)); printf("\n"); return 0; }
Given the root of the binary tree and a pointer to any random node in that tree, the objective is to print all the nodes at ‘k’ distance from the given random node
#include <stdio.h> struct TreeNode { TreeNode *left, *right; int el; explicit TreeNode(int _el) : left(NULL), right(NULL), el(_el) {} }; typedef TreeNode* Tree; /* prints all the descendent nodes which are k distance from t */ void printNodes(Tree t, int k) { if (t == NULL || k < 0) { return; }; if (k == 0) { printf ("%d", t->el); } else { printNodes(t->left, k - 1); printNodes(t->right, k - 1); } } /* prints all the nodes which are k distance from the given node n returns the distance of t from n */ int printNodes(Tree t, TreeNode *n, int k) { if (t == NULL) return -1; if (t == n) { printNodes(t, k); return 0; } int d; if (t->left) { d = printNodes(t->left, n, k); if (d >= 0) { d++; if (d == k) { printf("%d", t->el); } else { printNodes(t->right, k - d - 1); } return d; } } if (t->right) { d = printNodes(t->right, n, k); if (d >= 0) { d++; if (d == k) { printf("%d", t->el); } else { printNodes(t->left, k - d - 1); } return d; } } return -1; } /* Example Tree: 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 */ Tree newTree() { TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); root->left->left->left = new TreeNode(8); root->left->right->right = new TreeNode(9); root->right->right->left = new TreeNode(10); return root; } int main(int argc, char const *argv[]) { Tree t = newTree(); printNodes(t, t->left->right->right, 4); //prints nodes which are 4 distance away from 9 which are (8, 3) printf("\n"); printNodes(t, t, 3); //prints nodes which are 3 distance away from 1 which are (8, 9, 10) printf("\n"); printNodes(t, t->left->right, 4); //prints nodes which are 4 distance away from 5 which are (6, 7) printf("\n"); return 0; }
Inplace binary tree from spiral order traversal given in a doubly linked list
/* Example: Spiral order traversal: 1-2-3-4-5-6-7-8 Tree: 1 / \ 3 2 / \ / \ 4 5 6 7 \ 8 Algorithm: Using deque, push in one end and pop from other end, when the level changes, change the directions of push and pop */ #include <cstdio> #include <deque> struct DoublyLinkedListNode { int el; DoublyLinkedListNode *left; DoublyLinkedListNode *right; explicit DoublyLinkedListNode(int _el) : el(_el), left(NULL), right(NULL) {} }; typedef DoublyLinkedListNode* DoublyLinkedList; typedef DoublyLinkedListNode* Tree; struct DequeNode { DoublyLinkedListNode *dlNode; int level; DequeNode(DoublyLinkedListNode *_dlNode, int _level) : dlNode(_dlNode), level(_level) {} }; void spiralDoublyLinkedList2BinaryTree(DoublyLinkedList d) { if (!d) return; std::deque<DequeNode> q; q.push_back(DequeNode(d, 0)); DoublyLinkedListNode *right, *left, *iter = d; bool rightToLeft = true; int currentLevel = 0; while(!q.empty()) { DequeNode dqNode = rightToLeft ? q.back() : q.front(); if (dqNode.level != currentLevel) { rightToLeft = !rightToLeft; dqNode = rightToLeft ? q.back() : q.front(); currentLevel = dqNode.level; } if (rightToLeft) { q.pop_back(); } else { q.pop_front(); } DoublyLinkedListNode *tmpDlNode = dqNode.dlNode; if (iter == NULL) { tmpDlNode->right = tmpDlNode->left = NULL; } else { left = iter->right; right = left ? left->right : NULL; if (rightToLeft) { tmpDlNode->left = right; tmpDlNode->right = left; if (left) { q.push_front(DequeNode(left, currentLevel + 1)); } if (right) { q.push_front(DequeNode(right, currentLevel + 1)); } } else { tmpDlNode->left = left; tmpDlNode->right = right; if (left) { q.push_back(DequeNode(left, currentLevel + 1)); } if (right) { q.push_back(DequeNode(right, currentLevel + 1)); } } iter = right; } } } void spiralOrderTraversal(Tree t) { if (!t) return; std::deque<DequeNode> q; q.push_back(DequeNode(t, 0)); bool rightToLeft = true ; int currentLevel = 0; while(!q.empty()) { DequeNode dqNode = rightToLeft ? q.back() : q.front(); if (dqNode.level != currentLevel) { rightToLeft = !rightToLeft; dqNode = rightToLeft ? q.back() : q.front(); currentLevel = dqNode.level; } if (rightToLeft) { q.pop_back(); } else { q.pop_front(); } DoublyLinkedListNode *tmpDlNode = dqNode.dlNode; printf("%d", tmpDlNode->el); if (rightToLeft) { if (tmpDlNode->left) { q.push_front(DequeNode(tmpDlNode->left, currentLevel + 1)); } if (tmpDlNode->right) { q.push_front(DequeNode(tmpDlNode->right, currentLevel + 1)); } } else { if (tmpDlNode->right) { q.push_back(DequeNode(tmpDlNode->right, currentLevel + 1)); } if (tmpDlNode->left) { q.push_back(DequeNode(tmpDlNode->left, currentLevel + 1)); } } } printf("\n"); } DoublyLinkedList makeList(int n) { DoublyLinkedListNode *d = new DoublyLinkedListNode(1); DoublyLinkedListNode *tmpDlNode = d; for (int i = 2; i <= n; ++i) { tmpDlNode->right = new DoublyLinkedListNode(i); tmpDlNode->right->left = tmpDlNode; tmpDlNode = tmpDlNode->right; } return d; } void printList(DoublyLinkedList d) { while (d) { printf("%d", d->el); d = d->right; } printf("\n"); } int main(int argc, char const *argv[]) { DoublyLinkedList d = makeList(8); printf("Before spiralOrderTraversal : "); printList(d); spiralDoublyLinkedList2BinaryTree(d); printf("After spiralOrderTraversal : "); spiralOrderTraversal(d); return 0; }
Print ancestors of a given binary tree node without recursion
#include <stdio.h> #include <stack> struct TreeNode { TreeNode *left, *right; int el; explicit TreeNode(int _el) : left(NULL), right(NULL), el(_el) {} }; typedef TreeNode* Tree; struct StackNode { TreeNode *node; bool visited; explicit StackNode(TreeNode *t) : node(t), visited(false) {} ~StackNode() { delete node; } private: StackNode(const StackNode &); StackNode operator=(const StackNode &); }; void printAncestor(Tree t, int key) { std::stack<StackNode *> stack; if (!t || t->el == key) return; stack.push(new StackNode(t)); TreeNode *tmp = t->left; while (!stack.empty()) { if (tmp) { if (tmp->el == key) { //Key found print the ancestors while (!stack.empty()) { StackNode *s = stack.top(); printf("%d ", s->node->el); stack.pop(); } } else { stack.push(new StackNode(tmp)); tmp = tmp->left; } } else { //Traverse the right subtree, if not traversed StackNode *s = stack.top(); if (!s->visited) { s->visited = true; tmp = s->node->right; } else { stack.pop(); } } } } Tree newTree() { TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); root->left->left->left = new TreeNode(8); root->left->right->right = new TreeNode(9); root->right->right->left = new TreeNode(10); return root; } int main(int argc, char const *argv[]) { Tree t = newTree(); for (int i = 1; i <= 11; ++i) { printf("%d: ", i); printAncestor(t, i); printf("\n"); } return 0; }
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; }
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");
}
}
Effective Programming 