Interview Questions - akshaydhule/Codes GitHub Wiki

This section contains Implementations to frequent Interview Questions in C++.

https://github.com/akshaydhule/Codes/tree/codes/Interview-Questions

• [1. LRU Cache] (https://github.com/akshaydhule/Codes/blob/codes/Interview-Questions/LRU_Cache.cpp)
  • Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
    • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
    • set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
• [2. Round-Robin] (https://github.com/akshaydhule/Codes/blob/codes/Interview-Questions/Round_robin.cpp)
  • Given a pipeline of process implement round robin algorithm to process all processes.
• [3. Valid Parantheses Combinations] (https://github.com/akshaydhule/Codes/blob/codes/Interview-Questions/Parantheses_Combination.cpp)
  • Given string of brackets and '', find the number of distinct balanced parentheses expressions you can make by replacing the ‘’ with either ‘(‘ or ‘)’ or removing the ‘’ Note : You have to replace each ‘’ with one of ‘(‘ or ‘)’ or remove it. If removed, assume the string has reduced by 1 character. Duplicate strings are not allowed. The final expressions to be counted have to be distinct As the answer may be large, please output it modulo 1000000007 (10^9+7) Output one integer per line corresponding to each testcase.
• [4. Array Range Addition] (https://github.com/akshaydhule/Codes/blob/codes/Interview-Questions/Array_Range_addition.cpp)

  • Assume you have an array of length n initialized with all 0's and are given k update operations.

    • Each operation is represented as a triplet: [startIndex, endIndex, inc]
    • which increments each element of subarray A[startIndex ... endIndex]
    • (startIndex and endIndex inclusive) with inc.

    Return the modified array after all k operations were executed.

• [5. Opinion Propagation Algorithm] (https://github.com/akshaydhule/Codes/blob/codes/Interview-Questions/Opinion_propagation_problem.cpp)

  • Given Persons list:

    1. if threshold is 0 then person is promoter.
    2. if threshold is 1 then person can not be promoter.
    3. if threshold is b/w 0 and 1 then the person can be promoter.

    if proportion of its promoter parents is atleast threshold. Return the list of promoters.

• [6. Sort Transformed Array] (https://github.com/akshaydhule/Codes/blob/codes/Interview-Questions/Array_Sort_TransformedArray.cpp)

  • Given a sorted array of integers nums and integer values a, b and c. Apply a function of the form f(x) = ax2 + bx + c to each element x in the array.

    The returned array must be in sorted order. Expected time complexity: O(n)

• [7. Valid Word Square] (https://github.com/akshaydhule/Codes/blob/codes/Interview-Questions/Valid_Word_Square.cpp)
  • Given a sequence of words, check whether it forms a valid word square. A sequence of words forms a valid word square if the kth row and column read the exact same string.
    • The number of words given is at least 1 and does not exceed 500.
    • Word length will be at least 1 and does not exceed 500.
    • Each word contains only lowercase English alphabets.