CareerCup

O(n) space, O(nlogn) time

Using min heap(priority queue) and array

#include <iostream>
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
class Point
{
	public: 
		int value;
		int start;
		int end;
};
class myComparator 
{ 
	public: 
	    int operator() (const Point* a, const Point* b) 
	    { 
	        return a->value > b->value; 
	    } 
};
int mod(int a)
{
	return a < 0 ? (-1 * a) : a;
}
void MergeIntervals(int* a, int n, int threshold)
{
	int parent[n];
	for(int i=0; i<n; i++)
	{
		parent[i] = i;
	}
	priority_queue<Point*, vector<Point*>, myComparator> pq;
	int min1 = mod(a[0] - a[1]);
	int min2 = INT_MAX;
	int a1 = 0;
	int a2;
	for(int i=1; i<n-1; i++)
	{
		if(mod(a[i] - a[i+1]) <= min1)
		{
			a2 = a1;
			a1 = i;
			min1 = mod(a[i] - a[i+1]);
			min2 = min1;
		}
		else if(mod(a[i] - a[i+1]) <= min2)
		{
			a2 = i;
			min2 = mod(a[i] - a[i+1]);
		}
	}
	if(a1 == a2+1 || a2 == a1+1)
	{
		int min = INT_MAX;
		for(int i=0; i<n-1; i++)
		{
			int x = mod(a[i] - a[i+1]);
			if(x < min && x != min1 && x != min2)
			{
				a2 = i;
				min = x;
			}
		}
		min2 = min;
	}
	
	cout<<"a1 "<<a1<<endl;
	cout<<"a2 "<<a2<<endl;
	Point* p1 = new Point();
	p1->value = min1;
	p1->start = a1;
	p1->end = a1+1;
	
	Point* p2 = new Point();
	p2->value = min2;
	p2->start = a2;
	p2->end = a2+1;
	
	pq.push(p1);
	pq.push(p2);
	
	while(pq.size() != 1 && pq.top()->value <= threshold)
	{
		Point* p = pq.top();
		pq.pop();
		int startParent = p->start;
		int endParent = p->end;
		a[startParent] = (a[p->start] + a[p->end])/2;
		a[endParent] = a[startParent];
		parent[startParent] = endParent;
		parent[endParent] = startParent;
		
		Point* new_p = new Point();
		int diff1 = INT_MAX;
		int diff2 = INT_MAX;
		if(startParent > 0)
		{
			diff1 = mod(a[startParent-1] - a[startParent]);
		}
		if(endParent < n-1)
		{
			diff2 = mod(a[endParent+1] - a[endParent]);
		}
		if(diff1 != INT_MAX || diff2 != INT_MAX)
		{
			if(diff1 < diff2)
			{
				Point* p_new = new Point();
				p_new->value = diff1;
				p_new->start = parent[startParent-1];
				p_new->end = parent[startParent];
			}
			else
			{
				Point* p_new = new Point();
				p_new->value = diff2;
				p_new->start = parent[endParent];
				p_new->end = parent[endParent+1];
			}
		}
	}
	
	int i =0;
	while(i < n)
	{
		cout<<i<<" "<<parent[i];
		i = parent[i] + 1;
		cout<<endl;
	}
	
}
int main() {
	int n;
	cin>>n;
	int a[n];
	for(int i=0; i<n; i++)
	{
		cin>>a[i];
	}
	int t;
	cin>>t;
	MergeIntervals(a, n, t);
}

O(n) space and time using dp

#include <iostream>
using namespace std;

int FindWays(int n)
{
	int dp[n+1][2];
	
	dp[0][0] = 1;
	dp[0][1] = 0;
	
	dp[1][0] = 1;
	dp[1][1] = 0;
	
	dp[2][0] = 1;
	dp[2][1] = 1;
	
	dp[3][0] = 0;
	dp[3][1] = 1;
	
	for(int i=4; i<=n; i++)
	{
		dp[i][0] = dp[i-1][1] + dp[i-2][1] + dp[i-4][1];
		dp[i][1] = dp[i-1][0] + dp[i-3][0] + dp[i-4][0];
	}

	return dp[n][0] + dp[n][1];
	
}

int main() {
	cout<<FindWays(4);
}

Using DFS

#include <iostream>
#include <limits.h>
#include <algorithm>
#define ROW 2
#define COL 2

using namespace std;

