two_Sum

  vector<int> twoSum(vector<int>& nums, int target) {
     
        map<int, int> k;
        map<int, int>::iterator it;
        int size = nums.size();
     
        for (int i = 0; i < size; i++)
        {
            k.insert(std::pair<int, int>(nums[0], i));
        }
     
        for (int j = 0; j < size - 1; j++)
        {
            it = k.find(target - nums[j]);
            if ( it != k.end())
            {
                return vector<int> (j, it->second);
            }
        }
     
        return vector<int> (-1, -1);
     
    }

Bit manipulation in C

reverseNthBit(unsigned x, unsigned n)
{
unsigned y = 1 << n;
unsigned z = x^y;
printf("The number before %u, the number is %u after reversing bit number %u\n", x, z, n);
}

reverseNthBitInCharArray(char a[], unsigned n)
{
unsigned N = sizeof(a);
unsigned CharNum = n / 8;
unsigned bitNum = n % 8;
a[CharNum] = a[CharNum] ^ (1 << bitNum);
printf("char is %c, CharNum is %u, BitNumber is %u\n", a[CharNum], CharNum, bitNum);
}

reverseBitsinChar(unsigned char a)
{
unsigned char m, n;
unsigned char tmp = 1;
printf ("before reversal char is %u ", a);
for (unsigned i = 0; i < 4; i++)
{
    m = a & (tmp << i);
    n = a & (tmp << (7 - i));
    if ((m > 0  && n > 0) || (m == 0 && n == 0))
    {
        continue;
    }
    else
    {
        if (m > 0)
        {
            a &= (~(1 << i));
            a = (a | (1 << (7-i)));
        }
        else
        {
            a |= ((1 << i));
            a &= (~(1 << (7-i)));
        }
    }
}
printf ("after reversal char is %u \n", a);
}

int main(void) {
//int arr[] = {1, 2, 4};
//int n = sizeof(arr)/sizeof(arr[0]);
//printf ("The odd occurring element is %d ", findOdd(arr, n));
char arr[] = {'a', 'b', 'c', 'd', 'e'};
unsigned int x = 77;
unsigned int n = 2;
reverseNthBit(x, n);
reverseNthBitInCharArray(arr, 30);
reverseNthBitInCharArray(arr, 34);
reverseBitsinChar(23);
reverseBitsinChar(13);
reverseBitsinChar(8);
return 0;
}
// Output: The odd occurring element is 90

C Programming - Confusing stuffs

1) http://stackoverflow.com/questions/3238482/pointer-subtraction-confusion

The idea is that you're pointing to blocks of memory

+----+----+----+----+----+----+
| 06 | 07 | 08 | 09 | 10 | 11 | mem
+----+----+----+----+----+----+
| 18 | 24 | 17 | 53 | -7 | 14 | data
+----+----+----+----+----+----+

If you have int* p = &(array[5]) then *p will be 14. Going p=p-3 would make *p be 17.

So if you have int* p = &(array[5]) and int *q = &(array[3]), then p-q should be 2, because the pointers are point to memory that are 2 blocks apart.

When dealing with raw memory (arrays, lists, maps, etc) draw lots of boxes! It really helps!

Convert integer from one base to another

Given an integer from any base 2 to 16, convert it into another base 2 to 16. So Binary can be converted to hex, hex to octal or decimal to hex or hex to base 3, hexadecimal to base 8 etc etc..

Program/Code is in C/C++/linux/g++

#include <iostream>
#include <inttypes.h>
#include <math.h>

using namespace std;

void convertbase(char *inp, uint16_t inp_base, char *out, uint16_t out_base);
bool validateinp(char *inp, uint16_t inp_base);

