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 numbers were used from that.

Input: 1,2,3,2,4 => 12 as sum
Expected: 1,2,3,4 => 10 as sum

Input - Expected => 2

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 1 ( Brute force solution )
a) Generate all substrings of string1 (“this is a test string”)
b) For each substring, check whether the substring contains all characters of string2 (“tist”)
c) Finally print the smallest substring containing all characters of string2.

Method 2 - Using 2 hashmaps

The main idea is to maintain two pointers which are called begin and end, then use two HashMap to record current status, one record what char need to find, another used to record what has found.

if the two HashMaps show current substring of S has contain all of the chars in T, then we try to shrink our start and end pointer 

Lets see the example

string1 = "acbbaca" and string2 = "aba".
Here, we also use the term "window", which means a contiguous block of characters from string1 (could be interchanged with the term substring).

1. string1 = "acbbaca" and string2 = "aba".
   
   
   
2. The first minimum window is found. Notice that we cannot advance begin pointer as hasFound['a'] == needToFind['a'] == 2. Advancing would mean breaking the constraint.
   
   
3. The second window is found. begin pointer still points to the first element 'a'. hasFound['a'] (3) is greater than needToFind['a'] (2). We decrement hasFound['a'] by one and advance begin pointer to the right.
   
   
4. We skip 'c' since it is not found in string2. Begin pointer now points to 'b'. hasFound['b'] (2) is greater than needToFind['b'] (1). We decrement hasFound['b'] by one and advance begin pointer to the right.
   
   
5. Begin pointer now points to the next 'b'. hasFound['b'] (1) is equal to needToFind['b'] (1). We stop immediately and this is our newly found minimum window.
   
   

The idea is mainly based on the help of two pointers (begin and end position of the window) and two tables (needToFind and hasFound) while traversing string1. needToFind stores the total count of a character in string2 and hasFound stores the total count of a character met so far. We also use a count variable to store the total characters in string2 that's met so far (not counting characters where hasFound[x] exceeds needToFind[x]). When count equals string2's length, we know a valid window is found.

Each time we advance the end pointer (pointing to an element x), we increment hasFound[x] by one. We also increment count by one if hasFound[x] is less than or equal to needToFind[x]. Why? When the constraint is met (that is, count equals to string2's size), we immediately advance begin pointer as far right as possible while maintaining the constraint.

How do we check if it is maintaining the constraint? Assume that begin points to an element x, we check if hasFound[x] is greater than needToFind[x]. If it is, we can decrement hasFound[x] by one and advancing begin pointer without breaking the constraint. On the other hand, if it is not, we stop immediately as advancing begin pointer breaks the window constraint.

Finally, we check if the minimum window length is less than the current minimum. Update the current minimum if a new minimum is found.
Essentially, the algorithm finds the first window that satisfies the constraint, then continue maintaining the constraint throughout.

Code in java

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);
}

References
http://stackoverflow.com/questions/2459653/how-to-find-smallest-substring-which-contains-all-characters-from-a-given-string
http://rleetcode.blogspot.in/2014/01/minimum-window-substring-java.html

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)
        {
            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;
}

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   -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;
}

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 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;
}

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

}

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 the reversing happens in-place.
*/

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;
    }
}

Method2

Another way to do it is, allocate as much memory as the input for the final output. Start from the right of the string and copy the words one by one to the output.
Input : I am a good boy
< --
< -------
< ---------
< ------------
< --------------
Output : boy
: boy good
: boy good a
: boy good a am
: boy good a am I
The only problem to this solution is the extra space required for the output and one has to write this code really well as we are traversing the string in the reverse direction and there is no null at the start of the string to know we have reached the start of the string!. One can use the strtok() function to breakup the string into multiple words and rearrange them in the reverse order later.

Method3

Create a linked list like
| I | -> | < spaces > | -> | am | -> | < spaces > | -> | a | -> | < spaces > | -> | good | -> | < spaces > | -> | boy | -> | NULL |
Now its a simple question of reversing the linked list!. There are plenty of algorithms to reverse a linked list easily. This also keeps track of the number of spaces between the words. Note that the linked list algorithm, though inefficient, handles multiple spaces between the words really well.

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.

1. Traverse the given list from head to tail and push every visited node to stack.
2. Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
3. 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 2 - By reversing the list
This method takes O(n) time and O(1) extra space.

1. Get the middle of the linked list using slow and fast pointer approach, shown here.
2. Reverse the second half of the linked list
3. Check if the first half and second half are identical.
4. Construct the original linked list by reversing the second half again and attaching it back to the first half

Corner cases
When number of nodes are even, the first and second half contain exactly half nodes. The challenging thing in this method is to handle the case when number of nodes are odd. We don’t want the middle node as part of any of the lists as we are going to compare them for equality. For odd case, we use a separate variable ‘midnode’.



Code

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

Method 3 - Recursion
The following code checks if the given singly linked list is a palindrome using recursion.
Time Complexity: O(n)
Space Complexity: O(n)


Java programs

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;
  }

We can also use iterative solution. This is very easy, and hence no code here.

Reference

• http://www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/

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 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);
}

Time Complexity: Time complexity of the above solution is O(mn).

Source : 1 , 

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 *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;

}

Read More