Netflix Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Written Test
This seems to work with the few tests I've done. I cheated a little and converted the letter indexed rows to just a number, but that wouldn't be too hard to swap back in if I had some real data to work with. I also assumed the "expressions" were just links to other cells, or null if there was no link.
import java.util.ArrayList;
import java.util.HashMap;
public class SpreadsheetProblem {
public static boolean hasCycle(ArrayList<ArrayList<String>> spreadsheet,
HashMap<String, Boolean> visited, int c, int r) {
System.out.println("looking at: " + c + ", " + r);
String thisId = String.valueOf(c) + '-' + String.valueOf(r);
if (visited.get(thisId) != null) {
// this node has been visited before, we have found a cycle
return true;
}
ArrayList<String> thisColumn = spreadsheet.get(c);
String thisNode = thisColumn.get(r);
if (thisNode == null) {
return false;
}
visited.put(thisId, true);
String[] edges = thisNode.split(" ");
for (int i = 0; i < edges.length; i++) {
String[] indexes = edges[i].split("-");
int newC = Integer.parseInt(indexes[0]);
int newR = Integer.parseInt(indexes[1]);
if (hasCycle(spreadsheet, visited, newC, newR)) {
return true;
}
}
return false;
}
public static ArrayList<String> createRow(int c) {
ArrayList<String> row = new ArrayList<String>();
for (int i = 0;i < c; i++) {
row.add(null);
}
return row;
}
public static ArrayList<ArrayList<String>> createSpreadsheet() {
ArrayList<ArrayList<String>> spreadsheet = new ArrayList<ArrayList<String>>();
ArrayList<String> r0 = createRow(10);
r0.set(0, "3-0 3-3");
r0.set(8, "1-2");
spreadsheet.add(r0);
ArrayList<String> r1 = createRow(10);
r1.set(1, "3-3");
spreadsheet.add(r1);
ArrayList<String> r2 = createRow(10);
spreadsheet.add(r2);
ArrayList<String> r3 = createRow(10);
r3.set(3, "0-0");
r3.set(0, "2-0");
spreadsheet.add(r3);
return spreadsheet;
}
public static void main(String[] args) {
ArrayList<ArrayList<String>> spreadsheet = createSpreadsheet();
HashMap<String, Boolean> visited = new HashMap<String, Boolean>();
boolean hasCycle = false;
for (int c = 0; c < spreadsheet.size();c++) {
ArrayList<String> thisCol = spreadsheet.get(c);
for (int r = 0;r < spreadsheet.size();r++) {
String thisNode = thisCol.get(r);
if (thisNode != null) {
visited.clear();
System.out.println();
if (hasCycle(spreadsheet, visited, c, r)) {
hasCycle = true;
break;
}
}
}
if (hasCycle) break;
}
System.out.println("Does the spreadsheet have a cycle? " + hasCycle);
}
}
I would like to ask Interviewer whether he want to find out a loop for a given Spreadsheet or upon updating value of a cell. The complexity of the problem will differ in both the cases.
- pc May 26, 2015In case of doing this when updating value of a cell, I will follow this simple approach
For a given Cell value, Get all the referenced Node
Recursively try to find the referenced node. Dead end of the recursion would be no further reference to any cell. A reference back to the Start cell should tell us this is a loop.
Now someone can argue that it is possible to have a loop on the way, not to the start point. My answer would be, it will not be allowed when someone tried to edit value of C Cell.
E.g. A -> B ->C ->D ->C
If you really want to check loop in a given spread sheet, this is going to be little complex as one of the solution provided by thejediknight