We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
After some light research, it seems like SparseArrays are a memory lighter alternative to HashMaps in a subset of circumstances. However, HashMaps are faster and work for larger collections. I have no idea how to use SparseArrays, and since I already know how to use HashMaps, I also found the problem rather easy. I'm a little surprised the O(n^2) loop worked, but that's exactly the reason I came here (because at 1000x1000 it seemed feasible). This problem could use some improvement. Rather than re-classifying the difficulty, the problem statement and test cases should be improved to better illustrate the point, which may also raise the difficulty and block out the brute force method. Additionally, the problem statement would probably need to block the use of HashMaps, again, to illustrate the lesson on using SparseArrays.
Here is a solution that actually uses the notion of "Sparse Arrays" (if you used Maps or LINQ you really missed the point of the exercise):
usingSystem;usingSystem.Collections.Generic;usingSystem.IO;classSolution{publicclassNode{privateintcount=0;privateintdepth;privateNode[]subnodes=null;privateNode[]Subnodes{get{if(subnodes==null){subnodes=newNode[52];// support A-Z a-z}returnsubnodes;}}publicNode():this(0){}privateNode(intdepth){this.depth=depth;}publicintAdd(stringstr){Nodecurrent=this;for(inti=0;i<str.Length;i++){intindex=CharNodeIndex(str[i]);if(current.Subnodes[index]==null){current.Subnodes[index]=newNode(depth+1);}current=current.Subnodes[index];}current.count++;returncurrent.count;}publicintCountOf(stringstr){Nodecurrent=this;for(inti=0;i<str.Length;i++){intindex=CharNodeIndex(str[i]);if(current.Subnodes[index]==null){return0;}current=current.Subnodes[index];}returncurrent.count;}privateintCharNodeIndex(charc){intindex=0;if(c>='A'&&c<='Z'){index=c-'A';}elseif(c>='a'&&c<='z'){index=c-'a'+26;}else{thrownewArgumentException("String may only contain the letters A-Z and a-z");}returnindex;}}staticvoidMain(String[]args){Nodenode=newNode();intstrCount=int.Parse(Console.In.ReadLine());for(inti=0;i<strCount;i++){stringstr=Console.In.ReadLine();node.Add(str);}intqueryCount=int.Parse(Console.In.ReadLine());for(inti=0;i<queryCount;i++){stringstr=Console.In.ReadLine();Console.Out.WriteLine(node.CountOf(str));}}}
I tried to find a way to implement a fix that somehow relates to the "Sparse Array" concept, but in sparse array we convert the array into a linked a list with the non empty entries only to save storage, so I imagined that converting the sparse array of word characters to a linked list is the way to go, here is my try:
usingSystem;usingSystem.Collections.Generic;usingSystem.IO;classSolution{staticvoidMain(String[]args){/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */intstrCount=int.Parse(Console.In.ReadLine());for(inti=0;i<strCount;i++){stringstr=Console.In.ReadLine();AddWord(str);}intqueryCount=int.Parse(Console.In.ReadLine());for(inti=0;i<queryCount;i++){stringstr=Console.In.ReadLine();actual_WordCount(str);}}staticWordNodeStartWordNode=null;staticWordNodeLastWordNode=null;publicstaticvoidAddWord(stringword){//Every new word add new word node if(StartWordNode==null)LastWordNode=StartWordNode=newWordNode();elseLastWordNode=LastWordNode.NextWordNode=newWordNode();CharacterNodecurrentCharacter=null;for(inti=0;i<word.Length;i++){if(currentCharacter==null)currentCharacter=LastWordNode.Character=newCharacterNode();elsecurrentCharacter=currentCharacter.NextCharacterNode=newCharacterNode();currentCharacter.Char=word[i];currentCharacter.Position=i;}}privatestaticvoidactual_WordCount(stringword){intcount=0;WordNodecurrentWord=StartWordNode;while(currentWord!=null){CharacterNodecurrentCharNode=currentWord.Character;boolallCharsFound=true;for(inti=0;i<word.Length;i++){if(currentCharNode.Char!=word[i]||currentCharNode.Position!=i||(i==word.Length-1&¤tCharNode.NextCharacterNode!=null)){allCharsFound=false;break;}currentCharNode=currentCharNode.NextCharacterNode;}if(allCharsFound)count++;currentWord=currentWord.NextWordNode;}Console.WriteLine(count);}publicstaticvoidcountWords(){intstrCount=int.Parse(Console.In.ReadLine());for(inti=0;i<strCount;i++){stringstr=Console.In.ReadLine();AddWord(str);}intqueryCount=int.Parse(Console.In.ReadLine());for(inti=0;i<queryCount;i++){stringstr=Console.In.ReadLine();actual_WordCount(str);}}}publicclassCharacterNode{publiccharChar{get;set;}publicintPosition{get;set;}publicCharacterNodeNextCharacterNode{get;set;}}publicclassWordNode{publicintWordCount{get;set;}publicCharacterNodeCharacter{get;set;}publicWordNodeNextWordNode{get;set;}}
Hi. I am new to sparse arrays so could you explain your code to me?
As I see it, you are using a something like an array representation of a trie...is that correct? I particularly do not understand the use of the subnodes array properly.
How are you storing the indices with the values or storing the total number of zeroes?
Sparse Arrays
You are viewing a single comment's thread. Return to all comments →
After some light research, it seems like SparseArrays are a memory lighter alternative to HashMaps in a subset of circumstances. However, HashMaps are faster and work for larger collections. I have no idea how to use SparseArrays, and since I already know how to use HashMaps, I also found the problem rather easy. I'm a little surprised the O(n^2) loop worked, but that's exactly the reason I came here (because at 1000x1000 it seemed feasible). This problem could use some improvement. Rather than re-classifying the difficulty, the problem statement and test cases should be improved to better illustrate the point, which may also raise the difficulty and block out the brute force method. Additionally, the problem statement would probably need to block the use of HashMaps, again, to illustrate the lesson on using SparseArrays.
Here is a solution that actually uses the notion of "Sparse Arrays" (if you used Maps or LINQ you really missed the point of the exercise):
I used your solution to help me with my generic one but using LinkedLists instead of fixed size arrays
That You gived the solution solved my doubt on this problem.It's much better than using map directly as it used less memory.
Looks like a Trie implmentation to me. But again I am still trying to wrap my heads around Sparse Array and how to fit this problem into it.
I tried to find a way to implement a fix that somehow relates to the "Sparse Array" concept, but in sparse array we convert the array into a linked a list with the non empty entries only to save storage, so I imagined that converting the sparse array of word characters to a linked list is the way to go, here is my try:
Hi. I am new to sparse arrays so could you explain your code to me?
As I see it, you are using a something like an array representation of a trie...is that correct? I particularly do not understand the use of the subnodes array properly.
How are you storing the indices with the values or storing the total number of zeroes?