Implement three whiteboard coding tasks
Company: Palo Alto Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
The interview report described several coding questions in the same category:
1. **Binary search**: Given a sorted array of integers and a target value, return the index of the target if it exists, otherwise return `-1`. The expected time complexity is `O(log n)`.
2. **Randomized set data structure**: Design a data structure that supports the following operations in average `O(1)` time:
- `insert(x)`: add `x` if it is not already present
- `remove(x)`: delete `x` if it is present
- `getRandom()`: return a uniformly random element from the current set
3. **Expression evaluator**: Given a string containing non-negative integers, spaces, and the operators `+`, `-`, `*`, and `/`, evaluate the expression while respecting normal operator precedence. As a follow-up, extend the evaluator to support nested parentheses.
Overview: This set of whiteboard coding tasks evaluates proficiency in algorithmic problem-solving, data structure design, and parsing techniques by covering binary search, randomized set operations with average O(1) complexity, and operator-precedence expression evaluation including nested parentheses.
Read the full Palo Alto Networks Software Engineer interview experience this question came from
Community answers
Answer by krani_be23
class RandomizedSet {
public:
vectorstore;
unordered_mapmpp;
RandomizedSet() {
}
bool insert(int val) {
if(mpp.find(val)!=mpp.end()) return false;//already present
store.push_back(val);//store value
mpp[val]=store.size()-1;//store index
return true;
}
bool remove(int val) {
if(mpp.find(val)==mpp.end()) return false;//not present
int index=mpp[val];
int lastEle=store.back();//store last avlue
store[index]=lastEle;
mpp[lastEle]=index;
store.pop_back();
mpp.erase(val);
return true;
}
int getRandom() {
return store[rand()%store.size()];
}
};
/**
Your RandomizedSet object will be instantiated and called as such:
RandomizedSet* obj = new RandomizedSet();
bool param_1 = obj->insert(val);
bool param_2 = obj->remove(val);
int param_3 = obj->getRandom();
*/