main()
{

        char inp[64] = {'\0'};
        char out[64] = {'\0'};

        uint16_t inp_base, out_base;
        cout << "enter the base of input number (between 2 to 16): ";
        cin >> inp_base;

        if (inp_base < 2 || inp_base > 16) {
                cout << "output base not valid." << endl;
                return -1;
        }  

        cout << "enter input number: ";
        cin >> inp;

        bool isInpValid = validateinp(inp, inp_base);

        if (!isInpValid) {
                cout << "input num is not valid." << endl;
                return -1;
        }  

        cout <<"enter the base of output number (between 2 to 16): ";
        cin >> out_base;

        if (out_base < 2 || out_base > 16) {
                cout << "output base not valid." << endl;
                return -1;
        }  

        convertbase(inp, inp_base, out, out_base);   
}

bool validateinp(char *inp, uint16_t base) {
        char *ch = inp;
        uint32_t val;
        while (*ch != '\0') {
                val = (*ch > '9') ? ((*ch >= 'a') ? (*ch - 'a' + 10) : (*ch - 'A' + 10)) : (*ch - '0');
                if (val >= base) {
                       return false;
                }
                if (!((*ch >= 0 && *ch <= '9') || (*ch >= 'A' && *ch <= 'F' ) || (*ch >= 'a' && *ch <= 'f'))) {
                        return false;
                }
                ch++;
        }
        return true;
}

void convertbase(char *inp, uint16_t inp_base, char *out, uint16_t out_base)
{
        uint32_t val = 0, r = 0, i = 0, decimal = 0;
        char ch1, *ch = inp;

        while (*ch != '\0') {
                val = (*ch > '9') ? ((*ch >= 'a') ? (*ch - 'a' + 10) : (*ch - 'A' + 10)) : (*ch - '0');
                decimal = (decimal * inp_base) + val;
                ch++;
        }

        while (decimal > 0) {
                r = decimal % out_base;
                ch1 = (r >= 10) ? (r - 10 + 'A') : ('0' + r);
                out[i++] = ch1;
                decimal = decimal / out_base;
        }
        out[i] = '\0';

        for (r = 0; r < i/2; r++) {
                ch1 = out[r];
                out[r] = out[i - r - 1];
                out[i - r - 1] = ch1;
        }

        cout << "output is " << out << endl;
}

strtok in C/C++ Program - Code implementation - string tokenizer

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

using namespace std;

char* my_strtok(char *inp, char *delim);

main()
{
        char src[128] = {'\0'};
        char delim[16] = {'\0'};

        char *out;

        cout << "enter input string src: ";
        gets(src);
        cout << "enter input string dilimiter: ";
        gets(delim);

        cout << "src is " << src << endl;
        cout << "delimiter is " << delim << endl;

        out  = my_strtok(src, delim);  

        while(out != NULL) {
                cout << "token is " << out << endl;
                out = my_strtok(NULL, delim);
        }  
}

char *my_strtok(char *inp, char *deli) {

        static char *start = NULL;
        char *ch = NULL, *delim = NULL, *ret = NULL;
        uint32_t num_chars = 0;

        if (inp != NULL) {
                start = inp;
        }  

        if (start == NULL || deli == NULL) {
                return NULL;
        }  

        ch = ret = start;

        while (*ch != '\0') {
                delim = deli;
                while(*delim != '\0') {
                        if (*ch == *delim) {
                                *ch = '\0';
                                if (num_chars > 0) {
                                        start = ch+1;
                                        return ret;
                                } else {
                                        ret = ch+1;
                                        break;
                                }
                        }
                        delim++;
                }
                ch++;
                num_chars++;
        }
        if (*ch == '\0') {
                start = NULL;
                if (inp == NULL && strlen(ret) != 0) {
                        return ret;
                }
        }
        return NULL;
}

UEFI vs legacy BIOS

Technical Note: UEFI BIOS vs. Legacy BIOS, Advantech(EN)

https://www.youtube.com/watch?v=dRMIvY7BiL4

System BIOS

BIOS Session 1 - System Memory Map

https://www.youtube.com/watch?v=4hr1aXf2ark 