int FindClosestGuardRecurr(char matrix[ROW][COL], int i, int j, bool visited[ROW][COL], int dist)
{
	if(matrix[i][j] == 'G')
	{
		return dist;
	}
	int minDist = INT_MAX;
	visited[i][j] = 1;
	if(i > 0 && (matrix[i-1][j] == '.' || matrix[i-1][j] == 'G') && visited[i-1][j] == 0)
	{
		minDist = min(minDist, FindClosestGuardRecurr(matrix, i-1, j, visited, dist+1));
	}
	if(i < ROW-1 && (matrix[i+1][j] == '.' || matrix[i+1][j] == 'G') && visited[i+1][j] == 0)
	{
		minDist = min(minDist, FindClosestGuardRecurr(matrix, i+1, j, visited, dist+1));
	}
	if(j > 0 && (matrix[i][j-1] == '.' || matrix[i][j-1] == 'G') && visited[i][j-1] == 0)
	{
		minDist = min(minDist, FindClosestGuardRecurr(matrix, i, j-1, visited, dist+1));
	}
	if(j < COL-1 && (matrix[i][j+1] == '.' || matrix[i][j+1] == 'G') && visited[i][j+1] == 0)
	{
		minDist = min(minDist, FindClosestGuardRecurr(matrix, i, j+1, visited, dist+1));
	}
	visited[i][j] = 0;
	return minDist;
}

int** FindClosestGuard(char matrix[ROW][COL])
{
	bool visited[ROW][COL];
	int** result = new int*[ROW];
	for(int i=0; i<ROW; i++)
	{
		result[i] = new int[COL];
	}
	for(int i=0; i<ROW; i++)
	{
		for(int j=0; j<COL; j++)
		{
			visited[i][j] = 0;
		}
	}
	for(int i=0; i<ROW; i++)
	{
		for(int j=0; j<COL; j++)
		{
			if(matrix[i][j] != '#')
			{
				result[i][j] = FindClosestGuardRecurr(matrix, i, j, visited, 0);
				if(result[i][j] == INT_MAX)
				{
					result[i][j] = -1;
				}
			}
			else
			{
				result[i][j] = -1;
			}
		}
	}
	return result;
}

int main() {
	char a[ROW][COL];
	for(int i=0; i<ROW; i++)
	{
		for(int j=0; j<COL; j++)
		{
			cin>>a[i][j];
		}
	}
	int** result = FindClosestGuard(a);
	for(int i=0; i<ROW; i++)
	{
		for(int j=0; j<COL; j++)
		{
			cout<<result[i][j]<<" ";
		}
		cout<<endl;
	}
}

O(n) using longest prefix which is also a suffix KMP algo

#include <iostream>
using namespace std;

int GetValue(int* a, int* b, int m, int n, int index)
{
	if(index < n)
	{
		return b[index];
	}
	else
	{
		return a[index-n];
	}
	
}
void FindSubfixPrefix(int* a, int* b, int m, int n)
{
	int lps[m+n];
	lps[0] = 0;
	for(int i=1; i<m+n; i++)
	{
		int length = lps[i-1];
		while(length > 0)
		{
			if(GetValue(a, b, m, n, length) == GetValue(a, b, m, n, i))
			{
				lps[i] =  length + 1;
				break;
			}
			else
			{
				length = lps[length-1];
			}
		}
		if(length == 0)
		{
			if(GetValue(a, b, m, n, 0) == GetValue(a, b, m, n, i))
			{
				lps[i] = 1;
			}
			else
			{
				lps[i] = 0;
			}
		}
	}
	int result = lps[m+n-1];
	if(result > m || result > n)
	{
		result = m < n ? m : n;
	}
	for(int i=0; i<result; i++)
	{
		cout<<b[i]<<" ";
	}
}
int main() {
	int n;
	int m;
	cin>>m;
	cin>>n;
	int a[m];
	int b[n];
	for(int i=0; i<m; i++)
	{
		cin>>a[i];
	}
	for(int i=0; i<n; i++)
	{
		cin>>b[i];
	}
	FindSubfixPrefix(a, b, m, n);
}

O(n) time complexity, O(1) space

#include <iostream>
using namespace std;

