Question: Qualcomm, Interview Experience for Associate Software Engineer Position, 2022
1
Entering edit mode

Qualcomm Interview Experience for Associate Software Engineer Position

Basic discussion on resume and current company's tech stack and project was common in all rounds.

Round1

  • Discussion on time and space complexity.

Q1. Find missing smallest positive number in unsorted integer array.

{1,5,6,-2,4,2}, smallest positive number : 3

Click here to Practice
  • Was asked definition of complete binary tree.

Q2. Convert linked list to complete binary tree.

Input

1->2->3->4->5->6

Output

      1
     / \
    2   3
   /\   /\
  4  5 6
  • Was also asked what is MVC architecture.

Round2

  • Discussion on OOPS Concepts.
  • Interviewer also asked about design patterns in Java.

Q1. Check for balanced parenthesis in a string.

Click here to Practice

Q2. Attaching Screenshot for it.

Round3

  • Discussed about singleton class in Java.
  • Interviewer asked about dependency injection.
  • Unit Testing.

Q1. Print nth fibonacci number- both recursive and iterative.

Click here to Practice

Q2. Second most repeated char in a string

Click here to Practice

Input

nkslanfaaboutcec

Output

After the 3rd round there was a basic feedback sort of a round with a different interviewer.

Interviewer also asked why you want to switch and some other basic questions.

Also asked where do you want to see yourself in 3-4 years.

Then the interviewer said that Qualcomm Hyderabad works in sync with Qualcomm Seattle (or San Diego he said I guess), so there will be another interview round of 1 hour max with the Seattle team as well either on Friday or Monday.


Qualcomm Seattle Round

Interviewer asked few basic question related to resume and career like-

  • What was the most challenging task done till now in the current company?
  • How any of the unknown requirements were handled in any of the projects mentioned in the resume?
  • Are you aware about agile practices?

Next moved on to coding questions-

Q1.

Click here to Practice

Find the uncommon elements in two unsorted arrays.

Input1:

[3 4 2 3 4] 

Input2:

[3 6 3 2 1 1] 

Output:

[4 6 1]

I told him the brute force approach for this and moved on to the hashing based approach and coded it.

Q2.

Click here to Practice

Given a maze represented by a two dimensional arrays with R rows and C columns. Find a path from start position to exit.

You cannot move diagonally between cells.

Passable cells are marked with a period .

Impassable cells are marked with a hash #

The start position is at cell S

The exit is at cell E

For example:

###...##..
....#....#
#..###.#.#
S#.#.#.#..
...#...E#.

I applied DFS over here similar to what was used in the athletic arena problem and he was satisfied by this approach.

2
Entering edit mode

Question1 (Round 3)

Overview

  • To print the Nth fibonacci number from the fibonacci sequence.

Approach

  • We have a simple recurrence relation, F(n)=F(n-1)+F(n-2)
  • This will take exponential time to calculate.
  • We can speed up the process using Dynamic Programming.

PseudoCode

vector <int> dp(n+1);
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        dp[i]=(dp[i-1]%mod+dp[i-2]%mod)%mod;
    }

Complexity

  • O(n)

Note

  • Take care of overflows
ADD COMMENTlink 18 months ago Harsh Priyadarshi 70
1
Entering edit mode

Question 1: Missing Smallest Positive Number


Overview

  • Find the missing smallest positive number in an unsorted integer array.

Approach

  • The idea is to mark the elements in the array which are greater than N and less than 1 with 1.

  • The smallest positive integer is 1. First, we will check whether 1 is present in the array. If it is not present, then 1 is the answer.

  • If present, then, again, traverse the array. The largest possible answer is N+1, where N is the size of the array.

  • When traversing the array, if we find any number less than 1 or greater than N, change it to 1. This will not change anything, as the answer will always be between 1 to N+1.

  • Now, our array has elements from 1 to N. Now, for every ith number, increase arr[(arr[i]-1)] by N. But this will increase the value more than N. So, we will access the array by arr[(arr[i]-1)%N].

  • We will now find which index has a value less than N+1. Then i+1 will be our answer.

Complexity

Time Complexity: O(N), N is the size of the array.

ADD COMMENTlink 18 months ago Akash 230
1
Entering edit mode

Round 2 Question 1: Valid Parentheses


Overview

  • Check if the parentheses sequence is balanced or not.

Approach

  • An input string is valid if: Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

// Initialize a stack and a index idx = 0... 
stack<char> stack;
int idx = 0; 
// If the string is empty, return true... 
if(s.size() == 0){ 
   return true; 
} 
// Create a loop to check parentheses... 
while(idx < s.size()){ 
// If it contains the below parentheses, push the char to stack... 
     if( s[idx] == '(' || s[idx] == '[' || s[idx] == '{' ){ stack.push(s[idx]); } 
     // If the current char is a closing brace provided, pop the top element... 
     // Stack is not empty... 
     else if ( (s[idx] == ')' && !stack.empty() && stack.top() == '(') || (s[idx] == '}' && !stack.empty() && stack.top() == '{') || (s[idx] == ']' && !stack.empty() && stack.top() == '[') ){ 
        stack.pop(); 
     } 
     else { 
        return false;       // If The string is not a valid parenthesis... 
     } 
     idx++;      // Increase the index... 
 } // If stack.empty(), return true... 