BIOS Session 2 - Legacy BIOS

https://www.youtube.com/watch?v=D4SESHBT6C0

BIOS Session 3 - HIgh Level Overview of the BOOT flow

https://www.youtube.com/watch?v=dzEoSLfbFuA

UEFI

UEFI Specifications:

http://www.uefi.org/specifications

EDK Project page

http://www.tianocore.org/

Training material:

Online Training:

“Defining Specifications’ Role in Firmware” and Lessons 1-5 of “Implementing the Boot Process.” http://tianocore.sourceforge.net/wiki/UEFI_EDKII_Learning_Dev

I Recommend Downloading the Zip File** for each of the lessons

Latest Training Material:

–             https://sourceforge.net/projects/edk2/files/Training/TrainingMaterial/Lab-Material-FW.zip/download 

–             http://sourceforge.net/projects/edk2/files/Training/TrainingMaterial/Presentations141209.zip/download

–             Contains source code & documents needed for labs

–             Creates C:\FW sub-directory automatically

–             Follow the _UEFI_Lab_Guide.pdf for getting started

Getting Started Writing Application:

http://tianocore.sourceforge.net/wiki/Getting_Started_Writing_Simple_Application

Use Visual Studio command prompt to compile or Run.

Mailing List:

http://sourceforge.net/p/edk2/mailman/?source=navbar

It has a good archive. Search archive is very helpful.

EDK2 Documents:

https://github.com/tianocore/tianocore.github.io/wiki/EDK_II_Documents

Intel UEFI course page including UEFI shell:

https://software.intel.com/en-us/articles/uefi-framwork-course-contents

Basic instructions for using EFI - Whitepaper - Intel

http://download.intel.com/support/motherboards/server/sb/efi_whitepaper.pdf

Installing windows in UEFI mode

https://www.thomas-krenn.com/en/wiki/Installing_Windows_in_UEFI-mode

UEFI network stack getting started guide:

http://sourceforge.net/projects/network-io/files/Documents/EFINetworkStackGettingStarted.pdf

UEFI Driver Wizard Training (Intel, July 2013)

https://www.youtube.com/watch?v=vhmO2_6tGx0

UEFI HII Training (Intel, July 2013)

https://www.youtube.com/watch?v=11PIctg6pz8

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 

The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9

#include <iostream>
#include <vector>
#include <map>
#include <cstdlib>
using namespace std;

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

struct Node* newNode(int key)
{
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->key = key;
    node->left = node->right = NULL;
    return node;
}

void getVerticalOrder(Node* root,int verticalLevel,map< int,vector<int> >& m) {
if(!root) return;
m[verticalLevel].push_back(root->key);
getVerticalOrder(root->left,verticalLevel-1,m);
getVerticalOrder(root->right,verticalLevel+1,m);
}

void printVerticalOrder(Node* root) {
map < int,vector<int> > m;
int verticalLevel = 0;
getVerticalOrder(root,verticalLevel,m);

map< int,vector<int> > :: iterator it;

for(it=m.begin();it!=m.end();it++) {
for(int i=0;i<it->second.size();++i) {
cout<<it->second[i]<<" ";
}
cout<<endl;
}
}

int main() {

Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);
    root->right->right->right = newNode(9);

    cout << "Vertical order traversal is \n";
    printVerticalOrder(root);

    return 0;
}

Non programming questions

1) How smart pointer like provided by Boost work?
2) How memory leak and corruption is detected by tools like Valgrind?
3) How storage allocator like malloc works? Implement a basic one.
3) how deadlock can be detected? Then how to prevent it from happening?
4) How ping works? How telnet works? How SSH works? How FTP works? How http works? what is ICMP? What is NAT? What is PAT? DHCP servers. DNS servers.
5) Just on top level how virtualization softwares like VMware work?
6) Design questions. Like design a LIFT/elevator setup with multiple lifts
7) Setuid. setgid, chroot <--- Unix/linux
8) How Java virtual machine works? How garbage collector works?
9) Active Directory Server, LDAP etc
10) how facebook work? How facebook stores/loads data of a "timeline"? Considering more than billion FB users, billions of pics/videos etc stored in thousands of servers.
11) Memcached - open source caching system. Used by Facebook.

