Practo Interview Question SDE1s
Country: India
Interview Type: Written Test
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
struct compare
{
bool operator()(const string& s1,const string& s2)
{
return s1.length()<s2.length();
}
};
int find_length(string arr[], int n)
{
int* temp = new int[n+1];
for(int i=0; i<n+1; i++)
temp[i] = 1;
sort(arr, arr+n, compare());
map<string, int> m;
for(int i=0; i<n; i++)
{
int p = arr[i].length();
string q = arr[i];
m[q]=i+1;
for(int j=0; j<p; j++)
{
char c= q[j];
q.erase(q.begin()+j);
if(m[q]!=0 && temp[m[q]]+1>temp[i+1])
temp[i+1] = temp[m[q]]+1;
q.insert(j,1,c);
}
}
int max = 0;
for(int i=1; i<n+1; i++)
{
if(temp[i]>max)
max = temp[i];
}
return max;
}
int main()
{
string arr[]={"i","as", "sa", "hi", "sash","ssahi","sashi", "ashi","shi"};
cout<<find_length(arr, 9)<<endl;
cin.get();
return 0;
}
#include<iostream>
#include<map>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n;
cin >> n;
string s;
vector<int> longest_chain;
vector <string> v;
map<int, string> m;
int i = 0;
while (i<n){
cin >> s;
v.push_back(s);
m[i] = s;
i++;
}
// count longest chain for each string entered
for (int i = 0; i < n; i++){
string s = m[i]; int count = 1;
for (int j = 0; j < s.size(); j++){
string s2=s;
s2.erase(s2.begin() + j);
//copy(s.begin(), s.end() - 2, s);
for (int i = 0; i < m.size()&&s2!=""; i++){
if (m[i] == s2){
s = s2;
count++;
j = 0;
break;
}
}
}
longest_chain.push_back(count);
}
auto itr= *max_element(longest_chain.begin(), longest_chain.end());
std::cout << itr;
return 0;
}
}
for each word in the array delete a char and recursively call to see how deep into the stack it goes. the max stack deep is the max chain number.
public class StringChain {
public static void main(String[] args) {
String[] words = new String[]{"bdcafg", "bdcaf","a", "b", "ba", "bca", "bda", "bdca"};
int longestChain = longest_chain(words);
System.out.println("longestChain " + longestChain);
}
static int longest_chain(String words[]) {
int max = Integer.MIN_VALUE;
for (String word:words) {
int curr = findNextWord(words, word, 0);
max = Math.max(max, curr);
}
return max;
}
static int maxStack=0;
static int findNextWord(String[] words, String word, int stack) {
if (!contains(words, word)) {
return 0;
}
stack++;
maxStack = stack;
System.out.println("1 stack "+stack+" maxStack "+maxStack);
for (int i = 0; i < word.length(); i++) {
StringBuilder sb = new StringBuilder(word);
sb.delete(i, i + 1);
findNextWord(words, sb.toString(), stack);
}
System.out.println("2 stack "+stack+" maxStack "+maxStack);
return maxStack;
}
static boolean contains(String[] words, String wordToSearch) {
for (String currentWord : words) {
if (currentWord.equals(wordToSearch)) {
return true;
}
}
return false;
}
}
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class Solutions{
public static void main(String[] args) {
String[] words = {
"a",
"b",
"ba",
"bca",
"bda",
"bdca"
};
System.out.println("Longest Chain Length : " + longest_chain(words));
}
static int longest_chain(String[] w) {
if (null == w || w.length < 1) {
return 0;
}
int maxChainLen = 0;
HashSet<String> words = new HashSet<>(Arrays.asList(w));
HashMap<String, Integer> wordToLongestChain = new HashMap<>();
for (String word : w) {
if (maxChainLen > word.length()) {
continue;
}
int curChainLen = find_chain_len(word, words, wordToLongestChain) + 1;
wordToLongestChain.put(word, curChainLen);
maxChainLen = Math.max(maxChainLen, curChainLen);
}
return maxChainLen;
}
static int find_chain_len(String word, HashSet<String> words, HashMap<String, Integer> wordToLongestChain) {
int curChainLen = 0;
for (int i = 0; i < word.length(); i++) {
String nextWord = word.substring(0, i) + word.substring(i + 1);
if (words.contains(nextWord)) {
if (wordToLongestChain.containsKey(nextWord)) {
curChainLen = Math.max(curChainLen, wordToLongestChain.get(nextWord));
} else {
int nextWordChainLen = find_chain_len(nextWord, words, wordToLongestChain);
curChainLen = Math.max(curChainLen, nextWordChainLen + 1);
}
}
}
return curChainLen;
}
}
def find_max_chain(data1,max_chain):
global Prev_chains
if(data1):
for i in range (len(data1)):
w = str(data1[:i] + data1[i+1:])
if (w):
if w in words:
if Prev_chains < max_chain:
max_chain+=1
find_max_chain(w,max_chain)
if Prev_chains < max_chain:
Prev_chains = max_chain
max_chain = 1
return
"""
n = int(input("enter the number of element in list"))
data = []
for i in range(0,n):
data.append(input("enetr the element"))
print (data)
"""
max_chain = 1
Prev_chains = 0
data = "bdca"
li = []
words = ["a", "b", "ba", "bca", "bda", "bdca"]
for data in words:
max_chain = 1
Prev_chains = 0
find_max_chain(data,max_chain)
li.append(Prev_chains)
print(li)
print("max chain length = ",max(li))
def find_max_chain(data1,max_chain):
global Prev_chains
if(data1):
for i in range (len(data1)):
w = str(data1[:i] + data1[i+1:])
if (w):
if w in words:
if Prev_chains < max_chain:
max_chain+=1
find_max_chain(w,max_chain)
if Prev_chains < max_chain:
Prev_chains = max_chain
max_chain = 1
return
"""
n = int(input("enter the number of element in list"))
data = []
for i in range(0,n):
data.append(input("enetr the element"))
print (data)
"""
max_chain = 1
Prev_chains = 0
data = "bdca"
li = []
words = ["a", "b", "ba", "bca", "bda", "bdca"]
for data in words:
max_chain = 1
Prev_chains = 0
find_max_chain(data,max_chain)
li.append(Prev_chains)
print(li)
print("max chain length = ",max(li))
def find_max_chain(data1,max_chain):
global Prev_chains
if(data1):
for i in range (len(data1)):
w = str(data1[:i] + data1[i+1:])
if (w):
if w in words:
if Prev_chains < max_chain:
max_chain+=1
find_max_chain(w,max_chain)
if Prev_chains < max_chain:
Prev_chains = max_chain
max_chain = 1
return
"""
n = int(input("enter the number of element in list"))
data = []
for i in range(0,n):
data.append(input("enetr the element"))
print (data)
"""
max_chain = 1
Prev_chains = 0
data = "bdca"
li = []
words = ["a", "b", "ba", "bca", "bda", "bdca"]
for data in words:
max_chain = 1
Prev_chains = 0
find_max_chain(data,max_chain)
li.append(Prev_chains)
print(li)
print("max chain length = ",max(li))
static int longestChain(List<String> wordList) {
Collections.sort(wordList,new Comparator<String>() {
public int compare(String str1, String str2) {
return str1.length()-str2.length();
}
});
Map<String ,Integer> map = new HashMap<String ,Integer>();
map.put(wordList.get(0),1);
int[] dp = new int[wordList.size()];
dp[0] =1;
int ans =dp[0];
for(int i=1;i < wordList.size();i++){
dp[i] =1;
String s = wordList.get(i);
int size = s.length();
for(int j=0;j<size;j++){
String newstring=s.substring(0,j)+s.substring(j+1);
if(map.containsKey(newstring)){
dp[i]=Math.max(dp[i],map.get(newstring)+1);
}
}
ans=Math.max(ans,dp[i]);
map.put(s,dp[i]);
}
return ans;
}
#include <bits/stdc++.h>
using namespace std;
bool isvalid(string word,string cur){
if(cur=="")
return true;
map<char,int> hash1;
map<char,int> hash2;
for(int i=0;i<word.length();i++)
hash1[word[i]]++;
for(int i=0;i<cur.length();i++)
hash2[cur[i]]++;
int sum=0;
for(map<char,int>::iterator it = hash1.begin();it!=hash1.end();it++){
it->second = it->second - hash2[it->first];
sum+=it->second;
}
// cout<<sum<<endl;
return (sum==1);
}
bool compare(string &a,string &b){
return a.length()<=b.length();
}
int stringchain(vector<string> a,string curword,int start){
if(start>=a.size())
return 0;
if(a[start].length()==curword.length()+1 && isvalid(a[start],curword))
return max(1+stringchain(a,a[start],start+1),stringchain(a,curword,start+1));
return stringchain(a,curword,start+1);
}
int main() {
int n;
cin>>n;
string s;
vector<string> a;
while(n--){
cin>>s;
a.push_back(s);
// sort(a.begin,a.end(),comparator);
}
// cout<<isvalid("and","bn")<<endl;
sort(a.begin(),a.end(),compare);
cout<<stringchain(a,"",0)<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
bool isvalid(string word,string cur){
if(cur=="")
return true;
map<char,int> hash1;
map<char,int> hash2;
for(int i=0;i<word.length();i++)
hash1[word[i]]++;
for(int i=0;i<cur.length();i++)
hash2[cur[i]]++;
int sum=0;
for(map<char,int>::iterator it = hash1.begin();it!=hash1.end();it++){
it->second = it->second - hash2[it->first];
sum+=it->second;
}
// cout<<sum<<endl;
return (sum==1);
}
bool compare(string &a,string &b){
return a.length()<=b.length();
}
int stringchain(vector<string> a,string curword,int start){
if(start>=a.size())
return 0;
if(a[start].length()==curword.length()+1 && isvalid(a[start],curword))
return max(1+stringchain(a,a[start],start+1),stringchain(a,curword,start+1));
return stringchain(a,curword,start+1);
}
int main() {
int n;
cin>>n;
string s;
vector<string> a;
while(n--){
cin>>s;
a.push_back(s);
// sort(a.begin,a.end(),comparator);
}
// cout<<isvalid("and","bn")<<endl;
sort(a.begin(),a.end(),compare);
cout<<stringchain(a,"",0)<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
bool isvalid(string word,string cur){
if(cur=="")
return true;
map<char,int> hash1;
map<char,int> hash2;
for(int i=0;i<word.length();i++)
hash1[word[i]]++;
for(int i=0;i<cur.length();i++)
hash2[cur[i]]++;
int sum=0;
for(map<char,int>::iterator it = hash1.begin();it!=hash1.end();it++){
it->second = it->second - hash2[it->first];
sum+=it->second;
}
// cout<<sum<<endl;
return (sum==1);
}
bool compare(string &a,string &b){
return a.length()<=b.length();
}
int stringchain(vector<string> a,string curword,int start){
if(start>=a.size())
return 0;
if(a[start].length()==curword.length()+1 && isvalid(a[start],curword))
return max(1+stringchain(a,a[start],start+1),stringchain(a,curword,start+1));
return stringchain(a,curword,start+1);
}
int main() {
int n;
cin>>n;
string s;
vector<string> a;
while(n--){
cin>>s;
a.push_back(s);
// sort(a.begin,a.end(),comparator);
}
// cout<<isvalid("and","bn")<<endl;
sort(a.begin(),a.end(),compare);
cout<<stringchain(a,"",0)<<endl;
return 0;
}
public class Maiintest {
// now create a method where we are removing the character from the string
public static int maxStringChain(List<String> list) {
// lets start with the Single String
int count = 0;
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < list.size(); i++) {
count = 0;
if (list.get(i).length() <= 1) {
count = 0;
} else {
String str = list.get(i);
char ch[] = str.toCharArray();
for (int j = 0; j < ch.length; j++) {
String str1 = removeChar(str, ch[j]);
boolean check = checkString(list, str1);
if (check == true) {
count++;
}
}
}
}
set.add(count);// set is used to remove the duplicacy
int max = displayCount(set);
return max;
}
public static int displayCount(Set<Integer> set) {
// here we need to retrun the maximum count
int max = -1;
for (Integer ss : set) {
if (ss > max) {
max = ss;
}
}
return max;
}
public static String removeChar(String str, char target) {
int index = str.indexOf(target);
if (index < 0)
return str;
else {
return removeChar(str.substring(0, index) + str.substring(index + 1), target);
}
}
public static boolean checkString(List<String> list, String str)
{
for (String str1 : list) {
if (str1.equals(str))
return true;
}
return false;
}
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("ba");
list.add("bca");
list.add("bda");
list.add("dca");
list.add("bdc");
list.add("bdca");
int max = maxStringChain(list);
System.out.println("Max difference is " + max);
}
}
public class Maiintest {
// now create a method where we are removing the character from the string
public static int maxStringChain(List<String> list) {
// lets start with the Single String
int count = 0;
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < list.size(); i++) {
count = 0;
if (list.get(i).length() <= 1) {
count = 0;
} else {
String str = list.get(i);
char ch[] = str.toCharArray();
for (int j = 0; j < ch.length; j++) {
String str1 = removeChar(str, ch[j]);
boolean check = checkString(list, str1);
if (check == true) {
count++;
}
}
}
}
set.add(count);// set is used to remove the duplicacy
int max = displayCount(set);
return max;
}
public static int displayCount(Set<Integer> set) {
// here we need to retrun the maximum count
int max = -1;
for (Integer ss : set) {
if (ss > max) {
max = ss;
}
}
return max;
}
public static String removeChar(String str, char target) {
int index = str.indexOf(target);
if (index < 0)
return str;
else {
return removeChar(str.substring(0, index) + str.substring(index + 1), target);
}
}
public static boolean checkString(List<String> list, String str)
{
for (String str1 : list) {
if (str1.equals(str))
return true;
}
return false;
}
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("ba");
list.add("bca");
list.add("bda");
list.add("dca");
list.add("bdc");
list.add("bdca");
int max = maxStringChain(list);
System.out.println("Max difference is " + max);
}
}
#include <bits/stdc++.h>
using namespace std;
const int maxn=10000;
unordered_map< string,int > hashTable;
int dp[maxn];
int LongestChain(vector<string> V)
{
vector< pair<int,string> > list;
for (auto s:V){
list.push_back({s.size(),s});
}
sort(list.begin(),list.end());
int N=list.size();
hashTable.insert( {list[0].second,0} );
dp[0]=1;
int answer=dp[0];
for (int i=1;i<N;i++){
dp[i]=1;
string s=list[i].second;
int size = s.size();
for (int j=0;j<size;j++){
string tmpStr = s;
tmpStr.erase(tmpStr.begin()+j);
auto it = hashTable.find(tmpStr);
if (it!=hashTable.end())
dp[i] = max (dp[i],dp[it->second]+1);
}
answer = max ( answer , dp[i]);
hashTable.insert({s,i});
}
return answer;
}
int main()
{
int N;
cin >> N;
vector<string> V(N);
for (int i=0;i<N;i++)
cin >> V[i];
cout << LongestChain(V) << endl;
return 0;
}
package leetCode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
class Pair implements Comparable<Pair>{
String str;
int count;
Pair(String str){
this.str = new String(str);
count = str.length();
}
public int compareTo(Pair p){
return this.count - p.count;
}
}
public class StringChain {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner inp = new Scanner(System.in);
int N = inp.nextInt();
inp.nextLine();
Pair[]arr = new Pair[N];
for(int i=0; i<N; i++){
String s = inp.nextLine();
arr[i] = new Pair(s);
}
Arrays.sort(arr);
compute(arr, N);
inp.close();
}
static void compute(Pair[] arr, int N){
int[]dp = new int[N];
dp[0] = 1;
for(int i=1; i<N; i++){
int max = 1;
for(int j=i-1; j>=0; j--){
if(arr[i].count - arr[j].count > 0){
if(arr[i].count - arr[j].count == 1){
String arrI = arr[i].str;
for(int rem = 0; rem<arrI.length(); rem++){
String afterR = arrI.substring(0, rem) + arrI.substring(rem+1, arrI.length());
if(afterR.equals(arr[j].str)){
if(dp[j] + 1 > max){
max = dp[j]+1;
}
}
}
}
else{
break;
}
}
}
dp[i] = max;
}
int max = Integer.MIN_VALUE;
for(int i=0; i<N; i++){
if(dp[i] > max){
max = dp[i];
}
}
System.out.println(max);
}
}
public class Maiintest {
// now create a method where we are removing the character from the string
public static int maxStringChain(List<String> list) {
// lets start with the Single String
int count = 0;
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < list.size(); i++) {
count = 0;
if (list.get(i).length() <= 1) {
count = 0;
} else {
String str = list.get(i);
char ch[] = str.toCharArray();
for (int j = 0; j < ch.length; j++) {
String str1 = removeChar(str, ch[j]);
boolean check = checkString(list, str1);
if (check == true) {
count++;
}
}
}
}
set.add(count);// set is used to remove the duplicacy
int max = displayCount(set);
return max;
}
public static int displayCount(Set<Integer> set) {
// here we need to retrun the maximum count
int max = -1;
for (Integer ss : set) {
if (ss > max) {
max = ss;
}
}
return max;
}
public static String removeChar(String str, char target) {
int index = str.indexOf(target);
if (index < 0)
return str;
else {
return removeChar(str.substring(0, index) + str.substring(index + 1), target);
}
}
public static boolean checkString(List<String> list, String str)
{
for (String str1 : list) {
if (str1.equals(str))
return true;
}
return false;
}
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("ba");
list.add("bca");
list.add("bda");
list.add("dca");
list.add("bdc");
list.add("bdca");
int max = maxStringChain(list);
System.out.println("Max difference is " + max);
}
}
- Anonymous October 30, 2015#include<iostream> #include<map> #include<string> #include<algorithm> using namespace std; struct compare { bool operator()(const string& s1,const string& s2) { return s1.length()<s2.length(); } }; int find_length(string arr[], int n) { int* temp = new int[n+1]; for(int i=0; i<n+1; i++) temp[i] = 1; sort(arr, arr+n, compare()); map<string, int> m; for(int i=0; i<n; i++) { int p = arr[i].length(); string q = arr[i]; m[q]=i+1; for(int j=0; j<p; j++) { char c= q[j]; q.erase(q.begin()+j); if(m[q]!=0 && temp[m[q]]+1>temp[i+1]) temp[i+1] = temp[m[q]]+1; q.insert(j,1,c); } } int max = 0; for(int i=1; i<n+1; i++) { if(temp[i]>max) max = temp[i]; } return max; } int main() { string arr[]={"i","as", "sa", "hi", "sash","ssahi","sashi", "ashi","shi"}; cout<<find_length(arr, 9)<<endl; cin.get(); return 0; }