Live Before You Die – স্টিভ জবস্‌

২০০৫ সালের ১২ জুন। অ্যাপল ইনকর্পোরেটের সহ-প্রতিষ্ঠাতা স্টিভ জবস্‌ স্ট্যানফোর্ড বিশ্ববিদ্যালয়ের সমাবর্তনে দেন তাঁর বিখ্যাত বক্তৃতা “How To Live Before you Die”। তাঁর এই বক্তৃতায় তিনি বলেন তাঁর জীবনের তিনটি গল্পের কথা। স্টিভ জবসের জবানিতেই আমরা আজকে এই লেখায় জানবো তাঁর সেই তিনটি গল্প।

পৃথিবীর অন্যতম সুন্দর একটি বিশ্ববিদ্যালয়ে তোমাদের সামনে আজ আসতে পেরে আমি আনন্দিত এবং সম্মানিত। আমি কলেজের গন্ডি পেরুতে পারিনি। সত্যি বলতে, আজকেই প্রথম আমি একটি বিশ্ববিদ্যালয়ের গ্রাজুয়েশনের সবচেয়ে কাছে আসতে পেরেছি। আজকে আমি তোমাদের আমার জীবনের ছোট্ট তিনটি গল্প বলবো।

প্রথম গল্পটির নাম আমি দিবো এক সূতোয় গাঁথা।

আমি রিড কলেজ থেকে প্রথম ৬ মাসের মাথায় ড্রপ আউট হই। কলেজ ড্রপ করার পরেও সেখানে আমি ১৮ মাসের মত ছিলাম। কিন্তু কেন আমি কলেজ থেকে ড্রপ আউট হয়েছিলাম? এই প্রক্রিয়াটি আসলে শুরু হয়েছিল আমার জন্মের আগে থেকে। আমার মা একজন অবিবাহিত কলেজ গ্রাজুয়েট হওয়ার কারণে সে সময় আমাকে দত্তক দেয়ার পরিকল্পনা করেন। আমার মা চেয়েছিলেন একটি সুন্দর ভবিষ্যতের জন্য আমাকে কোন শিক্ষিত পরিবারের কাছে দত্তক দিতে। সেজন্য তিনি পছন্দ করেছিলেন একজন নিঃসন্তান উকিল দম্পতিকে। কিন্তু সেই উকিল দম্পতি আসলে একটি মেয়ে সন্তানের বাবা-মা হতে চেয়েছিলেন। তাই আমার জন্মের পর তারা আর আমাকে নিতে চাননি। আমাকে নেয়ার জন্য অপেক্ষমান তালিকায় আরো এক দম্পতি ছিলেন। তাঁরা মধ্যরাতে একদিন একটা ফোনকল পান। আমার বায়োলজিক্যাল বাবা মা তাঁদের জিজ্ঞেস করলেন, “অপ্রত্যাশিতভাবে আমাদের একটি ছেলে হয়েছে। তোমরা কী তাকে দত্তক নিতে আগ্রহী?” আমার সেই বাবা-মা সানন্দে আমাকে তাঁদের পুত্র হিসেবে গ্রহণ করে নিলেন। যদিও আমার গর্ভধারিণী মা পরে যখন জানতে পেরেছিলেন আমাকে দত্তক নেয়া বাবা-মার দুজনের একজনও গ্রাজুয়েট নন। এমনকি তাঁরা স্কুল পাশও ছিলেন না, তখন তিনি চূড়ান্ত চুক্তিপত্রে সই দিতে অস্বীকার করেছিলেন। কয়েকমাস পরে, যখন আমার দত্তক নেয়া বাবা-মা আমার মার কাছে প্রতিজ্ঞা করেন যে তাঁরা আমাকে অবশ্যই লেখাপড়া শিখাবেন এবং একদিন আমি অবশ্যই কলেজে যাবো।

এর ঠিক ১৭ বছর পরে আমি কলেজে ভর্তি হই। আমি যে কলেজে ভর্তি হয়েছিলাম সেটি ছিলো এই স্ট্যানফোর্ডের মতই ব্যয়বহুল। আমার ছাপোষা চাকুরিজীবি বাবা-মা তাঁদের সারাজীবনের সঞ্চয় ব্যয় করে যাচ্ছিলেন আমার কলেজের পড়াশোনার পিছনে। ছয়মাস পর এসব আমার কাছে একদম নিরর্থক মনে হলো। আমি জীবনে কী করতে চাই সে সম্পর্কিত কোন ধারণা আমার ছিলো না এবং সেই ধারণা পেতে কলেজ আমাকে কতটুকু সাহায্য করতে পারবে সেটিও আমি বুঝতে পারছিলাম না। অর্থহীনভাবে আমি আমার বাবা-মায়ের সঞ্চয়ের টাকা শেষ করে যাচ্ছিলাম। তখন আমি কলেজ ছেড়ে দেয়ার সিদ্ধান্ত নেই এবং সেটি ছিল সঠিক একটি সিদ্ধান্ত। যদিও সে সময় এটি ছিল বেশ ভয়ঙ্কর একটি সিদ্ধান্ত, কিন্তু আজকে আমার জায়গায় দাঁড়িয়ে আমি পিছনে তাকালে বুঝতে পারি আমার এই কলেজ ছেড়ে দেয়ার সিদ্ধান্তটি ছিল আমার জীবনের নেয়া শ্রেষ্ঠ সিদ্ধান্ত। যে মূহুর্ত থেকে আমি কলেজ ড্রপ আউট হই, সে মূহুর্ত থেকে যেসব বিষয় পড়তে আমার ভাল লাগতো না সেগুলোর ক্লাস করা বন্ধ করে দেই এবং যেসব বিষয়ে আমার আগ্রহ ছিলো সেসব বিষয়ের ক্লাস করা শুরু করি।

অবশ্য ব্যাপারটা খুব একটা রোমান্টিক ছিলো না। সেসময় আমার কোন থাকার জায়গা ছিলো না। আমি আমার বন্ধুর ডরমেটরির রুমের মেঝেতে ঘুমাতাম। কোকের খালি বোতল কুড়িয়ে দোকানে জমা দিয়ে ৫ সেন্ট করে জোগাড় করতাম এবং সেটি দিয়ে আমার খাবার খরচ চালাতাম। প্রতি রবিবার ৭ মাইল হেঁটে হরেকৃষ্ণ মন্দিরে যেতাম শুধুমাত্র একবেলা ভালো খাবারের আশায়। এসব আমি খুব পছন্দ করতাম। আমি তখন আমার যেসব কাজ করতে ভালো লাগতো সেটাই করতাম এবং আস্তে আস্তে আমার কাছে শিক্ষাপ্রতিষ্ঠানের ভূমিকা গৌণ হয়ে গেল।

ছোট্ট একটা উদাহরণ দেইঃ
রিড কলেজে সেসময় দেশের সবচেয়ে ভালো ক্যালিগ্রাফি কোর্স চালু ছিল। ক্যাম্পাসের সব পোষ্টার, ড্রয়ার, শিরোনামে খুব সুন্দর সুন্দর হাতে তৈরি ক্যালিগ্রাফি শোভা পেত। যেহেতু আমি সেসময় কলেজ ড্রপআউট ছিলাম, রেগুলার কোর্সগুলো করার কোন বাধ্যবাধকতা ছিল না। কিভাবে ক্যালিগ্রাফি করা হয় এই আগ্রহ থেকে আমি ক্যালিগ্রাফির কোর্সগুলো করার সিদ্ধান্ত নেই। আমি Serif এবং San Serif ফন্ট দুইটি শিখি, অক্ষরগুলোর মাঝে স্পেসের ব্যবহার কিভাবে অপূর্ব টাইপফেসের সৃষ্টি করতে পারে সেটা বুঝতে পারি। সেটি ছিল অপূর্ব, ঐতিহাসিক এবং শৈল্পিক একটি বিষয় যা বিজ্ঞান দিয়ে ব্যাখ্যা করা যায় না এবং আমি এতে মুগ্ধতা খুঁজে পাই।

