CareerCup

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
using namespace std;

// a b c d e
// f g h i j
// k l m n o 
// p q r s t
// u v w x y
// z

//helper function that takes a map of coordinates and print out the path of instructions
void print_instructions( vector< pair<int, int> >& );
//print out path
void printout(int, int ,int ,int );



int main(int argc, char* argv[])
{
  if(argc!=2) {
    cout<<"Please provide one input argument!"<<endl;
    return 1;
  }  

  string word = string(argv[1]);
  vector< pair<int, int> > map;
  

  for(string::const_iterator p = word.begin();p!=word.end();p++){
    // position from 1-26
    int position = int(*p)-int('a')+1;
    //convert position to X-Y coordiates
    int X_cor = ceil(double(position)/5.0);
    int Y_cor = position % 5;
    if(Y_cor==0) Y_cor=5;
    
    map.push_back( make_pair(X_cor,Y_cor) );    

  }
  


  print_instructions(map);
  


  return 0;
  
}


//helper function that takes a map of coordinates and print out the path of instructions
void print_instructions( vector< pair<int, int> >& map )
{

  //assume the current cursor is at [1,1] == 'a'
  printout(map[0].first,1,map[0].second,1);


  for(vector< pair<int, int> >::const_iterator p = map.begin();p!=map.end();p++){
    vector< pair<int, int> >::const_iterator next = p+1;
    if(next==map.end()) continue;
    int x_next = next->first;
    int x =p->first;
    int y_next = next->second;
    int y =p->second;

    printout(x_next,x,y_next,y);
    

  }// loop over all coordinate elements in map
  



}

//print out path
void printout(int x_next, int x,int y_next,int y)
{

 //X direction    
    if(x_next >= x){
      for(int i=0;i< (x_next-x);i++){
        cout<<"D";
      }
    }
    
    else{
      for(int i=0;i< (x-x_next);i++){
        cout<<"U";
      }
    }
    

    //Y direction
    if(y_next >= y){
      for(int i=0;i< (y_next-y);i++){
        cout<<"R";
      }
    }
    
    else{
      for(int i=0;i< (y-y_next);i++){
        cout<<"L";
      }
    }    

    cout<<"!";
    

}

A little more challenging questions would look like this:

You are given two sorted lists of size m and n. Give an O(log m + log n) time algorithm for computing the kth smallest element in the union of the two lists.

Algorithm GetMutualMedian(A[m], B[n])

Input: sorted array A[m] and B[n]
Output: return the median of the combined array C[m+n]

if m=1, n=1 return A[m] or B[n]

if A[m/2] < B[n/2]: upper half of B is larger than lower half of B and lower half of A, thus upper half of B
should be larger than (m+n)/2 elements, recursively call GetMutualMedian(A[m], B[1-n/2])


if A[m/2] > B[n/2]: upper half of A is larger than lower half of A and lower half of B, thus upper half of A
should be larger than (m+n)/2 elements, recursively call GetMutualMedian(A[1-m/2], B[n])

if A[m/2] == B[n/2]: return A[m/2] or B[n/2]


Time complexity = log(m)+log(n)

how about using a prefix tree (trie) data structure:
key #1 (1,2,3)
key #2 (4,5,6)
key #3 (7,8,9)
key #4 (0)
if dial 415-6789-5432 then dial 212-233... with automatic completion provided

This is a sub-sequence problem, instead of sub-string, I think the right algorithm to use should be "building a prefix table" using dynamic programming.

#include <iostream>
#include <vector>
using namespace std;


int main()
{
//sort 26 chats from A-Z using "counting sort"
//time complexity O(n)

string input("SHEEP");
string ruler("PSEH");
vector<int> C(256,0), C_prime(256,0);//use ASCII code as index for counting array
string result=input;

//create counting auxilliary array called "C", it counts frequencies for each char
for(string::const_iterator p=input.begin();p!=input.end();p++){
C[int(*p)]++;
}

//convert C to C_prime (Auxilliary array)
int count=0;
for(string::const_iterator p=ruler.begin();p!=ruler.end();p++ ){
count += C[int(*p)];
C_prime[int(*p)]=count;
}

// input --> C_prime --> result mapping
for(string::const_iterator p = input.end()-1;p>=input.begin();p--){
result[C_prime[int(*p)]-1] = *p;
C_prime[int(*p)]--;
}

// output the sorted array : "PSEEH"
cout<<result<<endl;

return 0;
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main(int argc, char* argv[]){

int N = atoi(argv[1]);


vector<bool> flags(N,true);


for(int i=2;i<=sqrt(N);i++){
if(flags[i-1]==true){
for(int j=i*i;j<=N;){
flags[j-1]=false;
j+=i;
}//inner for
}//if

}//outer for

int count=0;
for(int ii=1;ii<flags.size();ii++)
{
if(flags[ii]==true) count++;
}

cout<<count<<endl;

return 0;


}




0:56#hepc1 ./a.out 100
25
0:56#hepc1
0:56#hepc1 ./a.out 1000000
78498

#include <iostream>
using namespace std;
#include <stdio.h>
#include <stdlib.h>



/* A binary tree node has data, pointer to left child
and a pointer to right child */

class node
{
public:
node(int dat){ data = dat; left = NULL; right=NULL; }
int data;
node* left;
node* right;
};



/* returns max of two integers */
int max(int a, int b);

/* function to Compute height of a tree. */
int height(node* node);

/* Function to get diameter of a binary tree */
int diameter(node * tree)
{
/* base case where tree is empty */
if (tree == 0) return 0;

/* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);

/* get the diameter of left and right sub-trees */
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);

/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */

cout<< lheight + rheight + 1 <<" "<< ldiameter << " "<< rdiameter <<endl;



return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}