string FindLargestSubString(string s)
{
	int length = s.length();
	int i = 0;
	int j = i+1;
	while(j<length)
	{
		if(s[j] > s[i])
		{
			i = j;
			j = j+1;
		}
		else if(s[j] < s[i])
		{
			j = j+1;
		}
		else
		{
			int k = i;
			int l = j;
			while(l < length)
			{
				if(s[k] > s[i])
				{
					i = k;
					j = l;
					break;
				}
				else if(s[l] > s[i])
				{
					i = l;
					j = l+1;
					break;
				}
				else if(s[k] > s[l])
				{
					j = l+1;
					break;
				}
				else if(s[k] < s[l])
				{
					i = j;
					j = l+1;
					break;
				}
				else
				{
					l++;
					k++;
				}
			}
			
			if(l == length)
			{
				j = l;
				break;
			}
		}
	}
	return s.substr(i);
}

int main() {
	string s;
	cin>>s;
	cout<<FindLargestSubString(s);
}

time: O(k) space: O(k) using recursion

#include <iostream>
using namespace std;

int FindValue(int k, int j)
{
	if(k == 0)
	{
		return 0;
	}
	int x = FindValue(k-1, j/2);
	if(x == 0)
	{
		if(j%2 == 0)
		{
			return 0;
		}
		return 1;
	}
	else
	{
		if(j%2 == 0)
		{
			return 1;
		}
		return 0;
	}
}

int main() {
	cout<<FindValue(3, 4);
}

Using dp: time O(m*m*n*n), space(m*n*n)

#include <iostream>
using namespace std;

class myClass
{
	int** matrix;
	int M; 
	int N;
	public :
	myClass()
	{
		cin>>M;
		cin>>N;
		matrix = new int*[M];
		for(int i=0; i<M; i++)
		{
			matrix[i] = new int[N];
		}
		for(int i=0; i<M; i++)
		{
			for(int j=0; j<N; j++)
			{
				cin>>matrix[i][j];
			}
		}
	}
	
	int FindArea(int budget)
	{
		int dp1[M][N][N];
		int dp2[M][N][N];
		int dp3[M][N][N];
		int maxArea = 0;
		for(int i=0; i<M; i++)
		{
			for(int j=0; j<N; j++)
			{
				dp1[i][j][j] = matrix[i][j];
			}
		}
		for(int i=0; i<M; i++)
		{
			for(int j=0; j<N; j++)
			{
				for(int k=j+1; k<N; k++)
				{
					dp1[i][j][k] = dp1[i][j][k-1] + dp1[i][k][k];
				}
			}
		}
		for(int i=0; i<M; i++)
		{
			for(int j=0; j<N; j++)
			{
				for(int k=j; k<N; k++)
				{
					dp2[i][j][k] = dp1[i][j][k];
					//cout<<dp2[i][j][k]<<endl;
					if(dp2[i][j][k] <= budget && maxArea < (k-j+1))
					{
						maxArea = k-j+1;
					}
				}
			}
		}
		int count = 1;
		for(int i=0; i<M-count; i++)
		{
			for(int j=0; j<N; j++)
			{
				for(int k=j; k<N; k++)
				{
					dp3[i][j][k] = dp2[i][j][k] + dp1[i+count][j][k];
					if(dp3[i][j][k] <= budget  && maxArea < (count + 1)*(k-j+1))
					{
						maxArea = (count + 1)*(k-j+1);
					}
				}
			}
			for(int l=0; l<M-count; l++)
			{
				for(int j=0; j<N; j++)
				{
					for(int k=j; k<N; k++)
					{
						dp2[l][j][k] = dp3[l][j][k];
					}
				}
			}
			count++;
		}
		
		return maxArea;
	}
};

int main() {
	myClass* obj = new myClass();
	cout<<obj->FindArea(11);
}

O(nlogn) using binary search

#include <iostream>
using namespace std;

int FindIndex(int* array, int mid)
{
	if(array[mid-1] == array[mid] && array[mid] == array[mid+1])
	{
		return mid+1;
	}
	else if(array[mid-1] == array[mid])
	{
		return mid;
	}
	else if(array[mid] == array[mid+1])
	{
		return mid+1;
	}
	else
	{
		return -1;
	}
}

int FindLastIndexOfDuplicate2(int* array, int start, int end)
{
	if(start == end)
	{
		return -1;
	}
	if(start+1 == end)
	{
		return (array[start] == array[end] ? end : -1);
	}
	else if(start+2 == end)
	{
		return FindIndex(array, start+1);
	}
	else if(start+3 == end)
	{
		int x = FindIndex(array, start+2);
		return x == -1 ? FindIndex(array, start+1) : x;
	}
	int mid = (end-start)/2 + start;
	if(array[mid-1] == array[mid] && array[mid] == array[mid+1])
	{
		return FindLastIndexOfDuplicate2(array, mid, end);
	}
	else if(array[mid-1] == array[mid])
	{
		return FindLastIndexOfDuplicate2(array, mid-1, end);
	}
	else if(array[mid] == array[mid+1])
	{
		return FindLastIndexOfDuplicate2(array, mid, end);
	}
	else
	{
		return FindLastIndexOfDuplicate2(array, mid+1, end);
	}
}