আমি ধরেই নিয়েছিলাম আমার এই শিক্ষাগুলো কখনোই আমার ব্যক্তিগত জীবনে কোন কাজে আসবে না। কিন্তু ১০ বছর পর যখন আমরা প্রথম ম্যাকিনটস কম্পিউটার ডিজাইন করি, তখন সব ফিরে এসেছিলো। আমরা সেগুলোকে ম্যাকে ব্যবহার করি। এটা ছিল সুন্দর টাইপোগ্রাফি সমৃদ্ধ প্রথম কম্পিউটার। আমি যদি তখন কলেজ ড্রপআউট না করতাম তাহলে ম্যাকিনটস কখনো এত বৈচিত্র্যময় টাইপফেস বা যথাযথ স্পেস সম্বলিত টাইপ ফন্ট পেত না। তখন থেকে উইন্ডোজ-ও এটা কপি করে আসছে, অর্থাৎ কোন পারসোনাল কম্পিউটারেই এত সুন্দর টাইপফেস আমরা পেতাম না। আমি যদি সেসময় কলেজ ড্রপ না করতাম, ক্যালিগ্রাফির সেইসব কোর্স গুলো না করতাম , তাহলে হয়ত আজকে এত সুন্দর ফন্ট আমরা কম্পিউটারে পেতাম না। অবশ্যই সামনে দাঁড়িয়ে হাজার হাজার বিন্দুর মধ্যে যোগসূত্র স্থাপন করা আজ থেকে ১০ বছর আগে যখন আমি কলেজে পড়তাম তখন অসম্ভব ছিল। কিন্তু সেই বিন্দুগুলোকে সংযুক্ত করা আজকে এখানে দাঁড়িয়ে আমার জন্য অনেক সহজ।

সামনের দিকে তাকিয়ে কখনোই বিন্দু সংযোগ দেয়া সম্ভব না, কিন্তু পিছন থেকে কাজটা করা অনেক সহজ। তোমাকে বিশ্বাস রাখতে হবে নিজের উপর যে, ভবিষ্যতে অবশ্যই কোন না কোনভাবে বিন্দুগুলো সংযুক্ত করা যাবেই। হতে পারে সেটা তোমার কর্মফল, তোমার ভাগ্য, তোমার পরিশ্রম, তোমার ক্ষমতা। আমার নিজের উপর এই বিশ্বাস কখনোই আমাকে পিছিয়ে পরতে দেয়নি এবং আমার এই সিদ্ধান্তই পাল্টে দিয়েছে আমার পুরো জীবনকে।

আমার দ্বিতীয় গল্পটা হচ্ছে ভালবাসা এবং হারিয়ে ফেলার গল্পঃ

আমি ভাগ্যবান ছিলাম – যা করতে ভালবাসতাম সেটি অল্প বয়সেই করতে পেরেছিলাম। ওজ এবং আমি অ্যাপল শুরু করেছিলাম আমাদের ব্যক্তিগত গ্যারেজে মাত্র ২০ বছর বয়সে। আমরা কঠোর পরিশ্রম করেছিলাম বলেই, গ্যারেজের দুইজনের কোম্পানি থেকে মাত্র ১০ বছরে অ্যাপল ২ বিলিয়ন ডলারের, ৪০০০ কর্মীর কোম্পানিতে পরিণত হয়েছে। আমরা যখন আমাদের সবচেয়ে সুন্দর আবিষ্কার ম্যাকিনটস তৈরি করলাম তখন আমার বয়স মাত্র ৩০। তখন আমাকে অ্যাপল থেকে ছাটাই করা হয়। প্রশ্ন হতে পারে, যে কোম্পানির শুরু আমি নিজে করেছি সেখান থেকে আমাকে কিভাবে ছাঁটাই করা যায় ? ধীরে ধীরে যখন অ্যাপল বড় হতে থাকলো, তখন আমি খুব মেধাবী একজনকে খুঁজতে থাকি যে কিনা আমার সাথে অ্যাপলকে আরো সমৃদ্ধ করবে। প্রথম একবছর আমাদের কাজ ভালই চলেছিল, কিন্তু যখন আমাদের লক্ষ্য আলাদা হয়ে গেল তখন আমরা ব্যর্থ হলাম। সেসময় অ্যাপলের বোর্ড অফ ডাইরেক্টরস্‌ আমার পক্ষ না নিয়ে তাঁর পক্ষ নিলো এবং ৩০ বছর বয়সে নিজ কোম্পানি থেকে আমাকে ছাঁটাই করা হলো। আমি আমার সারা জীবন যেখানে মনোনিবেশ করেছিলাম, সেটি এক মুহুর্তে চলে গেল; যা ছিল অত্যন্ত বিধ্বংসী।

সামনের কয়েকমাস কী করে আমার কাটবে, আমি বুঝতে পারছিলাম না। আমার মনে হয়েছিল আমি আমার পূর্ববর্তী প্রজন্মের উদ্যোক্তাদের পিছনে ফেলে দিয়েছিলাম, সেটা ঠিক কাজ হয়নি। আমি বব নয়েস এবং ডেভিট পাকার্ডের সঙ্গে দেখা করি এবং তাঁদের কাছে ক্ষমা চাই। যদিও এটা ছিল বড় ধরণের একটা ভুল এবং আমি একসময় সিলিকন ভ্যালি থেকে পালিয়ে যাওয়ার চিন্তাও করেছিলাম। কিন্তু ধীরে ধীরে আমি আমার আমিতে ফিরে এলাম এবং আবার নিজের কাজকে ভালবাসতে শুরু করলাম। আমার প্রস্থানে অ্যাপলে তেমন কোন পরিবর্তন হলো না। যদিও আমাকে বাতিল করা হয়েছিল অ্যাপল থেকে আমি, কিন্তু আমি তখনো আমার কাজকে ভালবাসতাম। তাই আমি আবারো নতুন করে সবকিছু শুরু করার সিদ্ধান্ত নেই।

তখন বুঝতে না পারলেও আমি পরে বুঝেছিলাম যে, অ্যাপল থেকে বিতাড়িত হওয়া আমার জীবনে ঘটা সর্বোত্তম একটি ঘটনা ছিল। সাফল্যের চূড়া থেকে হঠাৎ করেই ছিটকে যাওয়া এবং আবারো নিজেকে একদম তলানিতে আবিষ্কার করেছিলাম আমি; যেখানে নিশ্চিত ছিল না কোন কিছুই। এই ঘটনাটি আমাকে আমার জীবনের সবচেয়ে সৃজনশীল সময়টিতে পৌঁছে দেবার রাস্তাটাকে সহজ করে দিয়েছিলো।

পরবর্তী পাঁচ বছরে আমি NeXT এবং Pixar নামক দুইটি কোম্পানি প্রতিষ্ঠা করি এবং অসাধারণ একজন নারীর প্রেমে পরি , যিনি পরবর্তীতে আমার স্ত্রী হন। পিক্সার তখন বিশ্বের প্রথম কম্পিউটার এ্যানিমেটেড ফিচার ফিল্ম Toy Story তৈরি করে এবং এখন পর্যন্ত এটি বিশ্বের সবচেয়ে সফল এ্যানিমেশন স্টুডিও। এই অভূতপূর্ব সাফল্যের কারণে, অ্যাপল তখন NeXT-কে কিনে নেয়। আমি আবার অ্যাপলে ফিরে আসি। টেকনোলজি, যা NeXT এ তৈরি করা হয়েছিলো, এটি বর্তমান অ্যাপল যুগের প্রাণ। এবং লরেন্স ও আমি তখন একটি সুন্দর পরিবার গঠন করেছিলাম।

