mock_interview_2

mock_interview_2.txt

//
//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