CareerCup

It should be log(N). My Previous answer is wrong.

y = (-1) + (-1) – (0) + (1) + (1) - (1);
y=-1;

N/2

I assume streaming related questions should be tackled using observer design pattern.

This question is not clear:
What is the input ?
Give an example and expected result

std::string findCommonSuffix(std::string s1, std::string s2)
{
    int i, j; 
    for(i = s1.size()-1, j = s2.size()-1 ; i >= 0 && j >= 0; --i, --j)
    {
        if(s1[i] != s2[j]) break;
        if(i == 0 || j == 0) break;
    }
    std::string result;
    if(i == 0)
         result = s1;
    else if(j == 0)
        result = s2;
    else
        result = s1.substr(i+1, s1.size() - i);
    return result;
}

There are following independent services:
Authentication and authorization service- which will manage the session by using AccessToken
GameInitialization service- This service will identify the competitors and initialize the game instance
GameExecutionService - Which will manage the turn in between players

There should be an API gateway to control request pipeline to the system.

System should have following classes:
1. Grid
---------------------
cells[][]

2. Game
---------------------
Grid* grid
players[2]
status
AccessToken

3. Player
---------------------
Id
placedPieces
balancePieces
Game id
CompetetorId
AccessToken
RefreshToken
----------------------
move()

4.piece
--------------------
id
type
int: x
int: y
player id
Game id

5. cell
---------------------
bool occupied
int x
int y
playerId
typeOfPiece

I assume it can be achieved in O(n) complexity. We don't need to buffer the data and search for the key string again within buffer. Instead keep only k number of lines in memory and if new line is equals to key string, print the buffer along with key.

I assume, k number of lines are read already before reading the key value.

package careercup;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class LimitedLengthQueue {

    private List<String> innerStore;
    private int size;
    private static final String FILENAME="C:/filepath.txt.txt";
    public LimitedLengthQueue(int size) {
        this.innerStore = new ArrayList<>();
        this.size = size;
    }

    boolean add(String s){
        if(innerStore.size() == size){
            innerStore.remove(0);
            innerStore.add(s);
            return true;
        }
        innerStore.add(s);
        return true;
    }


    public static void main(String[] args)
                     throws FileNotFoundException, IOException  {
        LimitedLengthQueue inputQueue =
                   new LimitedLengthQueue(Integer.parseInt(args[0]));
        String key = args[1];

        try( FileReader fr = new FileReader(FILENAME);
             BufferedReader br = new BufferedReader(fr)){

            String input = null;

            while( (input = br.readLine()) != null){

                if(key.equals(input.trim())){
                    inputQueue.innerStore.forEach(System.out::println);
                    System.out.println(input);
                    break;
                }
                inputQueue.add(input);
             }
        }
    }
}

#include <string>
#include <algorithm>

void sortSegments(std::string& input)
{
    bool toggle1 = isalpha(input[0])? true:false;
    size_t k = 0;
    for(size_t i = 1; i < input.size(); ++i)
    {
        bool toggle2 = isalpha(input[i])? true:false;
        if(toggle1 != toggle2)
        {
            std::sort(input.begin()+k, input.begin()+i);
            toggle1= toggle2;
            k=i;           
        }       
    }  
}

This is nothing but LRU cache.

In a minimal version of payment gateway system, we need to collect account details from the client and pass the information to banking service and communicate back the status of the transaction.

So we need a secure channel to pass the data in between multiple modules. We have to maintain the reliability as well as system should handle concurrent transactions.

Presentation layer collects the data and pass details as a message to an asynchronous message queuing system, so we can maintain a reliability and concurrency. Controller layer can asynchronously process and communicate back to the presentation layer the status as response message. It may be an error message or a successful status message. Controller layer can invoke reprocessing a limited time if it is error out during the transaction.

In controller layer we can develop a adapter design pattern and depends on the target system we can reprocess the input message and pass the message depends on each target system's API.

x=x++ + ++y; 
y=y++ + ++x;

Both these statements shows undefined behavior. Study about sequence points in C or C++. Between the previous and next sequence point, a scalar object shall have its stored value modified at most once by the evaluation of an expression.

double maxProfit(std::vector<double> & prices)
{
    double minSoFar = std::numeric_limits<double>::max();
    double maxProfit = 0;
    for( auto const& price: prices)
    {
        double CurrentMaxProfit = price - minSoFar;
        maxProfit = std::max(CurrentMaxProfit, maxProfit);
        minSoFar= std::min(price, minSoFar);        
    }    
    return maxProfit;
}

std::vector<std::vector<int> > kmeans(std::vector<int> & vec, int k)
{
    std::vector<std::vector<int> > result (k, std::vector<int> () );
if(k == 1)
    {
       result.push_back(vec);
       return result;
    }
    int target = std::ceil(std::accumulate(vec.begin(), vec.end(), 0.0) / k ); 
    std::vector<bool> taken(vec.size(), false);
    
    for(int i = 0; i < k ; ++i)
    {
        for( size_t j = 0; j < vec.size() ; ++j)
        {
             if( !taken[j] )
             {
                 result[i].push_back(vec[j]);
                 
                 if(std::accumulate(result[i].begin(), result[i].end(), 0)  > target)
                 {
                     result[i].pop_back();                     
                     break;
                 }
                 taken[j] = true;
             }
        }
    }
    
    for(auto& x: result)
    {
        for(auto& y : x)
        {
            std::cout << y;
        }
        std::cout << "\n";
    }
    return result;
}

int main()
{ 
    std::vector<int> vec = {1,3,6,9,10};
    kmeans(vec, 3);
    vec = {-1,1,1,1,8,10};
    kmeans(vec, 2);
}

Result :

136
9
10
-11118
10

unsigned fact(unsigned result, int x)
{
    if(x > 1)
       return fact(result*x, x-1);
    else
        return result;
}
unsigned factorial(int x)
{
    return fact(1,x);
}

int main()
{    
  printf("Fact: %u",factorial(5));
}

class Point{
    private:
        int x, y;   
    public:
        Point(int xval, int yval):x(xval),y(yval){}
        Point operator+(const Point& other)
        {
            this->x += other.x;
            this->y += other.y;
            return *this;
        }
        void print()
        {
            std::cout << "x: " << x << "\n";
            std::cout << "y: " << y << "\n";
        }
        
};