আমি মনেপ্রাণে বিশ্বাস করি, এসবের কিছুই হতো না যদি না আমাকে অ্যাপল থেকে বের করে দেয়া হতো। তিক্ত ওষুধ খাওয়ার অভিজ্ঞতা কোন রোগীর জন্য সুখকর না হলেও, রোগীর জন্য সেটি আবশ্যক। কখনো কখনো জীবন ইট দিয়ে তোমার মাথায় আঘাত করবে। বিশ্বাস হারানো যাবে না। আমি বিশ্বাস করতাম যে, একটি জিনিসই আমাকে সামনে এগিয়ে নিয়ে যেতে পারে, তা হলো নিজের কাজকে ভালবাসা। কী করতে তুমি ভালবাসো, সেটা তোমাকেই খুঁজে বের করতে হবে। এটা যেমন তোমার কাজের জন্য সত্য, তেমনি সত্য তোমার ভালবাসার মানুষের জন্যও। তোমার কর্ম তোমার জীবনের বিরাট একটি অংশকে পূর্ণ করবে, তাই পরিপূর্ণ সন্তুষ্টির জন্য তুমি যে কাজকে শ্রেষ্ঠ কাজ বলে মনে করো, সেটিকেই বেঁছে নাও। এবং শ্রেষ্ঠ কাজ করার সর্বোত্তম উপায় হলো নিজের বর্তমান কাজকে ভালবাসা। যদি তুমি এখনো সেটি খুঁজে না পাও, খুঁজতে থাকো। কখনো বসে পরো না। একসময় না একসময় তুমি ঠিকই তাকে খুঁজে পাবে। যেকোন সুন্দর সম্পর্কের মত যতদিন যাবে সেটি সুন্দর থেকে সুন্দরতর হতে থাকবে। তাই খুঁজে যাও তোমার তোমার ভালবাসার কাজটিকে, যতক্ষণ না পাও। হাল ছেড়ো না।

আমার শেষ গল্পটি মৃত্যু নিয়ে।
যখন আমার বয়স ১৭, তখন আমি একটি বাণী শুনেছিলাম এমন যে, “তুমি যদি তোমার জীবনের প্রতিদিনকে তোমার জীবনের শেষ দিন মনে করে কাজ করো, তাহলে একদিন তুমি অবশ্যই সফল হবে।” এই কথাটি আমাকে এতটাই মুগ্ধ করেছিলো যে, গত ৩৩ বছর আমি প্রতিদিন সকালে আয়নার সামনে দাঁড়িয়ে নিজেকে প্রশ্ন করি, “যদি আমি জানি যে আজকে আমার জীবনের শেষ দিন, তাহলে কী আমি সেই কাজ করবো যা আমি আজকে করতে চাচ্ছি?” পরপর কয়েকদিন যদি উত্তর পেতাম “না”, তখন আমি মনে করতাম কিছু পরিবর্তন করা আবশ্যক।

আমি খুব তাড়াতাড়ি মারা যাবো, এই কথাটি ছিল আমার জীবনে বড় বড় সিদ্ধান্ত নেয়ার মূল চালিকাশক্তি। কারণ, বলতে গেলে প্রায় সব কিছুই – সব ধরণের চাওয়া-পাওয়া, অহম, ভয়-ভীতি, লজ্জা, ব্যর্থতা সব কিছুই মৃত্যুর কাছে তুচ্ছ; সব কিছুই মূল্যহীন শুধুমাত্র যা সত্যিকার অর্থেই যা দরকার সেটা ছাড়া। যখন তুমি মনে করবে তুমি মরে যাচ্ছো, তখন তোমার কাছে মনে হবে না, তোমার হারাবার কিছু আছে। যখন তুমি নিঃস্ব, তখন নিজের মনের কথা শোনা ছাড়া আর কোন উপায়ই তোমার নেই।

একবছর আগে, আমি ক্যান্সারে আক্রান্ত হই। সকাল ৭ঃ৩০ এ স্ক্যান করে আমার অগ্ন্যাশয়ে একটি টিউমারের অস্তিত্ব শনাক্ত করা হয়। তখন আমি জানতাম অগ্ন্যাশয় কী জিনিস। আমার চিকিৎসক আমাকে বললেন, এই ক্যান্সারটি অনিরাময়যোগ্য ক্যান্সারগুলোর একটি এবং আমার আয়ু বড় জোড় ৩-৬ মাসের মত। আমার ডাক্তার আমাকে বলেছিলেন বাড়ি চলে যেতে এবং মৃত্যুর জন্য নিজেকে প্রস্তুত করতে। প্রস্তুতি বলতে ছিলো নিজের সন্তানদের কয়েক মাসের মধ্যে সবকিছু বলা যা আমি গত ১০ বছরে তাঁদের বলতে পারিনি। এটা ছিলো মূলত নিজের পরিবারকে বুঝানো যে, সময় সন্নিকটে যেন সবকিছু গ্রহণ করা তাঁদের জন্য সহজ হয়। ব্যাপারটা আসলে ছিলো পরিবারকে চিরবিদায় জানানো।

ঐদিন সারাদিনই আমার নানারকম পরীক্ষা-নিরীক্ষা চলে। সন্ধ্যায় আমার একটি বায়োপসি করানো হয়। আমার অগ্ন্যাশয়ের টিউমার থেকে কিছু কোষ নিয়ে পরীক্ষা করা হয়। আমি সেসময় অচেতন ছিলাম। জ্ঞান ফেরার পরে আমার স্ত্রীর কাছ থেকে আমি জানতে পারি যে, যখন আমার টিউমারের কোষগুলো মাইক্রোস্কোপের নিচে ধরা হয়, তখন হঠাৎ করে ডাক্তার কাঁদতে শুরু করে। কারণ, ক্যান্সারটি ততদিনে অপারেশনের মাধ্যমে নিরাময়যোগ্য একটি বিরল ক্যান্সারে পরিণত হয়েছে। আমার অপারেশন করার ফলে এখন আমি সুস্থ।

সেসময় খুব কাছ থেকে আমি মৃত্যুকে প্রত্যক্ষ করেছিলাম। মৃত্যুর কাছাকাছি যেয়ে আমি বুঝতে পেরেছি এটা নিখাদ এবং একটি আধ্যত্নিক ভাবনা। কোন মানুষই মরতে চায় না। এমনকি যারা স্বর্গে যেতে চায়, তারাও মৃত্যুকে হাসিমুখে গ্রহণ করে স্বর্গে যেতে চায় না। তারপরেও, এটি এমন একটি ঠিকানা, যেখানে আমরা সবাই একদিন পৌঁছে যাবো। কেউ সেখান থেকে পালাতে পারবে না। মৃত্যু জীবনের সুন্দরতম আবিষ্কারগুলোর একটি। পুরোনোকে মুছে ফেলে এটা নতুনদের জন্য পথকে পরিষ্কার করে। বর্তমানে নতুন হচ্ছো তোমরা, কিন্তু ধীরে ধীরে তোমরা বুড়ো এবং পুরোনো হতে থাকবে এবং একসময় মুছে যাবে। দার্শনিক মন্তব্য দেয়ার জন্য দুঃখিত, কিন্তু এটাই নিয়তি।

তোমার সময় সীমিত, সেসময়কে অন্যের জীবনের মত যাপন করে নষ্ট করো না। মানুষের চিন্তার ফলাফলের ফাঁদে নিজেকে আটকে রেখো না। অন্যের মতামতের চিৎকারে নিজের ভেতরকার আওয়াজকে থমকে যেতে দিও না। এবং অবশ্যই সাহস রাখো নিজের মনের কথা এবং অনুমানশক্তির উপর। কারণ, তারা সত্যিকার অর্থেই জানে তুমি কী হতে চাও। বাকিসব কিছুই সেখানে গৌণ।

আমার যুবক বয়সে একটি বই বেশ সাড়া ফেলেছিল। বইটির নাম দ্যা হোল আর্থ ক্যাটালগ (The Whole Earth Catalog), যাকে আমরা সেসময়ের তরুণ সমাজ বাইবেল জ্ঞান করতাম। স্টুয়ার্ড ব্রান্ড তাঁর কাব্যিক ছোয়ায় এটিকে মানুষের কাছে নিয়ে এসেছিল। এটা ১৯৬০ সালের ঘটনা, যখন পারসোনাল কম্পিউটার এবং ডেস্কটপ আবিষ্কার হয়নি। তাই এই বইটিতে ছিল টাইপরাইটার, কাঁচি, পোলারয়েড ক্যামেরার ছোঁয়া। এটাকে বলা যায় “গ্রন্থাকৃতির গুগল”।

