NVIDIA Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
import java.util.*;
/**
* Created by Sibendu on 4/24/2017.
*/
class TrieNode {
String value;
HashMap<String, TrieNode> trieNodes;
int count;
TrieNode(String value) {
this.value = value;
trieNodes = new HashMap<>();
}
public void addTrieNode(String trieNodeValue) {
if (trieNodes == null)
trieNodes = new HashMap<>();
trieNodes.put(value+trieNodeValue , new TrieNode(value+trieNodeValue));
}
public HashMap<String , TrieNode> getTrieNodes() {
return trieNodes;
}
public boolean isLeaf() {
return trieNodes != null && trieNodes.size() > 0 ? false : true;
}
}
public class Device {
private static Scanner sc = new Scanner(System.in);
public static void main(String args[]) {
TrieNode head = new TrieNode("//");
int inputs = sc.nextInt();
sc.nextLine();
for ( int i = 0 ; i < inputs ; i++) {
String input = sc.nextLine();
parseInputs( head , input);
}
findCount(head);
}
private static void findCount(TrieNode head) {
for ( Map.Entry<String , TrieNode> node : head.getTrieNodes().entrySet()) {
System.out.println( node.getKey() + "=" + node.getValue().count);
findCount(node.getValue());
}
}
private static void parseInputs(TrieNode head, String input) {
head.count++;
for ( String str : input.split("/")) {
if ( !head.getTrieNodes().containsKey(head.value + str + "/")) {
head.getTrieNodes().put(head.value + str + "/" , new TrieNode( head.value + str + "/"));
}
head = head.getTrieNodes().get(head.value + str + "/");
head.count++;
}
}
}
package nvidia;
import java.util.HashMap;
import java.util.Map;
// import org.junit.Assert;
public class Node {
String value;
Map<String, Node> children;
private int freq;
Node(String val){
value = val;
children = new HashMap<String, Node>();
freq = 0;
}
/**
* increment freq if already exists
* @param path
* assumption path begins with /, /a at root adds child
* @return
*/
Node addPath(String path){
if(path == null || path.isEmpty()){
return null;
}
String[] token = path.split("/");
if(path.equals("/")) {
token = new String[] { "" };
}
int n = token.length;
//System.out.println(Arrays.toString(token));
if(n == 0 || token[0].length() > 0) {
return null;
} else {
return addPath(token, 1, n);
}
}
private Node addPath(String[] token, int index, int length){
// sanity , skip
freq++;
// base
if(index == length) {
return this;
}
String key = token[index];
Node child;
if(children.containsKey(key)){
child = children.get(key);
} else {
child = new Node(key);
children.put(key, child);
}
return child.addPath(token, index+1, length);
}
Node find(String path){
if(path == null || path.isEmpty()){
return null;
}
String[] token = path.split("/");
if(path.equals("/")) {
token = new String[] { "" };
}
int n = token.length;
//System.out.println(n + " " + Arrays.toString(token));
if(n == 0 || token[0].length() > 0) {
return null;
} else {
return find(token, 1, token.length);
}
}
private Node find(String[] token, int index, int length){
// sanity , skip
// base
if(index == length) {
return this;
}
String key = token[index];
Node child;
if(children.containsKey(key)){
child = children.get(key);
return child.find(token, index+1, length);
} else {
return null;
}
}
int getFreq(){
return freq;
}
public static void main(String[] args){
String[] descendants = {
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/TVs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs",
"/Electronics/TVs",
"/Garden",
"/Automotive/Parts"
};
Node root = new Node("");
for(String s : descendants){
root.addPath(s);
//System.out.println("CHECK tree size " + root.getFreq());
}
String[] testcases = {
"/",
"/Electronics",
"/Electronics/Computers",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs"
};
int[] results = {11, 9, 6, 4, 3};
for(int i = 0; i < testcases.length; i++){
String path = testcases[i];
Node n = root.find(path);
int freq = 0;
if(n != null){
freq = n.getFreq();
};
System.out.println(path + "\n" + freq + "\t" + results[i]);
}
}
}
package nvidia;
import java.util.HashMap;
import java.util.Map;
// import org.junit.Assert;
public class Node {
String value;
Map<String, Node> children;
private int freq;
Node(String val){
value = val;
children = new HashMap<String, Node>();
freq = 0;
}
/**
* increment freq if already exists
* @param path
* assumption path begins with /, /a at root adds child
* @return
*/
Node addPath(String path){
if(path == null || path.isEmpty()){
return null;
}
String[] token = path.split("/");
if(path.equals("/")) {
token = new String[] { "" };
}
int n = token.length;
//System.out.println(Arrays.toString(token));
if(n == 0 || token[0].length() > 0) {
return null;
} else {
return addPath(token, 1, n);
}
}
private Node addPath(String[] token, int index, int length){
// sanity , skip
freq++;
// base
if(index == length) {
return this;
}
String key = token[index];
Node child;
if(children.containsKey(key)){
child = children.get(key);
} else {
child = new Node(key);
children.put(key, child);
}
return child.addPath(token, index+1, length);
}
Node find(String path){
if(path == null || path.isEmpty()){
return null;
}
String[] token = path.split("/");
if(path.equals("/")) {
token = new String[] { "" };
}
int n = token.length;
//System.out.println(n + " " + Arrays.toString(token));
if(n == 0 || token[0].length() > 0) {
return null;
} else {
return find(token, 1, token.length);
}
}
private Node find(String[] token, int index, int length){
// sanity , skip
// base
if(index == length) {
return this;
}
String key = token[index];
Node child;
if(children.containsKey(key)){
child = children.get(key);
return child.find(token, index+1, length);
} else {
return null;
}
}
int getFreq(){
return freq;
}
public static void main(String[] args){
String[] descendants = {
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/TVs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs",
"/Electronics/TVs",
"/Garden",
"/Automotive/Parts"
};
Node root = new Node("");
for(String s : descendants){
root.addPath(s);
//System.out.println("CHECK tree size " + root.getFreq());
}
String[] testcases = {
"/",
"/Electronics",
"/Electronics/Computers",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs"
};
int[] results = {11, 9, 6, 4, 3};
for(int i = 0; i < testcases.length; i++){
String path = testcases[i];
Node n = root.find(path);
int freq = 0;
if(n != null){
freq = n.getFreq();
};
System.out.println(path + "\n" + freq + "\t" + results[i]);
}
}
}
package nvidia;
import java.util.HashMap;
import java.util.Map;
// import org.junit.Assert;
public class Node {
String value;
Map<String, Node> children;
private int freq;
Node(String val){
value = val;
children = new HashMap<String, Node>();
freq = 0;
}
/**
* increment freq if already exists
* @param path
* assumption path begins with /, /a at root adds child
* @return
*/
Node addPath(String path){
if(path == null || path.isEmpty()){
return null;
}
String[] token = path.split("/");
if(path.equals("/")) {
token = new String[] { "" };
}
int n = token.length;
//System.out.println(Arrays.toString(token));
if(n == 0 || token[0].length() > 0) {
return null;
} else {
return addPath(token, 1, n);
}
}
private Node addPath(String[] token, int index, int length){
// sanity , skip
freq++;
// base
if(index == length) {
return this;
}
String key = token[index];
Node child;
if(children.containsKey(key)){
child = children.get(key);
} else {
child = new Node(key);
children.put(key, child);
}
return child.addPath(token, index+1, length);
}
Node find(String path){
if(path == null || path.isEmpty()){
return null;
}
String[] token = path.split("/");
if(path.equals("/")) {
token = new String[] { "" };
}
int n = token.length;
//System.out.println(n + " " + Arrays.toString(token));
if(n == 0 || token[0].length() > 0) {
return null;
} else {
return find(token, 1, token.length);
}
}
private Node find(String[] token, int index, int length){
// sanity , skip
// base
if(index == length) {
return this;
}
String key = token[index];
Node child;
if(children.containsKey(key)){
child = children.get(key);
return child.find(token, index+1, length);
} else {
return null;
}
}
int getFreq(){
return freq;
}
public static void main(String[] args){
String[] descendants = {
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/TVs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs",
"/Electronics/TVs",
"/Garden",
"/Automotive/Parts"
};
Node root = new Node("");
for(String s : descendants){
root.addPath(s);
//System.out.println("CHECK tree size " + root.getFreq());
}
String[] testcases = {
"/",
"/Electronics",
"/Electronics/Computers",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs"
};
int[] results = {11, 9, 6, 4, 3};
for(int i = 0; i < testcases.length; i++){
String path = testcases[i];
Node n = root.find(path);
int freq = 0;
if(n != null){
freq = n.getFreq();
};
System.out.println(path + "\n" + freq + "\t" + results[i]);
}
}
}
Possible solution using Trie structure for C++/11 with verification and couple of corner cases added (it is worth to check them for other solutions mentioned here):
#include <iostream>
#include <utility>
#include <queue>
#include <string>
#include <regex>
#include <unordered_map>
#include <memory>
class TrieStructure {
public:
void append(const std::string &record) {
if (record.empty()) {
return;
}
std::queue<std::string> tokens = split(record);
fill(tokens, nodes);
}
int getCount(const std::string &record) {
if (record.empty()) {
return 0;
}
std::queue<std::string> tokens = split(record);
return fetch(tokens, nodes);
}
private:
struct TrieNode {
int count;
std::shared_ptr<std::unordered_map<std::string, TrieNode>> nodes;
};
std::shared_ptr<std::unordered_map<std::string, TrieNode>> nodes;
static std::queue<std::string> split(const std::string &record) {
std::queue<std::string> tokens{};
std::regex r{"/"};
std::sregex_token_iterator tokenizer_it{record.begin(), record.end(), r, -1};
std::sregex_token_iterator tokenizer_end{};
while (tokenizer_it != tokenizer_end) {
tokens.push(*tokenizer_it);
tokenizer_it++;
}
return tokens;
}
void fill(std::queue<std::string> &tokens, std::shared_ptr<std::unordered_map<std::string, TrieNode>> &trie) {
if (tokens.empty()) {
return;
}
if (!trie) {
trie = std::make_shared<std::unordered_map<std::string, TrieNode>>();
}
std::string token = tokens.front();
tokens.pop();
(*trie)[token].count ++;
fill(tokens, (*trie)[token].nodes);
}
int fetch(std::queue<std::string> &tokens, std::shared_ptr<std::unordered_map<std::string, TrieNode>> &trie) const {
if (!trie) {
return 0;
}
std::string token = tokens.front();
tokens.pop();
if (tokens.empty()) {
return (*trie)[token].count;
}
return fetch(tokens, (*trie)[token].nodes);
}
};
int main(int argc, char *argv[]) {
const std::vector<std::string> inputData{
"",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/TVs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs",
"/Electronics/TVs",
"/Garden",
"/Automotive/Parts"
};
const std::vector<std::pair<std::string, int>> verifyData{
{"/Electronics/Computers/Nothing", 0},
{"/Electronics/Computers/Graphics Cards/Nothing", 0},
{"", 0},
{"/", 11},
{"/Electronics", 9},
{"/Electronics/Computers", 6},
{"/Electronics/Computers/Graphics Cards", 4},
{"/Electronics/TVs", 3}
};
TrieStructure trie;
for (const auto& inputRecord : inputData) {
trie.append(inputRecord);
}
std::cout << "Verification: " << std::endl;
for (const auto& verifyRecord : verifyData) {
if (trie.getCount(verifyRecord.first) == verifyRecord.second) {
std::cout << "[PASSED] " << verifyRecord.first << std::endl;
} else {
std::cout << "[FAILED] " << verifyRecord.first << std::endl;;
}
}
system("pause");
return 0;
}
I think that the question is about Trie structure, but another possible solution, using map only, may looks like this. I think it is much faster to get the answer (number of occurences) using that structure instead of Trie:
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <regex>
#include <unordered_map>
#include <memory>
struct TrieNode{
TrieNode() :count(0) {}
int count;
std::shared_ptr<std::unordered_map<std::string, TrieNode>> nodes;
};
class DataStructure {
public:
void append(const std::string &record) {
if (record.empty()) {
return;
}
std::vector<std::string> tokens = split(record);
fill(tokens);
}
int getCount(const std::string &dir) {
return data[dir];
}
private:
static const std::string separator;
std::unordered_map<std::string, int> data;
static std::vector<std::string> split(const std::string &record) {
std::regex r{separator};
std::sregex_token_iterator tokenizer_it{record.begin(), record.end(), r, -1};
std::sregex_token_iterator tokenizer_end{};
std::vector<std::string> tokens{tokenizer_it, tokenizer_end};
return tokens;
}
void fill(std::vector<std::string> &tokens) {
std::string dir = separator;
for (const auto& token : tokens) {
dir += token;
data[dir] ++;
if (!token.empty())
dir += separator;
}
}
};
const std::string DataStructure::separator{"/"};
int main(int argc, char *argv[]) {
const std::vector<std::string> inputData{
"",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/TVs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs",
"/Electronics/TVs",
"/Garden",
"/Automotive/Parts"
};
const std::vector<std::pair<std::string, int>> verifyData{
{"/Electronics/Computers/Nothing", 0},
{"/Electronics/Computers/Graphics Cards/Nothing", 0},
{"", 0},
{"/", 11},
{"/Electronics", 9},
{"/Electronics/Computers", 6},
{"/Electronics/Computers/Graphics Cards", 4},
{"/Electronics/TVs", 3}
};
DataStructure dataStructure;
for (const auto& inputRecord : inputData) {
dataStructure.append(inputRecord);
}
std::cout << "Verification: " << std::endl;
for (const auto& verifyRecord : verifyData) {
if (dataStructure.getCount(verifyRecord.first) == verifyRecord.second) {
std::cout << "[PASSED] " << verifyRecord.first << std::endl;
} else {
std::cout << "[FAILED] " << verifyRecord.first << std::endl;;
}
}
system("pause");
return 0;
}
The task is to store and count all folders so why all these complex solutions? Why not just store all keys to the dict? Just so simple.
void solution(const std::vector<std::string>& A) {
std::unordered_map<std::string, int> dict;
for (auto& a : A) {
std::string b;
b.reserve(a.size());
for (char c : a) {
if (c == '/') {
if (b.empty()) {
b.push_back(c);
}
auto res = dict.try_emplace(b, 1);
if (!res.second) {
++(res.first->second);
}
if (b.size() == 1) {
continue;
}
}
b.push_back(c);
}
if (!b.empty() && b.back() != '/') {
auto res = dict.try_emplace(b, 1);
if (!res.second) {
++(res.first->second);
}
}
}
for (auto& kv : dict) {
std::cout << kv.second << "\t- " << kv.first << endl;
}
}
map<string, int> StoreElectroncisInfo(string str_array[], int len) {
map<string, int> dict;
string word;
for(int i=0; i < len; i++) {
for(int j=0; j < str_array[i].size(); j++) {
word += str_array[i][j];
if( str_array[i][j] == '/' || j == str_array[i].size()-1 ) {
int back = word.back();
if(word.size() == 1) {
dict[word]++;
}
else if(back == '/') {
word.resize(word.size()-1);
}
dict[word]++;
word += '/';
//cout << word << " = " << dict[word] << endl;
}
}
word = "";
}
return dict;
}
map<string, int> StoreElectronicsInfo(string str_array[], int len) {
// "/Electronics/Computers/Graphics Cards"
map<string, int> dict;
string word;
for(int i=0; i < len; i++) {
// Travarse each string in array
for(int j=0; j < str_array[i].size(); j++) {
// Add chars to word string
word += str_array[i][j];
// Check for '/' and end of string
if( str_array[i][j] == '/' || j == str_array[i].size() - 1 ) {
if(word.size() == 1) {
dict[word]++; // First '/'. Add '/' word and increment word count in map
}
else if(word.back() == '/') {
word.resize(word.size() - 1); // Remove last '/' from word, before adding it to map
}
dict[word]++; // Increment string count (minus last '/') to map
word += '/'; // Add '/' back to word
}
}
word = ""; // Erase word
}
return dict;
}
/*
Given the following set of strings, write a function that stores this information.
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/SSDs
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/SSDs
// /Electronics/TVs
// /Electronics/Computers/Graphics Cards
// /Electronics/TVs
// /Electronics/TVs
// /Garden
// /Automotive/Parts
Your datastructure should be able to provide information as such:
// / = 11
// /Electronics = 9
// /Electronics/Computers = 6
// /Electronics/Computers/Graphics Cards = 4
// /Electronics/TVs = 3
// etc
// ["/Electronics/Computers/Graphics Cards", "/Garden"]
*/
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
string name;
unordered_map<string, Node*> children;
int count;
Node(string s):name(s), count(0){}
~Node(){}
};
vector<string> stringparser(const string& s)
{
vector<string> ans;
int i = 0, j = 0;
while(i < s.size())
{
if(s[i] == '/')
{
ans.push_back(string(s.begin()+j, s.begin()+i+1));
j = i+1;
}
i++;
}
if(j < s.size())
ans.push_back(string(s.begin()+j, s.begin()+i+1));
return ans;
}
int main()
{
vector<string> inputs = { "/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/TVs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs",
"/Electronics/TVs",
"/Garden",
"/Automotive/Parts"
};
unordered_map<string, Node*> nodes;
Node* toproot = new Node("/");
for(auto s: inputs)
{
s += "/";
vector<string> tokens = stringparser(s);
Node* root = toproot;
for(string t:tokens)
{
cout << "processing token: "<< t << endl;
if(t == "/")
{
toproot->count++;
root = toproot;
}
else if(root->children.find(t) != root->children.end())
{
root->children[t]->count++;
root = root->children[t];
}
else
{
Node* newNode = new Node(t);
newNode->count++;
if(root != nullptr)
{
root->children[t] = newNode;
}
root = newNode;
}
}
cout << "----------" << endl;
}
vector<string> queries = {
"/",
"/Electronics",
"/Electronics/Computers",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs"
};
for(auto query:queries)
{
if(query != "/") query += "/";
vector<string> tokens = stringparser(query);
Node* root = toproot;
for(auto t = 1; t < tokens.size(); t++)
{
root = root->children[tokens[t]];
}
cout << query << " = " << root->count << endl;
}
return 0;
}
/*
Given the following set of strings, write a function that stores this information.
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/SSDs
// /Electronics/Computers/Graphics Cards
// /Electronics/Computers/SSDs
// /Electronics/TVs
// /Electronics/Computers/Graphics Cards
// /Electronics/TVs
// /Electronics/TVs
// /Garden
// /Automotive/Parts
Your datastructure should be able to provide information as such:
// / = 11
// /Electronics = 9
// /Electronics/Computers = 6
// /Electronics/Computers/Graphics Cards = 4
// /Electronics/TVs = 3
// etc
// ["/Electronics/Computers/Graphics Cards", "/Garden"]
*/
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
string name;
unordered_map<string, Node*> children;
int count;
Node(string s):name(s), count(0){}
~Node(){}
};
vector<string> stringparser(const string& s)
{
vector<string> ans;
int i = 0, j = 0;
while(i < s.size())
{
if(s[i] == '/')
{
ans.push_back(string(s.begin()+j, s.begin()+i+1));
j = i+1;
}
i++;
}
if(j < s.size())
ans.push_back(string(s.begin()+j, s.begin()+i+1));
return ans;
}
int main()
{
vector<string> inputs = { "/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/Computers/SSDs",
"/Electronics/TVs",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs",
"/Electronics/TVs",
"/Garden",
"/Automotive/Parts"
};
unordered_map<string, Node*> nodes;
Node* toproot = new Node("/");
for(auto s: inputs)
{
s += "/";
vector<string> tokens = stringparser(s);
Node* root = toproot;
for(string t:tokens)
{
cout << "processing token: "<< t << endl;
if(t == "/")
{
toproot->count++;
root = toproot;
}
else if(root->children.find(t) != root->children.end())
{
root->children[t]->count++;
root = root->children[t];
}
else
{
Node* newNode = new Node(t);
newNode->count++;
if(root != nullptr)
{
root->children[t] = newNode;
}
root = newNode;
}
}
cout << "----------" << endl;
}
vector<string> queries = {
"/",
"/Electronics",
"/Electronics/Computers",
"/Electronics/Computers/Graphics Cards",
"/Electronics/TVs"
};
for(auto query:queries)
{
if(query != "/") query += "/";
vector<string> tokens = stringparser(query);
Node* root = toproot;
for(auto t = 1; t < tokens.size(); t++)
{
root = root->children[tokens[t]];
}
cout << query << " = " << root->count << endl;
}
return 0;
}
map<string, int> StoreElectronicsInfo(string str_array[], int len) {
// "/Electronics/Computers/Graphics Cards"
map<string, int> dict;
string word;
for(int i=0; i < len; i++) {
// Travarse each string in array
for(int j=0; j < str_array[i].size(); j++) {
// Add chars to word string
word += str_array[i][j];
// Check for '/' and end of string
if( str_array[i][j] == '/' || j == str_array[i].size() - 1 ) {
// First '/'
if(word.size() == 1) {
dict[word]++; // Add '/' word and increment word count in map
}
else if(word.back() == '/') {
word.resize(word.size() - 1); // Remove last '/' from word, before adding it to map
}
dict[word]++; // Increment string count (minues last '/') to map
word += '/'; // Add '/' back to word
//cout << word << " = " << dict[word] << endl;
}
}
word = ""; // Erase word
}
return dict;
}
// Taher: I think i solved this problem
map<string, int> CommonStuff::StoreElectronicsInfo( string str_array[], int len )
{
// "/Electronics/Computers/Graphics Cards"
map<string, int> dict;
string word;
for(int i=0; i < len; i++) {
// Travarse each string in array
for(int j=0; j < str_array[i].size(); j++) {
// Add chars to word string
word += str_array[i][j];
// Check for '/' and end of string
if( str_array[i][j] == '/' || j == str_array[i].size() - 1 ) {
// First '/'
if(word.size() == 1) {
dict[word]++; // Add '/' word and increment word count in map
}
else if(word.back() == '/') {
word.resize(word.size() - 1); // Remove last '/' from word, before adding it to map
}
dict[word]++; // Increment string count (minues last '/') to map
word += '/'; // Add '/' back to word
//cout << word << " = " << dict[word] << endl;
}
}
word = ""; // Erase word
}
return dict;
}
class Node {
Node(String name) {
this.nodeName = name;
this.count = 0;
this.children = new HasMap<>();
}
String nodeName;
int count;
Map<String Name, Node child> children;
}
class DataStructure {
private Node parent = null;
public DataStructure {
parent = new Node("root");
}
public void populate(List<String> inputs) {
if(null == inputs)
return;
for(String input : inputs) {
//input : /Electronics/Computers/Graphics Cards
List<String> categories = parseInput(input); // categories : Electronics, Computers, Graphics Cards
if(null == categories)
continue;
Node current = parent;
for(String category : categories) { // category : Electronics
if(!current.children.containsKey(category)) {
Node child = new Node(category);
current.children.add(category, child);
}
current.count++;
current = current.children.get(category);
}
}
}
private List<String> parseInput(String input) {
if(input.isEmpty())
return null;
List<String> result = new ArrayList<String>(Arrays.asList(input.split("/")));
return result;
}
}
package com.testApp;
import java.util.ArrayList;
import java.util.List;
public class DSAlgos {
public static void main(String args[]){
List<String> allItems = new ArrayList<>();
allItems.add("// /Electronics/Computers/Graphics Cards");
allItems.add("// /Electronics/Computers/Graphics Cards");
allItems.add("// /Electronics/Computers/SSDs");
allItems.add("// /Electronics/Computers/Graphics Cards");
allItems.add("// /Electronics/Computers/SSDs");
allItems.add("// /Electronics/TVs");
allItems.add("// /Electronics/Computers/Graphics Cards");
allItems.add("// /Electronics/TVs");
allItems.add("// /Electronics/TVs");
allItems.add("// /Garden");
allItems.add("// /Automotive/Parts");
String input = "// /Electronics/TVs";
int found = 0;
for (String item : allItems){
if (item.contains(input)){
found ++;
}
}
System.out.println("\n \n Found " +found+ " items for " +input);
}
}
We can use Trie concept. Hope the below code works but I have not tested.
- Ruban Antony April 21, 2017