Longest Substring Without Repeat

#include <iostream>

#include <string>

using namespace std;

class LongSubstring {

public:

       LongSubstring();

       ~LongSubstring();

       int getLongestSubstring(string s);

       string out;

       int maxlength;

private:

       bool isMax(int a, int b);

       void map_to_hash(char, int);

       int get_hash_value(char);

       void update(int, int);

       int start;

       int hash[26];

};

bool LongSubstring::isMax(int a, int b){

       if(a > b) return true;

       return false;

}

LongSubstring::LongSubstring() {

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

       {

              hash[i] = -1;

       }

       maxlength = 1;

       start = 0;

}

LongSubstring::~LongSubstring(){

}

int LongSubstring::getLongestSubstring(string s) {

       // Start typing your C/C++ solution below

       // DO NOT write int main() function

       if(s.size() == 0)

              return 0;

      

       int temp = 0;

       map_to_hash(s[0], 0);

       for(int i = 1; i < s.size(); i++){

              if(get_hash_value(s[i]) < temp){

                     map_to_hash(s[i], i);          

              }

              else{

                     temp = get_hash_value(s[i]) + 1;

                     map_to_hash(s[i], i);              

              }            

              if (!isMax(maxlength,  i-temp+1)) update(i, temp);

       }

       out.assign(s,start,maxlength);

       return maxlength;

}

void LongSubstring::update(int cur, int oldpos){

       start = oldpos;

       maxlength = cur-oldpos+1;

}

void LongSubstring::map_to_hash(char ch, int pos){

       hash[ch – ‘a’] = pos;

}

int LongSubstring::get_hash_value(char ch) {

       return hash[ch – ‘a’];

}

void main() {

       string str;

       //char* ch;

       LongSubstring ls;

       str = “abcabcdbb”;

       //ch = &str[0];

       cout<<ls.out<<”      length: “<<ls.getLongestSubstring(str)<<endl;

}

Longest palindrome substring

/***Compute the longest palindrome substring ***/

#include <iostream>

#include <string>

using namespace std;

bool isPalindrom(string str, int start, int end) {

       if (start == end || start > end) return true;

       while (start != end && start < end)

       {

              if (str[start] != str[end]) return false;

              else {

                     start += 1;

                     end -= 1;

              }

       }

       return true;

}

string chk_longPalindrom(string str, int start, int chklen) {

       string outstr;

       int st;

      

       while (chklen != 0)

       {

              st = start;

              for(unsigned int i = 0; i < str.size()-chklen+1; i++) {

                     if (isPalindrom(str, st, st+chklen-1))

                     {

                           outstr.assign(str.begin()+st, str.begin()+st+chklen);

                           return outstr;

                     }

                     st++;

              }

              chklen–;

       }

       return “”;

}

void main() {

       string str = “FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth”;

       string longsub = chk_longPalindrom(str, 0, str.size());

       cout<<“Long sub string is [ “<<longsub<<” ]”<<endl;

}

Compute Adjacent pair

/****

Integer V lies strictly between integers U and W if U < V < W or if U > V > W.

A non-empty zero-indexed array A consisting of N integers is given. A pair of indices (P, Q), where 0 ≤ P < Q < N, is said to have adjacent values if no value in the array lies strictly between values A[P] and A[Q].

For example, in array A such that:

A[0] = 0 A[1] = 3 A[2] = 3

A[3] = 7 A[4] = 5 A[5] = 3

A[6] = 11 A[7] = 1

the following pairs of indices have adjacent values:

(0, 7), (1, 2), (1, 4),

(1, 5), (1, 7), (2, 4),

(2, 5), (2, 7), (3, 4),

(3, 6), (4, 5), (5, 7).

For example, indices 4 and 5 have adjacent values because there is no value in array A that lies strictly between A[4] = 5 and A[5] = 3; the only such value could be the number 4, and it is not present in the array.

Write a function that returns number of adjacent values ****/

#include<iostream>

#include<map>

#include<vector>

#include<algorithm>

using namespace std;

class find_adjacent_pair

{

public:

       find_adjacent_pair();

       ~find_adjacent_pair();

       void print_adjacent_pairs(int*);

private:

       map<int, vector<int>> mymap;

       void map_input(int*);

       void add_new_entry(int, int);

       void compute_self_pair(vector<int>);

       void compute_neighbour_pair(vector<int>, vector<int>);

};

find_adjacent_pair::find_adjacent_pair()

{

       mymap.clear();

}

find_adjacent_pair::~find_adjacent_pair()

