សរសេរមុខងារដើម្បីទទួលបានចំនុចប្រសព្វនៃបញ្ជីទំនាក់ទំនងពីរ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ គួរឱ្យគោរព ក្រុមហ៊ុន Amazon DE Shaw រោងចក្រ ក្រុមហ៊ុន Goldman Sachs MakeMyTrip MAQ ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន qualcomm Snapdeal ទិដ្ឋាការ ហ្សូភើព
បញ្ជីភ្ជាប់

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ សរសេរមុខងារមួយដើម្បីទទួលបានចំនុចប្រសព្វនៃបញ្ជីទំនាក់ទំនងពីរ” ដែលអ្នកត្រូវបានផ្តល់អោយនូវបញ្ជីភ្ជាប់ពីរ។ ប៉ុន្តែពួកគេមិនមែនជាបញ្ជីភ្ជាប់ឯករាជ្យទេ។ ពួកគេត្រូវបានភ្ជាប់នៅចំណុចខ្លះ។ ឥឡូវអ្នកត្រូវរកចំណុចប្រសព្វនៃបញ្ជីទាំងពីរនេះ។

ឧទាហរណ៍

សរសេរមុខងារដើម្បីទទួលបានចំនុចប្រសព្វនៃបញ្ជីទំនាក់ទំនងពីរ

1 -> 2
      \
        5 -> 6
      /
3 -> 4
Point of intersection: 5

ការពន្យល់ៈមានបញ្ជីភ្ជាប់ពីរដែលបង្ហាញនៅក្នុងធាតុបញ្ចូលដែលមាន ១, ២, ៥, ៦ និង ៣, ៤, ៥, ៦ ។ ទាំងពីរត្រូវបានបញ្ចូលគ្នានៅថ្នាំងដែលតម្លៃរបស់វាគឺ ៥ ។

វិធីសាស្រ្ត

បញ្ហាគឺសាមញ្ញដើម្បីពិពណ៌នា។ មាន​ពីរ បញ្ជីដែលបានភ្ជាប់ ប៉ុន្តែពួកគេត្រូវបានភ្ជាប់ឬភ្ជាប់គ្នានៅចំណុចខ្លះ។ មុនពេលចំនុចភ្ជាប់ទាំងពីរបញ្ជីដែលបានភ្ជាប់មានថ្នាំងខុសគ្នាហើយបន្ទាប់ពីថ្នាំងចូលរួម។ ពួកវាត្រូវបានតំណាងដោយបញ្ជីតែមួយ។ ដូច្នេះបញ្ហាគឺថាតើយើងរកឃើញថ្នាំង (ឬចំណុច) យ៉ាងដូចម្តេច? វាអាចមានចម្លើយ / ដំណោះស្រាយជាច្រើនដែលអាចកើតមានចំពោះបញ្ហានេះ។ ប៉ុន្តែវិធីសាមញ្ញបំផុតគឺត្រូវស្វែងរកប្រវែងនៃបញ្ជីដែលបានភ្ជាប់។ នៅពេលណាដែលដំណោះស្រាយមានលក្ខណៈសាមញ្ញវាមិនមានប្រសិទ្ធភាពគ្រប់គ្រាន់ក្នុងការឆ្លងកាត់ពេលវេលាកំណត់ឡើយ។ ប៉ុន្តែនោះមិនមែនជាករណីនៅទីនេះទេ។ ដំណោះស្រាយនេះមានប្រសិទ្ធភាពនិងសាមញ្ញ។

ការពន្យល់

នៅក្នុងដំណោះស្រាយនេះយើងនឹងស្វែងរកប្រវែងនៃបញ្ជីដែលបានភ្ជាប់គ្នាពីរ។ ហើយបន្ទាប់មកយើងនឹងផ្លាស់ប្តូរក្បាលនៃបញ្ជីដែលបានតភ្ជាប់វែងជាងមុនដោយ (លីនអេ - lenB) ថ្នាំង។ នៅទីនេះ លីនអេ និង lenB បញ្ជាក់ប្រវែងនៃបញ្ជីដែលភ្ជាប់ A និង B រៀងៗខ្លួន។ ប៉ុន្តែហេតុអ្វីបានជាយើងធ្វើបែបនេះ?

