Blog

Day 1: Preparing For Placements

Today’s work:-

The DSA questions were asked in Myntra in OA.

Other Subject Notes

DBMS [Revision Started] [Today’s Notes Link]:- https://drive.google.com/file/d/15lJtpU089dXVKmEjh6VrMCXDhHklpx6F/view?usp=drive_link

[Chaos] Mock Interview Experience Today

I scheduled a mock interview today.

I was excited.

But the platform’s audio wasn’t working well.

I had to give an interview by typing comments.

The worst part is that the question was easy, but I needed help.

The question was to detect a cycle in a linked list. Yes, just that.

And here’s how I went:

// let me rephrase the question to confirm.
// i am given a root node of linked list and I need to determine if it has a cycle or not.
// I had one question what if the list is empty?
// [Interviewer]: consider you'll always have a head node.

// ok done so here's my approach to check this in O(n) time.
// I'll start with the head of linked list and will use a do while loop.
// if then I reach till the end of the list that is see a null pointer I'll return false.
// if not and I end up reaching the head again. I'll return true.
// does that sound good enough to proceed with?
// [Kill me already]

// [Interviewer]: yes approach is little bit correct but not completely, if loop does not end at head then ?
// [I never felt so stupid]

// alright got the issue so the cycle isn't necessarily from head back to head is that the question? In that case I'll
// need to modify my approach.
// ok let me take a minute to define an approach.
// I am thinking of having two pointers instead of one.
// one fast pointer and one slow pointer.
// if the fast one reaches the end then there is no cycle
// however if there is a cycle then, I would find atleast one point where fast and slow pointers point to the same node.
// initially I'll start both with head and have again t

// [Interviewer]: Ok get onto to coding now
#include <iostream>
#include <vector>


struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
    // your code goes here
    ListNode* slow =head, fast=head;
   
    do {
        slow = slow->next;
        fast = fast->next->next;
        if(fast==slow)return true;
    } while(fast != nullptr);
    return false;
}

// when I ran it on test cases It showed error. I thought it was because there was no copy constructor
// so I did this: ListNode* slow =new ListNode(head) slow->next = head->next; [same for fast too.] 
// [The interviewer stepped in and corrected code]:
ListNode* slow =head;
ListNode*fast=head;
// [At this point I asked my self how foolish can you be??]
// Ran again and new erro this time.
// I was accessing a nullptr interviewer noticed and corrected it.
while(fast != nullptr && fast->next!=nullptr);
// [Couldn't have gone more wrong]
// final run again. And error. 
//  I got this one was an edge case of having a single node. for safety I added head null check too.
if(head==nullptr || head->next==nullptr){return false;}

// [first interview and a nightmare performance. I hate me but I think I'll do better next time.]
//Final code:
#include <iostream>
#include <vector>


struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};


bool hasCycle(ListNode* head) {
    if(head==nullptr || head->next==nullptr){return false;}
    ListNode* slow =head;
    ListNode*fast=head;
   
    do {
        slow = slow->next;
        fast = fast->next->next;
        if(fast==slow)return true;
    } while(fast != nullptr && fast->next!=nullptr);
    return false;
}

If you are thinking this is just me, I solved a 3d dp on a graph question under OA pressure in a go, all by myself, just 2 cases missed, which were hidden, so I’ll never know.

Lesson: Mock interviews are extremely important.

DSA Question 1 [Easy]

Problem Statement

You are going to develop a smart home automation system that means different devices will be connected through voice. However, the system has to incorporate means of determining if the given voice command contains only lowercase letters because for security reasons the system can only accept lowercase voice commands.

Write a program to check if a given voice command (string) is entirely lowercase and contains no consecutive repeating characters (like “aa”, “bb”, etc.). If both conditions are satisfied, the program should return “VALID”; otherwise, it should return “INVALID”.

Input Format

A single string represents the voice command.

Output Format

Print “VALID” if the entire string is in lowercase and has no consecutive repeating characters else print “INVALID” if the string has any uppercase letters or consecutive repeating characters.

Constraints

  • 1 ≤ string length ≤ 10^2
  • The string may only contain alphabetic characters (a-z, A-Z).

Sample case 1

Testcase Input

turnonlights

Testcase Output

VALID

Explanation

The string “turnonlights” is in all lowercase, and no two consecutive characters are the same, so the program outputs “VALID”.

Sample case 2

Testcase Input

turnonlightss

Testcase Output

INVALID

Explanation

Although “turnonlightss” is in all lowercase, it has consecutive repeating characters (‘ss’), so the program outputs “INVALID”.

Code Solution:

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

string solve(string s) {
    unordered_set<char> alpha = {'a','b','c','d','e','f','g','h', 'i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    if(alpha.find(s[0]) == alpha.end()) {
        return "INVALID";
    }
    for(int i = 1; i < s.length();i++) {
        if(alpha.find(s[i]) == alpha.end()) {
            return "INVALID";
        }
        if(s[i-1]==s[i]) {
            return "INVALID";
        }
    }
    return "VALID";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    if (cin >> s) {
        cout << solve(s) << endl;
    }
    return 0;
}

DSA Question 2 [Medium]

Problem Statement

During a vibrant festival, a fun game has everyone lining up to receive numbers assigned in a unique pattern that depends on a mysterious parameter k. The process starts with the first k people, who are given numbers from 1 to k in increasing order. Immediately following, the next [unclear] people receive numbers in a descending order, starting [unclear] k-1 down to 2. This alternating pattern—ascending [unclear] numbers and descending [unclear] numbers—repeats [unclear] along the line.

Rohan, one of the enthusiastic participants, finds himself puzzled because he has forgotten the value of k. However, he distinctly remembers both his position in the line and the specific number he was given. Your challenge is to determine how many different k values could be consistent with the details that Rohan remembers. Note that the game only works when k > 1.

Input

The single line containing two space-separated integers N and X denoting the Rohan’s position in line and the number Rohan received during the numbering respectively.

Output Format

Print a single integer denoting the number of different values of K that satisfy the given conditions and it is guaranteed that under these constraints, the answer is always finite.

Constraints

1 ≤ X < N ≤ 10^9

Sample Testcase 1

Testcase Input

3 1

Testcase Output

1

Question Simple Description

First k positions:

1 2 3 4 ... k

Next k-2 positions:

k-1 k-2 ... 2

Then repeat.

Which means many such cycles exist.

N → your global position in the infinite line

X → the number written at that position

You need to try to figure out:

“For which values of k would the repeating pattern put X at position N?”

I tried a lot! I cannot even understand its solution after an hour.

I need to watch this playlist for number theory I guess:

Leave a Reply