aman.bansal4u
BAN USERstarting from root
for all neighbours of the current node,
if search(p1)&&search(p1) == TRUE
set node to this neighbour
repeat
else if search(p1)^search(p2) == TRUE
return current node
count the different type of tasks, maintain a vector of number of tasks for the last run. time and space complexity O(tasks)
int neededTime(vector<int>tasks, int cooldown)
{
int slots = 0;
int count = 0;
int n = tasks.size();
for (int i = 0; i < n; i++)
{
if (tasks[i] > count)
count = tasks[i];
}
vector<int> last(count,0);
for (int i = 0; i < n; i++)
{
slots++;
int task = tasks[i]-1;
if (last[task] == 0 || slots - last[task] > cooldown)
last[task] = slots;
else
slots = last[task] = last[task] + cooldown+1;
}
return slots;
}
#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include<cmath>
#include <unordered_map>
#include<memory>
#include<algorithm>
#include<assert.h>
#include <sstream>
using namespace std;
bool issorted(vector<string> words, string ordering)
{
vector<int> alpha(26, 0);
int len = ordering.size();
for (int i = 0; i < len; i++)
alpha[ordering[i] - 'a'] = i+1;
len = words.size();
for (int i = 0; i < len-1; i++)
{
string::iterator s1 = words[i].begin();
string::iterator s2 = words[i + 1].begin();
while (*s1 == *s2)
{
s1++;
s2++;
}
if (s1 != words[i].end() && s2 == words[i + 1].end())
return false;
if (s1 != words[i].end() && s2 != words[i + 1].end())
if (alpha[*s1 - 'a'] != 0 && alpha[*s2 - 'a'] != 0 && alpha[*s1 - 'a'] > alpha[*s2 - 'a'])
return false;
}
return true;
}
//merge interval
#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include<cmath>
#include <unordered_map>
#include<memory>
#include<algorithm>
#include<assert.h>
#include <sstream>
using namespace std;
bool comparator(vector<int> a, vector<int> b)
{
return a[0] < b[0];
}
bool rcomparator(vector<int> a, vector<int> b)
{
return a[0] > b[0];
}
void mergeInterval(vector<vector<int>>& arr)
{
int n = arr.size();
int count = n;
sort(arr.begin(), arr.end(), comparator);
for (int i = 0; i < n-1; i++)
{
if (arr[i][1] >= arr[i + 1][0])
{
arr[i][1] = max(arr[i][1], arr[i + 1][1]);
arr[i + 1][0] = -1;
//arr.erase(arr.begin()+i + 1);
count--;
}
}
sort(arr.begin(), arr.end(), rcomparator);
arr.resize(count);
sort(arr.begin(), arr.end(), comparator);
}
int main() {
vector<vector<int>> arr = { { 6,8 },{ 1,9 },{ 2,4 },{ 4,7 } };
mergeInterval(arr);
int n = arr.size();
for (int i = 0; i < n; i++)
cout << arr[i][0] << " " << arr[i][1] << endl;
return 0;
}
int nonzero(vector<int> & arr)
{
int n = arr.size(), i = 0, j = n - 1;
while (i < j)
{
while (j>=0 && arr[j] != 0)
j--;
while (i<n && arr[i] == 0)
i++;
if (i>j||j<0||i>=n)
return n-(j + 1);
iter_swap(arr.begin() + i, arr.begin() + j);
}
}
void recurse(unordered_map<int, string> s, vector<int> indices, int ind, int n, vector<string>& result, string str)
{
if (ind >= n) return;
if (ind == 0) str.clear();
string temp = s.find(indices[ind])->second;
string::iterator it = temp.begin();
while (it!=temp.end())
{
if (ind == n - 1)
result.push_back(str + *it);
recurse(s, indices, ind + 1, n, result, str + *it);
it++;
}
}
void permutations(unordered_map<int, string> s, vector<int> indices)
{
string temp;
int n = indices.size();
vector<string> result;
recurse(s, indices, 0, n, result, temp);
for (auto i : result)
cout << i << " ";
}
int main() {
vector<int> indices = {1,2, 3};
unordered_map<int, string> strs;
strs.insert({ 1, "ABC" });
strs.insert({ 2, "DE" });
strs.insert({ 12, "X" });
strs.insert({ 3, "PQ" });
permutations(strs, indices);
return 0;
}
//C++
void interleave(vector<vector<int>> grid)
{
int m = grid.size();
int n = 0;
for (int i = 0; i < m; i++)
n = max(n, grid[i].size());
vector<int> result;
result.reserve(m*n);
for (int j = 0; j < n; j++)
for (int i = 0; i < m; i++)
if (j < grid[i].size())
result.push_back(grid[i][j]);
for (auto i:result)
cout << i << " ";
}
void findIsland(vector<string>& grid, int i, int j, int count)
{
int m = grid.size();
int n = grid[0].size();
if (i < 0 || j < 0 || i >= m || j >= n)
return;
if (grid[i][j] != 'X')
return;
grid[i][j] = '0'+count;
findIsland(grid, i - 1, j, count);
findIsland(grid, i + 1, j, count);
findIsland(grid, i, j-1, count);
findIsland(grid, i, j+1, count);
}
int idIslands(vector<string>& grid)
{
int m = grid.size();
int n = grid[0].size();
int count = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 'X')
findIsland(grid, i, j, ++count);
}
}
return count;
}
int greater(int num)
{
string str = to_string(num);
int n = str.size();
int i = 0, j=0;
for(i=n-1; i>-1; i--)
{
for (j=i-1; j>-1; j--)
{
if (str[i] > str[j])
{
str = str.substr(0, j) + str[i] + str.substr(j, i - j) + str.substr(i+1, n-(i+1));
sort(str.begin() + j + 1, str.end());
return stoi(str);
}
}
}
return -1;
}
1. Create a min_heap of just the first element of each array (using priority_queue in C++ STL). O(k) space
- aman.bansal4u February 28, 20212. A hash table contains <element, index of its array> mapping. O(k) space
3. An array contains the index of this element in its respective array. O(k) space
For next(), fetch the top of min heap. look up this element in the hash table and increment the index in the sorted array. add this element to the heap.
For hasnext(), we just need to return <pq>.empty()==false