স্টুয়ার্ট এবং তাঁর দল বইটিতে নানা ধরণের বিষয়ের অবতারণা করেছিলেন। বইটির শেষে তারা বলে গেছেন আসল কথা। এটা ৭০’ দশকের মাঝামাঝি সময়, তখন আমি তোমাদের বয়সী। তাঁদের বইয়ের শেষ পাতায় সকালের রাস্তার একটি সুন্দর আলোকচিত্র ছিল। তোমাদের মধ্যে যারা অভিযানপ্রিয় তারা এমন ছবি প্রায়ই দেখে থাকো। ছবির নিচে লেখা ছিল, “Stay Hungry. Stay Foolish.” এটা ছিল তাঁদের বিদায় সম্ভাষণ। Stay Hungry. Stay Foolish, যা আমি নিজে সবসময় নিজের জন্য কামনা করি। আজকে এখানে সবাই তোমরা প্রাজুয়েট হয়েছো। আজ আমি তোমাদের জন্যও বলছি, Stay Hungry. Stay Foolish

সবাইকে ধন্যবাদ।

[ Stay Hungry: কখনো তৃপ্ত হয়ো না এই ভেবে যে , তুমি সব জেনে গেছো। নিজেকে এগিয়ে নিয়ে যাও।
Stay Foolish: কাজ করে যাও এবং চেষ্টা করতে থাকো সেসব কাজ করার যেসব ব্যাপারে মানুষ বলে “কখনো এটা হবে না” ]

লেখকঃ তামান্না নিশাত রিনি


Facebook Comments

সকল সাবসেট তৈরি – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১৪

সমস্যাঃ একটি সেট দেওয়া আছে, সেই সেটের সকল সাবসেট তৈরি করার ফাংশন লিখতে হবে।

সমাধানঃ ইন্টারভিউতে এই প্রশ্ন করা হলে শুরুতেই দুটি বিষয় পরিষ্কার হয়ে নিতে হবে। সেটি হচ্ছে, ফাঁকা সেট এবং ওই সেটটি নিজে তার সাবসেট কী না। আমাদের এই আলোচনায়, দুটি উত্তরই হচ্ছে, হ্যাঁ।

সমাধান দেখার আগে নিজে চেষ্টা করা উচিত। এখানে গিয়ে সমস্যা দেখা যাবে ও সমাধান জমা দেওয়া যাবে – https://leetcode.com/problems/subsets/

তাহলে, ইনপুট যদি হয় [1, 2, 3], আউটপুট হবে, [[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]]। আউটপুট লিস্টের উপাদানগুলোর ক্রম ভিন্ন হলেও সমস্যা নেই, কিন্তু একই জিনিস দুইবার থাকতে পারবে না।

আমরা রিকার্শন ব্যবহার করে খুব সহজেই সমস্যাটির সমাধান করতে পারি। আমরা প্রতিবার সেট থেকে একটি উপাদান নেওয়ার চেষ্টা করব। তবে আমাদেরকে খেয়াল রাখতে হবে যেন, একই উপাদান একাধিকবার নেওয়া না হয়। সেজন্য একটি বুলিয়ান অ্যারে বা লিস্ট ব্যবহার করতে পারি (visited)। বিস্তারিত ব্যাখ্যা না করে, বরং কোড লিখে দিচ্ছি। তবে কোড বুঝার জন্য খাতা-কলম নিয়ে বসতে হবে। আর যারা ডিএফএস (dfs)-এর সঙ্গে পরিচিত, তারা সহজেই বুঝতে পারবে। আর যারা পরিচিত নও, তাদেরও খুব একটা সমস্যা হবে না।

def subsets1(S):
    if S == []:
        return [[]]
    
    result = [[]]
    n = len(S)
    visited = [False] * n
    
    def recurse(i, n, li):
        if i == n:
            return
        
        if len(li) > 0:
            result.append([x for x in li])
        
        for j in range(i, n):
            if visited[j]:
                continue
            visited[j] = True
            li.append(S[j])
            recurse(j, n, li)
            li.pop()
            visited[j] = False
            
    recurse(0, n, [])
    return result

এখন কথা হচ্ছে, ইন্টারভিউতে সমাধান করাই শেষ কথা নয়। কেউ এই কোড লেখা পরে ইন্টারভিউয়ার যদি বলেন, এবারে রিকার্শন ছাড়া সমাধান করে দেখান, তখন রিকার্শন ছাড়া সমাধান করতে হবে। যেসব সমস্যা রিকার্শন ব্যবহার করে সহজে করা যায়, সেগুলো রিকার্শন ছাড়া সমাধান করতে গেলে স্ট্যাক ব্যবহারের প্রয়োজন হতে পারে। আবার না বুঝে কোড লিখলেও হবে না। কারণ ইন্টারভিউতে পুরো কোড ব্যাখ্যাও করতে হবে। সুতরাং ভালো প্রস্তুতির প্রয়োজন।

সম্পূর্ণ কোড এখানে – https://gist.github.com/tamim/87d3b79ff15d3375a98e9e0cd73b7c73

 

Facebook Comments

permutation – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১৩

সমস্যাঃ একটি লিস্টে কিছু সংখ্যা থাকবে, সংখ্যাগুলোর সবগুলো বিন্যাস (permutation) বের করতে হবে।

উদাহরণ: লিস্টে যদি [1, 2, 3] থাকে, তাহলে বিন্যাসগুলো হবে –

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

সমাধানঃ এটি মোটামুটি সহজ একটি সমস্যা। তবে ইন্টারভিউয়ের সময় শুরুতেই একটি প্রশ্ন করে নিতে হবে – সংখ্যাগুলো অনন্য (unique) কী না। এটি না জেনেই হুট করে কোড শুরু করা যাবে না। যদি অনন্য হয়, তাহলে খুব সহজেই রিকার্শন ব্যবহার করে সমাধান করা যায়। আর যদি তা না হয়, তাহলে একটু সতর্ক থাকতে হবে, যেন একটি বিন্যাস একাধিকবার প্রিন্ট করা না হয়।

এরকম সহজ সমস্যা দেওয়ার কারণ হচ্ছে বেসিক রিকার্শন স্কিল পরীক্ষা করা। তারপরও আমার পরিচিত একজন ইন্টারভিউয়ারের মতে, ৮০% প্রার্থী এই সমস্যাটির সমাধান করতে ব্যর্থ হয়। যাই হোক, যারা এর সঙ্গে পরিচিত নয়, তারা শাফায়েতের ব্লগের ব্যাকট্র্যাকিং: পারমুটেশন জেনারেটর আর্টিকেলটি পড়তে পারে।

আমি পাইথন কোড দিচ্ছি –

def permute(i, n):
	if i == n:
		print(r)
		return
	
	for j in range(n):
		if visited[j]:
			continue
		visited[j] = True
		r[i] = a[j]
		permute(i+1, n)
		visited[j] = False

if __name__ == "__main__":
	a = [1, 2, 3, 4]
	r = [0] * len(a)
	n = len(a)
	visited = [False] * n
	permute(0, n)

এখন, এখানে আমি অতিরিক্ত একটি অ্যারে বা লিস্ট ব্যবহার করেছি। যদি সেটি করতে না চাই, তাহলে আরেকভাবে সমস্যাটির সমাধান করা যায়। সেক্ষেত্রে প্রতিটি অবস্থানের জন্য বাকী অবস্থানে যেসব সংখ্যা আছে, তাদের মধ্যে অদল-বদল করতে হবে। কোড হবে এরকম –

