Sharing the questions I got for Datadog tech screen and the solution I used in the interview. For both the problems the expectation is to run at least one test case presented in the question. Difficulty level - Easy to Medium.
Overall interview experience: Positive
Interview date: July-2024
Duration: 60 min (10 min intro, 45 min problem solving, 5 min wrap up)
Verdict: Pass
Question 1
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]);
}
}
}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. I didn't get chance to correctly implement the follow up but I was able to explain the approach. My solution to this problem might not be accurate as I had modified it for the follow up which I was not able to complete.
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
total_size(file_system) -> 8675777
Add a path parameter and return only the size underneath the specified path.
def total_size(file_system, path):
return 0
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"));
}
// Code till here was provided as part of the question setup
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;
}
}