Round 1
Questions:
Question
Given a list of (positive integer) latencies, a number of buckets and bucket width, calculate how frequently each range of latencies occurs.
The first bucket always starts at 0. For instance, the ranges for 11 buckets of width 10 are: 0-9, 10-19, 20-29, 30-39, 40-49, 50-59, 60-69, 70-79, 80-89, 90-99, >=100.
For example:
>>> latencies = [90, 11, 3, 35, 17, 28, 64, 53, 52, 87, 63, 46, 40, 50, 31, 92, 45, 32, 22, 54, 87, 108, 62, 33, 87, 12, 67, 56, 94, 119, 96, 23, 21, 25, 86, 5, 32, 77, 3, 16, 8, 61, 105, 88, 49, 57, 114, 118, 20, 79, 44, 55, 113, 23, 13, 86, 16, 81, 1, 111, 84, 76, 24, 54, 110, 7, 100, 40, 3, 37, 96, 37, 67, 48, 79, 47, 108, 36, 15, 112, 37, 13, 40, 66, 39, 110, 47, 87, 34, 50, 55, 112, 70, 88, 2, 86, 110, 20, 2, 57] >>> number_of_buckets = 11 >>> bucket_width = 10 >>> calc_buckets(latencies, number_of_buckets, bucket_width) 0- 9: 9 10-19: 8 20-29: 9 30-39: 11 40-49: 10 50-59: 11 60-69: 7 70-79: 5 80-89: 11 90-99: 5 100+ : 14
class Solution { int[] calc_buckets(int[] latencies, int number_of_buckets, int bucket_width) { int[] out = new int[number_of_buckets]; for (int i=0; i<latencies.length; ++i) { int idx = latencies[i]/bucket_width; if (idx >= number_of_buckets) { idx = number_of_buckets-1; } out[idx]++; } return out; } public static void main(String[] args) { int[] latencies = {90, 11, 3, 35, 17, 28, 64, 53, 52, 87, 63, 46, 40, 50, 31, 92, 45, 32, 22, 54, 87, 108, 62, 33, 87, 12, 67, 56, 94, 119, 96, 23, 21, 25, 86, 5, 32, 77, 3, 16, 8, 61, 105, 88, 49, 57, 114, 118, 20, 79, 44, 55, 113, 23, 13, 86, 16, 81, 1, 111, 84, 76, 24, 54, 110, 7, 100, 40, 3, 37, 96, 37, 67, 48, 79, 47, 108, 36, 15, 112, 37, 13, 40, 66, 39, 110, 47, 87, 34, 50, 55, 112, 70, 88, 2, 86, 110, 20, 2, 57}; Solution obj = new Solution(); int out[] = obj.calc_buckets(latencies, 11, 10); for (int i=0; i<out.length; ++i) { System.out.println(i + " " + out[i]); } } }
Candidate's Approach
The candidate implemented a method to calculate the frequency of latencies in specified buckets. They iterated through the latencies, determining the appropriate bucket index for each latency and incrementing the count for that bucket.
Interviewer's Feedback
The interviewer appreciated the candidate's clear understanding of the problem and the efficient implementation of the solution. They suggested considering edge cases for larger latency values.
Question 2
Given a file system structure representing directories and files, return the total size of files in the structure. The follow up to this was to find if the given path exists and then provide the size.
home/ ├── me/ │ ├── foo.txt : 416 │ ├── metrics.txt : 5892 │ └── src/ │ ├── site.html : 6051 │ ├── site.css : 5892 │ └── data.csv : 332789 └── you/ └── dict.json : 4913364 bin/ ├── bash: 618416 ├── cat: 23648 └── ls: 38704 var/ └── log/ ├── dmesg : 1783894 ├── wifi.log : 924818 └── httpd/ ├── access.log : 17881 └── access.log.0.gz : 4012
Expected results:
>>> total_size(file_system, "/") 8675777 >>> total_size(file_system, "/home") 5264404 >>> total_size(file_system, "/bin") 680768 >>> total_size(file_system, "var/") 2730605 >>> total_size(file_system, "/home/me/") 351040 >>> total_size(file_system, "/var/log/wifi.log") 924818
class Solution { public static abstract class FSEntry { String name; private FSEntry(String name) { this.name = name; } } public static class Directory extends FSEntry { public List<FSEntry> content; public Directory(String name, FSEntry... entries) { super(name); this.content = List.of(entries); } } public static class File extends FSEntry { public int size; public File(String name, int size) { super(name); this.size = size; } } public static void main(String[] args) { Directory root = new Directory( "", new Directory( "home", new Directory( "me", new File("foo.txt", 416), new File("metrics.txt", 5892), new Directory( "src", new File("site.html", 6051), new File("site.css", 5892), new File("data.csv", 332789))), new Directory("you", new File("dict.json", 4913364))), new Directory("bin", new File("bash", 618416), new File("cat", 23648), new File("ls", 38704)), new Directory( "var", new Directory( "log", new File("dmesg", 1783894), new File("wifi.log", 924818), new Directory( "httpd", new File("access.log", 17881), new File("access.log.0.gz", 4012))))); System.out.println(getTotalSize(root, "/home")); } public static int getTotalSize(FSEntry entry, String path) { if(path == null || path.length() == 0) { return 0; } if (path.equals("/")) { return getTotalSizeUtil(entry); } String paths[] = path.split("/"); FSEntry outEntry = getEntry(paths, 0, entry); return getTotalSizeUtil(outEntry); } static FSEntry getEntry(Stack<String> currPath, FSEntry entry) { if (entry.name == currPath.peek()) { currPath.pop(); if (!currPath.isEmpty()) return getEntry(currPath, entry); return entry; } if (entry instanceof Directory) { Directory currD = (Directory)entry; for (int i=0; i<currD.content.size(); ++i) { FSEntry entryL = getEntry(currPath, currD.content.get(i)); if (entryL != null) { return entryL; } } } return null; } static int getTotalSizeUtil(FSEntry entry) { if (entry == null) { return 0; } int total = 0; if (entry instanceof File) { File curr = (File)entry; total = curr.size; } else if (entry instanceof Directory) { Directory curr = (Directory)entry; for (int i=0; i<curr.content.size(); ++i) { total += getTotalSizeUtil(curr.content.get(i)); } } return total; } }
Candidate's Approach
The candidate explained their approach to calculate the total size of files in a file system structure. They created classes for files and directories and implemented a recursive method to traverse the structure and sum the sizes of the files. They also discussed the follow-up requirement to check for a specific path, although they did not complete the implementation.
Interviewer's Feedback
The interviewer noted that the candidate had a solid understanding of the file system structure and provided a good explanation of their approach. They encouraged the candidate to focus on completing the follow-up implementation in future interviews.