Sapient test : OA Jmi on campus
Problem 1 : Insert a linked list in the middle of another linked list
Leetcode of the same Problem
Solution 1
Code
```cpp
SinglyLinkedListNode f=list1,s=list1;
for(int i=0;i<a-2;i++)
f=f.next;
for(int i=0;i<b-1;i++)
s=s.next;
if(a>=2)
f.next=list2;
else
list1=list2;
while(list2.next!=NULL)
list2=list2.next;
list2.next=s.next;
return list1;
```
Problem 2 : given a unweighted undirected graph with exactly one cycle. Find the distance of each node from the cycle. Return an array. The nodes in the cycle have distance 0
Similar Question to problem 2
Approach
- First motive is to find cycle.
- Once found, then we can put all elements on queue, and go for (multisource BFS / multisource shortest path).
- Colouring
- color == 0: unvisited.
- color == 1: Exploring, seen somewhere before, either parent-child or **cycle**.
- color == 2: visited, no need to visted again.
- Then there is a parent array, to store the parents and to backtrack once we found the cycle.
- As we found cycle, we will then backtrack all related nodes and store them in a queue, to BFS them.
Code for the same.
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<vector> graph;
vector color;
vector parent;
int n;
void dfs(const int &u) {
color[u] = 1;
for (const auto &v : graph[u]) {
if (color[v] == 0) {
parent[v] = u;
dfs(v);
} else if (color[v] == 1) {
if (parent[u] == v) {
// Baap hai uska wo
} else {
// yeah, cycle
int start = u;
int end = v;
queue qu;
vector used(n + 1);
vector dist(n + 1, 0);
while (start != end) {
qu.push(start);
used[start] = true;
dist[start] = 0;
start = parent[start];
}
qu.push(end);
used[end] = true;
dist[end] = 0;
while (!qu.empty()) {
auto curr = qu.front();
qu.pop();
for (const auto &c : graph[curr]) {
if (used[c])
continue;
used[c] = true;
dist[c] = dist[curr] + 1;
qu.push(c);
}
}
for (int i = 1; i <= n; i++) {
cout << dist[i] << ' ';
}
cout << '\n';
exit(0);
}
}
}
color[u] = 2;
}
void solve() {
int m;
cin >> n >> m;
graph = vector<vector>(n + 1);
color = vector(n + 1, 0);
parent = vector(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(1);
}
int main() { solve(); }
```
</details>
# Interview
## Publicis sapient technical round
1. What do you understand from oops
2. Tell different oops features and their implementation in java and c++
3. Explain polymorphism in detail in java and c++
4. Questions from method overriding in java
5. What is array and link list and difference
6) how does hashmap work in java and hash function
7. Coding question to find length and print maximum subarray containing consecutive numbers in an order(asceding or desc)
8. What is process synchronization and how to achieve it
9. What is normalisation
10. Design a database for your department (tables needed and logic as ti why you took them)
11. If sql query is optimised but yet the query is slow what will you do to improve efficiency, no more optimisation possible in the query