Top SDE Question -- Leetcode

[Sascha]

LeetCode shared an interesting post on May 17, 2025, featuring 12 of the most frequently asked coding interview questions by top tech companies. A must-read for anyone preparing for technical interviews!

Here right now, first try to do these questin yourself, and if not getting then I have provided the links to detailed solution also...!

1. 1004. Max Consecutive Ones -3

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

int longestOnes(vector<int>& nums, int k) {

int i = 0, j = 0, ans =0;
for(i=0; i<nums.size(); i++ ){

if(nums == 0) k--;

while(k<0){
if(nums[j] == 0) k++;
j++;
}
ans = max(ans, i-j+1);

}
return max(ans, i-j);

}

1. 125. Valid Palindrome

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

bool isPalindrome(string s) {
string res = "";
for(auto i=0; i<s.size(); i++){
if(isalnum(s)){
s = tolower(s);
res+=s;
}
}
int st = 0; int e = res.size()-1;
while(st<e){
if(res[st] != res[e]) return false;
st++; e--;
}
return true;
}

1. 35. Search Insert Position

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

int searchInsert(vector<int>& nums, int target) {
int n = nums.size();

int s = 0; int e = n-1; int ans;
while(s<=e){
int mid = (s+(e-s)/2);
if(nums[mid]== target){
ans = mid;
break;
}
else if(target>nums[mid]){
s = mid + 1;
ans = s;
if(s>e)
ans = s;

}
else{
e = mid-1;
ans = e;
if(s>e)
ans = s;
}
}
return ans;

1. 303. Range Sum Query - Immutable

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

class NumArray {
public:
vector<int>v;
NumArray(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i = 0; i<n; i++){
sum+=nums;
v.push_back(sum);
}
}

int sumRange(int left, int right) {
return v

- v

}
};

1. 71. Simplify Path

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

string simplifyPath(string path) {
vector<string> sv;
stringstream ss(path);
string t;

while (getline(ss, t, '/')) {
if (t == "" || t == ".") {
continue;
} else if (t == "..") {
if (!sv.empty()) sv.pop_back();
} else {
sv.push_back(t);
}
}

string ans = "/";
for (int i = 0; i < sv.size(); ++i) {
ans += sv;
if (i != sv.size() - 1) {
ans += "/";
}
}

return ans;
}

1. 725. Split Linked List in Parts

countNode Function:
Counts the total number of nodes in the list.

Returns 1 if the list is empty (though this is slightly unusual — usually should return 0).
solve Function:
common = count / k: Each part should have at least this many nodes.

rem = count % k: This many parts will have 1 extra node.

For each part i:

Calculate the number of nodes to assign: common + (rem > 0 ? 1 : 0).

Decrease rem if extra node is added.

Traverse and assign nodes to ans.

Break the link at the end of each part to separate them.

If the list ends early, remaining parts are set to nullptr.

splitListToParts Function:
Returns a vector of k linked lists.

Handles edge case when head == nullptr.


int countNode(ListNode* head, int k) {
if (head == NULL)
return 1;

int count = 0;
ListNode* temp = head;
while (temp != nullptr) {
count++;
temp = temp->next;
}
return count;
}

vector<ListNode*> solve(ListNode* head, int k, int count) {
int common = (floor)(count / k);
int rem = count % k;
// cout<<common << "->"<<count<<"--"<<rem<<endl;
ListNode* curr = head;
ListNode* prev = nullptr;

vector<ListNode*> ans(k, nullptr);
bool check = false;
for (int i = 0; i < k; i++) {
int addi = (rem>0) ? 1 : 0;
int run = common + addi;
if (rem > 0) {
rem--;
}
if (!check) {
ans = curr;

for (int j = 0; j < run; j++) {
prev = curr;
if (curr->next != nullptr) {
curr = curr->next;
} else if (curr->next == nullptr) {
check = true;
break;
}
}
}
else if(check){
ans = nullptr;
}

if (prev != nullptr) {
prev->next = nullptr;
}
}
return ans;
}

vector<ListNode*> splitListToParts(ListNode* head, int k) {
vector<ListNode*> ans(k, nullptr);
if(head == nullptr) return ans;

int count = countNode(head, k);

return solve(head, k, count);
}

1. 94. Binary Tree Inorder Traversal

void inordertra(TreeNode* root, vector<int> &v ){
if(root == NULL) return;

inordertra(root -> left, v);
v.push_back(root -> val);
inordertra(root -> right,v);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>v;
inordertra(root, v);
return v;
}

1. 207. Course Schedule

• 
  Build Graph
  Create an adjacency list adj where adj[a] contains all courses b that must be done before a.
  
  
• 
  Compute In-Degree
  Count how many prerequisites (incoming edges) each course has → store in indegree.
  
  
  [*]
  Initialize Queue
  Push all courses with 0 prerequisites (in-degree 0) into the queue.
  
  
  [*]
  Topological Sort (Kahn’s Algorithm)
  While the queue is not empty:
  Pop a course.
  Add it to the topo order.
  For each dependent course, reduce its in-degree.
  If any dependent course now has 0 in-degree, push it into the queue.
  
  
  [*]
  Final Check
  If all courses are in topo (i.e. topo.size() == n), return true (no cycles).
  Otherwise, return false (cycle exists).
  
  

bool canFinish(int n, vector<vector<int>>& prerequisites) {
vector<vector<int>>adj(n);
for(auto i : prerequisites){
int first = i[0]; int second = i[1];
adj[first].push_back(second);
}

vector<int>indegree(n, 0);
for(int i = 0; i<n; i++){
for(auto it : adj){
indegree[it]++;
}
}

queue<int> q;
for(int i=0; i<n; i++){
if(indegree == 0) q.push(i);
}

vector<int>topo;
while(!q.empty()){
int node = q.front();
q.pop();
topo.push_back(node);

for(auto it : adj[node]){
indegree[it]--;
if(indegree[it] == 0) q.push(it);
}
}
if(topo.size() == n) return true;
return false;

}

1. 198. House Robber

• 
  Base Cases:
  If n < 0: No houses left → return 0.
  If n == 0: Only one house → rob it → return nums[0].
  
  
• 
  Check:
  If already computed (dp[n] != -1), return saved value.
  
  
• 
  Choices:
  one: Rob this house (nums[n]) + solve for n-2 (skip next).
  two: Skip this house → solve for n-1.
  
  
• 
  Store and Return Max:
  Store the max of one and two in dp[n].
  Return dp[n].
  

int solve(vector<int>& nums, int n, vector<int>& dp){
if(n<0) return 0;
if(n == 0) return nums[0];
if(dp[n]!=-1) return dp[n];
int one = solve(nums, n-2, dp)+nums[n];
int two = solve(nums, n-1, dp);

dp[n] = max(one, two);
return dp[n];
}
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, -1);
return solve(nums, n-1, dp);
}

Источник:

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.

​