Number of operations to make it palindrome

 

Introduction

   Recently found an interesting Warmup problems @HackerRank. It’s simple and doesn’t use much algorithms. But has palindrome logic which is my favorite. :). And it came with a scramble love letter on it. Ok!! Here i come.

The Problem

Courtesy: https://www.hackerrank.com/challenges/the-love-letter-mystery

James got hold of a love letter that his friend Harry has written for his girlfriend. Being the prankster that James is, he decides to meddle with it. He changes all the words in the letter into palindromes.

While modifying the letters of the word, he follows 2 rules:

(a) He always reduces the value of a letter, e.g. he changes 'd' to 'c', but he does not change 'c' to 'd'.
(b) If he has to repeatedly reduce the value of a letter, he can do it until the letter becomes 'a'. Once a letter has been changed to 'a', it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations he carries out to convert a given string into a palindrome.

Input Format
The first line contains an integer T, i.e., the number of test cases.
The next T lines will contain a string each.

Output Format
A single line containing the number of minimum operations corresponding to each test case.

Constraints
1 ≤ T ≤ 10
1 ≤ length of string ≤ 10⁴
All characters are lower cased english alphabets.

The Solution

 

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

int cramble(string str) {
    int size = str.length();
    int count = 0;
    for(int i = 0, j = size-1; i < j; ++i, --j) {
        if(str[i] != str[j]) {
            count += abs(str[i] - str[j]);
        }
    }
    return count;
}

int main()
{
    int T;
    cin>>T;
    for(int i=0; i<T; i++) {
        string love;
        cin>>love;
        cout<<cramble(love)<<endl;
    }    
    return 0;
}

• The solution is simple enough that the code explains it. We compare the first and last letter in string and try to make it equal. Whatever difference we get is taken into count for how many alterations required.
• Note that, we move only until the mid of the string. mid of the string is always equal to itself.
• abs is required since greater letter ASCII code might be in either side, may be on the first or at the last

Hash tables & Dictionaries

 

Introduction

   Many normal developers simply think that hash tables are something to store a key-value pair. That’s it. What are its applications are not known. Some people directly correlate with C++ STL data structures map and hash map. :)

   hash map is faster than map. But why is that?

We have seen many sorting algorithms already. For searching there are neat data structures available which does our job. What is necessary for a best searching algorithm?

• lookup should be O(1)
• insert should also be O(1)
• delete should also be O(1)

In the sorting case, this is never possible. :) But sorting becomes the basis for searching like binary search. But even that won’t give you O(1).

That’s where we go for the dictionaries. Dictionaries or Hash tables, both mean the same. Don’t confuse!!.. I did that.. :)

Dictionaries are nothing but hash tables which gives you lookup of O(1). Just an another name. :D

Concept

   To explain this simply, take a normal English dictionary. You know the word you need to search for. Just take the dictionary and go directly to the first letter page then continue to scan for the second letter. This means, dictionary is organized in such a way that, your lookup is fast.

   Even hash tables are designed so that your lookup is fast. But you should know the key to look for. For example, Take a normal array. You know that you need to get the 5th element from it. then, you simply do array[5]. This means, your lookup is just O(1).

  Plainly, hash tables are expected to work like arrays. Just give a key, you get a value in O(1) time. But note that, in worst case, in hash tables you get O(n) as well. This happens when, your key doesn’t directly get you the value.

  So, hash tables or linked list both give the same O(n) worst case. But practically hash tables need to be designed so that, the hash or the key used to access the table is unique and can identify clearly a single slot in the table.

  What we are discussing till now, is direct access table. You can always find a value with the key given. If key is not unique, we may need to search a linked list. That’s it.

My understandings

• Just remember bucket sort. Hash tables are similar to that.
• Direct access table is impractical. But the best, if the data set to represent is small. Key’s are mostly embedded part of the table and also the data will be part of the table rather than being a list.
• If the key is not unique, it perfectly matches your bucket sort.
• Upcoming articles we will try direct access tables. Hash map has more concepts like collisions, using a cyclic buffer, rehashing etc. But without understanding direct access tables, studying those are useless.. :D

Implement push, pop, min in O(1) performance

 

