Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Need to use a producer consumer queuel.
- Create a threadsafe q=queue<string> that should contain File paths (relative or absolute)
- Create a Thread pool of n threads that monitors q
- Each thread's task is to dequeue and delete
- Main thread will do the following:
-- Enumerate all children of the Folder
-- If child is File, add to q
-- If child is Folder, recurse
Should do the trick
Need to use a producer consumer queuel.
- Create a threadsafe q=queue<string> that should contain File paths (relative or absolute)
- Create a Thread pool of n threads that monitors q
- Each thread's task is to dequeue and delete
- Main thread will do the following:
-- Enumerate all children of the Folder
-- If child is File, add to q
-- If child is Folder, recurse
Should do the trick
Need to use a producer consumer queue.
- Create a threadsafe q=queue<string> that should contain File paths (relative or absolute)
- Create a Thread pool of n threads that monitors q
- Each thread's task is to dequeue and delete
- Main thread will do the following:
-- Enumerate all children of the Folder
-- If child is File, add to q
-- If child is Folder, recurse
Should do the trick
Need to use a producer consumer queue.
- Create a threadsafe q=queue<string> that should contain File paths (relative or absolute)
- Create a Thread pool of n threads that monitors q
- Each thread's task is to dequeue and delete
- Main thread will do the following:
-- Enumerate all children of the Folder
-- If child is File, add to q
-- If child is Folder, recurse
Should do the trick
public void removeForceFJ(String filePath) {
long startTime = System.nanoTime();
File file = new File(filePath);
if (file.exists()) {
ForkJoinPool forkJoinPool = new ForkJoinPool();
forkJoinPool.invoke(new ForkJoinTask(file));
}
long endTime = System.nanoTime();
System.out.printf("timeTaken = %d ns %n", (endTime - startTime));
}
private static class ForkJoinTask extends RecursiveAction {
private File file;
ForkJoinTask(File file) {
this.file = file;
}
@Override
protected void compute() {
if (file.isDirectory()) {
File[] children = file.listFiles();
if (children != null && children.length > 0) {
List<ForkJoinTask> forkJoinTaskList = new ArrayList<ForkJoinTask>();
for (File child : children) {
forkJoinTaskList.add(new ForkJoinTask(child));
}
invokeAll(forkJoinTaskList);
}
file.delete();
} else {
file.delete();
}
}
}
public void removeForceFJ(String filePath) {
long startTime = System.nanoTime();
File file = new File(filePath);
if (file.exists()) {
ForkJoinPool forkJoinPool = new ForkJoinPool();
forkJoinPool.invoke(new ForkJoinTask(file));
}
long endTime = System.nanoTime();
System.out.printf("timeTaken = %d ns %n", (endTime - startTime));
}
private static class ForkJoinTask extends RecursiveAction {
private File file;
ForkJoinTask(File file) {
this.file = file;
}
@Override
protected void compute() {
if (file.isDirectory()) {
File[] children = file.listFiles();
if (children != null && children.length > 0) {
List<ForkJoinTask> forkJoinTaskList = new ArrayList<ForkJoinTask>();
for (File child : children) {
forkJoinTaskList.add(new ForkJoinTask(child));
}
invokeAll(forkJoinTaskList);
}
file.delete();
} else {
file.delete();
}
}
}
#include <string>
#include <mutex>
#include <thread>
#include <iostream>
#include <dirent.h>
#include <vector>
#include <sys/types.h>
#include <unistd.h>
using namespace std;
vector<string> buf;
int produced_count = 0;
int consumed_count = 0;
condition_variable counts_cv;
mutex counts_mutex;
vector<thread> threads;
int idle_threads_count = 0;
bool stop = false;
void ProduceFile(string const item)
{
unique_lock<mutex> lock(counts_mutex);
while (produced_count - consumed_count == buf.size()) {
counts_cv.wait(lock);
}
buf[produced_count++ % buf.size()] = item;
counts_cv.notify_all();
cerr << "produced: " << item << "\n";
}
void ConsumeFiles()
{
while (true) {
unique_lock<mutex> lock(counts_mutex);
while (produced_count == consumed_count) {
++idle_threads_count;
counts_cv.notify_all();
counts_cv.wait(lock);
--idle_threads_count;
if (stop) {
return;
}
}
string item = buf[consumed_count++ % buf.size()];
counts_cv.notify_all();
lock.unlock();
cerr << "removing file: " << this_thread::get_id() << ": " << item << "\n";
}
}
void RemoveEmptyDir(string const &dir)
{
unique_lock<mutex> lock(counts_mutex);
while (idle_threads_count != threads.size()) {
counts_cv.wait(lock);
}
cerr << "removing dir: " << dir << "\n";
}
void Rm(string const &dir_name)
{
DIR *dir, *dir2;
struct dirent *ent;
if ((dir = opendir(dir_name.c_str())) != NULL) {
while (ent = readdir(dir)) {
string item_name(ent->d_name);
string item(dir_name + '/' + item_name);
if (item_name != "." &&
item_name != "..")
{
if ((dir2 = opendir(item.c_str())) != NULL) {
closedir(dir2);
Rm(item);
} else {
ProduceFile(item);
}
}
}
closedir(dir);
RemoveEmptyDir(dir_name);
}
}
void RemoveDir(string const &dir_name)
{
buf.resize(16); // must be true: (INT_MAX + 1) % buf.size() == 0
for (int i = 0; i < 8; ++i) {
threads.push_back(thread(ConsumeFiles));
}
Rm(dir_name);
unique_lock<mutex> lock(counts_mutex);
stop = true;
lock.unlock();
counts_cv.notify_all();
for (int i = 0; i < threads.size(); ++i) {
threads[i].join();
}
}
int main(int argvc, char const **argv)
{
RemoveDir("./tmp");
return 0;
}
Need to use a producer consumer queuel.
- Pranay August 18, 2017- Create a threadsafe q=queue<string> that should contain File paths (relative or absolute)
- Create a Thread pool of n threads that monitors q
- Each thread's task is to dequeue and delete
- Main thread will do the following:
-- Enumerate all children of the Folder
-- If child is File, add to q
-- If child is Folder, recurse
Should do the trick