Dr.H
BAN USER- 0of 0 votes
Answersyou have Trie tree , not ordered , juts don't worry about the order.
- Dr.H in United States for SQL Server / DPG Group
write an efficient algorithm to Serialize and DeSerialize
the tree , in the same order , you need to construct the same tree.
what if the tree have millions of node ? optimize everything| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answers-write an algorithm to tell if the tree is balanced ?
- Dr.H in United States for SQL Server / DPG Group
-what is the mathematics rule that can help us to define this? O(log(h)) , how to use this model in your algorithm
- what types of Balanced Tree ? Red-Black Tree.
write an algorithm to balance a tree ? and also to Auto balance a tree while you are inserting the nodes.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answersyou have a table of 2 columns , describe task scheduler, tasks can't run unless other tasks it depends
- Dr.H in United States for SQL Server / DPG Group
on finished running
Task | Depend
-----------------------
A | B
B | C
C | D
and so on ..
from that table design an algorithm that output the task workflow execution in sequence.
A->B->C->D
it can be repeated , there can be loop cycle .
design an algorithm that output this in O(n) , space is not an issue.
anyway it was very though question you need to ask as many question as you know .
after this hard time , the solution will use a graph to represent the relation first
then you will traverse the graph to output the workflow.
in the final you need to have a knowledge of Topological Sort to be able to solve it.
so if you will not depend on luck try to study graph and graph algorithms very hard before you go .| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
Answersyou have a file with words , and we need to select top N repeated words in this file.
- Dr.H in United States for SQL Server / DPG Group
challenge Imagine this file is TB file that can't fit in memory what will you do?| Report Duplicate | Flag | PURGE
Algorithm
+1 @oOzz , I will enhance your solution just instead of checking all the words in the dictionary.
get the words from dictionary that start with the letters in the tiles.
consider this a MapReduce step .
now for those only apply the algo:
for each word filtered from dictionary
if all the letters of the words exist in the map of the 1-7 tiles
then print it other wise next word
O(n) match any pattern of char
add chars in map , from the string remove all the non repeated char
you will end up with string compare char neighbors if they are different it is subseq
if not try to remove the noise see how many char/pattern you have detect the false positive
and ignore it.
here is the solution
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
bool IsSubSequent(string s){
map<char,int> seqMap;
bool IsSubSeq=false;
string subSequent="";
for(char c: s){
if(seqMap.count(c)>0){
seqMap[c]+=1;
}
else{
seqMap[c]=1;
}
subSequent+=c;
}
int patternCount=0;
for(auto i: seqMap){
if(i.second==1){
subSequent.erase(subSequent.find(i.first),1);
}
else{
patternCount++;
}
}
char prev='\0',next='\0';
int falseCount=0;
for(char c : subSequent){
prev=next;
next=c;
if(prev=='\0' || next == '\0') continue;
if(prev==next)falseCount++;
}
IsSubSeq=falseCount<patternCount-1;
cout<<"*"<<subSequent<<"*";
return IsSubSeq;
}
int main(int argc, const char * argv[]) {
vector<string> v= {"abab","abba","acbdaghfb","abcdfdcab"};
for(string s : v){
cout<<s<<"=>"<<(IsSubSequent(s)?"true":"false")<<endl;
}
}
you are building a trie and the trie node had a container or map for each node !
the trie solution use N containers for N words , it is so complex for the problem you are trying to solve. and will not scale .
read my solution again it is very simple using only a map.
this is very easy :
this is O(n) solution
a- scan all the words add the first letter to a map , this will tell you the letters you need to process
b- scan the list for each letter collect the words for that letter
c- for the collected words start add them to a temp map
c-1: if the collected words is more than 1 start by adding using the first 2 letters
c-2: if you couldn't add all the words using first 2 letters retry using 3 letters and so on
d- After all you words added to temp map Add them to the main map
e: continue till you finish your letter map
here it is :
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
void shortestPrefixMap(){
string wordList[] ={"dog","done","good","go","gogo","gold","golf","why","which","while","zebra", "duck","dot"};
map<char,int> lettersMap ;
int len = sizeof(wordList)/sizeof(wordList[0]);
for(int i=0;i<len;i++){
char firstWordLetter = wordList[i].at(0);
if(lettersMap.count(firstWordLetter)>0){
lettersMap[firstWordLetter]+=1;
}
else{
lettersMap[firstWordLetter]=1;
}
}
map<string,string> wordsMap;
map<string,string> MainMap;
vector<string> words;
for(auto it : lettersMap){
words.clear();
wordsMap.clear();
for(auto word : wordList){
if(word.at(0)!=it.first) continue;
words.push_back(word);
}
// for the collected words start the prefix
if(words.size()==1){
// add it to the main
MainMap[words[0]]=words[0].at(0);
}
else {
// prefix
int substrignEnd=1;
int count=0;
while(count<it.second){
string key = words[count].substr(0,substrignEnd);
while(wordsMap.count(key)>0){
substrignEnd+=1;
key = words[count].substr(0,substrignEnd);
}
wordsMap[key]=words[count];
substrignEnd=1;
count++;
}
// everything done add them to the main map
for(auto it : wordsMap){
MainMap[it.second]=it.first;
}
}
}
for(auto it : MainMap ){
cout<<it.first<<"=>"<<it.second<<endl;
}
}
int main(int argc, const char * argv[]) {
shortestPrefixMap();
return 0;
}
you can do easier than this by constructing a fingerprint of of sorted pairs
so the array of 10 should be reduced to an array of 5 sort the pair desc
then construct a fingerprint of the box using a simple string which will be the same for the same domino pieces in the box whatever the order
#include <iostream>
#include <map>
using namespace std;
int compare(const void * a, const void * b){
return ((*(int*)a)-(*(int*)b));
}
class DominoChecker{
public:
bool AddBox(int dominoBox[],int len){
bool result=false;
string fingerPrint;
int* x=new int[len/2];
for (int i=0,j=0; i<len/2; i++,j+=2) {
x[i]=dominoBox[j]>dominoBox[j+1]?dominoBox[j]*10+dominoBox[j+1]:dominoBox[j]+dominoBox[j+1]*10;
}
std::qsort(x,5,sizeof(int),compare);
for(int i=0 ; i<len/2;i++){
fingerPrint+=std::to_string(x[i]);
}
cout<<fingerPrint<<endl;
if(dominoBoxes[fingerPrint]!= NULL){
result= true;
}
else{
dominoBoxes[fingerPrint]=dominoBox;
}
delete[] x;
return result;
}
private:
std::map<string,int*> dominoBoxes;
};
int main(void){
int a[10]={1,2,3,5,6,6,5,6,0,3};
int b[10]={1,2,6,6,5,3,5,6,0,3};
DominoChecker dc ;
bool result=dc.AddBox(a,10);
cout<<result<<endl;
result=dc.AddBox(b,10);
cout<<result<<endl;
return 0;
}
- Dr.H October 23, 2014this only works for NxN matrix if it MxN matrix your solution will not work.
it is a recursive problem you need to think in it recursively first.
#include <iostream>
using namespace std;
const int tw=3,th=3;
void printRow(int a[th][tw],int h,int w){
for(int i=0;i<w;i++){
cout<<a[h][i];
}
}
void printCol(int a[th][tw],int h,int w){
for(int i=h;i<th;i++){
cout<<a[i][w];
}
}
void printDiagonalR(int a[th][tw],int h,int w){
if(h>th) return;
printRow(a,h,w);
if(w<0) return;
printCol(a,h,w);
string spaces="";
for(int i=0;i<h+1;i++){
spaces+=" ";
}
cout<<endl<<spaces;
printDiagonalR(a,h+1,w-1);
}
int main(int argc, const char * argv[]) {
int a[th][tw]={{1,2,3},
{4,5,6,},
{7,8,9}};
printDiagonalR(a,0,tw-1);
return 0;
}
it is Knuth-Morris-Pratt string matching algorithm
- Dr.H November 05, 2014