Given numbers from 1 to N+1, with number being from 1 and N and one of the number being repeatative. Find the repeating element.

Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it? Solution: Just add them all up, and subtract the total you would expect if only 1001...

Read More

Find the smallest window in a string containing all characters of another string

Problem 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). Example S = "ADOBECODEBANC",  T = "ABC", Minimum window is "BANC". Note: If there is no such window in S that covers all characters in T, return the emtpy string "". If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. Solution  Method...

Read More

Deleting a node in singly linked list if it is less than any of the successor nodes

Question : Given a link list of integers delete all nodes which have value smaller than the value of any following node. Example :7 4 5 2 3 6 Output :  7 6 Solution: The solution is to : 1. Reverse the list 6 3 2 5 4 7 2. Delete all the elements which are below the max-till-now element. eg. max-till-now=6....Delete all the elements below 6...till you find another max element = max-till-now = 7 6 7 3. Reverse the left out list again 7 6 ...

Read More

Duplicate removal in Binary Search Tree

#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) ...

Read More

Squeeze all multiple spaces in a string into one space

  #include <stdio.h>void trimspace(char *dst) { const char *src = dst; int tocopy = 1; char c; while((c = *src++)) { if(tocopy) *dst++ = c; tocopy = (c != ' ') || (*src != ' '); } *dst = '\0';}int main() { char s[64]; scanf("%[^\n]c", s); trimspace(s); printf("%s\n", s);}...

Read More

Given a binary tree, print the sum( inclusive of the root ) of sub-tree rooted at each node in in-order

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 -1Output: 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,...

Read More

Leveling sectors in a circle

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...

Read More

To find the longest substring with unique characters in a given string

#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; ...

Read More

Reverse the words in a sentence in place

Problem Given a sentence you have to reverse it word by word. Example That is, given a sentence like this : I am a good boy The in place reverse would be: boy good a am I Solutions Method1 - Reverse the sentence first and then words again First reverse the whole string and then individually reverse the words I am a good boy <-------------> yob doog a ma I <-> <--> <-> <-> <-> boy good a am I Here is some C code to do the same .... /* Algorithm.. 1. Reverse whole sentence first. 2. Reverse each word individually. All...

Read More

Check if singly linked list is Palindrome

There are couple of solution to it : Method 1 - Using the stack A simple solution is to use a stack of list nodes. This mainly involves three steps. Traverse the given list from head to tail and push every visited node to stack. Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node. If all nodes matched, then return true, else false. Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space. Method...

Read More

Spiral printing of a two dimensional array

Given a 2D array, print it in spiral form. Examples See the following examples. 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 Code is : #include <stdio.h> void spiralPrint(int m, int...

Read More

Sum of two long positive numbers (each represented by linked lists)

Code : #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...

Read More