Given an integer find the immediate larger integer which is a palindrome

// #palindrome #C #Programming #String 

#include <stdio.h>
#include <string.h>

typedef unsigned int uint;

uint find_next_palin(uint inp);

main()
{
        uint num;
        printf("enter the number: ");
        scanf("%u", &num);

        uint ret = find_next_palin(num);

        printf("next palindrome is %u\n", ret);
}

uint find_next_palin(uint inp)
{
        char buff[32];
        uint ret, i1 =0, i2 =0, i = 0;

        sprintf(buff, "%d", inp);

        int len = strlen(buff);

        if (len == 1) {
                return inp;
        }

        if (len % 2 == 0) {
                i1 = buff[len/2 -1] - '0';
                i2 = buff[len/2] - '0';

                if (i1 < i2) {
                        buff[len/2 -1] = i1 + '0'+1;
                }
                for (i = 0; i < len/2; i++) {
                        buff[len/2+i] = buff[len/2-i-1];
                }
        } else {
                i1 = buff[len/2 -1] - '0';
                i2 = buff[len/2 +1] - '0';

                if (i1 < i2) {
                        buff[len/2 -1] = i1 + '0'+1;
                }
                for (i = 0; i < len/2; i++) {
                        buff[len/2+i+1] = buff[len/2-i-1];
                }
        }

        sscanf(buff, "%u", &ret);
        return ret;
}                                                                                                                                                                                  

meru genie cab/taxi guys highly unprofessional - review

My experience with them is highly disappointing. I had to go to railway station which is around 20KM from my house. I had booked the can in the afternoon for 6PM same day. As **they had accepted the booking** so cab should have come. But by 6'o clock no SMS or no call. Should not at least they inform the customers if due to some reason cab can't be arranged?

I called them at 6. They told that they are arranging and by 6:15 I will get the cab. Again no call or sms till 6.15. Again I called after 6:15, they said sir its not possible. I said at least you should have informed. He has no answer other that "sorry".

My personal advice don't have the option of this cab service. Very Very unprofessional.

#Bangalore #Cab #Taxi #Railway #Station #Airport #Meru #Genie #india #Review

Sanpdeal very unprofessional

I had ordered an item on snapdeal.com on 3rd july and as per them item would have been delivered by 7th july. Today its 10th july and still I have not seen the item. This is still ok. But the real issue is their customer care guys can’t tell me the status of the item. they just say its on transit. They also say they can’t cancel the item as item is on transit. how on earth they cant find where the item is. As per the policy I am reading as the item cost is less than 1000Rs I wont get the money refunded instead some snapdeal coupons. Full torturousexperience for me. They don’t have toll free number for customer care too. Also customer care guys are as good as nothing. They just read you rulebook that’s all. No help. Their email/facebook support doesn’t work too. You write n number of mails but no one replies.

I have been doing online shoping since last 10 years and have ordered 100s of items maily on ebay and flipkart and this is the worst exp. This was my first time on snapdeal and I tell everyone it is last time.

Read below FAQs on snapdeal. Just to tell these are plain lies.

http://www.snapdeal.com/info/orderStatus

I was never informed that there will be delay in delivery. Here in FAQs they write I will be informed about new date when item will be delivered. But even after 3 days forget email, even customer care guys can’t tell me when the item will be delivered.

here is the update on 14h July. What a unprofessional people they are.