/* UTILITY FUNCTIONS TO TEST diameter() FUNCTION */

/* The function Compute the "height" of a tree. Height is the
number f nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(node* node)
{
/* base case tree is empty */
if(node == NULL) return 0;

/* If tree is not empty then height = 1 + max of left
height and right heights */

return 1 + max(height(node->left), height(node->right));
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */

/* returns maximum of two integers */
int max(int a, int b)
{
return (a >= b)? a: b;
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
/ \
6 7
*/
node *root = new node(1);
root->left = new node(2);
root->right = new node(3);
root->left->left = new node(4);
root->left->right = new node(5);
root->left->left->left = new node(6);
root->left->right->right = new node(7);


printf("Diameter of the given binary tree is %d\n", diameter(root));

cout<< "node 1 has height "<< height(root)<<endl;


return 0;
}

Suppose the 5 seats are numbered thus different than each other.

Total # of possible ways to sit = 5 !
# of possible ways to sit when two people are together = 10 (10 ways to arrange the two peopl) x 3!

Probability = (10 x 3 !)/5! = 1/2 = 50%

Based upon quick sort algorithm:

Randomized-Select(A[p..r],i) looking for ith o.s.
if p = rreturn A[p]
q <- Randomized-Partition(A,p,r)
k <- q-p+1 the size of the left partition
if i=k then the pivot value is the answer
return A[q]
else if i < k then the answer is in the front
return Randomized-Select(A,p,q-1,i)
else then the answer is in the back half
return Randomized-Select(A,q+1,r,i-k)


T[n] = O(n)

class C
{
1) A default constructor
C();

2) A default destructor
~C();

3) A copy constructor
C(const C & );

4) A copy assignment operator
C& operator = (const C &);

};



plus

C* operator &();
const C* operator &() const;

class A vtable points to base virtual function A::foo()
class B vtable points to most derived function which is B::foo() (if there is one), otherwise it points to base virtual function too

#include <iostream>
#include <deque>
using namespace std;


void main()
{

int d(0);
deque<char> binary;
cout<<"Please Enter Decimal Number:"<<endl;
cin >> d;



while(d > 0)
{
if(d%2==0)
{
binary.push_front('0');
}
else
{
binary.push_front('1');
}


d = d/2;
}

for (deque<char>::iterator it = binary.begin(); it!=binary.end(); ++it){
cout << *it;
}

cout<<endl;


}

int i, x;

i = 2;
x = ++i;
// now i = 3, x = 3

i = 2;
x = i++;
// now i = 3, x = 2

'Post' means after - that is, the increment is done after the variable is read. 'Pre' means before - so the variable value is incremented first, then used in the expression.

case( I )

#include <iostream>
using namespace std;

void main()
{
int count = 0;
for(int i=0; i < 10; ++i){
count = count++;
}

cout<<"Output of this code is: "<<endl;
std::cout << count <<endl;


}


root [0] .L main.C
root [1] main()
Output of this code is:
0

case ( II )

#include <iostream>
using namespace std;

void main()
{
int count = 0;
for(int i=0; i < 10; ++i){
count = ++count;
}

cout<<"Output of this code is: "<<endl;
std::cout << count <<endl;


}


root [0] .L main.C
root [1] main()
Output of this code is:
10

#include <iostream>
#include <string>
using namespace std;



int convert_string()
{

cout<<"Please input your string-number here: "<<endl;
string in;
cin >> in ;


double tens(1),sum(0);

for(int i= in.length()-1 ; i>=0 ; i--)
{
sum += (int(in[i])-int('0'))*tens;
tens *= 10;
}

cout<<sum<<endl;


return sum;


}





int convert_char()
{

cout<<"Please input your string-number here: "<<endl;
char in[100];
cin >> in ;


double tens(1),sum(0);

int j = 0;
int count = 0;
while(in[j]!='\0')
{
j++;
count++;
}



for(int i= count-1 ; i>=0 ; i--)
{
sum += (int(in[i])-int('0'))*tens;
tens *= 10;
}

cout<<sum<<endl;


return sum;


}

#include <iostream>
using namespace std;


class integer
{
public:
  int output(){return inte;  }
  

protected:
 void input()
  {
    cout<<"Enter Integer: ";
    cin>>inte;
       
  }  

private:
  int inte;
};


class character : public integer
{
public:
  void calc();
  void display();
  void useinput(){input();}
  
protected:

private:
  char ch;
  
};


void character::calc()
{
  cout<<"Enter Character: ";
  cin>>ch;
}

void character::display()
{  

  if( (int(ch)-48) % this->output() ==0 ){
    cout<< "Divides Completely"<<endl;
  }
  else{
    cout<< "Does not divide"<<endl;
  }
  
}


int main()
{
  character a;
  a.useinput();
  a.calc();
  a.display();
  
  
  return 0;
}

The level of the water should be lower compared to L1, the reasons are explained as following:

case (I), boat + rock are in an equlibrium state which means: floating force generated by water == gravitational force of the boat+rock, in physics language
rho * Volume_water * g = (m_rock + m_boat) *g

case (II), boat is still in an equilibrium state (floating force== gravitational force) however the rock must go to the bottom of the water as it has much larger density (floating force << gravitational force)
so rho * Volume_water * g << (m_rock+m_boat) *g

to conclude, Volume_water_1 > Volume_water_2
so, water_level_2 < water_level_1