Find an element in a two dimensional array in O(n)

#include <iostream>
using namespace std;

int search(int a[4][4], int n, int x){
int i = 0;
int j = n - 1;

while( i < n && j >= 0){
if(a[i][j] == x){
cout<<"Found at "<<i<<" "<<j;
return 1;
} else if(a[i][j] > x){
j--;
} else {
i++;
}
}
}

int main()
{
int mat[4][4] = { {10, 20, 30, 40},
                    {15, 25, 35, 45},
                    {27, 29, 37, 48},
                    {32, 33, 39, 50}};
search(mat, 4, 31);
 
return 0;
} 

Anagrams of a string

import java.util.*;
import java.lang.*;
import java.io.*;

class Anagram
{

public static String swap(String s, int i, int j){
char[] carr = s.toCharArray();
char tmp = carr[i];
carr[i] = carr[j];
carr[j] = tmp;
return new String(carr);
}

static int count = 0;

public static void anagram(String s, int start, int end){
if(start == end){
System.out.println(s);
count++;
return;
}

for(int i = start;i<=end; i++){
s = swap(s, start, i);
anagram(s, start+1, end);
s = swap(s, start, i);
}
}

public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
String s = "ABCD";
anagram(s, 0, s.length() -1 );
System.out.println(count);
}
}

Trie Implementation with Map

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {
    private static final Scanner scanner = new Scanner(System.in);

    private static class HashedTrie {
        private class Trie{
            int count;
            Map<Character, Trie> children;
            Boolean isLeafNode;

            public Trie() {
                count = 0;
                isLeafNode = false;
                children = new HashMap<Character, Trie>();
            }

            public Trie setChild(char ch){
                return children.put(ch, new Trie());
            }

            public Trie getChild(char ch){
                return children.get(ch);
            }

            public int getCount(){
                return count;
            }

            public void setCount(int count){
                this.count = count;
            }

            public Boolean isLeafNode(){
                return isLeafNode;
            }

            public void setLeafNode(Boolean isLeafNode){
                this.isLeafNode = isLeafNode;
            }
        }
     
        Trie trie;
     
        public HashedTrie(){
            trie = new Trie();
        }
     
        public Boolean InsertString(String s){
            Trie head = trie;
            head.setCount(head.getCount() + 1);
            for(char sChar: s.toCharArray()){
                if(head.getChild(sChar) == null){
                    head.setChild(sChar);
                }
                head = head.getChild(sChar);
                head.setCount(head.getCount() + 1);
            }
         
            head.setLeafNode(true);
            return true;
        }
     
        public int partialSearch(String s){
            Trie head = trie;
            for(char ch : s.toCharArray()){
                head = head.getChild(ch);
             
                if(head == null){
                    return 0;
                }
            }
         
            return head.getCount();
        }
    }
 
    public static void main(String[] args) {
        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
        List<String> list = new ArrayList();
        HashedTrie trie = new HashedTrie();
     
        for (int nItr = 0; nItr < n; nItr++) {
            String[] opContact = scanner.nextLine().split(" ");

            String op = opContact[0];

            String contact = opContact[1];
         
            if(op.contains("add")) {
                trie.InsertString(contact);
            }
         
            if(op.contains("find")){
                int count = trie.partialSearch(contact);
                System.out.println(count);
            }
        }

        scanner.close();
    }
}

Rotating an array by n

    static int gcd(int a , int b){
        if(b == 0){
            return a;
        } else {
            return gcd(b, a%b);
        }
    }
   
    // Complete the rotLeft function below.
    static int[] rotLeft(int[] a, int d) {
        if(a.length <= 1) {
            return a;
        }
       
        int length = a.length;
       
        for(int i = 0 ; i < gcd(length, d) ; i++) {
            int temp = a[i];
            int j = i;
            while(true) {
                int k = j + d;
                if(k >= length) {
                    k = k - length;
                }
               
                if(k == i) {
                    break;
                }
                a[j] = a[k];
                j=k;
            }
            a[j] = temp;
        }
       
        return a;
    }

Reverse all words in a string

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

using namespace std;

void reverse(char * str, int start, int end) {

    while(start < end) {
        char tmp =  *(str + start);
        str[start++] = str[end];
        str[end--] = tmp;
    }
}

void reverse_words(char * str) {
    int start = 0;
    int end = 0;
    int len = strlen(str);

    start = 0;
    for (int i = 0; i <= len; i++) {
        if( *(str + i) != ' ' && *(str + i) != 0){
            continue;
        }
        end = i - 1;
        reverse(str, start, end);
        start = i + 1;
    }
}

int main()
{
    char str[] = "This is a string to be reversed";

    std::cout<<"\n The original string is : " << str;

    reverse_words(str);

    std::cout <<"\n The string after reversing is : " << str;
    std::cout<<"\n";

    return 0;
}

Replace all spaces in a string with "%20".Assume the string is big enough to accomodate extra characters

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

using namespace std;

void replace_str(char * str) {

    int count = 0;
    int len = strlen(str);

    for (int i = 0 ; i < strlen(str) ; i++) {
        if(str[i] == ' ') {
            count++;
        }
    }

    int newlen = count*2 + len;

    while(len >= 0) {

        if(str[len] != ' ') {
            str[newlen] = str[len];
            newlen--;
            len--;
        } else {
            str[newlen]='0';
            str[newlen - 1]='2';
            str[newlen - 2]='%';
            newlen -= 3;
            len--;
        }
    }

    cout<<"\n The new string is : "<<str<<endl;
}

int main()
{
    char str[100] = "This is a string";

    replace_str(str);

    return 0;
}

Check is a tree is a binary search tree

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node * newNode(int data)
{
  // Allocate memory for new node
  struct Node * node = (struct Node*)malloc(sizeof(struct Node));

  // Assign data to this node
  node->data = data;

  // Initialize left and right children as NULL
  node->left = NULL;
  node->right = NULL;
  return(node);
}

int isLeftSubtreeLesser(Node * root, int data) {
if (root->data > data) {
return 0;
}
if (isLeftSubtreeLesser(root->left, data) && isLeftSubtreeLesser(root->right, data))
return 1;

return 0;
}

int isRightSubtreeGreater(Node * root, int data) {
if (root->data <= data) {
return 0;
}
if (isRightSubtreeGreater(root->left, data) && isRightSubtreeGreater(root->right, data))
return 1;

return 0;
}

int isBinarySearchTree (Node * root) {
if (root == NULL) {
return 1;
}

if (isLeftSubtreeLesser(root->left, root->data) && isRightSubtreeGreater(root->right, root->data)
&& isBinarySearchTree(root->left) && isBinarySearchTree(root->right)){
return 1;
} else {
return 0;
}
}

int main() {

struct Node *root = newNode(1);

  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);

isBinarySearchTree(root);
return 0;
}