NVIDIA Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use Trie concept. Hope the below code works but I have not tested.

public class Device
{	
	Dictionary<string,Device> children = new Dictionary<string,Device>();
	int size;
	public Store(string devicePath)
	{
		string[] devices = devicePath.Split(new char[] {'//'});
		Store(devices, 0);
	}
	
	private void Store(string[] devices, int index)
	{
		size++;
		if(devices.Length == index)
		{
			return;
		}
		
		if(children[index] == null)
		{
			Device device = new Device();
			children[index] = device;
		}
		
		children[index].Store(devices, index+1);
	}
	
	public int FindCount(string[] devices, int index)
	{
		if(devices.Length == index)
		return size;
		
		if(children[index] == null)
		return 0;
		
		children[index].FindCount(devices, index++);
	}
}

- Ruban Antony April 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
        }
    }
}

- Sibendu Dey April 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
	   }
   }
}

- Anonymous May 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
	   }
   }
}

- Anonymous May 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}
}
}

- just_do_it May 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Marek October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Marek October 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
    }
}

- JSDUDE April 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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);
}
}

- Sachinrk May 11, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More