Introduction

   This is a popular interview question found in a site. (ihas1337code). You need to implement push, pop, min all with just O(1) performance. You can use extra space and you can do any push & pops. Every time you should get the minimum in the stack using the min function.

Concept

  Do do this, you need 2 stacks. One which maintains all the minimums found until then and one which contains all the numbers.

For example, the main stack is.

3

2

10

1

7

5

9

The stack with all the min’s found will be

1

5

9

NaN

 

Now, when you pop from the main stack, make sure that you pop the min stack as well only when the element is equal to the popping element.

So, if we have pop-ed 3,2,10, we will still have 1 as min in the min stack. Remove 1 as well in the main stack, you must remove 1 in the min stack as well. Now, definitely 5 is the min.

  With this approach, you can implement pop, push, min all in O(1).

Code

class PerStack

{

    int arr1[100];

    int arr2[100];

    int top1;

    int top2;

public:

    PerStack() : top1(0), top2(0) {

        arr2[0] = INT_MAX;

    }

    void push(int val)

    {

        arr1[top1++] = val;

        if(val < arr2[top2] )

        {

            arr2[++top2] = val;

        }

    }

    int pop()

    {

        if(arr1[top1] == arr2[top2])

            arr2[top2--] = INT_MIN;

        return arr1[--top1];

    }

    int min() {

        return arr2[top2];

    }

};

void main()

{

    int A[] = {9,5,7,1,10,2,3};

    PerStack n;

    for(int i=0; i<7;i++)

        n.push(A[i]);

    cout<<"minimum : "<<n.min();

}

Rotate an Array–90*

Question
This is a most asked interview question in Microsoft :). Rotate an NxN array 90* clock-wise. Give code for both using extra storage and not using it.

Answer

Using extra storage is easily predictable.
Consider a 3x3 array,
       1    2    3  |   0   i
      4   5    6   |   1
      7   8    9   |   2
     -------------
j –> 0   1    2

The rotated array will look like this:
i 0 | 7      4     1
  1 | 8      5     2
  2 | 9      6     3
      ----------------
j->   2      1      0
You can see how the j is inverted to get the 90* rotation.
Usually, if you put a iteration like this,

for(i=0;i<N;i++) 

{

for(j=0; j<N; j++)

{

// A[i][j]

}

}

You get rows traversed from top –> bottom. The movement is left->right.
In our rotation case, we have to come from bottom –> top. The movement is still left->right.
But to do the above kind of movement we need extra array of equal size.
Code

int** rotate(int** arr, int N)

{

int** b = (int**)calloc(N, sizeof(int));

for(int i=0; i< N; i++)

b[i] = (int*) calloc(N, sizeof(int));

for(int i=N-1; i>=0; i--)

{

for(int j=0; j < N; j++)

{

b[j][(N-1)-i] = arr[i][j];

}

}

return b;

}

void printArray(int** arr, int N)

{

for(int i=0;i<N;i++) {

for(int j=0;j<N;j++)

std::cout<<arr[i][j]<<" ";

std::cout<<std::endl;

}

}

void main()

{

int N=4;

int** rot90;

int c=1;

int **A = (int**)calloc(N, sizeof(int*));

for(int i=0; i<N; i++) {

A[i] = (int*) calloc(N, sizeof(int));

for(int j=0; j<N; j++) {

A[i][j] = c++;

}

}

printArray(A, N);

rot90 = rotate(A, N);

printArray(rot90, N);

}

Important points:

• In above code, b[j][(N-1)-i] is required to copy top->bottom into b[] from bottom->top of arr[]
• (N-1)-i is required to convert the coordinate which moving from bottom to top, to move top to bottom.
• j loop is the main loop which performs the rotation
• the above code cannot be reused for in-place since it replaces the contents of the array

Without space
If we want to do without space, there is one more tricky and tough to guess approach.
The below diagram is for a 4x4 matrix on how to swap array contents in-place to achieve a 90* rotation.

We first do a outer shell swap and then move to the inner circle. Thinking this logic is simple, but putting it in code is not so simple for a dummy.. :)
If you do this in code as well, you might get more tougher questions :D