if(stack.empty()) { 
    return true; 
} 
return false;

Complexity

Time Complexity: O(|S|)

ADD COMMENTlink 18 months ago Akash 230
0
Entering edit mode

Solution : Round 3 - Question 2

Overview

  • We are given a string containing ASCII characters.
  • We need to find the second most occurring character in the given string.
  • If there are multiple such characters, we need to prefer the character with lower ASCII value.

Approach

  • We need to first find the number of occurrences of each character. We will use a hashmap to maintain the same.
  • Lets define a hashmap F1 (char->int) to maintain the frequency of each character while you traverse the string.
  • Use this hashmap F1 (char->int) to create a new hashmap F2(int->char) of frequencies mapped to smallest ASCII character having that particular frequency.
  • Find the second highest key in F2 and print the character mapped associated to that frequency.
  • If size of F2 < 2 , this means that there isn't a second-highest frequency ( we print -1)

Example

  • string = "aaabbccfed"
  • F1 = {a:3 , b:2 , c:2 , d:1 , e:1 , f:1}
  • F2 = {1:d , 2:b , 3:a}
  • Second largest key in F2 = 2
  • Print(F2[2]) == 'b'

Complexity

  • O(N) time complexity to traverse the array
  • O(1) space , since the number of ASCII characters in a string is constant.

Code

ADD COMMENTlink 18 months ago Gigaliths 540
0
Entering edit mode

Qualcomm Seattle round Q2

Approach

  • We can just do BFS (breadth first search) from 'S'.
  • If we can reach 'E', output is "YES", else "NO".
  • For outputting the path, we can store parent in each iteration of bfs, and backtrack from 'E'.

C++ Code

vector&lt;int&gt; dx={1,-1,0,0};
vector&lt;int&gt; dy={0,0,1,-1};

int solve(vector&lt;string&gt; v)
{
    int n=v.size(),m=v[0].size();
    int sx=-1,sy=-1,ex=-1,ey=-1;
    for(int i = 0;i &lt; n;i++)
    {
        for(int j = 0;j &lt; m;j++)
        {
            if(v[i][j]=='S')
            {
                sx=i,sy=j;
            }
            if(v[i][j]=='E')
            {
                ex=i,ey=j;
            }
        }
    }
    queue&lt;pair&lt;int,int&gt;&gt; q;
    q.push({sx,sy});
    vector&lt;vector&lt;int&gt;&gt; vis(n,vector&lt;int&gt;(m,0));
    vector&lt;vector&lt;pair&lt;int,int&gt;&gt;&gt; par(n,vector&lt;pair&lt;int,int&gt;&gt;(m,{-1,-1}));
    vis[sx][sy]=1;

    while(!q.empty())
    {
        auto x=q.front();
        q.pop();
        for(int l = 0;l &lt; 4;l++)
        {
            int ni=x.first+dx[l],nj=x.second+dy[l];
            if(ni &lt; 0||ni &gt;= n||nj &lt; 0||nj &gt;= m)
                continue;
            if(v[ni][nj]=='#'||vis[ni][nj]==1)
            {
                continue;
            }
            par[ni][nj]=x;
            q.push({ni,nj});
            vis[ni][nj]=1;
        }
    }
    if(par[ex][ey]!=(pair&lt;int,int&gt;){-1,-1}){
        vector&lt;pair&lt;int,int&gt;&gt; path;
        path.push_back({ex,ey});
        pair&lt;int,int&gt; curr={ex,ey};
        while(curr!=(pair&lt;int,int&gt;){-1,-1})
        {
            curr=par[curr.first][curr.second];
            if(curr!=(pair&lt;int,int&gt;){-1,-1})
                path.push_back(curr);
        }
        reverse(path.begin(),path.end());
        for(auto x:path)
            cout&lt;&lt;x.first&lt;&lt;" "&lt;&lt;x.second&lt;&lt;endl;
    }
    return par[ex][ey]!=(pair&lt;int,int&gt;){-1,-1};
}

Time Complexity : O(N*M)

ADD COMMENTlink 18 months ago hardik kapoor 130
0
Entering edit mode

Seattle Round Q1

Solution

  • The question can be solved by iterating over each elements of array and check whether it occurs in another array or not.
  • Searching whether an element occurs in another array can be done in O(N)time by bruteforce, and can be optimized by maintaining a HashMap of the array for doing it in O(1) time.
  • We should also keep a track of whether an element is not repeated in the answer , again it could be also done using HashMap in O(1) time.
ADD COMMENTlink 18 months ago Shikhar Mehrotra 480

Login before adding your answer.

Similar Posts
Loading Similar Posts