Google SWE Internship

One can apply for Google's SWE Internship either through LinkedIn or through their own site. After shortlisting you will be invited for the Google’s Online Challenge Round. Here you need to solve 2 questions. Time Limit is - 1 hr

Coding Question 1

Array queries: You are given an array of integers whose length is N, you must perform the following five types of query on the given array :

1. Left: Perform one cyclic left rotation.
2. Right: Perform one cyclic right rotation.
3. Update Pos Value: Update the value at index Pos of the array by Val.
4. Increment Pos: Increment value at index Pos of the array by 1.
5. Pos: Print the current value at index Pos.

• One cyclic left rotation changes (arr1, arr2, arr3, . . . , arrN-1, arrN) to (arr2, arr3, . . .arrN-1, arrN, arr1).
• One cyclic right rotation changes (arr1, arr2, arr3, . . . , arrN-1, arrN) to (arrN, arr1, arr2, arr3, . . .arrN-1).

• The first line contains an integer N denoting the length of the array.
• The second line contains N space-separated integers denoting the elements of the array.
• The third line contains an integer Q denoting the number of queries.
• Next, Q lines contain the described type of query.

    
        #include<bits/stdc++.h>
        using namespace std;
        
        //maintaing counter rather than shifting which takes O(n)
        int diff=0; 
        
        //get updated position
        int position(int p,int n){
            p = (p-1+diff)%n;
            if(p<0)
              p = p+n;
            return p;  
        }
        
        int main(){
            
            int n;
            cin>>n;
            int arr[n];
            for(int i=0;i<n;i++)
             cin>>arr[i];
            int q;
            cin>>q;
            cin.ignore();
            while(q--){
                string str;
                getline(cin,str);
                if(str[0]=='L'){ //Left
                   diff++;
                }else if(str[0]=='R'){ //Right
                   diff--;
                }else if(str[0]=='U'){ //Update Pos Value
                    string pos = "",val = "";
                    int i=7;
                    while(str[i]!=' ')
                      pos+=str[i++];
                    i++;
                    while(i<str.size())
                      val+=str[i++];
                   int p = position(stoi(pos),n);
                   int v = stoi(val);
                   arr[p]=v;
        
                      
                }else if(str[0]=='I'){ //Increment pos
                  int i=10;
                  string pos="";
                  while(i<str.size())
                    pos+=str[i++];
                  int p = position(stoi(pos),n);
                  arr[p]++;  
        
                }else if(str[0]=='?'){ //? pos
                  int i=2;
                  string pos="";
                  while(i<str.length())
                    pos+=str[i++];
                  int p = position(stoi(pos),n);
                  cout<<arr[p]<<endl;   
                }
            } 
        
            return 0;
        }
    

Coding Question 2

There are N-words in a dictionary such that each word is of fixed length M and consists of only lowercase English letters that are (‘a’, ‘b’, ……. ‘z’).
A query word denoted by Q. The length of query word in M. These words contain lowercase English letters but at some places instead of a letter between ‘a’, ‘b’, ……. ‘z’ there is ‘?’ .Refer to the Sample input section to understand this case.
A match count of Q, denoted by match_count(Q), is the count of words that are is the dictionary and contain the same English letters (excluding a letter that can be in the position of ?) in the same position as the letters are there are in the query word Q.
In other words, a word in the dictionary can contain any letters at the position ‘?’ but the remaining alphabets must match with the query word.
You are given a query word Q and you are required to compute match_count(Q).
Input format

• First-line contains two space-separated integers M and N denoting the number of words in the dictionary and length of each word respectively.
• The next N lines contain one word each from the dictionary.
• The next line contains an integer Q denoting the number of query words for which u have to compute match_count()
• The next Q lines contain one query word each.

    
        import sys


# Time Complexity = max( O(M*N) , O(Q*N) ) = O(M*N), Space Complexity = O(M*N)
def match_count(words,queries):
    
    res = []
    
    lookup = [{} for i in range(len(words[0]))]
    
    # Time complexity for this loop is O(M*N)
    
    for i in range(len(words[0])): #O(N)
        for x in words:			   #O(M)
            if lookup[i].get(x[i]):#O(1)
                lookup[i][x[i]] += 1 
            else:
                lookup[i][x[i]] = 1 
    
    # Time complexity for this loop is O(Q*N)
    for q in queries:				#O(Q)
        count = sys.maxsize
        for j in range(len(q)):		#O(N)
            if lookup[j].get(q[j]): #O(1)
                count = min(count,lookup[j][q[j]])
            else:
                pass
        res.append(count)
        
    return res

if __name__=="__main__":
    MN = list(map(int,input().split()))
    M = MN[0]
    N = MN[1]
    words = []
    for i in range(M):
        words.append(input())
    Q = int(input())
    queries = []
    for i in range(Q):
        queries.append(input())
    res = match_count(words,queries)
    
    for x in res:
        print(x)