{

       mymap.clear();

}

void find_adjacent_pair::print_adjacent_pairs(int* in) {

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

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

       map_input(in);

       //key in the map is already sorted

       its = mymap.begin();

       compute_self_pair(its->second);

       while(its != mymap.end()) {

              itd=its;

              its++;

              compute_self_pair(its->second);

              compute_neighbour_pair(itd->second, its->second);            

       }

}

void find_adjacent_pair::map_input(int* in) {

       int *ptr, val, pos; 

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

       ptr = in;

       pos = 0;

       while (ptr != NULL)

       {

              val = *ptr;

              it = mymap.find(val);

              if (it != mymap.end()) it->second.push_back(pos);

              else add_new_entry(val, pos);

              ptr++;

              pos++;

       }

}

void find_adjacent_pair::add_new_entry(int value, int pos) {

       vector<int> ps;

       ps.push_back(pos);

       mymap.insert(pair<int, vector<int>>(value, ps));

}

void find_adjacent_pair::compute_self_pair(vector<int> ps) {

      

       vector<int> :: iterator it;

       vector<int> :: iterator itv;

       int i = 0;

       for(itv = ps.begin(); i < ps.size()-1; itv++) {

              for(it = itv+1; it != ps.end(); it++)

                     cout << “(“<<*itv<<“, “<<*it<<“)  “;

              i++;

       }

}

void find_adjacent_pair::compute_neighbour_pair(vector<int> ps1, vector<int>ps2) {

       vector<int> :: iterator it1;

       vector<int> :: iterator it2;

       for(it1 = ps1.begin(); it1 != ps1.end(); it1++)

              for(it2 = ps2.begin(); it2 != ps2.end(); it2++)

                     cout<<“(“<<*it1<<“, “<<*it2<<“) “;

}

Min in Array

/***

Find the minimum element in a sorted and rotated array

July 2, 2013

A sorted array is rotated at some unknown point, find the minimum element in it.

Following solution assumes that all elements are distinct.

Examples

Input: {5, 6, 1, 2, 3, 4}

Output: 1

Input: {1, 2, 3, 4}

Output: 1

Input: {2, 1}

Output: 1

***/

#include

using namespace std;

int minInArray(int *a, int low, int high)

 {

       int mid, l,r;

       if(low >= high)

              return a[high];

       // the mid of low and high

       mid=(high + low)/2 ;

      

       if(a[mid] < a[mid-1])

              return a[mid];

       l=minInArray(a,low,mid);

       r=minInArray(a,mid+1,high);

 

       if(l<r)

              return l;

       return r;

}

void main() {

       int min;

       int a[] = {5, 6, 1, 2, 2, 3, 3, 4};

       int sz = sizeof(a) / sizeof(int);

       min = minInArray(a, 0, sz-1);

       cout << min<<endl;

}

Merge Array

/***

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,…cn]

Write a program to merge them like [a1,b1,c1,a2,b2,c2,…an,bn,cn].

PS: Doing without using extra memory would fetch more points

Sample Testcases:

Input #00:

{1,2,3,4,5,6,7,8,9,10,11,12}

Output #00:

{1,5,9,2,6,10,3,7,11,4,8,12}

Explanation:

Here as you can notice, the array is of the form

{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4}

***/

#include

#include

#include

#include

using namespace std;

class mergeArray {

public:

       mergeArray(string *str, int size);

       ~mergeArray();

       void arrangementArray();

       void print();

private:

       map<int, vector<int>> mymap;

       string *mystr;

       int sz;      

};

mergeArray::mergeArray(string *str, int size) {

       mystr = str;

       sz = size;

       //initial map;

       mymap.clear();

}

mergeArray::~mergeArray() {

       mymap.clear();

}

void mergeArray::arrangementArray() {

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

       int id;

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

              string s = mystr[i];

      

              //Note: direct access the number..

              id = atoi(s.c_str()+1);

              it = mymap.find(id);

              if(it != mymap.end()) {

                     it->second.push_back(i);

              } else {

                     vector<int> v;

                     v.push_back(i);

                     mymap.insert(pair<int, vector<int>>(id, v));

              }

       }

}

void mergeArray::print() {

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

       for(it = mymap.begin(); it != mymap.end(); it++) {

              vector<int> v = it->second;

              for(int i = 0; i < v.size(); i++)

                     cout<<mystr[v[i]]<<” “;

       }

       cout<<endl;

}