ពិចារណាលើប្រវែងនៃបញ្ជីដែលបានភ្ជាប់ជាទូទៅគឺ z ប្រវែងនៃបញ្ជីវែងជាង x + z ហើយនោះគឺជាបញ្ជីភ្ជាប់ខ្លីជាង y + z។ ដូច្នេះរហូតមកដល់ពេលនេះយើងបានរើទៅហើយ lenA - lenB នៅលើបញ្ជីដែលបានភ្ជាប់យូរជាងនេះ។ នោះគឺ (x + z - (y + z)) = x - y។ នេះមានន័យថាយើងបានផ្លាស់ប្តូរបញ្ជីដែលបានតភ្ជាប់យូរជាងនេះរហូតដល់ថ្នាំងដែលយើងកំពុងឈរមានប្រវែងផងដែរ y ពីថ្នាំងចូលរួមដូចជាក្បាលនៃបញ្ជីដែលមានតំណខ្លី។ បន្ទាប់មកយើងផ្លាស់ប្តូរដំណាលគ្នាលើបញ្ជីទាំងពីរដែលបានភ្ជាប់ហើយពិនិត្យមើលថាតើថ្នាំងបច្ចុប្បន្នទាំងពីរស្មើគ្នាឬអត់។ បើដូច្នេះយើងបានរកឃើញចំនុចប្រសព្វរបស់យើងហើយ។ ប៉ុន្តែប្រសិនបើយើងរកមិនឃើញចំនុចបែបនេះទេរហូតដល់ចុងបញ្ចប់នៃបញ្ជីភ្ជាប់។ បន្ទាប់មកនេះបង្ហាញថាពួកគេមិនមានចំនុចប្រសព្វទេ។

ដូច្នេះនេះគឺជារបៀបដែលយើងសរសេរមុខងារដើម្បីទទួលបានចំនុចប្រសព្វនៃបញ្ជីទំនាក់ទំនងពីរ។

លេខកូដ

លេខកូដ C ++ ដើម្បីស្វែងរកចំនុចប្រសព្វនៃបញ្ជីដែលបានតភ្ជាប់ពីរ

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

int length(ListNode *tmp){
    int cnt =  0;
    while(tmp != NULL){
        cnt++;
        tmp = tmp->next;
    }
    return cnt;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = length(headA);
    int lenB = length(headB);
    
    if(lenA > lenB){
        int cnt = lenA - lenB;
        while(cnt--)
            headA = headA->next;
    } else {
        int cnt = lenB - lenA;
        while(cnt--)
            headB = headB->next;
    }
    while(headA != NULL && headB != NULL){
        if(headA == headB)
            return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  ListNode *headB = create(3);
  headB->next = create(4);
  headA->next->next = headB->next->next = create(5);
  headA->next->next->next = headB->next->next->next = create(6);

  cout<<"Intersection at node: ";
  cout<<getIntersectionNode(headA, headB)->data<<endl;
}
Intersection at node: 5

កូដចាវ៉ាដើម្បីរកចំនុចប្រសព្វនៃបញ្ជីដែលបានតភ្ជាប់ពីរ

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static int length(ListNode tmp){
        int cnt =  0;
        while(tmp != null){
            cnt++;
            tmp = tmp.next;
        }
        return cnt;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);

        if(lenA > lenB){
            int cnt = lenA - lenB;
            while(cnt-- > 0)
                headA = headA.next;
        } else {
            int cnt = lenB - lenA;
            while(cnt-- > 0)
                headB = headB.next;
        }
        while(headA != null && headB != null){
            if(headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;        
    }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    ListNode headB = create(3);
    headB.next = create(4);
    headA.next.next = headB.next.next = create(5);
    headA.next.next.next = headB.next.next.next = create(6);

    System.out.print("Intersection at node: ");
    System.out.print(getIntersectionNode(headA, headB).data);
  }
}
Intersection at node: 5

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N), ចាប់តាំងពីយើងបានដំណើរការលើថ្នាំងនីមួយៗនៅក្នុងបញ្ជីដែលបានភ្ជាប់យ៉ាងពិតប្រាកដ។ ប្រសិនបើមានចំនុចប្រសព្វបន្ទាប់មកនៅពេលយើងទៅដល់ថ្នាំងនោះយើងត្រឡប់វា។ ប្រើថ្នាំងនីមួយៗត្រូវឆ្លងកាត់តែមួយដង។ នេះបញ្ជាក់ថាពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), រឿងតែមួយគត់ដែលយើងបានរក្សាទុកគឺប្រវែងនៃបញ្ជីដែលបានភ្ជាប់ដែលធ្វើឱ្យក្បួនដោះស្រាយនេះប្រើចន្លោះថេរ។