Entering edit mode

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

- 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

Submit Problem to OJ

- 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.

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

**Q1.** Check for balanced parenthesis in a string.

Click here to Practice

Submit Problem to OJ

**Q2.** Attaching Screenshot for it.

- 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

Submit Problem to OJ

**Q2.** Second most repeated char in a string

Click here to Practice

Submit Problem to OJ

**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.

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

Submit Problem to OJ

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

Submit Problem to OJ

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.

Entering edit mode

**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

Entering edit mode

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

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.

Time Complexity: `O(N), N`

is the size of the array.

Entering edit mode

- Check if the parentheses sequence is balanced or not.

- 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;
```

Time Complexity: `O(|S|)`

Entering edit mode

- 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.

- 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)

- 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'

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

Entering edit mode

- 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'.

```
vector<int> dx={1,-1,0,0};
vector<int> dy={0,0,1,-1};
int solve(vector<string> v)
{
int n=v.size(),m=v[0].size();
int sx=-1,sy=-1,ex=-1,ey=-1;
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
if(v[i][j]=='S')
{
sx=i,sy=j;
}
if(v[i][j]=='E')
{
ex=i,ey=j;
}
}
}
queue<pair<int,int>> q;
q.push({sx,sy});
vector<vector<int>> vis(n,vector<int>(m,0));
vector<vector<pair<int,int>>> par(n,vector<pair<int,int>>(m,{-1,-1}));
vis[sx][sy]=1;
while(!q.empty())
{
auto x=q.front();
q.pop();
for(int l = 0;l < 4;l++)
{
int ni=x.first+dx[l],nj=x.second+dy[l];
if(ni < 0||ni >= n||nj < 0||nj >= 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<int,int>){-1,-1}){
vector<pair<int,int>> path;
path.push_back({ex,ey});
pair<int,int> curr={ex,ey};
while(curr!=(pair<int,int>){-1,-1})
{
curr=par[curr.first][curr.second];
if(curr!=(pair<int,int>){-1,-1})
path.push_back(curr);
}
reverse(path.begin(),path.end());
for(auto x:path)
cout<<x.first<<" "<<x.second<<endl;
}
return par[ex][ey]!=(pair<int,int>){-1,-1};
}
```

Time Complexity : `O(N*M)`

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.

Loading Similar Posts