def permute2(l, r):
	if l == r:
		print(a)
		return
	
	for i in range(l, r+1):
		a[l], a[i] = a[i], a[l]
		permute2(l+1, r)
		a[l], a[i] = a[i], a[l]

if __name__ == "__main__":
	a = [1, 2, 3, 4]
	r = [0] * len(a)
	n = len(a)
	visited = [False] * n
	permute2(0, n-1)

এখন, যদি বলা হয়, লিস্টের সংখ্যাগুলো অনন্য নয়, একই সংখ্যা একাধিকবার থাকতে পারে, কিন্তু একই বিন্যাস একাধিকবার প্রিন্ট করা যাবে না, তাহলে আমরা দুটি পদ্ধতি প্রয়োগ করতে পারি। প্রথমত একটি সেট ব্যবহার করবো। প্রতিটি বিন্যাস পাওয়ার পরে সেটি সেটে আছে কী না পরীক্ষা করবো, যদি না থাকে, তাহলেই কেবল প্রিন্ট করব এবং সেটে যোগ করে নিব।

def permute3(i, n):
	if i == n:
		tpl = tuple(r)
		if tpl in s:
			return
		s.add(tpl)
		print(r)
		return
	
	for j in range(n):
		if visited[j]:
			continue
		visited[j] = True
		r[i] = a[j]
		permute3(i+1, n)
		visited[j] = False

if __name__ == "__main__":
	a = [1, 2, 3, 1]
	n = len(a)
	r = [0] * n	
	visited = [False] * n
	s = set()
	permute3(0, n)

এখন আমরা যদি সেট ব্যবহার করতে না চাই, তাহলে দ্বিতীয় প্রোগ্রামের কোড একটু পরিবর্তন করে কাজটি করা যায় –

def permute4(l, r):
	if l == r:
		print(a)
		return
	
	for i in range(l, r+1):
		if a[i] in a[l:i]:
			continue
		a[l], a[i] = a[i], a[l]
		permute4(l+1, r)
		a[l], a[i] = a[i], a[l]


if __name__ == "__main__":
	a = [1, 2, 3, 1]
	n = len(a)
	r = [0] * n	
	visited = [False] * n

ওপরের প্রোগ্রামটি কীভাবে কাজ করে, সেটি বুঝতে হলে একটু খাতাকলম নিয়ে বসতে হবে। পরিশ্রম ছাড়া এমনি এমনি প্রোগ্রামিং শেখা যায় না।

Facebook Comments

LCS-Zero – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১২

সমস্যাঃ একটা ইন্টিজারের অ্যারে দেওয়া আছে। সেখানে যদি পরপর কতগুলো সংখ্যা পাওয়া যায়, যাদের সমষ্টি শূন্য, সেই সংখ্যাগুলোর মধ্যে সবচেয়ে বেশিসংখ্যক ক্রমিক (অ্যারেতে ক্রমানুসারে সাজানো) সংখ্যাগুলো বের করতে হবে।

উদাহরণঃ 1, 2, -2, 4, -4 – এই সংখ্যাগুলোর মধ্যে, 2, -2 -এর যোগফল 0; 4, -4 – এর যোগফল 0; আবার 2, -2, 4, -4 সংখ্যাগুলোর যোগফলও 0। এখন সবচেয়ে বেশি সংখ্যক ক্রমিক সংখ্যা হচ্ছে 2, -2, 4, -4। তাই আমাদের উত্তর হবে 2, -2, 4, -4.

সমস্যাটি কেউ নিজে সমাধান করতে চাইলে এখানে চেষ্টা করতে হবে – https://www.interviewbit.com/problems/largest-continuous-sequence-zero-sum/

সমাধানঃ আমরা প্রথমে সবচেয়ে সহজ বুদ্ধি প্রয়োগ করতে পারি। অ্যারেতে যদি n সংখ্যক উপাদান থাকে, তাহলে সবগুলো উপাদানের সমষ্টি 0 কী না, সেটি পরীক্ষা করি। তারপরে n-1 সংখ্যক ক্রমিক সংখ্যার সমষ্টি 0 কী না পরীক্ষা করি। তারপর n-2 সংখ্যক ক্রমিক সংখ্যার সমষ্টি পরীক্ষা করি… এভাবে যতক্ষণ না আমরা সমষ্টি 0 পাচ্ছি, ততক্ষণ পরীক্ষা করবো আর n-এর মান এক কমাতে থাকবো 1 পর্যন্ত। যেমন, আমাদের যদি 1, 2, 3, -4, 5 – এই পাঁচটি সংখ্যা দেওয়া হয়, তাহলে প্রথমে পরীক্ষা করবো –

1 + 2 + 3 + -4 + 5 = 7

তারপরে চারটি করে ক্রমিক সংখ্যা নেব –
1 + 2 + 3 + -4 = 2
2 + 3 + -4 + 5 = 6

এবারে তিনটি করে ক্রমিক সংখ্যা –
1 + 2 + 3 = 6
2 + 3 + -4 = 1
3 + -4 + 5 = 4

এখন দুটি করে ক্রমিক সংখ্যা নেই –
1 + 2 = 3
2 + 3 = 5
3 + -4 = -1
-4 + 5 = 1

এখন একটি করে সংখ্যা নিয়ে দেখবো তাদের সমষ্টি (অর্থাৎ সেই সংখ্যাটির মান) 0 কী না। এই উদাহরণে এরকম সংখ্যা নাই।

যাই হোক, আশা করি, আমি কী করতে চাচ্ছি, তা বুঝাতে পেরেছি। এখন নিজে কোড লেখার চেষ্টা করতে হবে।

আমরা এরকম কোড লিখতে পারি –

def lszero1(A):
    n = len(A)
    
    for window_size in range(n, 0, -1):
        for start in range(0, n):
            if start+window_size > n:
                    break
            if 0 == sum(A[start:start+window_size]):
                return A[start:start+window_size]
                
    return []

এই কোডের কমপ্লেক্সিটি কত? sum() ফাংশনের কমপ্লেক্সিটি হচ্ছে O(n)। তাহলে আমাদের ফাংশনের কমপ্লেক্সিটি হবে O(n^3). প্রতিবার কিন্তু আসলে sum() ফাংশন ব্যবহার না করলেও চলে। আমরা যদি জানি, 1 + 2 + 3 = 6, তাহলে 2 + 3 + 4 হবে, আগের যোগফল থেকে 1 বিয়োগ ও 4 যোগ। বিষয়টি একটু ঠান্ডা মাথায় চিন্তা করলেই বুঝে ফেলার কথা। এই কাজটি ঠিকভাবে করতে পারলে আমরা আমাদের কোডের কমপ্লেক্সিটি O(n^2)-এ নামিয়ে আনতে পারবো।

for window_size in range(n, 0, -1):
    w_sum = sum(A[0:window_size])
    if w_sum == 0:
        return A[0:window_size]
    for start in range(1, n):
        if start + window_size > n:
            break    
        w_sum = w_sum - A[start-1] + A[start+window_size-1]
        if w_sum == 0:
            return A[start:start+window_size]                

এখন, আরো গভীরভাবে চিন্তা করলে, এই সমস্যাটির সমাধান O(n) কমপ্লেক্সিটিতেও করা সম্ভব। এবং 90% ক্ষেত্রে ইন্টারভিউয়ার হয়ত সেটিই আশা করবেন, কিংবা বলে দিবেন যে O(n) কমপ্লেক্সিটিতে সমাধান করতে। সেটি নিজে করার চেষ্টা করতে হবে। আমি কেবল একট হিন্ট দিয়ে দিচ্ছি –

A = [1, 2, -2, 4, -4], এর শুরু থেকে ক্রমিক সংখ্যাগুলোর যোগফল 1, 3 (1+2), 1 (1+2+-2), 5 , (1+2+-2+4), 1 (1+2+-2+4+-4)। এগুলো একটি অ্যারেতে রাখি –
S = [1, 3, 1, 5, 1]. এখন এই ক্ষেত্রে, প্রথম সংখ্যাটি 1, আবার পঞ্চম সংখ্যাটিও 1। অর্থাৎ প্রথম সংখ্যার পরে পরপর চারটি সংখ্যা যোগ করে যোগফলের কোনো পরিবর্তন হলো না। এতে আমরা কী বুঝলাম?