horrible exp with snapdeal. Order something here first time with them and was told will be delivered on 7th. But was not delivered even on 10th. As I needed the time urgently so I wanted to cancel the order. They said item can’t be cancelled unless item is delivered back to them. Today on 14th also item is not delivered to me and when again I am requesting to cancel the delivery they say it cant be cancelled as its still in "transit". Even shamelessly they say they don’t know where the item is? I asked why dont you talk to your courier partner then they say as a customer I should talk to them.

=========================

#Snapdeal #Online #Buy #ebay #flipkart #review #Feedback #Delhi #Bangalore #India

Good questions in Linked List

1. Given a linked list of 0s, 1s and 2s, sort it.
2. Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter.
3. Given a Doubly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Doubly Linked List. The tree must be constructed in-place (No new node should be allocated for tree conversion)
4. Given a Singly Linked List, write a function to delete a given node. Your function must follow following constraints:

               a) It must accept pointer to the start node as first parameter and node to     be  deleted as second parameter i.e., pointer to head node is not global.

               b) It should not return pointer to the head node.

               c) It should not accept pointer to pointer to head node.

5. Write a function detectAndRemoveLoop() that checks whether a given Linked List contains loop and if loop is present then removes the loop and returns true.

6. Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list.

7. Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm.

Example:
Inputs:   1->2->3->4->5->6->7->8->9->NULL and k = 3
Output:   3->2->1->4->5->6->9->8->7->NULL.

8. Give a linked list, sort the list using merge sort

9. Write a function AlternatingSplit() that takes one list and divides up its nodes to make two smaller lists ‘a’ and ‘b’. The sublists should be made from alternating elements in the original list. So if the original list is 0->1->0->1->0->1 then one sublist should be 0->0->0 and the other should be 1->1->1
10. Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5 then the function should change it to 2->1->4->3->5, and if the linked list is 1->2->3->4->5->6 then the function should change it to 2->1->4->3->6->5.
11. Write a recursive function to print reverse of a Linked List
12. Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The”previous” pointers should be stored in the “small” field and the “next” pointers should be stored in the “large” field. The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list
13. Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
14. Nth node from the end of a Linked List
15. Pairwise swap elements of a given linked list

16. You have given a linked list in which each node have three items, 1) data, 2) a next pointer and 3) a random pointer which is pointing to its successor in sorted order. Replicate it  / create a copy of this linked list ? (Need to generate a new linked list in O(n) + O(n) complexity). 

Length of the longest substring without repeating characters

length of the longest substring without repeating characters in a given string

Reverse a string

C/C++ solution:

using namespace std;

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

string reverse(string input);

int main() {
        string input;
        cout << "Enter the string : " ;
        getline(cin, input);
        string output = reverse(input);
        cout << "Revered string :" << output << "\n";
}

string reverse(string input) {
        int len = input.length();
        int i = 0;
        char tmp;
        while(i < len/2) {
                tmp = input[i];
                input[i] = input[len -i -1];
                input[len - i - 1] = tmp;
                i++;
        }  
        return input;
}

Replace blanks with a string in a given string

Problem - Given a string, replace all blanks with "%20"

C/C++ solution


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

using namespace std;

main(int argc, char* argv[]) {

        string input = "i am boy. You are Mrs Smith. ";

        int i  = 0;

        int len = input.size();

        cout << "input len before replace = " << len << endl;

        while (i < len) {
                if ( input[i] == ' ') {
                        input.replace(i, 1, "%20");
                        len = len + 2;
   
                }  

                i++;
        }  

        cout << "input = " << input << endl;

        cout << "input len after replace = " << input.size() << endl;
}

 ./a.out 

input len before replace = 29

input = i%20am%20boy.%20You%20are%20Mrs%20Smith.%20

input len after replace = 43

String rotation

/* Program to check given two strings s1 and s2, if one is rotation of
 * other one. For example student is rotation of dentstu.
 */
#include <iostream>
#include <string.h>

using namespace std;

