Nvidia Software Engineering internship | 6 months

Round 1

Questions:

1. Multiple Choice Questions:

   • 15 questions covering:
     • Logical reasoning
     • Aptitude
     • Probability
     • Profit and loss
     • Combinations

2. Technical MCQs:

   • 12 questions covering:
     • Operating Systems (OS)
     • Database Management Systems (DBMS)
     • Guess the output (more focused on this)

3. Coding Questions:

   • 1st Question (to be done only in C language):

     • Given a binary string, find a regex that checks whether that binary number when converted to a decimal number is a power of two or not.
     • Complete the code in the editor below by replacing the blank (i.e.. " ") with a regular expression that matches something according to the criterion above. Locked code in the editor prints True for each correct match and False for each incorrect match.
     • Example:
       • S = 0101010
       • This is 42 in decimal which is not a power of 2. The regex should return a false value and the code stub will print 'False'.

   • 2nd Question (can use C or C++):

     • Given a binary string (composed of '1's and '0's) in such a way that it forms the largest lexicographical special string. A special string is defined as a string that satisfies two conditions:
       • It contains an equal number of '1's and '0's.
       • Any prefix of the string contains at least as many '1's as '0's.
     • Test case explanation:
       • For an input like "11011000":
         • The algorithm identifies the special substrings: "1100" and "10".
         • It would recursively build these substrings, sort them, and then combine them to form the largest special string possible.
     • Summary:
       • The problem essentially involves breaking down the binary string into valid special components, rearranging those components, and then combining them to form the largest possible special string.

Code:

class Solution {
public:
    string makeLargestSpecial(string s) {
        if (s == "") return s;
        vector<string> ans;
        int cnt = 0;
        for (int i = 0, j = 0; i < s.size(); ++i) {
            cnt += s[i] == '1' ? 1 : -1;
            if (cnt == 0) {
                ans.push_back("1" + makeLargestSpecial(s.substr(j + 1, i - j - 1)) + "0");
                j = i + 1;
            }
        }
        sort(ans.begin(), ans.end(), greater<string>{});
        return accumulate(ans.begin(), ans.end(), string{});
    }
};