Facebook Comments

লিঙ্কড লিস্ট ১ – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১১

সমস্যাঃ একটি সিঙ্গলি লিঙ্কড লিস্ট দেওয়া আছে, যেখানে প্রতিটি নোডের ডেটা ও পরবর্তী নোডের ঠিকানা থাকবে।

class SinglyLinkedListNode:
    def __init__(self, node_data):
        self.data = node_data
        self.next = None

এখন একটি ফাংশন লিখতে হবে –

int getNode(SinglyLinkedListNode* head, int positionFromTail)

অর্থাৎ লিঙ্কড লিস্টের শুরুর নোড (হেড নোড) দেওয়া থাকবে, আর একটা সংখ্যা দেওয়া থাকবে, ওই সংখ্যার মান যত, লিঙ্কড লিস্টের শেষ থেকে ততঘর বা ততটি নোড আগে এসে যেই নোড পাওয়া যায়, তার মান রিটার্ন করতে হবে।

এটা বেশ সহজ একটি সমস্যা। ইন্টারভিউতে এই সমস্যা দিলে ইন্টারভিউয়ার আশা করবেন যে 10-12 মিনিট বা তার চেয়ে কম সময়ে এটি সমাধান করতে হবে।

কেউ সমস্যাটি সমাধান করতে চাইলে এখানে চেষ্টা করতে পারে – https://www.hackerrank.com/challenges/get-the-value-of-the-node-at-a-specific-position-from-the-tail/problem

সমাধানঃ আমরা রিকার্শন ব্যবহার করে সহজেই সমাধান করতে পারি। ইন্টারভিউতে শুরুতেই কোড লিখে ফেলা যাবে না। প্রথমে আলোচনা করে নিতে হবে যে, কাজটি কিভাবে করা হবে। যেমন, “আমি রিকার্শন ব্যবহার করে লিঙ্কড লিস্টের শেষে চলে আসবো, তারপরে শেষ থেকে শুরু করে কাউন্ট করে যাবো।”

পাইথনে রিকার্শন দিয়ে এভাবে কোড লেখা যেতে পারে –

def getNode(head, positionFromTail):
    count = 0
    value = None
    
    def traverse_ll(node):
        nonlocal count
        nonlocal value
        if node is None:
            return
        traverse_ll(node.next)
        if count == positionFromTail:
            value = node.data
        count += 1
        
    traverse_ll(head)
    
    return value

nonlocal-এর ব্যবহার লক্ষ করতে হবে। এ বিষয়ে আমি এখানে একটি আর্টিকেল লিখেছি।

এখন ইন্টারভিউয়ার বলতে পারেন, স্ট্যাক ব্যবহার করে সমস্যাটির সমাধান করতে। তখন সেভাবে করার চেষ্টা করতে হবে। তাহলে আমরা সবগুলো নোডের মান একটি স্ট্যাকে রেখে দেবো। তারপরে positionFromTail এর চেয়ে একবার বেশি স্ট্যাক থেকে পপ করবো। কোড বেশ সহজ হবে, এরকম –

def getNode(head, positionFromTail):
    value = None
    stk = []
    
    node = head
    while node:
        stk.append(node.data)
        node = node.next
        
    while positionFromTail >= 0:
        value = stk.pop()
        positionFromTail -= 1
       
    return value

আমরা তো দুটি পদ্ধতিতে সমস্যাটির সমাধান করলাম? দুটোর টাইম ও স্পেস কমপ্লেক্সিটির মধ্যে পার্থক্য কী?

 

Facebook Comments

রানিং মিডিয়ান – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১০

সমস্যাঃ একটি অ্যারেতে বা লিস্টে শুরুতে কোনো সংখ্যা নেই। অ্যারেতে ক্রমান্বয়ে n সংখ্যক সংখ্যা যুক্ত হবে, আর প্রতিটি সংখ্যা যুক্ত হওয়ার পরে ওই অ্যারের বর্তমান সংখ্যাগুলোর মিডিয়ান বের করতে হবে।

অ্যারের সংখ্যাগুলো যদি সর্ট করা হয়, তাহলে মাঝখানের সংখ্যাটি হচ্ছে মিডিয়ান। তবে অ্যারেতে যদি জোড় সংখ্যক সংখ্যা থাকে, তাহলে মাঝখানের দুটি সংখ্যার গড় হচ্ছে ওই অ্যারের মিডিয়ান।

উদাহরণঃ ধরা যাক, অ্যারেতে ক্রমান্বয়ে 1, 2, 3, 4-এই চারটি সংখ্যা যুক্ত করতে হবে। শুরুতে অ্যারেটি খালি। তারপর 1 যোগ করি, তাহলে অ্যারের অবস্থা দাঁড়াবে এমন – [1]। এখন মিডিয়ান হচ্ছে 1। তারপর 2 যোগ করি – [1, 2]। এখন মিডিয়ান হচ্ছে 1.5 ((1 + 2) / 2)। তারপর 3 যোগ করি – [1, 2, 3]। এখন মিডিয়ান হচ্ছে 2। তারপর 4 যোগ করি – [1, 2, 3, 4]। এখন মিডিয়ান হবে 2.5 (2 ও 3-এর গড়)।

সমাধানঃ সমস্যাটির সহজ একটি সমাধান হচ্ছে ইনসার্শন সর্ট (insertion sort)। আমরা প্রতিবার একটি করে সংখ্যা নিয়ে অ্যারেটি সর্ট করে ফেলবো, আর যেহেতু নতুন সংখ্যা আসার পূর্ব পর্যন্ত অ্যারেটি সর্ট করা আছে, তাই ইনসার্শন সর্ট এক্ষেত্রে একটি কার্যকর পদ্ধতি। ইন্টারভিউয়ারের সঙ্গে আলোচনা করার পরে উনি বলবেন যে, এই পদ্ধতির কমপ্লেক্সিটি কত সেটা বের করতে, কিংবা হয়ত এটি ইমপ্লিমেন্ট করতেও বলতে পারেন। এই পদ্ধতির ওয়ার্স্ট কেস টাইম কমপ্লেক্সিটি হচ্ছে O(n^2), বেস্ট কেস হচ্ছে O(n)। আর কোড করতেও 5-6 মিনিটের বেশি সময় লাগা উচিত নয়। এখন প্রশ্ন হচ্ছে, আমরা কিভাবে আরো ভালো পদ্ধতিতে সমাধান করতে পারি?

কেউ সমস্যাটি সমাধান করতে চাইলে এখানে করতে পারে – https://www.hackerrank.com/challenges/find-the-running-median/

আমরা ইতিমধ্যে যেই সমাধান প্রস্তাব করেছি, সেখানে প্রতিবার নতুন সংখ্যা যোগ হলে O(n) পরিমাণ কাজ হয়, কারণ সংখ্যাটিকে সঠিক স্থানে বসানোর জন্য বাকী সংখ্যাগুলো সরানো হয়। এই কাজটি কমাতে হবে, ইনসার্শন সর্ট ব্যবহার করা চলবে না। তাই বিভিন্ন রকম ডেটা স্ট্রাকচারের কথা চিন্তা করতে হবে।

