Walmart Labs Interview Question for Software Developers


Team: Customer experience
Country: United States
Interview Type: In-Person




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

initializations_

/*reader lock*/
mutex_init(r_lock)
/*writer lock*/
mutex_init(w_lock)
/*critical area lock*/
mutex_init(c_lock)
/*mutex and cond var for queue empty case*/
mutex_init(qe)
condvar_init(q_empty)
/*mutex and cond var for queue full case*/
mutex_init(qf)
condvar_init(q_full)

Assume that the queue has functions named remove() and insert(). Also, we have a function named generate() to create data to be entered in the queue

reader_code

/*exclusive access for readers*/
mutex_lock(r_lock)
/*wait till we have some data in the queue*/
mutex_lock(qe)
if (q_num_elem == 0) {
	/*not using the timeout condvar here as I dont know how to unlock qe and r_lock at timeout*/
	condvar_wait(q_empty, qe)
}
mutex_unlock(qe)
/*still we need to avoid sharing the queue with a writer*/
mutex_lock(c_lock)
/*read*/
elem = remove(queue)
q_num_elem--
/*signal a writer if waiting*/
//TODO actually PThreads dont define signal behavior when there is no waiting thread
if (q_num_elem == n-1) {
	cv_signal(q_full)
}
/*release critical area lock*/
mutex.unlock(c_lock)
/*release readers lock*/
mutex_unlock(r_lock)

Writer code is similar
writer_code

/*exclusive access for writers*/
mutex_lock(w_lock)
/*wait if the queue is full*/
mutex_lock(qf)
if (q_num_elem == n) {
	/*not using the timeout condvar here as I dont know how to unlock qf and w_lock at timeout*/
	condvar_wait(q_full, qf)
}
mutex_unlock(qf)
/*still we need to avoid sharing the queue with a reader*/
mutex_lock(c_lock)
/*write*/
elem = generate()
insert(queue, elem)
q_num_elem++
/*signal a reader if waiting*/
//TODO actually PThreads dont define signal behavior when there is no waiting thread
if (q_num_elem == 1) {
	cv_signal(q_empty)
}
/*release critical area lock*/
mutex.unlock(c_lock)
/*release writers lock*/
mutex_unlock(w_lock)

Please let me know if there is a starvation or deadlock.

- footloose June 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is similar to typical producer consumer problem except a small difference. We don't need to block writing while reading and vice-versa. Here is pseudo code:-

mutex m1
 mutex m2
 semaphore sem_full = SIZE_Q
 semaphore sem_empty = 0

 Read()
{
   wait(sem_empty)
   m1.lock()
       //Do read operation of first element from Q
   m1.unlock()
   post(sem_full)
}

Write()
{
   wait(sem_full)
    m2.lock()
     // Do write operation to write at back
    m2.unlcok()
    post(sem_empty)
}

- awagh1 March 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <chrono>
#include <condition_variable>
#include <iostream>
#include <mutex>
#include <queue>
#include <stdexcept>
#include <thread>

template<typename T>
class BoundedQueue {
private:
    std::mutex readMutex, writeMutex;
    std::condition_variable readCond, writeCond;
    std::queue<T> queue;
    size_t capacity;

public:
    BoundedQueue(size_t capacity) : capacity(capacity) {}

    // Attempt to read an element with a timeout
    bool Read(T& value, std::chrono::milliseconds timeout) {
        std::unique_lock<std::mutex> readLock(readMutex);
        if (!readCond.wait_for(readLock, timeout, [this]{ return !queue.empty(); })) {
            return false; // Timeout or condition not met
        }

        {
            std::lock_guard<std::mutex> writeLock(writeMutex); // Ensure not to block writers
            value = queue.front();
            queue.pop();
        }

        writeCond.notify_one(); // Notify one waiting writer, if any
        return true;
    }

    // Attempt to write an element with a timeout
    bool Write(const T& value, std::chrono::milliseconds timeout) {
        std::unique_lock<std::mutex> writeLock(writeMutex);
        if (!writeCond.wait_for(writeLock, timeout, [this]{ return queue.size() < capacity; })) {
            return false; // Timeout or condition not met
        }

        {
            std::lock_guard<std::mutex> readLock(readMutex); // Ensure not to block readers
            queue.push(value);
        }

        readCond.notify_one(); // Notify one waiting reader, if any
        return true;
    }
};

int main() {
    BoundedQueue<int> queue(5); // Example with an int queue and capacity of 5

    // Example usage
    std::thread writer([&queue] {
        for (int i = 0; i < 10; ++i) {
            if (queue.Write(i, std::chrono::seconds(1))) {
                std::cout << "Wrote: " << i << std::endl;
            } else {
                std::cout << "Write timed out for: " << i << std::endl;
            }
            std::this_thread::sleep_for(std::chrono::milliseconds(100));
        }
    });

    std::thread reader([&queue] {
        int value;
        while (queue.Read(value, std::chrono::seconds(2))) {
            std::cout << "Read: " << value << std::endl;
        }
        std::cout << "Read timed out or queue closed." << std::endl;
    });

    writer.join();
    reader.join();

    return 0;
}

- igvedmak March 28, 2024 | 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