int FindLastIndexOfDuplicate(int array[], int length)
{
	return FindLastIndexOfDuplicate2(array, 0, length-1);
}
int main() {
	int n;
	cin>>n;
	int A[n];
	for(int i=0; i<n; i++)
	{
		cin>>A[i];
	}
	cout<<FindLastIndexOfDuplicate(A, n);
	return 0;
}

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

struct TreeNode
{
	int val;
	vector<TreeNode*> children;
	TreeNode(int val)
	{
		this->val = val;
	}
};

bool IsMirrorImage(TreeNode* t1, TreeNode* t2)
{
	if(t1 == NULL && t2 == NULL)
	{
		return true;
	}
	if(t1 == NULL || t2 == NULL)
	{
		return false;
	}
	bool isMirrorImage = t1->val == t2->val && (t1->children).size() == (t2->children).size();
	int size = (t1->children).size();
	for(int i=0; isMirrorImage == true && i < size; i++)
	{
		isMirrorImage = IsMirrorImage((t1->children)[i], (t2->children)[size-i-1]);
	}
	return isMirrorImage;
}
int main() {
	TreeNode* root1 = new TreeNode(1);
	root1->children.push_back(new TreeNode(2));
	root1->children.push_back(new TreeNode(3));
	TreeNode* root2 = new TreeNode(1);
	root2->children.push_back(new TreeNode(3));
	root1->children.push_back(new TreeNode(2));
	cout<<IsMirrorImage(root1, root2);
}

Source : abc. Target : acb. The answer is 2.
abc => cab => acb, 2 swaps required.
Your solution give 3

Source : abc. Target : acb. The answer is 2.
abc => cab => acb, 2 swaps required.

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
	int length;
	cin>>length;
	int n;
	cin>>n;
	int a[n+2];
	a[0] = 0;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
	}
	a[n+1] = length;
	int dp[n+2][n+2];
	for(int i=0; i<=n; i++)
	{
		dp[i][i+1] = 0;
	}
	for(int l=2; l<=length; l++)
	{
		for(int i=0; i<n+1-l+1; i++)
		{
			int j = i+l;
			int min = INT_MAX;
			for(int k = i+1; k<j; k++)
			{
				int x = dp[i][k] + dp[k][j] + a[j] - a[i];
				if(x < min)
				{
					min = x;
				}
			}
			dp[i][j] = min;
		}
	}
	cout<<dp[0][n+1];
}

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int FindMinimum(int i, string s1, string& s2)
{
if(s1[i] == s2[i])
{
return 0;
}
int length = s1.length();
string final;
int MIN = INT_MAX;
for(int j=0; j<length; j++)
{
if(s1[j] != s2[j] && s1[i] == s2[j])
{
string dummy = s2;
dummy[j] = s2[i];
dummy[i] = s1[i];
int min = FindMinimum(j, s1, dummy);
if(min < MIN)
{
MIN = min;
final = dummy;
}
}
}
s2 = final;
return MIN + 1;
}
int main() {
string s1;
string s2;
cin>>s1;
cin>>s2;
int count = 0;
int length = s1.length();
for(int i=0; i<length; i++)
{
count += FindMinimum(i, s1, s2);
}
cout<<count;
}

#include <iostream>
using namespace std;

string GetPeriodicString(string s)
{
	int length = s.length();
	int* lps = new int[length];
	lps[0] = 0;
	for(int i=1; i<length; i++)
	{
		int len = lps[i-1];
		while(len > 0)
		{
			if(s[i] == s[len])
			{
				lps[i] = len + 1;
				break;
			}
			else
			{
				len = lps[len-1];
			}
		}
		if(len == 0)
		{
			if(s[i] == s[0])
			{
				lps[i] = 1;
			}
			else
			{
				lps[i] = 0;
			}
		}
	}
	int x = length - lps[length-1];
	for(int i=length-x-1; i>=x; i-=x)
	{
		if(i+1-lps[i] != x)
		{
			return s;
		}
	}
	return s.substr(0, x);
}
int main() {
	string s;
	cin>>s;
	cout<<GetPeriodicString(s);
}