হিপ ব্যবহার করে আমরা সমস্যাটির সমাধান করতে পারি। আমাদের সবসময় মাঝখানের সংখ্যা বা সংখ্যাদ্বয় (মোট সংখ্যা জোড় হলে)-এর হিসেব রাখতে হবে। এজন্য আমরা অ্যারের বর্তমান সংখ্যাগুলো দুইভাগে ভাগ করতে পারি – একভাগে থাকবে বর্তমান মিডিয়ানের চেয়ে ছোট সংখ্যা, আরেকভাগে থাকবে বর্তমান মিডিয়ানের চেয়ে বড় সংখ্যা। আমরা সবসময় ছোট সংখ্যার লিস্ট থেকে সবচেয়ে বড়টি, আর বড় সংখ্যার লিস্ট থেকে সবচেয়ে ছোট সংখ্যাটি পেতে চাইব। এজন্য ছোট সংখ্যাগুলো রাখতে পারি ম্যাক্স-হিপে আর বড় সংখ্যাগুলো রাখতে পারি একটি মিন-হিপে। অর্থাৎ আমাদেরকে দুটি হিপ ব্যবহার করতে হবে। আরেকটা বিষয় খেয়াল রাখতে হবে, দুটি হিপের মোট সংখ্যার পার্থক্য যেন এক-এর বেশি না হয়।

হিপ ডেটা স্ট্রাকচার নিয়ে আমি বিস্তারিত আলোচনা করেছি কম্পিউটার প্রোগ্রামিং ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি এবং পাইথন দিয়ে প্রোগ্রামিং শেখা ৩য় খণ্ড – ডেটা স্ট্রাকচার ও অ্যালগরিদম পরিচিতি বইতে। যারা হিপের সঙ্গে পরিচিত নয়, তারা ওই বইগুলো থেকে, কিংবা ডেটা স্ট্রাকচারের অন্য কোনো বই বা ইন্টারনেট ঘেঁটে শিখে নিতে পারবে।

এখন কথা হচ্ছে হিপ কি আমরা শুরু থেকে ইমপ্লিমেন্ট করবো নাকি কোনো লাইব্রেরি (পাইথনে যেমন heapq) ব্যবহার করবো? এটি ইন্টারভিউয়ারকে জিজ্ঞাসা করতে হবে। হিপ নিজে ইমপ্লিমেন্ট করার অভ্যাস থাকতে হবে কারণ অনেক ইন্টারভিউয়ার সেটাও দেখতে চাইবেন। আমি এখানে কোড লিখে রেখেছি – https://gist.github.com/tamim/4dd1e7fede8e5d76f0b4c4e397e3538c

Facebook Comments

বিটের পার্থক্যের সমষ্টি – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৯

সমস্যাঃ একটা অ্যারেতে কতগুলো অঋণাত্মক সংখ্যা আছে। ওই সংখ্যাগুলোর মাঝে যতগুলো জোড়া (pair) আছে, তাদের মধ্যে বিটের পার্থক্যের যোগফল বের করতে হবে। অর্থাৎ, কোনো একটি অ্যারেতে তিনটি সংখ্যা n1, n2, n3 থাকলে বের করতে হবে : n1 ও n2-এর মধ্যে বিটের পার্থক্য + n1 ও n3-এর মধ্যে বিটের পার্থক্য + n2 ও n3-এর মধ্যে বিটের পার্থক্য + n2 ও n1-এর মধ্যে বিটের পার্থক্য + n3 ও n1-এর মধ্যে বিটের পার্থক্য + n3 ও n2-এর মধ্যে বিটের পার্থক্য।

n1 ও n2-এর বিটের পার্থক্য হচ্ছে, সংখ্যা দুটিকে বাইনারিতে প্রকাশ করলে, যতগুলো পজিশনে তাদের বিটগুলো ভিন্ন হয়। যেমন, 7-কে বাইনারিতে প্রকাশ করলে আমরা পাই 111। আর 2-কে বাইনারিতে প্রকাশ করলে পাই 010। তাহলে 7 ও 2-এর মধ্যে প্রথম ও তৃতীয় বিট আলাদা, অর্থাৎ তাদের বিটের পার্থক্য 2।

উদাহরণঃ একটি অ্যারেতে যদি থাকে – [2, 4, 6], তাহলে তাদের সব জোড়ার বিটের পার্থক্য হবে –

f(2, 4) + f(2, 6) + 
f(4, 2) + f(4, 6) +
f(6, 2) + f(6, 4)  = 

2 + 1
2 + 1
1 + 1  = 8

সমস্যাটির সমাধান করতে হলে বিট অপারেশন সম্পর্কে পরিষ্কার ধারণা থাকতে হবে। সমস্যাটি এখানে সমাধান করে যাচাই করা যাবে – https://www.interviewbit.com/problems/sum-of-pairwise-hamming-distance/

সমাধানঃ আমরা একটি নেস্টেড লুপ ব্যবহার করে প্রতি জোড়ার মধ্যে বিটের পার্থক্য বের করতে পারি। তারপর সেগুলো যোগ করে দিতে পারি। বিটের পার্থক্য বের করার কাজটা একাধিকভাবে করা যায়, সহজ কাজ – আমি কোড লিখে দেখালাম না। এই সমাধানের কমপ্লেক্সিটি হবে O(n^2). ইন্টারভিউতে প্রশ্ন দেখেই কোড লেখা শুরু করা যাবে না। ইন্টারভিউয়ারকে বলতে হবে তুমি কোন পদ্ধতিতে সমাধান করতে চাইছ। তারপরে ইন্টারভিউয়ার যদি বলেন কোড লিখতে, তাহলে কোড লেখা শুরু করবে। নেস্টেড লুপ চালিয়ে কোড লিখলে ইন্টারভিউয়ার বলবেন এটার কমপ্লেক্সিটি বের করতে, এবং তারপর বলবেন এটাকে আরো ইফিশিয়েন্ট করতে।

সমস্যাটি O(n) কমপ্লেক্সিটিতেও সমাধান করা যায়। সেক্ষেত্রে আমাদেরকে জানতে হবে একটি সংখ্যা সর্বোচ্চ কত বিটের হবে। ইন্টারভিউয়ারকে সেটি প্রশ্ন করে জেনে নিতে হবে। ধরা যাক, সংখ্যাগুলো 32 বিটের। তখন বিটের প্রতিটি অবস্থানের জন্য (অর্থাৎ ১ম বিট, ২য় বিট, ৩য় বিট … ) কতগুলো সংখ্যায় ওই বিটে 1 আছে (একে বলা হয় সেট বিট) সেটি বের করতে হবে। ধরা যাক, এর মান হচ্ছে count। আর অ্যারেতে মোট সংখ্যা হচ্ছে nটি। তাহলে n – count সংখ্যায় ওই অবস্থানের বিটটি হচ্ছে 0। তাহলে ওই অবস্থানের জন্য বিটের মোট পার্থক্য হবে count * (n – count) * 2। দুই দিয়ে গুণ করার কারণ হচ্ছে, n1, n2 ও n2, n1 আলাদা জোড়া।

হিন্টসঃ একটি সংখ্যা n-এর i-তম (ডান দিক থেকে) বিট 1 কী না, সেটি বেরা যায় n & (1 << i) -এর মাধ্যমে।

 

Facebook Comments

১->০, ০->১ – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৮

সমস্যাঃ সম্প্রতি আমি একটা ইন্টারভিউতে এই সমস্যাটি দেখেছি – একটা ফাংশন লিখতে হবে, যেখানে ইনপুট 0 হলে আউটপুট হবে 1 আর ইনপুট 1 হলে আউটপুট হবে 0। ফাংশনটা বিভিন্নভাবে লিখতে হবে। ফাংশনের ইনপুট কেবল 0 আর 1 হবে, অন্য কোনো সংখ্যা নয়।

সমাধানঃ আমার সমাধান দেখার আগে নিজে নিজে চেষ্টা করা উচিত।

এটা আসলে ঠিক কতভাবে করা যায়, আমার জানা নেই। তবুও পাইথন ব্যবহার করে আমি বেশ কয়েকভাবে ফাংশনটি লিখতে পারি।

প্রথমে অবশ্যই if-else ব্যবহার করে –

def fnc1(n):
    if n == 1:
        return 0
    else:
        return 1

ওপরের প্রোগ্রামটা পাইথনে আরেকটু সুন্দরভাবে লেখা যায় –

def fnc2(n):
    return 0 if n == 1 else 1

এবারে কিছু গাণিতিক বুদ্ধিশুদ্ধি ব্যবহার করি –

