Last active
January 5, 2021 14:29
-
-
Save bobfang1992/88f3c2ceeaedbede3f633babb9955dfd to your computer and use it in GitHub Desktop.
mock_interview_2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
//Given two sequences pushed and popped with distinct values, | |
//return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack. | |
//Example 1: | |
//Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] | |
//Output: true | |
//Explanation: We might do the following sequence: | |
//push(1), push(2), push(3), push(4), pop() -> 4, | |
//push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 | |
//Example 2: | |
//Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2] | |
//Output: false | |
//Explanation: 1 cannot be popped before 2. | |
// interview | |
class solution | |
{ | |
public: | |
bool pushPop(vector<int>& pushed, vector<int>& popped) | |
{ | |
stack<int> s; | |
int idx = 0; | |
for (int n : popped) | |
{ | |
while ((s.empty() || s.top() != n) && idx < pushed.size()) | |
s.push(pushed[idx++]); | |
if (s.top() != n) | |
return false; | |
s.pop(); | |
} | |
return s.empty(); | |
} | |
}; | |
// reference solution | |
class Solution { | |
public: | |
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { | |
stack<int> s; | |
int i = 0; | |
for(int x: pushed) | |
{ | |
s.push(x); | |
while(!s.empty() && s.top() == popped[i]) | |
{ | |
s.pop(); | |
i++; | |
} | |
} | |
return i == pushed.size(); | |
} | |
}; | |
/* | |
You are given an array of positive integers w where w[i] describes the weight of ith index (0-indexed). | |
We need to call the function pickIndex() which randomly returns an integer in the range [0, w.length - 1]. | |
pickIndex() should return the integer proportional to its weight in the w array. | |
For example, for w = [1, 3], the probability of picking the index 0 is 1 / (1 + 3) = 0.25 (i.e 25%) | |
while the probability of picking the index 1 is 3 / (1 + 3) = 0.75 (i.e 75%). | |
More formally, the probability of picking index i is w[i] / sum(w). | |
Example 1: | |
Input | |
["Solution","pickIndex"] | |
[[[1]],[]] | |
Output | |
[null,0] | |
Explanation | |
Solution solution = new Solution([1]); | |
solution.pickIndex(); // return 0. Since there is only one single element on the array the only option is to return the first element. | |
Example 2: | |
Input | |
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] | |
[[[1,3]],[],[],[],[],[]] | |
Output | |
[null,1,1,1,1,0] p(1) : p(0) = 3 : 1 | |
Explanation | |
Solution solution = new Solution([1, 3]); | |
solution.pickIndex(); // return 1. It's returning the second element (index = 1) that has probability of 3/4. | |
solution.pickIndex(); // return 1 | |
solution.pickIndex(); // return 1 | |
solution.pickIndex(); // return 1 | |
solution.pickIndex(); // return 0. It's returning the first element (index = 0) that has probability of 1/4. | |
Since this is a randomization problem, multiple answers are allowed so the following outputs can be considered correct : | |
[null,1,1,1,1,0] | |
[null,1,1,1,1,1] | |
[null,1,1,1,0,0] | |
[null,1,1,1,0,1] | |
[null,1,0,1,0,0] | |
...... | |
and so on. | |
1 <= w.length <= 10000 | |
double uniform_random() -> 0 <= n <= 1 with uniform probablity | |
*/ | |
0.7 | |
[0.11, 0.45, 0.6, 1] | |
left = 0, right = 3; | |
mid = 1; | |
left = 2, right = 3; | |
mid = 2; | |
left = 3, right = 3; | |
mid = 3; | |
[1, 3] | |
[0.25, 1] | |
r <= 0.25 -> 0 | |
// interview | |
class Solution { | |
public: | |
Solution(vector<int>& w) { | |
double val = 0; | |
double sum = 0; | |
for (int n : w) | |
sum += n; | |
for (int n : w) | |
{ | |
val += n / sum; | |
boundary.push_back(val); | |
} | |
} | |
int pickIndex() { | |
auto randVal = uniform_random(); | |
int left = 0; | |
int right = boundary.size() - 1; | |
int mid; | |
while (left < right) | |
{ | |
mid = (left + right) / 2; | |
if (boundary[mid] < randVal) | |
{ | |
left = mid + 1; | |
} | |
else if (boundary[mid] >= randVal) | |
{ | |
right = mid; | |
} | |
} | |
return left; | |
} | |
private: | |
vector<double> boundary; | |
}; | |
//reference solution | |
import random | |
class Solution: | |
def __init__(self, w: List[int]): | |
self.csum = [] | |
for i in range(len(w)): | |
if i == 0: | |
self.csum.append(w[i]) | |
else: | |
self.csum.append(self.csum[i-1] + w[i]) | |
self.total_sum = self.csum[-1] | |
def pickIndex(self) -> int: | |
pick = random.uniform(0, 1) * self.total_sum | |
# print(pick) | |
l = 0 | |
r = len(self.csum) - 1 | |
while l < r: | |
mid_point = (l + r) // 2 | |
# print(l, r, mid_point) | |
if self.csum[mid_point] < pick: | |
l = mid_point + 1 | |
else: | |
r = mid_point | |
# print(l) | |
return l | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment