Interview Resources

1. https://www.interviewcake.com/coding-interview-meditation
2. https://leetcode.com/discuss/interview-question/910825/google-bloomberg-others-interview-questions-this-year

Google

1. LC | Google-or-L4-or-Zurich-or-Sept-Nov-2020-Reject

Amazon

1. shopping-patterns
2. five-star-sellers

1. String Stream

Header file : sstream

stringstream is a stream class to operate on strings. It implements input/output operations on memory (string) based streams. stringstream can be helpful in different type of parsing. The following operators/functions are commonly used here

Operator >> Extracts formatted data. Operator << Inserts formatted data. Method str() : returns a string object with a copy of the current contents of the stream. Method str(string) : sets s as the contents of the stream, discarding any previous contents.

 std::stringstream ss;
  ss.str ("Example string");
  std::string s = ss.str();
  std::cout << s << '\n';

Common use : One common use of this class is to parse comma-separated integers from a string (e.g., "23,4,56").

stringstream ss("23,4,56");
char ch;
int a, b, c;
ss >> a >> ch >> b >> ch >> c;  // a = 23, b = 4, c = 56

If the >> operator returns a value, that is a true value for a conditional. Failure to return a value is false.

2. String

Size:
    int len = a.size();
    int len1 = a.length();

Accessing  element:

   string s = "abc";
   char   c0 = s[0];   // c0 = 'a'
   char   c1 = s[1];   // c1 = 'b'

How to Concatenate Strings with integers?

Link Reference :https://www.techiedelight.com/concatenate-integer-string-object-cpp/

std::to_string() -

        int i = 17;
	std::string s = "C++" + std::to_string(i);

std::stringstream

        int a = 17;
        stringstream ss;
        ss<<a<<" "<<"hello"<<" "<<a;

        /*
        Output:
        17hello 17
        */ 

3. Structs

It ends with ;

struct Student {
    int age;
    string first_name;
    string last_name;
    int standard;
};

Student a; //initialized

4. Class

The data members of a class are private by default and the members of a structure are public by default.

class SampleClass {
    private:
        int val;
    public:
        void set(int a) {
            val = a;
        }
        int get() {
            return val;
        }
};

5. Class And Object

How to initalize vector in class?

You cannot do this:

vector<int> scores(5); //error in these 2 lines
vector<int> val(5,0);

//Error : 
//error: expected identifier before numeric constant vector<int> scores(5);

in a class outside of a method.

This is because, we can initialize in class only inside constructor.

So following are correct : - Stackoverflow Ans : https://stackoverflow.com/a/11491003/14138269

• Before C++11, you need to declare them first, then initialize them e.g in a constructor

class Foo {
    vector<string> name;
    vector<int> val;
 public:
  Foo() : name(5), val(5,0) {}   //constructor initializer lists
};

• You can initialize the data members at the point of declaration, but not with () brackets:

class Foo {
    vector<string> name = vector<string>(5);
    vector<int> val{vector<int>(5,0)};
};

Class Foo{
   vector<int> scores;
    
   Foo(){
    scores = vector<int>(5);
    }
}

6. Vector

cplusplus.com > erase()

iterator erase (iterator position) : Removes a single element (position) eg : myvector.erase (myvector.begin()+5);

iterator erase (iterator first, iterator last) : Removes a range of elements ([first,last)). (inclusive of first and exclusive of last iterator) eg : myvector.erase (myvector.begin(),myvector.begin()+3);

Because vectors use an array as their underlying storage, erasing elements in positions other than the vector end causes the container to relocate all the elements after the segment erased to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list).

7. STL

i) lower_bound (vector.begin(), vector.end(), val):

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.** (not less than val)**

template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val);

template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val, Compare comp);

The elements are compared using operator< for the first version, and comp for the second.

eg :

     vector<int> arr;
     vector<int>::iterator it = **lower_bound(arr.begin(), arr.end(), 10)**;

ii) set st

cplusplus => set

Sets are containers that store unique elements following a specific order.

• size : int length=st.size();
• insert : st.insert(x);
• erase : st.erase(val);
• find : set::iterator itr=s.find(val); //Gives the iterator to the element val if it is found otherwise returns s.end() .

Ex: set::iterator itr=s.find(100);

iii) map<string,int> m

cplusplus => map

Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order.

• declare : map<string,int>m;
• size : int length=m.size();
• insert : m.insert(make_pair("hello",9));
• erase : m.erase(val); //Erases the pair from the map where the key_type is val.
• find : map<string,int>::iterator itr=m.find(val); //Gives the iterator to the element val if it is found otherwise returns m.end() .

Ex: map<string,int>::iterator itr=m.find("Maps");

• access : int val = m["name"]
• set : m["name"] = val;

Q. Whats difference between insert and [] in map?

Ans : ??

Q. Cannot use operator + on iterator, gives compilation error?

Ans: error: invalid operands to binary expression

stackoverflow ref std::set iterators are bidirectional iterators. These do not support increment via the addition operator. You need to increment then step by step, or use std::next or std::advance, both of which which do the same behind the scenes. This operation will be O(N) regardless.

Q. unordered_map: which one is faster find() or count()?

Ans:

find() and count() are applicable to many containers in C++.

For maps, sets etc. find will always have constant execution time, since it just calculate the hash, and returns an iterator to the first element found (end() if not found).

count() on the other hand, has a constant execution time O(e), where e is the number of times the provided key is found. The worst case is a collection where all members are the same, so count could have a complexity O(n)

map or unordered_map do not allow for duplicates, therefore their asymptotic run time would be the same.

The choice depends on the semantics in your code. If you want just to check if a key exist, you could just use count. If you would like to check if a key exists, and use its value, then go for find since you will already have an iterator pointing to that element.

Manipulator

cplusplus => manipulator

Manipulators are functions specifically designed to be used in conjunction with the insertion (<<) and extraction (>>) operators on stream objects, for example:

cout << boolalpha;

They are still regular functions and can also be called as any other function using a stream object as argument, for example:

boolalpha (cout);

For some , you may need header file :

Example:

double A,B,C
        cout<<hex<<showbase <<left<<nouppercase<<(long long)A<<"\n";
        cout<<showpos<<right<<setw(15)<<setfill('_')<<setprecision(2)<<fixed<<B<<endl;
        cout<<noshowpos<<scientific<<setprecision(9) << uppercase<<C<<"\n";

From Problem : PrettyPrint

We have a two strings: A and B. We need to find miniumum number of times that we could concatenate B to get A. Also we can omit any number of letters from B in any of the concatenations if we want. Example:

A = "ZAZA"
B = "BAZ"

A is obtained from 3 copies of B A= (--Z)(-AZ)(-A-)

Can you suggest any algorithmic approach which is better than O(nm) where n is length of A and m is length of B.