चक्रीय ऐरे: हेड इंडेक्स से ओ(१) घुमाव (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ७.९: जेनेरिक चक्रीय ऐरे जो हेड पॉइंटर हिलाकर ओ(१) में घूमता है, मॉड्यूलो से तार्किक इंडेक्स मैप करता है, और इटरेबल से फॉर-ईच चलाता है।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तुम ऐसा ऐरे चाहते हो जिसे घुमा सको बिना पूरी कॉपी चुकाए। बाएँ या दाएँ घुमाओ, फिर नए सामने से सामान्य for (T x : array) लूप से तत्व चलाओ। हर घुमाव पर हर सेल खिसकाना धीमा रास्ता है। इंटरव्यू का जवाब तत्वों को जहाँ हैं वहीं छोड़ता है, एक हेड इंडेक्स हिलाता है, फिर हर तार्किक इंडेक्स को उसी हेड से मॉड्यूलो से मैप करता है।

यह पोस्ट शुरुआती लोगों के लिए जावा में मूल शिक्षण है। इंटरव्यू वाले चक्रीय बफ़र डिज़ाइन का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ७ (ऑब्जेक्ट-ओरिएंटेड डिज़ाइन) यहाँ एक छोटी, साफ़ डेटा संरचना से आगे बढ़ता है।

१. रोज़मर्रा की उपमा

मेज़ पर एक घुमाने वाली थाली सोचो। प्लेट थाली पर जमी रहती हैं। कोई थाली घुमाए तो कोई हर प्लेट उठाकर फिर से नहीं सजाता। थाली घूमती है; तुम्हारे सामने क्या है, वही बदलता है।

तुम्हारा ऐरे थाली है। प्लेटें तत्व हैं। एक पूर्णांक, head, याद रखता है कौन सी भौतिक स्लॉट अभी तार्किक शुरुआत है। get(0) हमेशा मतलब “अतिथि के सामने अभी क्या है”, “भौतिक इंडेक्स ०” नहीं।

जब तुम k से घुमाते हो, सिर्फ head अपडेट होता है। इटरेशन उसी हेड से शुरू होकर घेरे के चारों ओर चलती है जब तक हर स्लॉट एक बार न देख ली जाए।

२. समस्या सादे शब्दों में

लक्ष्य: एक चक्रीय ऐरे बनाओ जो स्थिर आकार के ऐरे जैसा चले, सस्ता घुमाव दे, और मानक फॉर-ईच इटरेशन चले।

ज़रूरतें:

निश्चित संख्या तत्व रखो (निर्माण पर क्षमता)।
मौजूदा घुमाव के बाद तार्किक इंडेक्स 0 .. size-1 पर get(i) / set(i, value)।
rotate(shiftRight): पूरा ऐरे कॉपी किए बिना तार्किक शुरुआत बदलो।
जेनेरिक प्रकार T (जावा टाइप पैरामीटर) पसंद करो।
Iterable<T> से for (T item : circularArray) चलाना।

कोड से पहले साफ करो:

स्थिर क्षमता या बढ़ने वाली? इस समस्या के लिए स्थिर काफी है।
rotate(1) का मतलब? तार्किक इंडेक्स ० वही बन जाता है जो पहले तार्किक १ था (हेड आगे बढ़ता है)।
ऋणात्मक rotate? उपयोगी; बाएँ-दाएँ दोनों के लिए मॉड्यूलो से सामान्य करो।
खाली आकार? कंस्ट्रक्टर में गैर-धनात्मक क्षमता अस्वीकार करो।
इटरेटर का remove()? बिना समर्थन ठीक है जब तक न पूछा जाए।

छोटा चित्र (size = 4, मान ए बी सी डी):

हेड	तार्किक क्रम `get(0)`..`get(3)`	भौतिक ऐरे
०	ए बी सी डी	`[A, B, C, D]`
१	बी सी डी ए	`[A, B, C, D]` (वही)
२	सी डी ए बी	अभी भी वही
३	डी ए बी सी	अभी भी वही

भौतिक सेल नहीं हिलतीं। सिर्फ मैप हिलता है।

३. पहले सोचो

बुरा विचार: हर तत्व खिसकाओ

rotate(1): copy items[1] into a temp buffer, or loop:
  for i in 0..n-2: items[i] = items[i+1]
  items[n-1] = first

यह हर घुमाव पर ओ(एन) है। एक बार के लिए ठीक, बार-बार या बड़े n पर दर्द। इंटरव्यूअर चाहता है तुम इसे बोलकर मुख्य डिज़ाइन से हटा दो।

अच्छा विचार: हेड + इंडेक्स मैप

रखो:

items: लंबाई n का कच्चा ऐरे
head: मौजूदा तार्किक शुरुआत का भौतिक इंडेक्स

तार्किक इंडेक्स से भौतिक:

physical = (head + logical) mod n

जावा का % शेष है, गणितीय मॉड नहीं: ऋणात्मक पर ऋणात्मक रह सकता है। इंडेक्स से पहले सामान्य करो:

offset = logical % n
if offset < 0: offset += n
physical = (head + offset) % n

k से घुमाओ: head को उस भौतिक इंडेक्स पर सेट करो जो पहले तार्किक k था। अगर convert पहले से मौजूदा हेड जोड़ता है तो यही head = convert(k) है। एक असाइनमेंट। ओ(१)।

इटरेशन

फॉर-ईच को Iterable<T> चाहिए:

१. क्लास implements Iterable<T> घोषित करे। २. iterator() एक Iterator<T> लौटाए। ३. इटरेटर घुमे हुए हेड से ऑफसेट current रखे (0, 1, 2, ...), सिर्फ कच्चा भौतिक पॉइंटर नहीं। ४. hasNext: और ऑफसेट बाकी हैं। ५. next: ऑफसेट बढ़ाओ, items[convert(current)] लौटाओ।

फॉर-ईच में पहली कॉल श्रृंखला hasNext() फिर next() है। current को -1 से शुरू करो ताकि पहला next() ऑफसेट 0 (तार्किक आगे) पर आए।

जावा में जेनेरिक और ऐरे

new T[size] नहीं लिख सकते। आम पैटर्न:

items = (T[]) new Object[size];

कंस्ट्रक्टर पर एक बार अनचेक्ड चेतावनी दबाओ, या List<T> रखो। ऐरे + कास्ट सीटीसीआई शैली का आम जवाब है; चेतावनी का ज़िक्र करो ताकि जानबूझकर लगे।

४. जावा समाधान

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Fixed-capacity circular array.
 * rotate moves a head index; elements stay put.
 * Logical get/set and for-each all go through convert().
 */
public class CircularArray<T> implements Iterable<T> {
    private final T[] items;
    private int head = 0;

    @SuppressWarnings("unchecked")
    public CircularArray(int size) {
        if (size <= 0) {
            throw new IllegalArgumentException("size must be positive");
        }
        items = (T[]) new Object[size];
    }

    /** Map a logical index (and also raw shift amounts) into a physical slot. */
    private int convert(int index) {
        int n = items.length;
        int offset = index % n;
        if (offset < 0) {
            offset += n;
        }
        return (head + offset) % n;
    }

    /** New logical front is the old logical index shiftRight. O(1). */
    public void rotate(int shiftRight) {
        head = convert(shiftRight);
    }

    public T get(int i) {
        if (i < 0 || i >= items.length) {
            throw new IndexOutOfBoundsException("index " + i);
        }
        return items[convert(i)];
    }

    public void set(int i, T item) {
        if (i < 0 || i >= items.length) {
            throw new IndexOutOfBoundsException("index " + i);
        }
        items[convert(i)] = item;
    }

    public int size() {
        return items.length;
    }

    @Override
    public Iterator<T> iterator() {
        return new CircularArrayIterator();
    }

    /**
     * Walks logical offsets 0 .. n-1 from the current head.
     * Non-static inner class so convert() and items stay accessible.
     */
    private class CircularArrayIterator implements Iterator<T> {
        private int current = -1; // before first element

        @Override
        public boolean hasNext() {
            return current < items.length - 1;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            current++;
            return items[convert(current)];
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("remove not supported");
        }
    }
}

चलकर देखो: भरो, घुमाओ, पढ़ो, इटरेट करो।

CircularArray<String> ring = new CircularArray<>(4);
ring.set(0, "A");
ring.set(1, "B");
ring.set(2, "C");
ring.set(3, "D");
// logical: A B C D, head = 0

ring.rotate(1);
// head = 1; get(0)=B, get(1)=C, get(2)=D, get(3)=A

ring.rotate(2);
// from head=1, convert(2) -> head becomes 3
// logical: D A B C

for (String s : ring) {
    System.out.print(s + " "); // D A B C
}

कदम	कॉल	हेड	तार्किक दृश्य
शुरू	ए बी सी डी सेट	०	ए बी सी डी
१	`rotate(1)`	१	बी सी डी ए
२	`rotate(2)`	३	डी ए बी सी
३	फॉर-ईच	३	डी, फिर ए, बी, सी

हर जगह convert दोहराओ: get, set, rotate, और इटरेटर। मॉड्यूलो की किनारें एक जगह रहें।

५. जटिलता तालिका

ऑपरेशन	समय	अतिरिक्त जगह	नोट
`rotate(k)`	ओ(१)	ओ(१)	सिर्फ `head` अपडेट
`get` / `set`	ओ(१)	ओ(१)	एक कन्वर्ट + ऐरे ऐक्सेस
पूरा फॉर-ईच	ओ(एन)	ओ(१) इटरेटर	हर स्लॉट एक बार
भोला घुमाव (खिसकाना)	ओ(एन)	ओ(१) या ओ(एन)	मुख्य डिज़ाइन से बचाओ
निर्माण	ओ(एन)	`items` के लिए ओ(एन)	स्थिर ऐरे

इंटरव्यूअर ओ(१) घुमाव की कहानी और सही इंडेक्स मैप चाहता है। इटरेबल ग्रेड का दूसरा आधा है।

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छेड़ते हैं:

rotate(0): कोई बदलाव नहीं; हेड वही।
rotate(n) या n का गुणज: पूरे चक्कर; तार्किक क्रम वही। % n संभालता है।
ऋणात्मक घुमाव: rotate(-1) हेड को एक तार्किक कदम पीछे ले जाए। कच्चा % बिना ऋणात्मक सुधार के टूटता है।
get सीमा से बाहर: तार्किक i < 0 या i >= n पर फेंको। बिना दस्तावेज़ के उपयोगकर्ता इंडेक्स चुपचाप न लपेटो।
नल तत्व: रेफरेंस प्रकारों में ठीक; जब तक न पूछा जाए विशेष केस मत बनाओ।
घुमाव के बाद इटरेटर: नया फॉर-ईच मौजूदा हेड लेता है। पुराना स्नैपशॉट डिज़ाइन चुनाव है; यह सादा संस्करण convert से जीवित head पढ़ता है (सिंगल-थ्रेड इंटरव्यू कोड के लिए ठीक)।
जेनेरिक ऐरे बनाना: Object[] से कास्ट, या ArrayList।
size = 1: हर घुमाव उसी तत्व पर; फिर भी क्रैश नहीं होना चाहिए।

आम गलतियाँ:

१. rotate में ऐरे खिसकाना। चलता है, दक्षता की माँग चूकता है। २. ऋणात्मक मॉड्यूलो भूलना। जावा में -1 % 4 है -1, 3 नहीं। ३. इटरेटर जो भौतिक इंडेक्स ० से चले बिना head लगाए। फॉर-ईच घुमाव अनदेखा करता है। ४. current को ० से शुरू कर गलत इंक्रिमेंट जिससे पहला या आखिरी छूटे या दोहराए। कागज़ पर एक बार hasNext / next ट्रेस करो। ५. % n के बिना head + i। घुमाव के बाद सीमा पार। ६. सिर्फ भौतिक इंडेक्स पर बाउंड चेक। तार्किक बाउंड 0 .. n-1 हैं; कन्वर्ट स्टोरेज के लिए है, कॉलर के तार्किक इंडेक्स जाँच के लिए नहीं।

छोटा स्मोक स्केच:

void demo() {
    CircularArray<Integer> a = new CircularArray<>(3);
    a.set(0, 10);
    a.set(1, 20);
    a.set(2, 30);
    a.rotate(1);
    assert a.get(0) == 20;
    assert a.get(1) == 30;
    assert a.get(2) == 10;
    a.rotate(-1); // back to original logical order
    assert a.get(0) == 10;

    int sum = 0;
    for (int v : a) {
        sum += v;
    }
    assert sum == 60;
}

७. दोस्त को समझाने वाला सार

चक्रीय ऐरे पूछता है: क्या सस्ते में घुमा सकते हो और फिर भी तार्किक क्रम में चल सकते हो?

१. तत्वों को ऐरे में जमे रखो। तार्किक स्थान ० के भौतिक इंडेक्स के रूप में head रखो। २. physical = (head + logical) mod n से मैप करो, और जावा का ऋणात्मक शेष सुधारो। ३. rotate(k) उसी मैप से सिर्फ head बदलता है। ओ(१), ओ(एन) नहीं। ४. get / set हमेशा पहले कन्वर्ट करें ताकि कॉलर सिर्फ तार्किक इंडेक्स सोचे। ५. Iterable लागू करो: इटरेटर घुमे हेड से ऑफसेट 0 .. n-1 दे ताकि for (T x : array) चले। ६. जेनेरिक (CircularArray<T>) इस्तेमाल करो। Object[] को T[] में कास्ट करो या सूची लो।

अगर चार बक्से बना सको, हेड तीर हिला सको, और बिना ऑफ-बाय-वन के convert लिख सको, समस्या ७.९ तुम्हारी है। घुमाव पॉइंटर अपडेट है; इटरेशन उसी पॉइंटर से घेरे के चारों ओर चलना है।