18 months ago

rajat_singh0805 • 30

On Campus (IIT Goa)

CGPA cutoff: 8

Branches: CSE, MnC

Online Assessment

Duration: 2 hours

Pattern: MCQ

Topics: Aptitude, Programming, Computer Networks, Digital Design

Interview Round

Level: Easy-Medium

This was a technical interview.

After interviewer's and mine introduction, the interviewer asked me to rate myself out of 10 in CODING SKILLS.

Then he asked me that I need to solve the questions as fast as i could because there was only 30 mins and he said he'll ask 3 questions.

He allowed me to use any pre-installed compiler.

Ques-1: Given the pointer to head, reverse the linked list

ListNode* reverseList(ListNode* head) 
{
     ListNode* prev = nullptr;
     while(head!=NULL)
     {
         ListNode* next = head->next;
         head->next = prev;
         prev = head;
         head = next;
    }
    return prev;
}

Ques-2: Given an array, check if there exists three elements such that their sum equal to K

bool threeSum(vector<int> &nums, int K)
{
    int n = nums.size();
    if (n < 3)
        return false;

    sort(nums.begin(), nums.end());

    for (int i = 0; i < n - 2; i++)
    {
        int low = i + 1;
        int high = n - 1;
        int targ = K - nums[i];

        while (low < high)
        {
            if (nums[low] + nums[high] == targ)
                return true;
            else if (nums[low] + nums[high] < targ)
                low++;
            else
                high--;
        }
    }
    return false;
}

Ques-3: Given the pointer to root of binary tree, print the tree in spiral order

example:
                                1
                               / \
                              2   3
                             / \ / \
                            4  5 6  7
ans: {1, 3, 2, 4, 5, 6, 7}

vector<int> spiralOrder(TreeNode* root) 
{
    vector<int> ans;
    stack<TreeNode*> stk1, stk2;
    stk1.push(root);
    while(!stk1.empty() || !stk2.empty())
    {
        while(!stk1.empty())
        {
            TreeNode* curr = stk1.top();
            stk1.pop();
            if(curr==NULL)
                continue;
            ans.push_back(curr->val);
            stk2.push(curr->left);
            stk2.push(curr->right);
        }

        while(!stk2.empty())
        {
            TreeNode* curr = stk2.top();
            stk2.pop();
            if(curr==NULL)
                continue;
            ans.push_back(curr->val);
            stk1.push(curr->right);
            stk1.push(curr->left);
        }
    }
    return ans;
}

After this he told if I have any questions for him, I can ask. So I asked him

• What is the current project he and his team is currently doing
• What projects will I be given
• What is the biggest problem he faced as a Software Engineer
• I also asked him about a feedback of my performance.

Verdict: Selected

Tips:

• Think out loud while solving the question, keep interacting with the interviewer while solving.
• Leverage all the opportunities you get.

23 months ago

Harsh Priyadarshi 70

Question 2

Overview

• We are given an array of n integers and an integer k
• We have to tell whether there exist three integers at different indices in the array whose sum adds up to k

Approach

• We will use an approach very similar to the two-sum approach of using two pointers.
• We will sort the array, and start iterating the array from beginning.
• We will fix one integer, and make the new k as knew=k-nums[fixed]
• Then for the array on the left hand side of the fixed integer, we will apply the two sum approach.

PseudoCode

    for (int i = 0; i < n - 2; i++)
    {   if(flag==1) break;
        int low = i + 1;
        int high = n - 1;
        int targ = k - nums[i];

        while (low < high)
        {
            if (nums[low] + nums[high] == targ)
                {
                    flag=1;
                    break;
                }
            else if (nums[low] + nums[high] < targ)
                low++;
            else
                high--;
        }
    }

Complexity

• O(n^2)