Interview : a strategy to stop flipping the poker and win

Question:

You are playing a card game with me. Suppose I shuffle a deck of 52 cards, then I show you the card one by one to you from top to bottom. You can stop me during this whole process, based on your memory of the previous cards you have seen. If you stop me, and there are still cards left in the deck, if the next unshown card is red, you get one dollar from me, otherwise if the next unshown card is black, you give me one dollar; if no cards left in the deck, you get one dollar if the last card is red, and you give one dollar if the last card is black.

Is there a strategy for you to win with probability larger than 50%?


Sol:

There is not strategy for that. Think the game in a different way: when you stop me, suppose instead of deciding whether you win or lose based on the next unshown card, we decide whether you win or lose based on the last card in the deck: if the last card is red you get one dollar, otherwise if it is black I get one dollar. The two games are the same. But for the latter, whatever strategies you choose the probability for you to win is always 50%, and so does the former.

Interview : Expected time to see a bus

Suppose a bus is running on a loop route. It takes 10 mins for the bus to finish the route. If a guy arrives at a bus stop at uniformly random time. What is the expected bus waiting time?

Sol: image uniformly put a point at a line with length 10, so the expected waiting time is 5.



Now suppose there is a ice cream shop at the bus loop. Whenever the bus is close to the ice cream shop, the driver will flip a coin and decide whether to go eating an ice cream or not. It takes 10 mins for the driver to eat the ice cream. What is the expected bus waiting time if a guy arrives at a bus stop uniformly.

Sol: the key is to consider what uniform arriving time means. The bus is running either on a 10min-loop or a 20min-loop, each with probability 1/2. The bus keeps running, and the guy can arrive at any time between 0am - 24pm, uniformly. The time for the bus to be in a 20min-loop is two times larger than the time for a 10min-loop. So each day 2/3 of the time the bus is in a 20min-loop, and 1/3 of the time the bus is in a 10min-loop.

Thus, the probability for the guy to arrive when the bus is in a 20min-loop is 2/3. Expected waiting time is 10 for the 20min-loop and 5 for the 10min-loop. So the combined expected waiting time is

2/3 * 10 + 1/3 * 5

understand pure virtual function, abstract class, and virtual function.

See the following program:

#include <iostream>
using namespace std;


class MathSymbol {
public:
  virtual void doOperation() = 0; // pure virtual class, so MathSymbol is a abstract class
  virtual void print(){
    cout<<"print MathSymbol"<<endl;
  }
  void move(){
    cout<<"move MathSymbol"<<endl;
  }
};

class B : public MathSymbol {
public:
  void doOperation(){
    cout<<"Operation in B"<<endl;
  }
  void print(){
    cout<<"print B"<<endl;
  }
  void move(){
    cout<<"move B"<<endl;
  }
};


class C : public MathSymbol {
public:
  void doOperation(){
    cout<<"Operation in C"<<endl;
  }

  void print(){
    cout<<"print C"<<endl;
  }
  void move(){
    cout<<"move C"<<endl;
  }
};


int main(){
  // MathSymbol a; // this is error. because MathSymbol is abstract.
  MathSymbol *pa = NULL;

  B b, *pb = &b;
  C c, *pc = &c;

  MathSymbol* array[] = {pb,pc};
  int len = 2;

  for(int i = 0; i < len; i++){
    array[i] -> doOperation();
  }

  for(int i = 0; i < len; i++){
    array[i] -> print();
  }

  for(int i = 0; i < len; i++){
    array[i] -> move();
  }
  return 0;
}

Its running result is:

Operation in B
Operation in C
print B
print C
move MathSymbol
move MathSymbol

One example explaining the virtual function

 Virtual function will be realized after the it is called according to the object associated with it

Non virtual function will be realized by the compiler before the function is called.


See the program below:

#include <iostream>
using namespace std;


class A {
public:
  void move(){
    cout<<"move A"<<endl;
  }
  virtual void print(){
    cout<<"I am A"<<endl;
  };
};

class B : public A {
public:
  void move(){
    cout<< "move B"<< endl;
  }
  void print(){
    cout<<"I am B"<<endl;
  }
};

class C : public A {
public:
  void move(){
    cout<<"move C"<<endl;
  }
  void print(){
    cout<<"I am C"<<endl;
  }
};


int main(){
  A a, *pa = &a;;
  pa->print();

  B b, *pb = &b;
  C c, *pc = &c;
 
  cout<<endl;
  pb->move();
  ((A*)pb)->move();
 
  cout<<endl;
  pb->print();
  ((A*)pb)->print();
 
  cout<<endl;
  pc->print();
  ((A*)pc)->print();

  cout<<endl;

  A* array[] = {&a,&b,&c};
  int len = 3;
  for(int i = 0; i < len; i++){
    array[i]->print();
  }
  cout<<endl;
  for(int i = 0; i < len; i++){
    array[i]->move();
  }
  return 0;

}

 


The running result is listed as:

I am A

move B
move A

I am B
I am B

I am C
I am C

I am A
I am B
I am C

move A
move A
move A

Find the second largest element in an array with the minimum number of comparisons

I meet this question in an interview. It is actually a famous problem, whose solution is available here .

Here my thinking is provided.

1, The simplest case, suppose there are four elements, a,b,c,d, the minimum number of comparisons is 4:

a < b, c < d    ->   b < d  -> max(b,c) is the second largest element.

That is, we compare (a,b), (c,d) to get the largest values b,d, then find the largest value d, the second largest value is in the set of all elements that have been compared with d, that is, b or c.


2, Suppose we have 2n elements: (a,b), (c,d), (e,f), ....... We have n pairs, so select the larger element in each pair to form an n-array: b,d,f....In total n comparison is needed.

Suppose our algorithm can find the largest two values from b,d,f,...., which is (b,d) with b < d, for example.

The second largest element can either be b or c, compare b vs c we get the second largest element.

Thus, if x(2n) is the number of comparisons needed for an 2n-array, we have x(2n) = n + x(n) + 1

Solve this recursive function with x(4) = 4, we get x(n) = n + log2(n) - 2.