void printArray(int** arr, int N)

{

for(int i=0;i<N;i++) {

for(int j=0;j<N;j++)

std::cout<<arr[i][j]<<" ";

std::cout<<std::endl;

}

}

void rotate_inplace(int**& arr, int N)

{

//find the number of circles or shells in our matrix

// in a 5x5 matrix, the total circle is 2

// in 3x3 matrix, the total circle is 1

for(int shell=0; shell < N/2; shell++)

{

//for each shell, perform 4-way swap

int i=N-1-shell; // for 4x4, 3

int j=shell; // initial 0

for(int k=j; k<i; k++)

{

int movement = k-j; // initial, 0, movement in a shell

int top = arr[j][k]; // left most corner node

// top <- rotation start node

arr[j][k] = arr[i-movement][j];

// rotation start node <- right most corner node

arr[i-movement][j] = arr[i][i-movement];

// right most corner node <- top right corner

arr[i][i-movement] = arr[k][i];

// top right corner <- top

arr[k][i]=top;

}

}

}

void main()

{

int N=4;

int** rot90;

int c=1;

int **A = (int**)calloc(N, sizeof(int*));

for(int i=0; i<N; i++) {

A[i] = (int*) calloc(N, sizeof(int));

for(int j=0; j<N; j++) {

A[i][j] = c++;

}

}

printArray(A, N);

rot90 = rotate(A, N);

printArray(rot90, N);

rotate_inplace(A, N);

printArray(A, N);

}

Important points:

• We cover a full shell in each iteration. Total shells in a NxN matrix is always N/2
• At each shell we get the min and max size of the shell. i holds the max size, j holds the min size
• k is the iterator which iterates from shell min size to max size. So, for a 4x4, the outer shell will have min size 0, max size as 3. k will run from 0 to 3
• min size and max size also set the corners of the square shell. You think that, the square starts at min size coordinate and ends at max size coordinate.
• As the k loop continues,
  • the top holds the top line of of the square shell always (based on k value)
  • arr[i-movement][j] takes the left side line of the square ( based on movement)
  • arr[i][i-movement] takes the bottom line of the square(based on movement)
  • arr[k][i] takes the right line of the square (based on k value)
• Pictorially, there are 4 points in a square in a 4x4 matrix and all if connected forms another square.
• movement size will get reduced in inner shells.
• The loop exit condition is very important. As we know that the matrix is 4x4, we know that it has total 2 shells. So, we can stop after processing 2 shells. 

 

Without space(easier way)
  EDIT: Just change rows to columns, columns to rows by just swapping. After your swapping is done, you will get an array in which all rows has became columns and all columns would be rows. In this array, swap column-wise first and last. and continue until you reach the middle. You get 90* rotated array as final output. But performance is little bit more with same amount of swaps.

Detect Anagram in a String

 

Question

Detect whether a string is anagram of the another string. The normal brute force way would be like this,

Answer

bool detect_anagram(char* src, char* anagram)

{

    int isrc=0, iana=0;

    while(*src != '\0') {

        char* iter = anagram;

        while(*iter != '\0' && *src != ' ') {

            if(*src == *iter) {

                iana++;

                break;

            }

            iter++;

        }

        if(*src != ' ')

            isrc++;

        src++;

    }

    if(iana == isrc)

        return true;

    else

        return false;

}

void main()

{

    char *src=strdup("eleven plus two");

    char *a = strdup("so plew veluent");

    bool st = detect_anagram(src, a);

}

Important points

• The above approach ignores all space character ‘ ‘ and checks for occurrence of a character in the anagram string. If the number of equal characters is equal to the number of characters in source string, then the string is an anagram!!..
• iter is the iterator for the anagram string
• We iterate until we find a matching character in the iter. If we find one, we just increment the count and break.
• iana will be equal to isrc only when characters in source string = anagram string. This is the invariant we need to use to prove the correctness of the above code

Alternate approaches:

• sort both the strings and check whether both are equal!!
• Take count of characters in original string first and then start decrementing the count when seeing the same in the anagram string. If the count becomes zero for all the recorded character entries, then the string is an anagram. This approach is little bit faster than our above O(N2) approach.