int main()
{
    Point p1(1,2);
    Point p2(3,4);
    Point p4(4,5);
    Point p3 = p1+p2+p4;
    p3.print();
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>

int main ()
{
 
   std::vector< std::vector<int> > lists = { {1,2,3,4,5}, {4,5,6,2,3}, {11,10,9,3,5,6,2}, {4,6,7,9}, {2,3,4,5} };
   
   for( auto& list: lists )
   {
       std::sort( std::begin(list),std::end(list) );
   }
   std::vector<int> difference;
   
   std::vector< std::pair<int,int> > result;
   for( size_t i = 0; i < lists.size()-1 ; ++i )
   {
       for( size_t j = i+1; j < lists.size(); ++j )
       {
          std::set_intersection( std::begin(lists[i]), std::end(lists[i]),  std::begin(lists[j]), std::end(lists[j]), std::back_inserter(difference) );         
         
          if(difference.size() > 3)
          {
              result.push_back(std::pair<int,int>(i,j));
          }
          difference.clear();
       }
   }
  
  for (auto& ele: result)
  {
      std::cout << ele.first+1 << " " << ele.second+1 <<"\n";
  }
}

Here you go for O(n) solution in C++11:

#include<iostream>
int main ()
{ 
   int arr1[]= {1,2,3,4,5};
   int arr2[5];
   
   arr2[0] = 1;
   
   for( auto& val : arr1)
   {
       arr2[0] *= val;
   }    
   
   for( int i = 1; i < 5; ++i)
   {
       arr2[i] = arr2[0] / (i+1);
   }
   
    for( auto& val : arr2)
   {
      std::cout << val << "\n";   
   }  
}

What is the question?

@rangacoder you are wrong, run and check it. I got answer 'b'.

#include<string>
#include<set>
#include<iostream>

int main()
{
    std::string input="Salesforce is the best company to work for";
    std::set<char> counter;
    char output;
    for (auto it = std::rbegin(input); it != std::rend(input); ++it)
    {
        char value =  std::tolower(*it);
        if( counter.find(value) == std::end(counter))
        {
            output=value;
            counter.insert(value);
        }
    }
    std::cout << output << "\n";    
}

int findMissingAP(const std::vector<int>& series)
{
    //Assuming there is only one missing from AP
    //Assuming there are at least 4 elements in series
    //Assuming missing element is not zero
    int size = series.size();
    if( size < 4)
    {
        std::cout<<" There are not enough elements in series"<<"\n";
    }
    
    int diff1 = 0;
    int diff2 = 0;
    int diff3 = 0;
    
    if( size >= 4)
    {
       int first  = series.at(0);
       int second = series.at(1);
       int third  = series.at(2);
       int fourth = series.at(3);
    
       diff1 = second - first;
       diff2 = third - second;
       diff3 = fourth - third;
    }
    
    int diff=0;
    if( diff1 == diff2 )
    {
        diff = diff1;
    }
    else if( diff1 == diff3)
    {
        diff= diff1;
    }
    else if(diff2 == diff3)
    {
        diff = diff2;
    }
    
    auto end = series.end();
    int result=0;
    for( auto it = series.begin(); it != end; )
    {
        int x = *it;      
        int y = *(++it);
        if( y - x == diff)
           continue;
        result = x + diff ;
         break;       
    }
    return result;
 }

#include<vector>
#include<iostream>

struct Triplet 
{
    const int first;
    const int second;
    const int third;
};

std::vector<Triplet> findTriangleTriplets( const std::vector<int>& vec_input ) 
{
    std::vector<Triplet> triplets;
    const unsigned int size = vec_input.size();

    for( unsigned int i=0; i < size; ++i ) 
    {
        for( unsigned int j = i; j < size; ++j ) 
        {
            for( unsigned int k = j; k < size; ++k)
            {
                const int first  ( vec_input.at( i ) );
                const int second ( vec_input.at( j ) );
                const int third  ( vec_input.at( k ) );
                                
                if( [ &first, &second, &third ] {                    
                       return ( ( second + third  ) > first   )&&
                              ( ( first + third   ) > second  )&&
                              ( ( first + second  ) > third  );                                 
                    }())                 
                {
                    triplets.emplace_back( Triplet{ first, second, third } );
                }
            }
        }
    }
    return triplets;
}

int main()
{
    const std::vector<int> vec_input {  2, 4,  5, };

    std::vector<Triplet> triplets = findTriangleTriplets( vec_input );
    for ( auto &x : triplets )
    {
        std::cout<<x.first<<" "<<x.second<<" "<<x.third<<"\n";
    }
    return 0;

}

So it is not listing exclusively all possible triangles triplets from a given list of segments. For example, if you get 3,4,5 as a list of segments, it will not list 3,3,4 as a triangle triplet. If it is allowed duplicate triangle triplets O(N^2) is available otherwise it will end up in O(N^3) since it is a 3 dimensional problem!!!

Can you please post a code snippet for this, I am iffy on this argument.

As per my understanding here we go for O(n logn) solution in C++

#include<iostream>
#include<string>
#include<vector>
#include<regex>

void  tokenize(std::string & text, std::vector<std::string>& text_prefix_tokens, std::vector<std::string>& text_suffix_tokens )
{
     std::string text_copy(text);
     int length =  text_copy.length();
     
     int i = 1;
     while( i <= length ) 
     {
          text_prefix_tokens.push_back(text_copy.substr(0, i));
          ++i;
     }   
    
     while( length-- ) 
     {
          text_suffix_tokens.push_back(text_copy.substr(length));        
     }        
}

     
    
std::string findHighestPattern(std::string & pre_text, std::string & post_text, std::string & text)
{
     std::vector<std::string> text_prefix_tokens;
     std::vector<std::string> text_suffix_tokens;
     tokenize(text, text_prefix_tokens, text_suffix_tokens);
  
     std::smatch matches;
     int post_text_score = 0;
    
     std::string post_result;
     for( auto &x : text_suffix_tokens)
     {
        std::regex pattern (x+"(.*)");      
        std::regex_match(post_text,matches,pattern);
          
        if(matches.size() > 0)
        {                                 
            int post_length = x.length();
            if(post_length > post_text_score)
            {
                post_text_score = post_length;
                post_result = x;
            }
        }
    }    
    int pre_text_score = 0;
    
    std::string pre_result;
    for( auto &x : text_prefix_tokens)
    {
        std::regex pattern ("(.*)"+x);
        std::regex_match(pre_text, matches, pattern);
          
        if(matches.size() > 0)
        {
            int pre_length = x.length();
            if(pre_length > pre_text_score)
            {
                pre_text_score = x.length();
                pre_result = x;
            }
        }
    }
    std::string result = pre_result + post_result;
    if(result.length() == 0)
    {          
        text_suffix_tokens.insert(std::end(text_suffix_tokens), std::begin(text_prefix_tokens), std::end(text_prefix_tokens));
        std::sort(std::begin(text_suffix_tokens),std::end(text_suffix_tokens));
       
        result = text_suffix_tokens.at(0);
    }     
    return result;
}


int main()
{ 
     std::string pre_text ("bruno");
     std::string text("nothing");
     std::string post_text("ingenious");
  
     //std::string pre_text ("b");
     //std::string text("ab");
     //std::string post_text("a");
     
     std::cout<< findHighestPattern(pre_text,post_text,text) <<"\n";

}

There are few contradictions in your examples and your problem description:
For first example answer should be "noing" not "nothing" as per my understanding. Please correct me if I am wrong.

Second example, there is no match for pre_score and post score, so it is a tie. And multiple substrings of text holding the same score zero. So it should go for first string come lexicographically, so answer should be "a"

#include<iostream>
#include<string>
#include<algorithm>
  
std::string   find_intersection(std::string & first, std::string & second)
{
   std::sort(std::begin(first),std::end(first));
   std::sort(std::begin(second), std::end(second));
   int length = std::min(first.length(), second.length());
   std::string result(length,' ');
   std::set_intersection(std::begin(first),std::end(first),std::begin(second),std::end(second),std::begin(result));
   
   result.shrink_to_fit();
   return result; 
}

int main()
{
   std::string first="GermanTown";
   std::string second="Georgia";
    std::cout<<find_intersection(first,second)<<"\n";
   return 0;

}