Linkedin Interview Question SDE1s
Team: Hacker rank test
Country: United States
/* Extract all integers from string */
#include <iostream>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
string getSubString(string str, map<char, int> &m, int k)
{
int needed = k;
int count = 0;
int start = 0;
int end = 1;
int minLen = str.size()+1;
int minStart = 0;
int minEnd = 0;
if (m[str[start]] == 0) {
count++;
}
while(end != str.size()) {
if (m[str[end]] == 0) {
count++;
}
while(needed <= count && start < end) {
if (m[str[start]] == 1){
start++;
}
else if (needed < count && m[str[start]] == 0) {
count--;
start++;
}
else {
break;
}
}
if(needed == count && minLen > (end - start + 1)) {
minLen = (end - start + 1);
minStart = start;
minEnd = end;
}
end++;
}
return str.substr(minStart, (minEnd - minStart +1));
}
// Driver code
int main()
{
string str = "abcdebdac";
map<char, int> m;
m['a'] = 1;
m['b'] = 0;
m['c'] = 1;
m['d'] = 0;
m['e'] = 1;
m['f'] = 1;
m['g'] = 1;
m['h'] = 1;
m['i'] = 1;
m['j'] = 1;
m['k'] = 1;
m['l'] = 1;
cout << getSubString(str, m, 2) << endl;
return 0;
}
/* Extract all integers from string */
#include <iostream>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
string getSubString(string str, map<char, int> &m, int k)
{
int needed = k;
int count = 0;
int start = 0;
int end = 1;
int minLen = str.size()+1;
int minStart = 0;
int minEnd = 0;
if (m[str[start]] == 0) {
count++;
}
while(end != str.size()) {
if (m[str[end]] == 0) {
count++;
}
while(needed <= count && start < end) {
if (m[str[start]] == 1){
start++;
}
else if (needed < count && m[str[start]] == 0) {
count--;
start++;
}
else {
break;
}
}
if(needed == count && minLen > (end - start + 1)) {
minLen = (end - start + 1);
minStart = start;
minEnd = end;
}
end++;
}
return str.substr(minStart, (minEnd - minStart +1));
}
// Driver code
int main()
{
string str = "abcdebdac";
map<char, int> m;
m['a'] = 1;
m['b'] = 0;
m['c'] = 1;
m['d'] = 0;
m['e'] = 1;
m['f'] = 1;
m['g'] = 1;
m['h'] = 1;
m['i'] = 1;
m['j'] = 1;
m['k'] = 1;
m['l'] = 1;
cout << getSubString(str, m, 2) << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// void c_p_c()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("inputmst.txt", "r", stdin);
// freopen("outputmst.txt", "w", stdout);
// #endif
// }
int main()
{
// c_p_c();
string s,num;
cin>>s>>num;
int k;
cin>>k;
vector<int> v(26,0);
int m=0;
for(char ch:num)
{
int val=ch-'0';
v[m]=val;
m++;
}
vector<int> nums(s.length(),0);
m=0;
for(char ch:s)
{
nums[m]=v[ch-'a'];
m++;
}
int ans=0;
int count=0;
int st=0;
for(int i=0;i<s.length();i++)
{
count+=nums[i];
while(i-st+1-count>k)
{
count-=nums[st++];
}
ans=max(ans,i-st+1);
}
cout<<ans<<endl;
}
#include<bits/stdc++.h>
using namespace std;
int solve(string str, unordered_map<char, int> umap, int k){
int count = 0, maxSize = 0;
int i = 0, j = 0;
while(j < str.length()){
if(umap[str[j]] == 1){
count++;
}
while(count > k and i <= j){
if(umap[str[i]] == 1){
count--;
}
i++;
}
maxSize = max(maxSize, j - i + 1);
j++;
}
return maxSize;
}
int main(){
string p, q;
cin>>p;
cin>>q;
int k;
cin>>k;
unordered_map<char, int> umap;
for(int i = 0; i < 26; i++){
if(q[i] == '0'){
umap[i + 'a']++;
}
}
cout<<solve(p, umap, k)<<endl;
}
O(n) solution using sliding window technique...
s = input()
chVal = input()
l = []
k = int(input())
for i in s:
l.append(chVal[ord(i)-ord('a')])
i = 0
for j in range(len(l)):
if (l[j] == '0'): k -= 1
if (k < 0):
if l[i] == '0':
k += 1
i += 1
print(j+1-i)
#include <bits/stdc++.h>
using namespace std;
int substring(string p, string q, int k){
string normal;
int maxlength = INT_MIN, currlength = 0;
for(char i : p){
if (q[i - 'a'] == '0' && normal.find(i) == string::npos)
normal.push_back(i);
}
int temp, cnt = 0;
for(int i=0;i<p.size()-k;i++){
temp = i;
cnt = 0;
currlength = 0;
while (temp < p.size()){
if (normal.find(p[temp]) != string::npos){
cnt++;
currlength++;
}else
currlength++;
if (cnt == k)
break;
temp++;
}
maxlength = max(maxlength,currlength);
}
return maxlength;
}
int main() {
string p,q;
int k;
cin>>p>>q;
// cout<<"Enter k: ";
cin>>k;
cout<<substring(p,q,k);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
class SpecialSubstring
{
public:
int getSpecialSubstring(string str, string bitString, int k)
{
// Simple Sliding Window Technique.
int n = str.length();
int len = 0;
int i = 0;
int cnt = 0;
for (int j = 0; j < n; j++)
{
int pos = str[j] - 'a';
if (bitString[pos] == '0')
cnt++;
while (cnt > k and i < n)
{
pos = str[i] - 'a';
if (bitString[pos] == '0')
cnt--;
i++;
}
len = max(len, j - i + 1);
}
return len;
}
};
int main()
{
SpecialSubstring specialSubstring;
cout << specialSubstring.getSpecialSubstring("normal", "00000000000000000000000000", 1) << endl;
cout << specialSubstring.getSpecialSubstring("giraffe", "01111001111111111011111111", 2) << endl;
return 0;
}
- Arpit Baheti March 05, 2020/* Extract all integers from string */ #include <iostream> #include <sstream> #include <bits/stdc++.h> using namespace std; string getSubString(string str, map<char, int> &m, int k) { int needed = k; int count = 0; int start = 0; int end = 1; int minLen = str.size()+1; int minStart = 0; int minEnd = 0; if (m[str[start]] == 0) { count++; } while(end != str.size()) { if (m[str[end]] == 0) { count++; } while(needed <= count && start < end) { if (m[str[start]] == 1){ start++; } else if (needed < count && m[str[start]] == 0) { count--; start++; } else { break; } } if(needed == count && minLen > (end - start + 1)) { minLen = (end - start + 1); minStart = start; minEnd = end; } end++; } return str.substr(minStart, (minEnd - minStart +1)); } // Driver code int main() { string str = "abcdebdac"; map<char, int> m; m['a'] = 1; m['b'] = 0; m['c'] = 1; m['d'] = 0; m['e'] = 1; m['f'] = 1; m['g'] = 1; m['h'] = 1; m['i'] = 1; m['j'] = 1; m['k'] = 1; m['l'] = 1; cout << getSubString(str, m, 2) << endl; return 0; }