PoWerOnOff
BAN USERpublic class Customer{
private int userId;
private int numberOfPersons;
private Location location;
private Vehicle vehicle;
private Queue<Message> messageQueue;
public Customer(int userId, int number){...}
public void setLocation(Location location){...}
public void setVehicle(Vehicle vehicle){...}
public void setNumberOfPersons(int number){...}
public Location getLocation(){...}
public Vehicle getVehicle(){...}
public void getNumberOfPersons(){...}
public void receiveMessage(Message message){
messageQueue.add(message);
}
public Message sendMessage(){
return messageQueue.poll();
}
}
public class Vehicle{
private int vehicleId;
private Location location;
private int availableSeats;
private ArrayList<Customer> customersToPick;
private Queue<Message> messageQueue;
public Vehicle(int vehicleId, State state){...}
public void setSeats(int seats){...}
public void setLocation(Location location){...}
public void addCustomer(Customer person){...}
public void dropCustomer(Customer person){...}
public Location getLocation(){...}
public Customer getNearestCustomer(){...}
public int getSeats(){...}
public void receiveMessage(Message message){
messageQueue.add(message);
}
public Message sendMessage(){
return messageQueue.poll();
}
}
public class LocationBase{
private int baseId;
private Location location;
private int radius; // the radius that the base can cover
ArrayList<Customer> customers;
ArrayList<Vehicle> vehicles;
Queue<Message> messages;
public LocationBase(){
customers = new ArrayList<Customer>();
vehicles = new ArrayList<Vehicle>();
}
// set the location for location base
public void setLocation(Location location){...}
// add a customer
public void addCustomersInRange(Customer customer){...}
// update the locations of customers
public void updateCustomerLocation(){...}
// the customer goes out of the range
public void removeCustomerInRange(Customer customer){...}
// add a vehicle
public void addVehicleInRange(Vehicle v){...}
// the vehicle goes out of the range
public void removeVehicleInRange(Vehicle v){...}
// update the locations of vehicles
public void updateVehicleLocation(){...}
// send message to vehicle or to customer if messages queue is not empty
public void sendMessage(){...}
// receive message from vehicle or from customer, push it to message queue
public void receiveMessage(Message message){...}
// find a vehicle in the range of the base and assign a customer to it
public boolean connectCustomerToVehicle(){...}
// use a vehicle from another area
public void connectCustomerToVehicle(Vehicle v){...}
}
public class Network{
private ArrayList<LocationBase> network;
private int numberOfBases;
public Network(){}
...
}
void inward(TreeNode* root){
int count = 0;
queue<TreeNode*> q;
vector<vector<int> > result;
if(root != NULL){
count++;
q.push(root);
}
while(count != 0){
int newcount = 0;
vector<int> level;
for(int i = 0; i < count; ++i){
TreeNode* curr = q.front();
q.pop();
level.push(curr->val);
if(curr->left){
newcount++;
q.push(curr->left);
}
if(curr->right){
newcount++;
q.push(curr->right);
}
}
result.push_back(level);
count = newcount;
}
int left = 0, right = result.size() - 1;
while(left <= right){
vector<int> level = result[left++];
for(int i : level){
cout << i << " ";
}
cout << endl;
if(left < right){
level = result[right--];
for(int i = level.size() - 1; i >= 0; i--){
cout << i << " ";
}
cout << endl;
}
}
}
int maxProfit(vector<int> & prices){
int maxPrice = 0;
int profit = 0;
for(int i = prices.size() - 1; i >= 0; i--){
maxPrice = max(maxPrice, prices[i]);
profit = max(profit, maxPrice - prices[i]);
}
return profit;
}
void connect(TreeLinkNode* root){
queue<TreeLinkNode*> q;
int count = 0;
if(root != NULL) {
q.push(root);
count = 1;
}
while(count != 0){
int newcount = 0;
bool isFirstNode = true;
TreeLinkNode* prev = NULL;
for(int i = 0; i < count; ++i){
TreeLinkNode* curr = q.front();
q.pop();
if(isFirstNode){
isFirstNode = false;
prev = curr;
}
else{
prev->next = curr;
prev = curr;
}
if(curr->left != NULL){
q.push(curr->left);
newcount++;
}
if(curr->right != NULL){
q.push(curr->right);
newcount++;
}
}
count = newcount;
}
}
I doubt that is a group interview question.
- PoWerOnOff November 30, 2015I was asked a similar question in an interview. The premise of this question is that all the logs are static, like records saved during last week. They are not dynamic and on-going. Compared to using a priority queue, which is suitable for on-going stream information, it is better to pre-process the logs, push quantity-price pairs to an array, and sort the array based on quantity.
Then segregate the huge array to small segments, and distribute the segments to different computers. Use merge sort or quick sort or other sorting algorithms to sort those segments. Eventually combine the result and obtain a large sorted array.
I guess the interviewer wanted an answer like this.
how to build a distributed system for this particular case?
- PoWerOnOff November 29, 2015When you are standing at a node, this node has both left and right children, update the maximum value, and return the greater result from left and right node to its parent. If the node has only one child, return the value from that child. If it doesn't have children which indicates that's a leaf node, return itself.
int getLargestPathSize(TreeNode* root){
int sum = INT_MIN;
maxSum(root, sum);
return sum;
}
int maxSum(TreeNode* root, int & sum){
if(root == NULL) return 0;
int left = maxSum(root->left, sum);
int right = maxSum(root->right, sum);
if(root->left && root->right){
sum = max(sum, left + right + root->value);
return max(left, right) + root->value;
}
return (root->left ? left : right) + root->value;
}
#include <stdlib.h>
#include <iostream>
using namespace std;
// to reverse the linkedlist, I will use recursion to the end/right of the list, reverse the last k nodes there, return its new head, and link the last reversed list to the left side list. and operate on the section with k nodes, and then on next left k nodes... until reach the head
struct ListNode{
int value;
ListNode* next;
ListNode(int v) : value(v), next(NULL){}
};
ListNode* reverseKNodes(ListNode* head, int k, int sec){
// find the head of the next section (k nodes)
ListNode* curr = head;
for(int i = 0; i < k; i++){
if(curr == NULL){
return head;
}
curr = curr->next;
}
ListNode* end = head;
for(int i = 0; i < k - 1; i++){
end = end->next;
}
ListNode* next = curr; // head of the next section
// reverse the this section (k nodes) only if this is an odd section
if(sec % 2 == 1){
ListNode *prev = NULL;
curr = head;
for(int i = 0; i < k; i++){
ListNode* t = curr->next;
curr->next = prev;
prev = curr;
curr = t;
}
head->next = reverseKNodes(next, k, sec + 1); // link to the next section
// the new head of this section is prev
return prev;
}
else{
end->next = reverseKNodes(next, k, sec + 1);
return head;
}
}
ListNode* reverse(ListNode* head, int k){
return reverseKNodes(head, k, 1);
}
int main(){
ListNode* head = new ListNode(0);
ListNode* curr = head;
for(int i = 0; i < 21; i++){
curr->next = new ListNode(i+1);
curr = curr->next;
}
ListNode* result = reverse(head, 5);
cout << "******************" << endl;
while(result != NULL){
cout << result->value << " ";
result = result->next;
}
cout << endl;
return 0;
}
class Reservoir{
public:
Reservoir(int n){
size = n;
}
// put the number in stream in reservoir
void put(int n){
reservoir.push_back(n);
sort(reservoir.begin(), reservoir.end());
if(reservoir.size() >= size){
reservoir.resize(size);
}
}
// get the nth largest number
int get(){
return reservoir.back();
}
private:
int size;
vector<int> reservoir;
};
#include <unordered_map>
#include <vector>
#include <iostream>
#include <climits>
using namespace std;
bool validate(unordered_map<int, int> & map){
for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++){
if(it->second < 1){
return false;
}
}
return true;
}
vector<int> smallestWindow(vector<int> input, vector<int> keys){
unordered_map<int, int> map;
vector<int> result;
for(int i = 0; i < keys.size(); i++){
map.insert({keys[i], 0});
}
int left, right;
left = right = 0;
int len = INT_MAX;
int l=0, r=0;
while(right < input.size()){
// push a number to the window
if(map.find(input[right]) != map.end()){
map[input[right]]++;
// remove a number from the window until the window is invalid
while(validate(map)){
if(right - left < len){
len = right - left;
r = right;
l = left;
}
if(map.find(input[left]) != map.end()){
map[input[left]]--;
}
left++;
}
}
right++;
}
for(int i = l; i <= r;i++){
result.push_back(input[i]);
}
return result;
}
int main(){
vector<int> input = {2,5,7,9,8,5,1,3,6,5};
vector<int> keys = {1, 3, 5};
smallestWindow(input, keys);
return 0;
}
struct Comparator{
bool operator()(string & a, string & b){
return (a + b) > (b + a);
}
} comparator;
string largestNumber(vector<int>& nums) {
vector<string> strs;
for(int num : nums){
strs.push_back(to_string(num));
}
sort(strs.begin(), strs.end(), comparator);
string res;
for(string s : strs){
res += s;
}
return res[0] == '0' ? "0" : res;
}
int binarySearch(int target, vector<int> & array){
int left = 0, right = array.size() - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(array[mid] == target){
return target;
}
else if(array[mid] < target){
left = mid + 1;
}
else{
right = mid - 1;
}
}
if(right == -1){
return array[left];
}
else if(right == array.size() - 1){
return array[right];
}
else{
return abs(array[right] - target) > abs(array[left] - target) ? array[left] : array[right];
}
}
bool check(vector<int> & array, int a, int b){
if(a > b) swap(a, b);
// find the ga >= a; find the lb <= b;
// if(ga <= lb) return true;
// else return false;
int ga, lb;
int left = 0, right = array.size() - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(array[mid] == a){
ga = a;
break;
}
else if(array[mid] < a){
left = mid + 1;
}
else{
right = mid - 1;
}
}
if(right == array.size() - 1){
return false;
}
ga = array[right];
int left = 0, right = array.size() - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(array[mid] == b){
ga = a;
break;
}
else if(array[mid] < b){
left = mid + 1;
}
else{
right = mid - 1;
}
}
lb = array[left];
return ga <= lb;
}
int findMinimum(vector<int> & a, vector<int> & b, vector<int> & c){
int minSum = -1;
for(int i = 0; i < a.size(); i++){
int numb = binarySearch(a[i], b);
if(check(c, a[i], numb)){
minSum = min(minSum, 2 * abs(a[i] - numb));
}
int numc = binarySearch(a[i], c);
if(check(b, a[i], numc)){
minSum = min(minSum, 2 * abs(a[i] - numc));
}
}
for(int i = 0; i < b.size(); i++){
int numc = binarySearch(b[i], c);
if(check(a, b[i], numc){
minSum = min(minSum, s * abs(b[i] - numc));
}
}
return minSum;
}
But I think you could correct your solution like this, each time you get a minimum value, check it before you use it. For example, if current minimum value comes from f = 2|a-c|, determine whether there is b satisfying a>b>c or c>b>a. If such a b doesn't exist, discard the result. Otherwise, save it.
- PoWerOnOff November 17, 2015The final result is sum of three terms. You think the minimum sum would come from 2 minimum terms + 1 term (no restriction on it). Is it possible that none of the three terms is minimum but their sum is minimum?
- PoWerOnOff November 17, 2015Simplify the formula f = |a-b|+|b-c|+|c-a|, we get 6 scenarios:
a>b>c: f = 2a - 2c
a>c>b: f = 2a - 2b
b>a>c: f = 2b - 2c
b>c>a: f = 2b - 2a
c>a>b: f = 2c - 2b
c>b>a: f = 2c - 2a
It seems f = max(|a-b|,|a-c|,|c-a|)*2, but you may find the maximum result in case 1:
a>b>c: f = a-b+b-c+a-c = 2a - 2c. But what if you can't find b which satisfies a>b>c, this maximum value in fact is impossible to obtain. You erroneously get a max result.
Sort and remove duplicate
vector<int> dedup(vector<int> arr){
sort(arr.begin(), arr.end());
int slow = 0;
for(int i = 0; i < arr.size(); i++){
if(arr[slow] != arr[i]){
arr[++slow] = arr[i];
}
}
arr.resize(slow+1);
return arr;
}
A breadth first search solution
bool pathFinder(vector<vector<int> > & grid, pair<int, int> start, pair<int, int> end){
int row = grid.size();
int col = grid[0].size();
unordered_set<int> visited;
queue<pair<int, int> > q;
q.push(start);
visited.insert(start->first * col + start->second);
while(!q.empty()){
pair<int, int> p = q.front();
q.pop();
int y = p->first;
int x = p->second;
if(y == end->first && x == y->second){
return true;
}
visited.insert(y * col + x);
// right
if(x + 1 < col && grid[y][x+1] != 1 && visited.find(y * col + x + 1) == visited.end()){
q.push({y, x + 1});
}
// left
if(x - 1 >= 0 && grid[y][x-1] != 1 && visited.find(y * col + x - 1) == visited.end()){
q.push({y, x - 1});
}
// down
if(y + 1 < row && grid[y+1][x] != 1 && visited.find((y + 1) * col + x) == visited.end()){
q.push({y + 1, x});
}
// up
if(y - 1 >= 0 && grid[y-1][x] != 1 && visited.find((y - 1) * col + x) == visited.end()){
q.push({y - 1, x});
}
}
return false;
}
A quicksort solution.
struct Item{
string itemId;
int quantitySold;
};
void sortf(vector<Item*> & items, int start, int end){
if(start >= end) return;
int left = start, right = end;
int pivot = items[start]->quantitySold;
while(left < right){
if(items[left]->quantitySold > pivot && items[right]->quantitySold < pivot){
swap(items[left], items[right]);
}
else if(items[left]->quantitySold <= pivot){
left++;
}
else{
right--;
}
}
if(items[right]->quantitySold > pivot){
right--;
}
swap(items[start], items[right]);
sortf(items, start, right - 1);
sortf(items, right + 1, end);
}
void quickSort(vector<Item*> & items){
sortf(items, 0, items.size() - 1);
}
string find(vector<Item*> & items, int i){
quickSort(items);
return items[items.size() - i]->itemId;
}
The problem actually wants you to implement a min heap or a sorting algorithm.
- PoWerOnOff November 17, 2015Time complexity = O(m*n); space complexity = O(m * n).
It can also be solved by compressing the 2-D array to a linear array which only consumes O(n) space.
int maxGold(vector<vector<int> > & grid){
int row = grid.size();
int col = grid[0].size();
vector<vector<int> > gold(row, vector<int>(col, 0));
int res = 0;
// populate the first column
for(int j = 0; j < row; j++){
gold[j][0] = grid[j][0];
res = max(res, gold[j][0]);
}
// start from the second column
for(int i = 1; i < col; i++){
for(int j = 0; j < row; j++){
if(j == 0){
gold[j][i] = max(gold[j][i-1], gold[j+1][i-1]) + grid[j][i];
}
else if(j == row - 1){
gold[j][i] = max(gold[j][i-1], gold[j-1][i-1]) + grid[j][i];
}
else{
gold[j][i] = max(max(gold[j][i-1], gold[j-1][i-1]), gold[j+1][i-1]) + grid[j][i];
}
res = max(res, gold[j][i]);
}
}
return res;
}
I know to use O(n) space to solve it. But can you tell me how you use only O(1) to solve the problem?
- PoWerOnOff November 17, 2015Good idea! I implemented your idea in C++.
vector<int> firstLastNodes(TreeNode *root){
queue<TreeNode*> q;
vector<int> res;
int count = 0;
if(root != NULL) {
count = 1;
q.push(root);
}
while(count != 0){
int newcount = 0;
vector<int> level;
for(int i = 0; i < count; i++){
TreeNode *node = q.front();
q.pop();
level.push_back(node->val);
if(node->left != NULL){
newcount++;
q.push(node->left);
}
if(node->right != NULL){
newcount++;
q.push(node->right);
}
}
res.push_back(level.back()->val); // left node
if(level.size() >= 2){
res.push_back(level.front()->val); // right node
}
count = newcount;
}
return res;
}
Can you explain it in detail? I've never seen an algorithm that runs in O(n) for this problem.
- PoWerOnOff November 17, 20151. Traverse two trees and push numbers in hash set. Duplicated numbers are removed in hash set
2. Compare two hash sets: compare (1) their sizes; (2) numbers one by one.
void preorder(TreeNode *root, unordered_set<int> & set){
if(root == NULL)
return;
set.insert(root->val);
preorder(root->left, set);
preorder(root->right, set);
}
bool isIdentical(TreeNode *n1, TreeNode *n2){
unordered_set<int> set1, set2;
preorder(n1, set1);
preorder(n2, set2);
if(set1.size() != set2.size()){
return false;
}
for(unordered_set<int>::iterator it = set1.begin(); it != set1.end(); it++){
if(set2.find(*it) == set2.end()){
return false; // tree2 does not have a number in tree1
}
}
return true;
}
I don't quite understand the extension. Is the question meaning that the opening and closing parenthesis are no longer standalone. They are wrapped by quotation marks like '(' and ')' so we must see '(' and ')' as a whole. Do I understand it correctly?
- PoWerOnOff November 17, 2015bool isValid(string s){
stack<char> st;
for(int i = 0; i < s.length(); i++){
if(s[i] == '<' || s[i] == '(' || s[i] == '['){
st.push(s[i]);
}
else{
if(!st.empty() && ((s[i] == '>' && st.top() == '<') || (s[i] == ')' && st.top() == '(') || (s[i] == ']' && st.top() == '[')))
{
st.pop();
}
else if(isalpha(s[i]) || ispunct(s[i]) || (s[i] >= '0' && s[i] <= '9')){
continue;
}
else{
return false;
}
}
}
return st.empty();
}
struct TreeNode{
int id;
string name;
vector<string> children;
};
TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *n1, TreeNode *n2){
if(root == NULL){
return NULL;
}
vector<TreeNode*> res;
for(int i = 0; i < root->children.size(); i++){
res.push_back(lowestCommonAncestor(root->children[i], n1, n2));
}
if(root == n1 || root == n2){
return root;
}
int isN1 = -1, isN2 = -1;
for(int i = 0; i < res.size(); i++){
if(res[i] != NULL)
isN1 = i;
if(res[i] != NULL)
isN2 = i;
}
if(isN1 != -1 && isN2 != -1){
return root;
}
else{
if(isN1 != -1)
return res[isN1];
else if(isN2 != -1)
return res[isN2];
else
return NULL;
}
}
pair<ListNode*, ListNode*> partitionList(ListNode *head){
int fib = 1, fib2 = 1;
int count = 0;
ListNode *fibhead, *fp;
fibhead = fp = new ListNode(0);
ListNode *nfibhead, *nfp;
nfibhead = nfp = new ListNode(0);
while(head != NULL){
if(count == fib){
// add to fib list
fp->next = head;
fp = fp->next;
// calculate the next Fibonacci number
fib = fib + fib2;
fib2 = fib - fib2;
}
else{
// add to non-fib list
nfp->next = head;
nfp = nfp->next;
}
count++;
head = head->next;
}
fp = fibhead->next;
delete fibhead;
nfp = nfibhead->next;
delete nfibhead;
return {fp, nfp};
}
int minDistance(string s, string word1, string word2){
int slow = 0;
vector<string> words;
for(int i = 0; i < s.length(); i++){
if(s[i] == ' '){
words.push_back(s.substr(slow, i - slow));
slow = i + 1;
}
}
words.push_back(s.substr(slow, s.length() - slow));
int pos1 = -1, pos2 = - 1, min = 0;
for(int i = 0; i < words.size(); i++){
if(words[i] == word1){
pos1 = i;
if(pos2 != -1 && abs(pos1 - pos2) < min){
min = abs(pos1 - pos2);
}
}
if(words[i] == word2){
pos2 = i;
if(pos1 != -1 && abs(pos1 - pos2) < min){
min = abs(pos1 - pos2);
}
}
}
return min;
}
Good
- PoWerOnOff November 17, 2015
Good design. I write Java code to implement your idea. This is just a simple example.
- PoWerOnOff December 13, 2015