main() {
        string s1, s2;
   
        cout << "Enter both the strings ";

        cin >> s1;
        cin >> s2;

        string temp = s1+s1;

        if (temp.find(s2) == string::npos) {
                cout << s1 << " and " << s2 << " are not rotation of each other." << endl;
        } else {
                cout << s1 << " and " << s2 << " are rotation of each other." << endl;
        }  

}

$ ./a.out 

Enter both the strings student dentstu

student and dentstu are rotation of each other.

$ ./a.out 

Enter both the strings abc acb

abc and acb are not rotation of each other.

Find element in a sorted Matrix

 Given a matrix (two dimensional array) in which each row and each column is sorted, write a method to find an element in it.

Algorithm - start from bottom left element. If element is same then return row & column. If element is more than the given element to be searched, discard the current row. Otherwise discard the current column.

I am also returning total operations performed if element was found.


C/C++ solution



#include <iostream>

using namespace std;

main() {

        int rows, columns;

        cout << "Enter number of rows & columns : "; 
        cin >> rows;
        cin >> columns;

        int mat[rows][columns];

        cout << "Enter matrix elments : ";

        for (int i = 0; i < rows; i++) {
                for(int j = 0; j < columns; j++) {
                        cin >> mat[i][j];
                }   
        }   

        int start_row = 0, end_row = rows - 1, start_col = 0, end_col = columns - 1;

        cout << " Enter element to be searched ";

        int elemToBeSearched;

        cin >> elemToBeSearched;

        int numberOfOperations = 0;

        while (start_col < columns && end_row >=0) {
                numberOfOperations = numberOfOperations + 2; // conditions in while loop
                if (mat[end_row][start_col] == elemToBeSearched) {
                        cout << "element found at row " << end_row + 1 << " column " << start_col + 1 << endl;
                        cout << "total number of operations to find the element in the given matrix " << numberOfOperations << endl;

                       return 0;

                } else if (mat[end_row][start_col] < elemToBeSearched) {

                        start_col++;

                } else {

                        end_row--;

                }

                numberOfOperations += 3; // increment & condition check in above if and else 

        }

        cout << "Element not found " << endl;

}

$ ./a.out 

Enter number of rows & columns : 50 2

Enter matrix elments : 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

 Enter element to be searched 6

element found at row 3 column 2

total number of operations to find the element in the given matrix 242

$ ./a.out 

Enter number of rows & columns : 4 4 

Enter matrix elments : 1 10 15 25 7 12 17 35 13 28 20 39 21 27 49 60

 Enter element to be searched 25

element found at row 1 column 4

total number of operations to find the element in the given matrix 32

$ ./a.out 

Enter number of rows & columns : 10 10

Enter matrix elments : 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

 Enter element to be searched 81

element found at row 9 column 1

Find sub matrix with maximum sum

Suppose you have an NxN matrix of positive and negative integers. Write a code that finds the sub-matrix with the maximum sum of its elements.

or 

Bit less difficult  variant

Given a m * n matrix and value k. Find k * k matrix within the given matrix whose sum is maximum.

Check if unique characters in a string

C/C++ solution:

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

using namespace std;

main(int argc, char* argv[]) {

        string input ;
        cout << "Input string: ";
        cin >> input;

        bool val[26]; // assuming only english alphabets
        fill_n(val, 26, false);//{ [0 ... 25] = false };

        int len = input.size();

        if (len > 26) {
                cout << "string does not have unique characters." << "\n";
                return 0;
        }  
        while (len >= 0) {
                if(val[tolower(input[len-1]) - 'a'] == true) {
                        cout << "string does not have unique characters." << "\n";
                        break;
                } else {
                        val[tolower(input[len-1]) - 'a'] = true;
                }  
                len--;
           
        }  
        if (len < 0) {
                        cout << "string has all unique characters." << "\n";
        }  
}

Compress String

/* compress the string for example aabbbcccccdeff should become a2b3c5d1e1f2
 * if compress string length remain same as original string then return
 * original string */