void main() {

       string str[] = {“a1”,“a2”,“a3”,“a4”,“b1”,“b2”,“b3”,“b4”,“c1”,“c2”,“c3”,“c4”};

       int sz = sizeof(str) / sizeof(string);

       mergeArray mga(str, sz);

       mga.arrangementArray();

       mga.print();

}

Palindrome Integer

/***

a integer is the palindrome?

***/

#include

using namespace std;

bool ispalindrome(int x, int &y) {

       if(x == 0 || y == 0) return true;

      

       if(ispalindrome(x/10, y)) {

              if (x%10 == y%10) {

                     y /= 10;

                     return true;

              }

              else return false;

       } else return false;

}

void main() {

       int n = 135631;

       if (ispalindrome(n, n))

       {

              cout<<“is palindrome”<<endl;

       } else cout<<“no”<<endl;

}

Set Matix Zero

/***

Write a algorithm such that if an element in an M*N matrix is 0, its entire row and column are set to 0.

***/

/**

two sets store the zero column when the first scan. And set zero when the second scan.  **/

#include

#include

using namespace std;

void set0Matrix(int (*a)[5], int sz) {

set col, row;

set::iterator it1;

set::iterator it2;

int i,j;

//first scan

for(i=0; i<sz; i++) {

for(j=0; j<sz; j++) {

if(a[i][j] == 0) {

row.insert(i);

col.insert(j);

}

}

}

//second scan

for(i = 0, it1 = row.begin(); i<sz && it1 != row.end(); i++) {

if(i == *it1) {

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

a[i][j] = 0;

it1++;

} else {

for(j = 0, it2 = col.begin(); j < sz && it2 != col.end(); j++) {

if(j == *it2) {

a[i][j] = 0;

it2++;

}

}

}

}

}

void print(int (*a)[5], int sz) {

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

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

cout<<a[i][j]<<" ";

cout<<endl;

}

}

void main() {

int a[5][5] = {{1,2,0,5,2},{1,2,3,5,2},{1,2,2,5,2},{1,2,4,0,2},{0,2,1,5,2}};

print(a, 5);

cout<<endl;

set0Matrix(a, 5);

print(a, 5);

}

Rotated Matrix

/***
Given an image represented by an N*N matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
int – 4bytes
***/

/***
complexity O(N2)
a[i][j] -> a[j][sz-1-i]
a[j][sz-1-i] -> a[sz-1-i][sz-1-j]
a[sz-1-i][sz-1-j] -> a[sz-1-j][i]
a[sz-1-j][i] -> a[i][j]

(0,0) -> (0,n)
(0,n) -> (n,n)
(n,n) -> (n,0)
(n,0) -> (0,0)

trick: inner loop should be looped less than size..to avoid double rotate for the edge
***/

#include

using namespace std;

void rotate90(int (*a)[4], int sz) {

int temp;
for(int i = 0; i < sz/2; i++) {
for(int j = i; j < sz-2*i-1; j++) {
temp = a[i][j];
a[i][j] = a[sz-1-j][i];
a[sz-1-j][i] = a[sz-1-i][sz-1-j];
a[sz-1-i][sz-1-j] = a[j][sz-1-i];
a[j][sz-1-i] = temp;
}
}
}

void print(int (*a)[4], int sz) {
for(int i=0; i<sz; i++) {
for(int j=0; j<sz; j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}

void main () {
int a[][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
print(a, 4);
cout<<endl;
rotate90(a, 4);
print(a, 4);
}

Replace String

/***
Write a method to replace all spaces in a string with ‘%20’. You may assume that
the string has sufficient space at the end of the string to hold the additional 
characters and that you are given the “true” length of the string.
***/

#include
#include

using namespace std;

void replaceString(string *str) {
string::iterator it;
string str1 = “%20”;
for(it = str->begin(); it != str->end(); it++) {
if(*it == ‘ ‘) {
str->replace(it, it+1, str1);
}
}
}

Test
void main() {
string str = “Xiang is a joke.”;
replaceString(&str);
cout<<str<<endl;

}

is Permutation

***
Given two strings, write a method to decide if one is a permutation of the other.
***/

/***
1. if size is different, return false.
2. next_permutation, chk..
***/

#include
#include
#include

using namespace std;

bool isPermutation(string *str1, string *str2) {
if (str1->size() != str2->size()) return false;
do {
if(*str1 == *str2)
return true;
} while(next_permutation(str2->begin(), str2->end()));

return false;
}

Test
void main() {
string str1 = “happy”;
string str2 = “ahppy”;

if (isPermutation(&str1, &str2))
{
cout<<"yes"<<endl;
} else cout<<"no"<<endl;
}