Solution:
Input: 1,2,3,2,4 => 12 as sum
Expected: 1,2,3,4 => 10 as sum
Input - Expected => 2
Data structures, Algorithms, Coding, Technical Interview Questions and much more. (Still work in progress)
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
"acbbaca"
and string2 = "aba"
.public String minWindow(String S, String T) { if (S == null || T == null) { return null; } if (S.length() == 0 && T.length() == 0) { return ""; } if (S.length() < T.length()) { return ""; } HashMap<Character, Integer> needFind = new HashMap<Character, Integer>(); HashMap<Character, Integer> alreadyFind = new HashMap<Character, Integer>(); for (int i = 0; i < T.length(); i++) { alreadyFind.put(T.charAt(i), 0); if (needFind.containsKey(T.charAt(i))) { needFind.put(T.charAt(i), needFind.get(T.charAt(i)) + 1); } else { needFind.put(T.charAt(i), 1); } } int minStart = -1; int minEnd = S.length(); int start = 0; int len = 0; for (int i = 0; i < S.length(); i++) { if (alreadyFind.containsKey(S.charAt(i))) { alreadyFind.put(S.charAt(i), alreadyFind.get(S.charAt(i)) + 1); if (alreadyFind.get(S.charAt(i)) <= needFind.get(S.charAt(i))) { len++; } if (len == T.length()) { while (!needFind.containsKey(S.charAt(start)) || alreadyFind.get(S.charAt(start)) > needFind .get(S.charAt(start))) { if (needFind.containsKey(S.charAt(start))) { alreadyFind.put(S.charAt(start), alreadyFind.get(S.charAt(start)) - 1); } start++; } if (i - start < minEnd - minStart) { minStart = start; minEnd = i; } } } } if (minStart == -1) { return ""; } return S.substring(minStart, minEnd + 1); }
#include <stdio.h> class BinarySearchTree { private: int data; BinarySearchTree *left, *right; public: BinarySearchTree(const int d):data(d), left(NULL), right(NULL){} ~BinarySearchTree() { if(left != NULL) { delete left; } if(right != NULL) { delete right; } } //remove duplicates void removeDup() { if(left) { left->removeDup(); left->remove(data, this); } if(right) right->removeDup(); } void remove(int value, BinarySearchTree *parent) { if(value < data && left) { left->remove(value, this); } else if(value > data && right) { right->remove(value, this); } else remove(parent); } void remove(BinarySearchTree *parent) //remove this node { if(left == NULL && right == NULL) //leaf { ((parent->left == this) ? parent->left :
parent->right) = NULL; } else { if (left != NULL && right != NULL) //two child { right->removeMin(this); return; } else //one child { ((parent->left == this) ? parent->left :
parent->right) = (left != NULL) ? left : right; } } delete this; } void removeMin(BinarySearchTree *root) { BinarySearchTree *p = this, *parent = root; while(p->left) { parent = p; p = p->left; } root->data = p->data; p->remove(parent); //remove p } //constructs bst from an array void construct(const int a[], const int n, const int i) { int j; for(j= i; j < n; ++j) { insert(a[j]); } } void inorder() const { if(left) left->inorder(); printf("%d ", data); if(right) right->inorder(); } void insert(const int el) { if(el <= data) //same element insert in left { if(left) left->insert(el); else { left = new BinarySearchTree(el); } } else { if(right) right->insert(el); else { right = new BinarySearchTree(el); } } } }; int main() { int n; scanf("%d", &n); int i; int a[n]; for(i = 0; i <n; ++i) scanf("%d", a + i); BinarySearchTree *t = new BinarySearchTree(a[0]); t->construct(a, n, 1); BinarySearchTree *prev = NULL; t->inorder(); printf("\n"); t->removeDup(); t->inorder(); printf("\n"); return 0; }
Given a binary tree. Find the sum( inclusive of the root ) of sub-tree rooted at each node. Print the sum in in-order.
E.g.
3
/ \
2 4
/ / \
2 2 -1
Output: 2, 4, 12, 2, 5, -1.
Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode
{
struct TreeNode *left, *right;
int data;
}TreeNode;
typedef TreeNode * Tree;
/*
Two passes with constant space
*/
int printSum(Tree t, int toPrint)
{
if(t == NULL)
return 0;
int lsum = printSum(t->left, toPrint);
int rsum = printSum(t->right, 0);
int sum = lsum + t->data + rsum;
if(toPrint)
printf("%d ", sum);
printSum(t->right, toPrint);
return sum;
}
/*
One pass with n space
*/
int printSum2(Tree t, int a[], int *pos)
{
if(t == NULL)
return 0;
int lsum = printSum2(t->left, a, pos);
(*pos)++;
int p = *pos;
int rsum = printSum2(t->right,a, pos);
return a[p] = lsum + t->data + rsum;
}
/*Utilities*/
inline TreeNode * makeTreeNode(int data)
{
TreeNode *n = calloc(sizeof(TreeNode), 1);
n->data = data;
return n;
}
int main()
{
/*level 0*/
Tree t = makeTreeNode(3);
/*level 1*/
t->left = makeTreeNode(2);
t->right = makeTreeNode(4);
/*level 2*/
t->left->left = makeTreeNode(2);
t->right->left = makeTreeNode(2);
t->right->right = makeTreeNode(-1);
/*print sum*/
printSum(t, 1);
printf("\n");
int a[100];
int pos = -1;
printSum2(t, a, &pos);
int i;
for(i = 0; i <= pos; ++i) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
Problem : How to make the surface of the circular plot level in minimum number of moves
Detail:
The circular plot is divided into sectors. Each of these sectors has a level which is indicated by an integer. The sector can be either above the earth surface, in which case the integer is positive, or below the earth surface, when it will be negative. She can choose two consecutive sectors and increase the level of both the sectors by 1 at a time, which will be counted as one move. The level of sector 1 is increased when either she chooses 1 and 2 or n and 1. If she chooses 1 and 2, it is counted as a move on sector-pair 1; 2 and 3 as sector-pair 2, and so on. She can not decrease the level of the sectors. Please help her find a strategy to make the surface of the circular plot level in minimum number of moves
Input
The first line of the input gives an integer indicating the number of test cases, N. Each test case comprises of a non-zero positive even integer, n on the first line. This is followed by n integers each giving the level of the corresponding sector. A negative number signifies that the level is below the earth surface.
Output
For each test case: The output consists of n integers on a single line giving the number of moves for each sector-pair. If no such strategy is possible, print -1 at every position.
Sample Input
2
4
1 2 4 1
6
1 2 2 1 0 0
Sample Output
-1 -1 -1 -1
0 0 0 1 1 1
Solution
/*
Algo :
1. Find the maximum element in the array
2. Find the minimum element in the array
while minimum < maximum, choose the pair (min, prev(min)) or (min, next(min)) depending on the value of prev(min) and next(min)
update minimum
*/
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int numMoves(int a[], int ret[], int n){
int mx = 0, mn = 0;
for (int i = 1; i < n; ++i ) {
if(a[mx] < a[i])
mx = i;
if(a[mn] > a[i])
mn = i;
}
int m = a[mx], prev, next;
while(a[mn] < m) {
prev = mn == 0 ? n - 1 : mn - 1;
next = mn == n - 1 ? 0 : mn + 1;
if(a[prev] <= a[next]) {
ret[prev]++;
a[prev]++;
a[mn]++;
if(a[prev] > m) return 0;
}else {
ret[next]++;
a[next]++;
a[mn]++;
if(a[next] > m) return 0;
}
copy(a, a + n, ostream_iterator<int>(cout, " "));
cout<<endl;
mn = min_element(a, a + n) - a;
}
return a[mn] == a[mx];
}
int main() {
int a[6] = {2, 1, 1, 0, 0, 2};
int ret[6] = {0};
int success = numMoves(a, ret, 6);
cout<<"\nOutput: \n";
if(success) {
copy(ret, ret + 6, ostream_iterator<int>(cout, " "));
} else{
fill_n(ostream_iterator<int>(cout, " "), 6, -1);
}
cout<<endl;
return 0;
}
#include <stdio.h> #include <string.h> typedef struct { const char *start; size_t len; }Substring; Substring longestSubstring(const char *s){ Substring ret = {s, 1}; Substring cur = {s, 1}; size_t i, len = strlen(s); const char *p = NULL; for(i = 1; i < len; ++i){ p = memchr(cur.start, s[i], cur.len); if(p){ if(cur.len > ret.len) ret = cur; cur.len -= (p - cur.start) + 1; cur.start = p + 1; } cur.len++; } if(cur.len > ret.len) ret = cur; return ret; } int main(){ char s[64]; scanf("%s", s); Substring sub = longestSubstring(s); ((char *)sub.start)[sub.len] = '\0'; printf("%s\n", sub.start); return 0; }
Given a sentence you have to reverse it word by word.
void reverseWords( char * str ) { int i = 0, j = 0; reverseString( str, strlen(str) ); // yob doog a ma I // Found a word or reached the end of sentence while( 1 ) // Loop forever { if( *(str+j) == ' ' || *(str+j) == '\0') { reverseString( str+i, j-i ); i = j+1; } if( *(str+j) == '\0') { break; } j++; } } void reverseString(char* str, int len) { int i, j; char temp; i=j=temp=0; j=len-1; for (i=0; i<j; i++, j--) { temp=str[i]; str[i]=str[j]; str[j]=temp; } }
#include <stdio.h> #include <stdlib.h> typedef struct Node { char c; struct Node *next; }Node; typedef Node *slist; slist reverse(slist s) { if(s->next == NULL) return s; Node *ret = reverse(s->next); s->next->next = s; s->next = NULL; return ret; } Node *makeNode(char c) { Node * tmp = calloc(sizeof(Node), 1); tmp->c = c; return tmp; } void print(slist s) { if(s == NULL) return; printf("%c", s->c); print(s->next); } /* Divide the list into two halves using slowfast algo.. reverse the second part now compare both the parts incase odd number of elements in the list, second part is the big one */ int palindrome(slist s) { Node *prevslow = NULL; Node *slow = s; Node *fast = s; //divide into two parts while(fast!=null && fast->next!=null) { if(fast->next) fast = fast->next->next; else break; prevslow = slow; slow = slow->next; } //odd nodes case if (fast != NULL) { midnode = slow; slow = slow->next; } //slow is second half and prevslow is end of 1st half prevslow->next = NULL; //reverse the second part fast = reverse(slow); //to retain the list slow = fast; //compare two parts while(s && fast->c == s->c) { fast = fast->next; s = s->next; } if((fast == NULL || fast->next == NULL) && s == NULL) printf("Plaindrome\n"); else printf("Not Plaindrome\n"); //retain the list back prevslow->next = reverse(slow); } int main() { slist s = makeNode('s'); s->next = makeNode('a'); s->next->next = makeNode('a'); s->next->next->next = makeNode('a'); s->next->next->next->next = makeNode('s'); palindrome(s); return 0; }
public boolean isPalindrome() { Node node = isPalindrome(head, head); if(node == null) return false; return true; } private Node isPalindrome(Node left, Node right) { if(right == null) { return left; } left = isPalindrome(left, right.next); if(left != null) { boolean palindrome = left.data == right.data ? true : false; if(palindrome) { left = (left.next != null) ? left.next : left; return left; } } return null; }
Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11
#include <stdio.h> void spiralPrint(int m, int n, int a[][n]) { int i, k = 0, l = 0; m--, n--; /* k - min row m - max row l - min column n - max column i - iterator */ while(k <= m && l <= n){ for(i = l; i <= n; ++i) { printf("%d ", a[k][i]); } k++; for(i = k; i <= m; ++i) { printf("%d ", a[i][n]); } n--; if(m >= k) { for(i = n; i >= l; --i) { printf("%d ", a[m][i]); } m--; } for(i = m; i >= k; --i) { printf("%d ", a[i][l]); } l++; } printf("\n"); } int main() { printf("1, 2, 3, 4, 5, 6\n"); printf("7, 8, 9, 10, 11, 12\n"); printf("13, 14, 15, 16, 17, 18\n"); printf("19, 20, 21, 22, 23, 24\n"); printf("25, 26, 27, 28, 29, 30\n"); printf("35, 36, 37, 38, 39, 40\n\n"); int a[6][6] = { {1, 2, 3, 4, 5, 6}, {7, 8, 9, 10, 11, 12}, {13, 14, 15, 16, 17, 18}, {19, 20, 21, 22, 23, 24}, {25, 26, 27, 28, 29, 30}, {35, 36, 37, 38, 39, 40} }; spiralPrint(6, 6, a); }
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
unsigned char c;
struct Node *next;
}Node;
typedef Node *slist;
slist reverse(slist);
Node *makeNode(unsigned char);
/*
*/
slist Sum(slist left, slist right) {
if(!left || !right) {
return left ? left : right;
}
left = reverse(left);
right = reverse(right);
unsigned char carry = left->c + right->c;
slist ret = makeNode(carry % 10);
carry /= 10;
Node *p = left->next;
Node *q = right->next;
Node *r = ret;
while(p || q) {
carry += (p? p->c : 0) + (q ? q->c : 0);
r->next = makeNode(carry % 10);
carry /= 10;
r = r->next;
p = p ? p->next : NULL;
q = q ? q->next : NULL;
}
if(carry)
r->next = makeNode(1);
reverse(left);
reverse(right);
return reverse(ret);
}
/*
utilities
*/
slist reverse(slist s) {
if(s->next == NULL)
return s;
Node *ret = reverse(s->next);
s->next->next = s;
s->next = NULL;
return ret;
}
Node *makeNode(unsigned char c) {
Node * tmp = calloc(sizeof(Node), 1);
tmp->c = c;
return tmp;
}
void print(slist s) {
if(s == NULL) {
printf("\n");
return;
}
printf("%c", s->c + '0');
print(s->next);
}
slist listFromString(const unsigned char *s) {
if(!s || !*s) return NULL;
slist ret = makeNode(*s++ - '0');
Node *tmp = ret;
unsigned char c;
while((c = *s++)) {
tmp->next = makeNode(c - '0');
tmp = tmp->next;
}
return ret;
}
int main()
{
slist left = listFromString("99");
slist right = listFromString("233823");
slist sum = Sum(left, right);
print(sum);
return 0;
}