using namespace std;

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

main() {

        string input;
        cout << " enter input string to be compressed: ";
        cin >> input;

        string::size_type len = input.size();

        string::size_type orig_len = len;

        string::size_type i = 0;

        int sameCharCount = 1;

        bool in_progress = false;

        char buf[10];

        while (i < len) {
   
                if (input[i] == input[i+1]) {
                        in_progress = true;
                        sameCharCount++;
                } else if (in_progress) {
                        in_progress = false;
                        sprintf(buf, "%d", sameCharCount);
                        input.replace(i-sameCharCount+2, sameCharCount-1, buf);

                        len = len - sameCharCount + 1 + strlen(buf);

                        i = i - sameCharCount + 1 + strlen(buf);

                        sameCharCount = 1;

                } else {

                        input.insert(i+1, "1");

                        i++;

                        len++;

                }

                i = i + 1;

        }

        if (input.size() < orig_len) {

                cout << "changed string: " << input << endl;

        } else {

                cout << "string was not compressed" << endl;

        }

}

$ ./a.out 

 enter input string to be compressed: aaabb

changed string: a3b2

$ ./a.out 

 enter input string to be compressed: ab

string was not compressed

$ ./a.out 

 enter input string to be compressed: acc

string was not compressed

$ ./a.out 

 enter input string to be compressed: b

string was not compressed

$ ./a.out 

 enter input string to be compressed: bc

string was not compressed

$ ./a.out 

 enter input string to be compressed: abc

string was not compressed

$ ./a.out 

 enter input string to be compressed: aaabbbbbbbbbbbbddddddddddd

changed string: a3b12d11

Rotate square matrix by 90 degrees

Rotate a square matrix by 90 degrees

Solution in C/C++ - compiler g++


#include <iostream>

using namespace std;

main() {
        int m = 0;

        cout << "Enter number of rows & columns in square matrix " ;

        cin >> m;

        int mat[m][m];

        cout << "Enter elements \n";
        for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                        cin >> mat[k][l];
                }
        }

        for (int j = 0; j < m/2; j++) {
                for (int i = j; i < m - j -1; i++) {
                        int temp1 = 0, temp2 = 0;
                        temp1 = mat[i][m - j - 1];
                        mat[i][m - j - 1] = mat[j][i];
                        temp2 = mat[m - j - 1][m - i - 1];
                        mat[m - j - 1][m - i - 1] = temp1;
                        temp1 = mat[m - i -1][j];
                        mat[m - i -1][j] = temp2;
                        mat[j][i] = temp1;
                }
        }

        cout << "Elements after 90 degree rotation \n";
        for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                        cout << mat[k][l] << " ";

               }

        }

        cout << endl;

}

Execution result:

Enter number of rows & columns in square matrix 4

Enter elements 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Elements after 90 degree rotation 

13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 

Print a square matrix in spiral order

This is what I have written in C/C++


#include <iostream>
using namespace std;

main() {
        int m = 0;

        cout << "Enter number of rows & columns in square matrix " ;

        cin >> m;

        int mat[m][m];

        cout << "Enter elements \n";
        for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                        cin >> mat[k][l];
                }
        }

        for (int j = 0; j < m/2; j++) { // Do it square by square or layer by layer
                for (int i = j; i < m - j -1; i++) {
                        cout << mat[j][i] << " ";
                }
                for (int i = j; i < m - j -1 ; i++) {
                        cout << mat[i][m - j -1] << " ";
                }
                for (int i = j; i < m - j -1; i++) {
                        cout << mat[m - j - 1][m - i - 1] << " ";
                }
                for (int i = j; i < m - j -1; i++) {
                        cout << mat[m - i -1][j] << " ";
                }
                cout << endl;
        }
        if (m % 2 != 0) { // for odd number of rows & columns
                cout << mat[m/2][m/2] << endl;;
        }
}