def fnc3(n):
    return (n + 1) % 2

এবারে লিস্ট ডেটা স্ট্রাকচার ব্যবহার করি –

def fnc4(n):
    li = [1, 0]
    return li[n]

একইভাবে চাইলে টাপলও ব্যবহার করা যায়। ডিকশনারি ব্যবহার করেও করা যায় –

def fnc5(n):
    dt = {1: 0, 0: 1}
    return dt[n]

এবারে বিট লেভেলে চিন্তা করা যাক।  আমরা যদি 1 এর সঙ্গে 0-কে এক্সর (XOR) করি, তাহলে 1 পাবো, আর 1-কে এক্সর করলে 0 পাবো –

def fnc6(n):
    return 1 ^ n

আমার মাথায় এগুলোই এসেছে। আর কোনোভাবে ফাংশনটি লেখা যায়?

Facebook Comments

স্ট্রিং-এর ভেতর স্ট্রিং (সাবস্ট্রিং) – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৭

সমস্যাঃ দুটি স্ট্রিং দেওয়া আছে – A ও s. একটি ফাংশন লিখতে হবে, যার কাজ হচ্ছে, s যদি A-এর সাবস্ট্রিং হয়, তাহলে A-এর যেই ইনডেক্স থেকে s শুরু হয়েছে, সেই ইনডেক্স রিটার্ন করতে হবে। আর s যদি A-তে না থাকে, তাহলে -1 রিটার্ন করতে হবে।

সমাধানঃ প্রশ্নটা খুবই সহজ, তাই অনেকেই সরাসরি কোড লেখা শুরু করে দিবে। ইন্টারভিউতে এমন করলে কিন্তু হবে না। কারণ রিকোয়ারমেন্ট আরো পরিষ্কার করে নিতে হবে। যেমন, s যদি খালি স্ট্রিং হয়, তখন কী হবে? s যদি A-তে একাধিকবার থাকে, তখন কী হবে? – এসব প্রশ্নের উত্তর কোড লেখার আগেই জেনে নিতে হবে।

যারা পাইথন ব্যবহার করে অভ্যস্ত, তারা সহজেই কোড লিখে ফেলতে পারবে –

def string_search(A, s):
  if s in A:
    return A.index(s)
  else:
    return -1

খুবই সহজ কোড। তবে কেউ যদি বলে যে সে পাইথনে অভিজ্ঞ, তাহলে হয়ত তাকে ইন্টারভিউয়ার বলবেন যে, ফাংশনের ভেতরে এক লাইনে কোড লিখে ফেলতে। তখন কোড হবে এরকম –

def string_search(A, s):
  return A.index(s) if s in A else -1

এরপর ইন্টারভিউয়ার হয়ত বলবেন যে, index ফাংশন ব্যবহার করা যাবে না, আমি আসলে দেখতে চাইছি, আপনি এই ফাংশনটা নিজে তৈরি করতে পারেন কী না। তখন একটু চিন্তাভাবনা করে কোড লিখে ফেলতে হবে। আমার ধারণা আমার ব্লগের ৮০% পাঠকেরই এটা লিখতে দশ মিনিটের কম সময় লাগবে। আমি কোড লিখে দিচ্ছি –

if s == "" or A == "" or len(s) > len(A):
  return -1

lenA, lenS = len(A), len(s)

for i in range(lenA):
  if A[i] == s[0]:
    j, k = i, 0
    
    while j < lenA and k < lenS and A[j] == s[k]:
      j += 1
      k += 1

    if k == lenS:
      return i
    
return -1

এখন প্রশ্ন হচ্ছে এই যে কোড লিখলাম, এর টাইম কমপ্লেক্সিটি কত? আর কোনো কোনো ইন্টারভিউয়ার এটাও বলবেন যে, এখন ইউনিট টেস্ট লিখে দেখাতে হবে। আবার কেউ কেউ হয়ত শুরুতেই ইউনিট টেস্ট লিখতে বলতে পারেন। সেজন্য প্রস্তুত থাকতে হবে।

বি.দ্র. ইউনিট টেস্ট নিয়ে আমি আগে একটি আর্টিকেল লিখেছি।

নোটঃ কোনো কোনো ইন্টারভিউয়ার এই প্রশ্নের উত্তরে আরো ইফিশিয়েন্ট অ্যালগরিদম ব্যবহার করতে পরামর্শ দেবেন। সেক্ষেত্রে রবিন-কার্প স্ট্রিং ম্যাচিং, অথবা কেএমপি (নুথ-মরিস-প্র্যাট) অ্যালগরিদম ব্যবহার করতে হবে।

Facebook Comments

যোগফল শূন্য – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৬

সমস্যাঃ একটি পূর্ণসংখ্যার অ্যারেতে তিনটি করে সংখ্যা নিলে কতগুলো পৃথক ত্রয়ী পাওয়া যায়, যাদের যোগফল শূন্য (0) হবে?

যেমন, A = [-1, 0, 1, 2, -1, -4], দেওয়া থাকলে, সমাধান হচ্ছে, (-1, 0, 1) ও (-1, -1, 2). প্রতিটি ত্রয়ীর সংখ্যাগুলো ছোট থেকে বড় ক্রমে লিখতে হবে, মানে -1, 2, -1 লিখা যাবে না, বরং -1, -1, 2 লিখতে হবে।

সমাধানঃ সমস্যাটি খুব সহজেই তিনটি নেস্টেড লুপ ব্যবহার করে সমাধান করা যায়, সেক্ষেত্রে সমাধানের কমপ্লেক্সিট হয় O(n^3). ইন্টারভিউতে এই সমস্যা দিলে প্রথমেই এই কোড লেখা যাব না, বরং ইন্টারভিউয়ারকে জিজ্ঞাসা করতে হবে এবং আমার দৃঢ় বিশ্বাস, ইন্টারভিউয়ার এই সমাধানের কোড লিখে সময় নষ্ট করতে উৎসাহিত করবেন না, বরং কমপ্লেক্সিটি আরো কমাতে বলবেন।

আমরা যদি অ্যারেটি শুরুতেই সর্ট করে নিই, তাহলে সবচেয়ে ভেতরের লুপের বদলে বাইনারি সার্চ ব্যবহার করা যায়, এবং সেক্ষেত্রে কমপ্লেক্সিটি হয়, O(n^2 log n), যা O(n^3)-এর চেয়ে ভালো। কিন্তু সমস্যাটি O(n^2) কমপ্লেক্সিটিতেই সমাধান করা সম্ভব। আমি প্রথমেই বলব, পাঠককে একটু নিজে চেষ্টা করার জন্য। নিজে চেষ্টা করে নিচের যেকোনো একটি লিঙ্কে সমাধান করে যাচাই করা যাবে –
https://www.interviewbit.com/problems/3-sum-zero/
https://leetcode.com/problems/3sum/description/

আমি একটি নমুনা ইনপুট ও আউটপুট দিয়ে দিচ্ছি –

ইনপুট – A = [ 1, -4, 0, 0, 5, -5, 1, 0, -2, 4, -4, 1, -1, -4, 3, 4, -1, -1, -3]

আউটপুট – [[-5, 0, 5], [-5, 1, 4], [-4, -1, 5], [-4, 0, 4], [-4, 1, 3], [-3, -2, 5], [-3, -1, 4], [-3, 0, 3], [-2, -1, 3], [-2, 1, 1], [-1, 0, 1], [0, 0, 0]]

সমস্যাটি আমি আজকে সন্ধ্যায় সমাধান করেছি (আমি পাইথন ব্যবহার করেছি), কিন্তু পুরো সমাধান লিখে দিয়ে পাঠককে প্রোগ্রামিংয়ের আনন্দ থেকে বঞ্চিত করতে চাইছি না।

উল্লেখ্য যে, এই প্রশ্নটি গুগল ও ফেসবুকের ইন্টারভিউতে ইতিপূর্বে জিজ্ঞাসা করা হয়েছে।

Facebook Comments