[Powered by Google Translate] [సెమినార్: సాంకేతిక ఇంటర్వ్యూ]
[కెన్నీ యు, హార్వర్డ్ విశ్వవిద్యాలయం]
[ఈ CS50 ఉంది.] [CS50.TV]
హాయ్ అందరూ, నేను కెన్నీ ఉన్నాను. నేను ప్రస్తుతం ఒక జూనియర్ అధ్యయనం చేసే కంప్యూటర్ సైన్స్ am.
నేను ఒక మాజీ CS TF ఉన్నాను, నేను ఒక underclassman ఉన్నప్పుడు నేను ఈ కలిగి అనుకుంటున్నారా
నేను ఈ సదస్సు ఇచ్చి నేను ఎందుకు మరియు ఆ.
నేను మీరు ఆస్వాదిస్తారని భావిస్తున్నాము.
ఈ సదస్సు, సాంకేతిక ఇంటర్వ్యూ గురించి
మరియు నా వనరులు, ఈ లింక్ లో చూడవచ్చు
ఇక్కడే ఈ లింక్ వనరులు జంట.
నేను చాలా కొన్ని సమస్యలు, వాస్తవానికి, సమస్యల యొక్క జాబితా తయారు.
మేము చిట్కాలు వెదుక్కోవచ్చు ఇక్కడ కూడా ఒక సాధారణ వనరులు పేజీ
ఒక ఇంటర్వ్యూలో కోసం సిద్ధం ఎలా,
మీరు ఒక వాస్తవిక ఇంటర్వ్యూలో ఏమి చెయ్యాలి చిట్కాలు,
అలాగే భవిష్యత్ సూచన కోసం సమస్యలు మరియు వనరులను చేరుకోవటానికి ఎలా.
అన్ని ఆన్లైన్ యొక్క.
మరియు ఈ సదస్సు, ఒక డిస్క్లైమర్ ముందుమాటలో
ఈ చేయను - మీ ఇంటర్వ్యూలో తయారీ
ఈ జాబితా పరిమితం కాకుండా ఉండాలి.
ఈ మాత్రమే, ఒక గైడ్ అని అర్థం
మరియు మీరు ఖచ్చితంగా, నేను ఉప్పు ఒక ధాన్యంతో చెప్పే ప్రతీదీ తీసుకోవాలి
కానీ నేను మీ ఇంటర్వ్యూలో తయారీలో మీరు సహాయపడే ప్రతిదీ ఉపయోగిస్తారు.
>> నేను తరువాత కొన్ని స్లయిడ్లను ద్వారా వేగవంతం వెళుతున్న
కాబట్టి మేము అసలు కేస్ స్టడీస్ పొందవచ్చు.
ఒక సాఫ్ట్వేర్ ఇంజినీరింగ్ postion ఒక ఇంటర్వ్యూలో యొక్క నిర్మాణం,
సాధారణంగా 30 నుంచి 45 నిముషాలు,
సంస్థ మీద ఆధారపడి అనేక రౌండ్లు,.
తరచుగా మీరు ఒక వైట్ బోర్డ్ మీద కోడింగ్ వస్తారు.
కాబట్టి ఈ వంటి, కానీ తరచుగా చిన్న పరిమాణంలో తెల్ల బోర్డు.
మీరు ఒక ఫోన్ ఇంటర్వ్యూలో ఉన్నట్లయితే, మీరు బహుశా ఉపయోగించి వస్తుంది
collabedit లేదా Google పత్రాన్ని గాని తద్వారా మీరు కోడింగ్ జీవించాలని చూడగలరు
మీరు ఫోన్ ద్వారా బీయింగ్ ఇంటర్వ్యూడ్ చేస్తున్న సమయంలో.
ఒక ఇంటర్వ్యూలో కూడా సాధారణంగా 2 లేదా 3 సమస్యలు ఉంది
మీ కంప్యూటర్ సైన్స్ జ్ఞానం పరీక్ష.
మరియు అది దాదాపు ఖచ్చితంగా కోడింగ్ కలిగి ఉంటుంది.
మీరు చూస్తారు ఆ రకాల ప్రశ్నలు సాధారణంగా డేటా నిర్మాణాలు మరియు అల్గోరిథంలు.
మరియు సమస్యలను ఈ రకాల చేయడం,
నచ్చిన, మీరు అడుగుతాము, ఏ సమయంలో మరియు అంతరిక్ష సంక్లిష్టత, పెద్ద O ఉంది?
తరచుగా వారు కూడా అధిక స్థాయి ప్రశ్నలు అడగండి
కాబట్టి, ఒక వ్యవస్థ రూపకల్పన
ఎలా మీరు మీ కోడ్ బద్ధం చేస్తుంది?
ఏ ఇంటర్ఫేస్లు, ఏ తరగతులు, మీరు మీ కంప్యూటరు లో ఏం మాడ్యూళ్ళను ఉన్నాయి,
మరియు ఈ ఎలా కలిసి సంకర్షణ చెయ్యాలి?
కాబట్టి డేటా నిర్మాణాలు మరియు క్రమసూత్ర పద్ధతులు మరియు రూపకల్పన వ్యవస్థలు.
>> మేము మా కేస్ స్టడీస్ కు ఈత కొట్టడానికి ముందు కొన్ని సాధారణ చిట్కాలు.
నేను చాలా ముఖ్యమైన నియమం ఎల్లప్పుడూ బిగ్గరగా ఆలోచిస్తూ ఉంటుంది అనుకుంటాను.
ఇంటర్వ్యూ మీ ఆలోచన ప్రక్రియ ఆఫ్ చూపించడానికి ఇది ఒక అవకాశం భావించబడేది.
ఇంటర్వ్యూయర్ కొలవడానికి ఇంటర్వ్యూ యొక్క స్థానం
ఎలా మీరు భావించే మరియు ఎలా మీరు ఒక సమస్య ద్వారా వెళ్లండి.
మీరు చేయవచ్చు నీచమైన మొత్తం ఇంటర్వ్యూ అంతటా ఉంటుంది ఇవ్వలేదు.
అది ఏ బావుంటుంది.
మీరు ఒక ప్రశ్న ఇచ్చిన తర్వాత, మీరు కూడా మీరు ప్రశ్న అర్థం నిర్ధారించుకోవాలి.
మీ స్వంత మాటల్లో తిరిగి ప్రశ్న పునరావృతం
మరియు ప్రయత్నం పరిపూర్ణమైన కొన్ని సులభమైన పరీక్ష కేసులు పని
మీరు ప్రశ్న అర్థం నిర్థారించడానికి.
కొన్ని పరీక్ష కేసులు ద్వారా వర్కింగ్ కూడా మీరు ఈ సమస్యను పరిష్కరించడానికి ఎలా ఒక ఊహ ఇస్తుంది.
మీరు కూడా కొన్ని నమూనాలు మీరు సమస్యను పరిష్కరించడానికి సహాయం కనుగొనడంలో ఉండవచ్చు.
వారి పెద్ద చిట్కా విసుగు పెట్టలేదు ఉంది.
విసుగు పొందలేము.
ఇంటర్వ్యూ సవాలు, కానీ మీరు చేయవచ్చు నీచమైన,
నిశ్శబ్ద కాకుండా, కనిపించే విసుగు ఉంటుంది.
మీరు ఒక ఇంటర్వ్యూయర్ ఆ అభిప్రాయాన్ని ఇవ్వాలని లేదు.
ఒక విషయం మీకు - కాబట్టి, చాలా మంది ప్రజలు, వారు ఒక ఇంటర్వ్యూలో లోకి వెళ్ళినప్పుడు,
వారు, మొదటి ఉత్తమ పరిష్కారం కనుగొనేందుకు ప్రయత్నించండి ప్రయత్నం
ఉన్నప్పుడు నిజంగా, ఒక స్పష్టముగా స్పష్టమైన పరిష్కారం సాధారణంగా ఉంది.
ఇది నెమ్మదిగా ఉంటుంది, అది అసమర్థంగా కావచ్చు, కాని మీరు దాన్ని చెబుతూ ఉండాలి
అందువల్ల మీరు మంచి పని నుండి ప్రారంభ బిందువు కలిగి ఉంటుంది.
అలాగే, పరిష్కారం పై పరంగా, నెమ్మదిగా
పెద్ద O సమయం సంక్లిష్టత లేదా ఖాళీ సంక్లిష్టత,
మీరు అర్థం ఆ ఇంటర్వ్యూ కు ప్రదర్శిస్తారు
ఈ సమస్యలను కోడ్ రాసేటప్పుడు.
కాబట్టి మొదటి సాధారణ అల్గోరిథం పైకి రావటానికి బయపడకండి
తరువాత అక్కడి నుండి పని చేస్తాయి.
ఏదైనా ప్రశ్నలు ఇప్పటివరకు? సరే.
>> కాబట్టి లెట్స్ మా మొదటి సమస్య ప్రవేశిస్తాడు.
"N పూర్ణాంకాల యొక్క వ్యూహం కారణంగా, అర్రే shuffles ఒక చర్యను వ్రాయండి
n పూర్ణాంకాల అన్ని ప్రస్తారణల సమానంగా అవకాశం అలాంటి స్థానంలో. "
మరియు మీరు అందుబాటులో యాదృచ్చిక పూర్ణాంక జనరేటర్ కలిగి ఊహించుకోవటం
సగానికి శ్రేణి, 0 నుండి నేను ఒక పరిధిలో పూర్ణాంకం సృష్టిస్తుంది.
ప్రతి ఒక్కరూ ఈ ప్రశ్న అర్థం ఉందా?
నేను మీరు n పూర్ణాంకాల యొక్క వ్యూహం ఇవ్వండి, నేను మీరు షఫుల్ అది మీరు.
నా డైరెక్టరీ లో నేను వాట్ ఐ మీన్ ప్రదర్శించేందుకు కొన్ని కార్యక్రమాలు రాశారు.
నేను, షఫుల్ 20 మూలకాల యొక్క ఒక అమరిక వెళుతున్న
-10 నుండి +9 కు,
మరియు నేను మీరు ఈ జాబితా అవుట్పుట్ మీరు.
కాబట్టి ఈ నా క్రమబద్ధీకరించబడతాయి ఇన్పుట్ శ్రేణి, మరియు నేను మీరు షఫుల్ అది మీరు.
మేము దీన్ని మళ్లీ చేస్తాను.
ప్రతి ఒక్కరూ ప్రశ్న అర్థం ఉందా? సరే.
కాబట్టి అది మీ ఇష్టం.
కొన్ని ఆలోచనలు ఏమిటి? మీరు n ^ 2, n లాగ్ n, n గా చేయవచ్చు?
సూచనలు ఆహ్వానిస్తుంది.
సరే. ఎమ్మి సూచించారు కాబట్టి ఒక ఆలోచన,
మొదటి 0 నుండి 20 వరకు యాదృచ్చిక సంఖ్య, పూర్ణాంకం యాదృచ్ఛిక, ఒక పరిధిలో గణించడం ఉంది.
మా శ్రేణి 20 యొక్క పొడవు భావిస్తాయి.
20 అంశాల మా రేఖాచిత్రంలో,
ఈ మా ఇన్పుట్ శ్రేణి.
ఇప్పుడు, ఆమె సలహా, ఒక కొత్త శ్రేణి సృష్టించడానికి ఉంది
ఈ ఉత్పత్తి శ్రేణి ఉంటుంది.
నేను RAND ద్వారా తిరిగి ఆధారంగా -
నేను కనుక, 17, యొక్క అని పిలవబడు
మొదటి స్థానం లోకి 17 వ మూలకం కాపీ.
ఇప్పుడు మేము తొలగించాలి - మేము ఇక్కడ అన్ని అంశాలను బదిలీ అవసరం
ఆ విధముగా మేము చివరిలో ఖాళీ మరియు మధ్య ఏ రంధ్రాలు ఉంటాయి.
ఇప్పుడు మేము విధానాన్ని పునరుక్తి.
ఇప్పుడు మేము 0 మరియు 19 మధ్య ఒక కొత్త యాదృచ్ఛిక పూర్ణాంక ఎంచుకోండి.
మేము ఇక్కడ ఒక కొత్త హావ్, మరియు మేము ఈ స్థానాన్ని ఈ మూలకం కాపీ.
అప్పుడు మేము పైగా అంశాలను బదిలీ మరియు మేము మా పూర్తి కొత్త శ్రేణిని కలిగి వరకు మేము విధానాన్ని పునరుక్తి.
ఈ అల్గోరిథం యొక్క రన్ టైం అంటే ఏమిటి?
సరే, ఈ ప్రభావం పరిగణలోకి తెలియజేయండి.
మేము ప్రతి మూలకం బదిలీ చేస్తారు.
మేము ఈ i తొలగించడానికి, మేము ఎడమ దానిని తర్వాత అన్ని అంశాలను బదిలీ చేస్తారు.
మరియు ఒక O (n) ఖర్చు
ఎందుకంటే మనం మొదటి మూలకం తీసివేస్తే?
కాబట్టి ప్రతి తొలగింపు కోసం, మేము తొలగించు -
ప్రతి తొలగింపు, ఒక O (n) ఆపరేషన్ కలిగితే
మేము తొలగింపులు n నుంచి మరియు, ఈ ఒక O (n ^ 2) షఫుల్ దారితీస్తుంది.
సరే. సో గుడ్ ప్రారంభం. మంచి ప్రారంభం.
>> మరో సలహా, క్నుత్ షఫుల్ అని పిలుస్తారు ఏదో ఉపయోగిస్తారు
లేదా FISHER-యేట్స్ షఫుల్.
మరియు అది నిజానికి ఒక సరళ సమయం షఫుల్ ఉంది.
మరియు ఆలోచన చాలా పోలి ఉంటుంది.
మళ్లీ, మేము, మా ఇన్పుట్ శ్రేణి కలిగి
కానీ బదులుగా మా ఇన్పుట్ / అవుట్పుట్ కోసం రెండు శ్రేణుల ఉపయోగించి యొక్క,
మేము, మా దిగి భాగాన్ని ట్రాక్ శ్రేణి యొక్క మొదటి భాగం ఉపయోగించడానికి
మరియు మేము ట్రాక్, మరియు అప్పుడు మేము unshuffled భాగం కోసం మా శ్రేణి యొక్క మిగిలిన వదిలి.
ఇక్కడ నా ఉద్దేశ్యం ఏమిటి. మేము తో మొదలు - మేము ఒక నేను ఎంపిక,
0 నుండి 20 వరకు వ్యూహం.
మా ప్రస్తుత పాయింటర్ మొదటి ఇండెక్స్ కు సూచిస్తుంది.
మేము కొన్ని నేను ఇక్కడ ఎంచుకోండి
మరియు ఇప్పుడు మేము స్వాప్.
, ఈ 5 మరియు ఈ 4 కాబట్టి ఉంటే
ఫలితంగా శ్రేణి ఇక్కడ 5 ఇక్కడ మరియు 4 ఉంటుంది.
ఇప్పుడు మేము ఇక్కడ ఒక మార్కర్ గమనించండి.
ఎడమ ప్రతిదీ, దిగి ఉంది
మరియు కుడివైపున ప్రతిదీ unshuffled ఉంది.
ఇప్పుడు మేము ప్రక్రియ తిరిగి చేయవచ్చు.
మేము ఇప్పుడు 1 మరియు 20 మధ్య ఒక యాదృచ్ఛిక సూచిక ఎంచుకోండి.
నేను ఇక్కడ మా కొత్త అనుకుందాం.
ఇప్పుడు మేము ఇక్కడ మా ప్రస్తుత కొత్త స్థానం ఈ i స్వాప్.
కాబట్టి మేము ఈ వంటి ముందుకు వెనుకకు ఇచ్చిపుచ్చుకోవడంతో లేదు.
నాకు మరింత కాంక్రీటును తయారు చేసేందుకు కోడ్ తీసుకురావటానికి లెట్.
మేము నాకు మా ఎంపిక ప్రారంభం -
నేను 0 సమానం తో మేము ప్రారంభం, మనం ఒక యాదృచ్చిక నగర j ఎంచుకోండి
యెరే యొక్క unshuffled భాగంలో, నేను n-1 కు.
నేను ఇక్కడ ఉన్నాను చేస్తే, ఇక్కడ మరియు యెరే యొక్క మిగిలిన మధ్య ఒక యాదృచ్ఛిక సూచిక ఎంచుకోండి
మరియు మేము స్వాప్.
ఈ షఫుల్ మీ శ్రేణి అవసరమైన అన్ని స్మృతి.
ఏదైనా ప్రశ్నలు?
>> వెల్, ఒక ప్రశ్న అవసరం, ఎందుకు ఈ సరైన ఉంది?
ఎందుకు ప్రతి ప్రస్తారణను సమానంగా అవకాశం ఉంది?
నేను, ఈ నిరూపణ ద్వారా కాదు
కానీ కంప్యూటర్ సైన్స్ లో అనేక సమస్యలు ప్రేరణ ద్వారా నిరూపించబడింది.
ఎలా మీరు చాలా ప్రేరణ తెలిసిన?
సరే. కూల్.
కాబట్టి మీరు, సాధారణ ప్రేరణ ద్వారా ఈ అల్గోరిథం యొక్క సరి నిరూపించవచ్చు
మీ ప్రేరణ పరికల్పన ఉంటుంది, అక్కడ భావిస్తాయి
నా షఫుల్ ప్రతి ప్రస్తారణను సమానంగా అవకాశం తిరిగి
మొదటి నేను అంశాలను.
ఇప్పుడు నేను + 1 భావిస్తారు.
మరియు మేము మా ఇండెక్స్ j స్వాప్ ఎంచుకోవచ్చు ద్వారా,
, మరియు తర్వాత మీరు వివరాలను పని - ఈ దారితీస్తుంది
ఈ అల్గోరిథం తిరిగి ఎందుకు కనీసం ఒక పూర్తి రుజువు
సమానంగా అవకాశం సంభావ్యత ప్రతి ప్రస్తారణను.
>> All right, తర్వాత సమస్య.
కాబట్టి ", ప్రతికూల, సున్నా, అనుకూల పూర్ణాంకాల యొక్క వ్యూహం, ఇచ్చిన
గరిష్ట మొత్తం లెక్క ప్రకారం ఒక ఫంక్షన్ వ్రాయండి
ఇన్పుట్ శ్రేణి ఏ continueous subarray యొక్క. "
ఇక్కడ ఒక ఉదాహరణ, అన్ని సంఖ్యలు అనుకూలంగా ఉంటాయి సందర్భంలో, ఉంది
అప్పుడు ప్రస్తుతం ఉత్తమ ఎంపిక వ్యూహరచనలు పొందాలి.
1, 2, 3, 4, 10 సమానం.
మీరు అక్కడ కొన్ని ప్రతికూలతలు ఉన్నప్పుడు,
ఈ సందర్భంలో మనం కేవలం మొదటి రెండు కావలసిన
-1 మరియు / లేదా -3 ఎంచుకోవడం మా మొత్తం దించాలని ఉంటుంది.
కొన్నిసార్లు మేము శ్రేణి మధ్యలో ప్రారంభం ఉంటుంది.
కొన్నిసార్లు మేము అన్ని వద్ద ఏమీ ఎంచుకోవాలనుకుంటే ఇది ఏదీ తీసుకోదు చేయడం ఉత్తమం.
కొన్నిసార్లు, పతనం తీసుకోవాలని ఉత్తమం
అది తర్వాత విషయం సూపర్ పెద్ద ఎందుకంటే. ఏ ఆలోచనలు కాబట్టి?
(విద్యార్థి, అపారదర్శక) >> అవును.
నేను -1 తీసుకోకపోతే అనుకుందాం.
అప్పుడు గాని నేను 1,000 మరియు 20,000, ఎంచుకోండి
లేదా నేను 3 బిలియన్ ఎంచుకోండి.
Well, ఉత్తమ ఎంపిక అన్ని సంఖ్యలు పొందాలి.
ఈ -1, ప్రతికూల ఉన్నప్పటికీ,
మొత్తం మొత్తం నేను -1 తీసుకోకూడదని కంటే మరింత ఉత్తమంగా ఉంది.
నేను ఇదివరకు చెప్పిన చిట్కాలు ఒకటి స్పష్టంగా స్పష్టమైన రాష్ట్రానికి ఉంది
మొదటి మరియు బ్రూట్ ఫోర్స్ పరిష్కారం.
ఈ సమస్య లో బ్రూట్ ఫోర్స్ పరిష్కారం ఏమిటి? Yeah?
[జేన్] నేను బ్రూట్ ఫోర్స్ పరిష్కారం అనుకుంటున్నాను
అన్ని సాధ్యమైన కలయికల (అపారదర్శక) అప్ జోడించడానికి ఉంటుంది.
[యు] సరే. కాబట్టి జానే ఆలోచన ప్రతి సాధ్యం పొందాలి -
నేను paraphrasing ఉన్నాను - ప్రతి సాధ్యం నిరంతర subarray పొందాలి,
దాని మొత్తం గణించడం, మరియు అప్పుడు ఉన్న అన్ని నిరంతర subarrays గరిష్ట పడుతుంది.
ప్రత్యేకంగా నా ఇన్పుట్ శ్రేణిలో subarray గుర్తిస్తుంది?
ఏమి రెండు విషయాలు అవసరం, ఇలా? Yeah?
(విద్యార్థి, అపారదర్శక) >> కుడి.
తక్కువ ఇండెక్స్ మరియు ఒక ఉన్నత బౌండ్ ఇండెక్స్ లో కట్టుబడి
ప్రత్యేకంగా ఒక నిరంతర subarray నిర్ణయిస్తుంది.
[అవివాహిత విద్యార్థి] మేము ఇది ఏకైక సంఖ్యల వ్యూహం యొక్క అంచనా ఆర్?
[యు] నం ఆమె ప్రశ్న కాబట్టి, మేము మా శ్రేణి ఊహిస్తూ ఉంటాయి -
మా శ్రేణి అన్ని ఏకైక సంఖ్యలు, మరియు సమాధానం లేదు ఉంది.
>> మేము అప్పుడు మా బ్రూట్ ఫోర్స్ పరిష్కారం, ప్రారంభ / ముగింపు సూచీలు ఉపయోగిస్తే
ప్రత్యేకంగా మా నిరంతర subarray నిర్ణయిస్తుంది.
మేము అన్ని సాధ్యం ప్రారంభం ఎంట్రీలకు iterate అయితే,
మరియు అన్ని ముగింపు ఎంట్రీలకు> లేదా =, ప్రారంభం, మరియు <n కు
మీరు మొత్తం గణించడం, మరియు అప్పుడు మేము ఇప్పటివరకు చూసిన గరిష్ట మొత్తం పడుతుంది.
ఈ స్పష్టం?
ఈ పరిష్కారం యొక్క పెద్ద O ఏమిటి?
Timewise.
చాలా ^ 2 n Not.
, మేము 0 నుండి N వరకు iterate గమనించండి
కాబట్టి లూప్ ఒకటి.
మేము లూప్, దాదాపు ప్రారంభం నుండి చివరి వరకు మరొక iterate.
ఇప్పుడు, ఆ లోపల, మేము ప్రతి ఎంట్రీ అప్ సంకలనం కలిగి
కాబట్టి లూప్ ఇంకొక. కాబట్టి మేము మూడు ఉచ్చులు కోసం సమూహం, n ^ 3 ఉంటాయి.
సరే. ఈ ప్రారంభ బిందువుగా వెళుతుంది.
మా పరిష్కారం n ^ 3 కంటే దారుణంగా ఉంది.
ప్రతి ఒక్కరూ బ్రూట్ ఫోర్స్ పరిష్కారం అర్థం ఉందా?
>> సరే. ఉత్తమ పరిష్కారం డైనమిక్ ప్రోగ్రామింగ్ అని ఒక ఆలోచన ఉపయోగిస్తోంది.
మీరు CS124 తీసుకోకపోతే, ఇది ఆల్గోరిథమ్స్ మరియు డేటా స్ట్రక్చర్స్ ఉంది
మీరు ఈ టెక్నిక్ తో బాగా తెలిసిన అవుతుంది.
మరియు ఆలోచన, మొదటి చిన్న సమస్యలకు పరిష్కారాలను నిర్మించటానికి ప్రయత్నించండి.
ప్రారంభ మరియు ముగింపు: ఈ ద్వారా వాట్ ఐ మీన్, మేము ప్రస్తుతం రెండు విషయాల గురించి ఆందోళన.
మరియు ఆ బాధించే ఉంది. మేము ఆ పారామితులు ఒకటి వదిలించుకోవటం కాలేదు ఏమి?
మేము మా అసలు సమస్య ఇచ్చిన, - ఒక ఆలోచన ఉంది
ఒక పరిధిలో ఏ subarray గరిష్ట మొత్తం [O, n-1] చూడండి.
ఇప్పుడు మేము, మా ప్రస్తుత సూచిక నేను, మేము తెలిసిన ఒక కొత్త subproblem కలిగి
మేము అక్కడ ముగించారు ఉండాలి తెలుసు. మా subarray ప్రస్తుత సూచిక వద్ద ముగుస్తాయి.
మిగిలిన సమస్య కాబట్టి, అక్కడ మా subarray ప్రారంభం కావాలి?
ఈ కోణంలో రాబడుతుంది? సరే.
నేను ఈ అప్ కోడ్ చేసిన, మరియు దీని అర్థం చూద్దాం యొక్క.
Codirectory లో subarray అని పిలిచే ఒక కార్యక్రమం ఉంది
మరియు ఇది అంశాల సంఖ్య పడుతుంది
మరియు అది నా దిగి జాబితాలో గరిష్ట subarray మొత్తం తిరిగి.
కాబట్టి ఈ సందర్భంలో, మా గరిష్ట subarray 3.
మరియు కేవలం 2 మరియు 1 ఉపయోగించి తీసుకువెళ్లారు.
యొక్క మళ్లీ అమలు లెట్. ఇది 3 యొక్క.
కానీ ఈ సమయంలో, మేము 3 ఎలా గమనించండి.
మేము పట్టింది - మేము 3 స్వయంగా పడుతుంది
ఇది రెండు వైపులా ప్రతికూలతలు చుట్టూ ఎందుకంటే,
మొత్తానికి <3 తెచ్చే.
యొక్క 10 అంశాలను అమలు లెట్.
ఇది 7 యొక్క ఈ సమయం, మేము ప్రధాన 3 మరియు 4 పడుతుంది.
ఈ సమయంలో అది 8, మరియు మేము 1, 4 మరియు 3 తీసుకొని ఆ పొందటానికి.
కాబట్టి మీరు ఎలా ఒక ఊహ ఇవ్వాలని మేము ఈ రూపాంతరం సమస్య పరిష్కరించగల,
యొక్క ఈ subarray పరిశీలించి అనుమతిస్తుంది.
మేము ఈ ఇన్పుట్ శ్రేణి ఇచ్చిన, మరియు మేము సమాధానం 8 తెలుసు చేస్తున్నారు.
మేము 1, 4, 3 మరియు పడుతుంది.
కానీ యొక్క మేము నిజంగా ఆ సమాధానం ఎలా చూద్దాం.
యొక్క ఈ సూచికలకు ప్రతి వద్ద ముగిసింది గరిష్ట subarray చూద్దాం.
మొదటి స్థానం వద్ద ముగిసింది కలిగి గరిష్ట subarray ఏమిటి?
[స్టూడెంట్] జీరో. >> జీరో. జస్ట్ -5 తీసుకోరు.
ఇక్కడ అది 0 చేస్తాడు. Yeah?
(విద్యార్థి, అర్ధం కాని)
[యు] ఓహ్, క్షమించండి, -3 ఉంది.
ఈ ఒక 2 కాబట్టి, ఈ ఒక -3 ఉంది.
సరే. కాబట్టి -4, ఆ స్థానం ముగించడానికి గరిష్ట subarray ఏది
-4 లో ఎప్పుడు? జీరో.
ఒక? 1, 5, 8.
ఇప్పుడు నేను -2 వద్ద ఉన్న నగర వద్ద ముగుస్తాయి.
కాబట్టి 6, 5, 7, మరియు చివరి 4 ఉంటుంది.
ఈ నా ప్రవేశాలు తెలుసుకొని
నేను ఈ సూచికలకు ప్రతి వద్ద ముగుస్తాయి పేరు రూపాంతరం సమస్య కోసం,
నా చివరి సమాధానం ఉంది, అంతటా స్వీప్ పడుతుంది
మరియు గరిష్ట సంఖ్య పడుతుంది.
కాబట్టి ఈ విషయంలో అది 8 ఉంది.
ఇది గరిష్ట subarray ఈ ఇండెక్స్ వద్ద ముగుస్తుంది సూచిస్తుంది
మరియు అది ముందు ఎక్కడో ప్రారంభించారు.
ప్రతి ఒక్కరూ ఈ రూపాంతరం subarray అర్థం ఉందా?
>> సరే. సరే, ఈ కోసం పునరుక్తి గుర్తించడానికి అనుమతిస్తాయి.
యొక్క కేవలం మొదటి కొన్ని ఎంట్రీలను పరిగణలోకి లెట్.
ఇక్కడ అది, 8 0, 0, 0, 1, 5 ఉంది.
మరియు తరువాత ఇక్కడ ఒక -2 ఉంది, మరియు ఆ 6 దానిని తగ్గిపోయాయి.
నేను స్థానంలో ఎంట్రీ కాల్ అయితే నేను subproblem (i),
ఎలా మునుపటి subproblem సమాధానం ఉపయోగించవచ్చు
ఈ subproblem సమాధానం?
నేను విషయంలో చూస్తే, ఈ ఎంట్రీ, సే తెలియజేయండి.
నేను చూడటం ద్వారా సమాధానం 6 గణించాలి
ఈ శ్రేణి మరియు ఈ శ్రేణి గత ఉప సమస్యలను సమాధానాలు కలయిక? అవును?
[అవివాహిత విద్యార్థి] మీరు మొత్తాలను యొక్క శ్రేణి పడుతుంది
స్థానం లో కుడి అది ముందు, 8 కాబట్టి
మరియు తర్వాత మీరు ప్రస్తుత subproblem జోడించండి.
[యు], ఆమె సలహా ఈ రెండు సంఖ్యలను కు ఉంది కాబట్టి
ఈ సంఖ్య మరియు ఈ సంఖ్య.
కాబట్టి ఈ 8 subproblem కోసం సమాధానం (- 1 i) సూచిస్తుంది.
మరియు నా ఇన్పుట్ శ్రేణి A. కాల్ తెలియజేయండి
స్థానం i వద్ద ముగుస్తుంది ఒక గరిష్ట subarray కనుగొనేందుకు చేయడానికి,
నేను రెండు ఎంపికలు ఉన్నాయి: నేను గాని subarray కొనసాగించవచ్చు
ఆ మునుపటి సూచిక వద్ద ముగిసింది, లేదా ఒక కొత్త శ్రేణి ప్రారంభించండి.
నేను గత సూచిక వద్ద ప్రారంభించారు subarray కొనసాగించదలిస్తే
అప్పుడు నేను సాధించింది గరిష్ట మొత్తం మునుపటి subproblem సమాధానం ఉంది
ప్లస్ ప్రస్తుత శ్రేణి ఎంట్రీ.
కానీ, నేను కూడా, ఒక కొత్త subarray మొదలు ఎంపిక
ఈ సందర్భంలో మొత్తం 0.
1, ప్లస్ ప్రస్తుత శ్రేణి ఎంట్రీ - కాబట్టి సమాధానం 0 యొక్క మాక్స్, subproblem ఐ.
ఈ పునరుక్తి సమంజసం లేదు?
మా పునరుక్తి, మేము కనుగొనగా, subproblem ఐ
గత subproblem గరిష్ట ప్లస్ నా ప్రస్తుత శ్రేణి ఎంట్రీ సమానంగా ఉంటుంది
ఇది గత subarray కొనసాగుతుంది అర్థం
లేదా 0, నా ప్రస్తుత సూచిక ఒక కొత్త subarray ప్రారంభించండి.
మరియు ఒకసారి మేము మా చివరి సమాధానం అప్పటి, పరిష్కారాలను ఈ పట్టికలో పైకి నిర్మించారు,
కేవలం subproblem శ్రేణి అంతటా సరళ స్వీప్ చేయండి
మరియు గరిష్ట సంఖ్య పడుతుంది.
ఈ నేను మాట్లాడుతూ యొక్క ఒక ఖచ్చితమైన అమలు ఉంది.
కాబట్టి మేము ఒక కొత్త subproblem అర్రే, ఉప సమస్యలను సృష్టించవచ్చు.
మొదటి ఎంట్రీ 0 లేదా మొదటి ఎంట్రీ, ఆ రెండు గరిష్ట ఉంటుంది.
మరియు ఉప సమస్యలను మిగిలిన
మేము కేవలం కనుగొన్నారు ఖచ్చితమైన పునరుక్తి ఉపయోగించండి.
ఇప్పుడు మేము మా ఉపసమస్యలను శ్రేణి యొక్క గరిష్ట గణించడం, మరియు మా చివరి సమాధానం ఉంది.
>> కాబట్టి ఎంత ఖాళీ మేము ఈ అల్గోరిథం లో ఉపయోగిస్తున్నారు?
మీరు మాత్రమే CS50 తీసుకున్నారు, అప్పుడు మీరు చాలా స్పేస్ చర్చించారు ఉండకపోవచ్చు.
Well, గమనించదగ్గ ఒక మాట పరిమాణం n ఇక్కడ malloc అనే ఉంది.
మీరు ఏమి సూచిస్తున్నాయి లేదు?
ఈ అల్గోరిథం సరళ ప్రదేశాన్ని ఉపయోగించుకుంటుంది.
మేము బాగా చేయగలరని?
మీరు తుది సమాధానం గణించడం అనవసరమైన ఉంది అని గుర్తించలేకపోతే ఆ ఏదైనా ఉందా?
నేను ఊహిస్తున్నాను మరింత మంచి ప్రశ్న, ఏ సమాచారం
మేము చివరి వరకు అన్ని మార్గం కలిగి లేదు?
ఇప్పుడు మేము ఈ రెండు పంక్తులు చూస్తే,
మేము మాత్రమే గత subproblem శ్రద్ధ
మరియు మేము మాత్రమే మనం ఇప్పటివరకు చూసిన గరిష్ట పట్టించుకోనట్లు.
మా చివరి సమాధానం లెక్కించడానికి, మేము మొత్త అవసరం లేదు.
మేము గత సంఖ్య గత రెండు సంఖ్యలు మాత్రమే అవసరం.
గరిష్టంగా subproblem శ్రేణి, మరియు గత సంఖ్య చివరి సంఖ్య.
కాబట్టి, నిజానికి, మేము కలిసి ఈ వలయాలు కరుగుతాయి
మరియు సరళ స్పేస్ నుండి స్థిరమైన స్పేస్ వెళ్ళండి.
ప్రస్తుత మొత్తం ఇప్పటివరకు, ఇక్కడ, subproblem, మా subproblem శ్రేణి యొక్క పాత్ర తొలగించబడుతాయి.
కాబట్టి ప్రస్తుత మొత్తం ఇప్పటివరకు మునుపటి subproblem సమాధానం ఉంది.
ఈ మొత్తం ఇప్పటివరకు మా మాక్స్ యొక్క జరుగుతుంది.
మేము సహకరించు వంటి మేము గరిష్ట గణించడం.
కాబట్టి మేము, స్థిరమైన స్పేస్ సరళ స్పేస్ నుంచి
మరియు మేము కూడా మా subarray సమస్యకు పరిష్కారం సరళ ఉన్నాయి.
>> ప్రశ్నలు ఈ రకాల మీరు ఇచ్చిన ఇంటర్వ్యూలో పొందుతారు.
సమయం సంక్లిష్టత ఏమిటి; స్పేస్ సంక్లిష్టత ఏమిటి?
మీరు బాగా చేయగలరని? చుట్టూ ఉంచడానికి అనవసరమైన అంశాలు ఉన్నాయి?
నేను మీరు మీ సొంత తీసుకోమని విశ్లేషణలు హైలైట్ ఈ చేశాడు
మీరు ఈ సమస్యలపై పని చేస్తున్నపుడు.
ఎల్లప్పుడూ "నేను బాగా చేయగలరని?", మీరే అడుగుతూ కూడా
నిజానికి, మేము ఈ కంటే మెరుగైన చేయగలరు?
ఒక ట్రిక్ ప్రశ్న అబ్బాయి. మీరు అవసరం ఎందుకంటే మీరు, కాదు
కనీసం సమస్య ఇన్పుట్ చదవండి.
మీరు అవసరం వాస్తవం కనీసం సమస్య ఇన్పుట్ చదవండి కాబట్టి
మీరు, సరళ సమయం కంటే బాగా అర్థం ఏమిటంటే
మరియు మీరు స్థిరమైన ప్రదేశం కంటే బాగా లేదు.
కాబట్టి ఇది నిజానికి, ఈ సమస్య ఉత్తమ పరిష్కారం.
ప్రశ్నలు? సరే.
>> స్టాక్ మార్కెట్ సమస్య:
"అనుకూల, సున్నా, లేదా ప్రతికూల n పూర్ణ, ఒక వరుస కారణంగా,
ఆ, n రోజులలో స్టాక్ ధర ప్రాతినిధ్యం
మీరు చేయవచ్చు గరిష్ట లాభం లెక్కించడానికి ఒక ఫంక్షన్ వ్రాయండి
మీరు ఈ n రోజుల్లో ఖచ్చితంగా 1 స్టాక్ కొనుగోలు మరియు విక్రయించే ఇచ్చిన. "
ముఖ్యంగా, మేము, తక్కువ కొనుగోలు అధిక విక్రయించదలిచాను.
మరియు మేము చేయవచ్చు ఉత్తమ లాభం గుర్తించడానికి కావలసిన.
నా చిట్కా కు వెళుతున్నారు, ఏ వెంటనే స్పష్టమైన, సరళమైన సమాధానం, కానీ నెమ్మదిగా ఉంది?
అవును? (విద్యార్థి, అపారదర్శక) >> అవును.
>> కాబట్టి మీరు అయితే వెళ్ళి స్టాక్ ధరలు పరిశీలిస్తాడు
సమయం లో ప్రతి పాయింట్, (అపారదర్శక).
[యు] సరే, తన పరిష్కారం - కంప్యూటింగ్ ఆమె సలహా
అత్యల్ప మరియు అత్యధిక కంప్యూటింగ్ తప్పనిసరిగా పని లేదు
అత్యధిక అత్యల్ప ముందే కాబట్టి.
కాబట్టి ఈ సమస్యకు బ్రూట్ ఫోర్స్ పరిష్కారం ఏమిటి?
నేను ప్రత్యేకంగా నేను తయారు లాభం గుర్తించేందుకు అవసరమైన రెండు విషయాలు ఏమిటి? కుడి.
బ్రూట్ ఫోర్స్ పరిష్కారం - OH, కాబట్టి, జార్జ్ యొక్క సలహా మేము కేవలం రెండు రోజులు అవసరం
ప్రత్యేకంగా ఆ రెండు రోజులు లాభం గుర్తించడానికి.
కాబట్టి మేము, కొనుగోలు / అమ్మే ఇష్టం, ప్రతి జంట గణించడం
ప్రతికూల లేదా అనుకూల లేదా సున్నా చేసే ఆ లాభం, గణించడం.
మేము రోజుల అన్ని జతల పై iterating తర్వాత చేసే గరిష్ట లాభం కంప్యూట్.
మా చివరి సమాధానం ఉంటుంది.
ఆ పరిష్కారం ఉంది ఎందుకంటే, O (n ^ 2) ఉంటుంది n రెండు జతల ఎన్నుకుంటుంది -
మీరు ముగింపు రోజులు ఎంపిక చేసే రోజులు.
సరే, నేను ఇక్కడ బ్రూట్ ఫోర్స్ పరిష్కారం వెళ్ళి వెళుతున్న కాదు.
నేను ఒక n లాగ్ n పరిష్కారం అక్కడ మీరు చెప్పండి వెళుతున్న.
మీరు ప్రస్తుతం n లాగ్ n అని అంటే అల్గోరిథం తెలుసు?
ఇది ఒక ట్రిక్ ప్రశ్న కాదు.
>> క్రమీకరించు విలీనం. విలీనం విధమైన, n లాగ్ n ఉంది
నిజానికి, ఈ సమస్య పరిష్కరించేందుకు ఒక మార్గం ఉపయోగిస్తారు
అని ఆలోచన యొక్క ఒక విలీనంతో విధమైన రకం సాధారణంగా, విభజించి జయించటానికి.
మరియు ఈ విధంగా ఆలోచన.
మీరు బెస్ట్ బై గణించడం / ఎడమ భాగంలో జత విక్రయించదలిచాను.
మీరు రెండు రోజుల పాటు మొదటి n తో, చేయవచ్చు ఉత్తమ లాభం కనుగొనండి.
అప్పుడు మీరు, బెస్ట్ బై oompute / కుడి అర్ధభాగంలో జత విక్రయించదలిచాను
రెండు రోజుల పాటు గత n.
ఇప్పుడు ప్రశ్న ఎలా మేము తిరిగి కలిసి ఈ పరిష్కారాలను విలీనం లేదు, ఉంది?
అవును? (విద్యార్థి, అర్ధం కాని)
సరే >>. నాలో ఒక చిత్రాన్ని డ్రా తెలియజేయండి.
అవును? (జార్జ్, అర్ధం కాని)
ఖచ్చితంగా >>. జార్జ్ యొక్క పరిష్కారం సరిగ్గా హక్కు.
తన సలహా కాబట్టి, మొదటి, బెస్ట్ బై / అమ్మకపు జత గణించడం
మరియు ఎడమ భాగంలో సంభవిస్తుంది, అందుచే యొక్క ఎడమ, ఎడమ ఆ కాల్ తెలియజేయండి.
ఉత్తమ కుడి భాగంలో సంభవించే జత కొనుగోలు / అమ్మే.
మేము మాత్రమే ఈ రెండు సంఖ్యలను పోల్చి అయితే, మేము కేసు లేదు చేస్తున్నారు
మేము ఇక్కడ కొనుగోలు మరియు కుడి భాగంలో ఎక్కడో అమ్మే పేరు.
మేము ఎడమ భాగంలో కొనుగోలు, కుడి భాగంలో అమ్మే.
మరియు రెండు భాగాలుగా ఈజిప్టు బెస్ట్ బై / అమ్మకపు జత గణించడం ఉత్తమ మార్గం
ఇక్కడ కనీస గణించడం మరియు ఇక్కడ గరిష్ట లెక్కించడానికి ఉంది
మరియు వారి తేడా పడుతుంది.
కొనుగోలు / అమ్మకపు జంట మాత్రమే ఇక్కడ సంభవించే రెండు కేసులు కాబట్టి,
మాత్రమే ఇక్కడ, లేదా రెండూ విభజించటం ఈ మూడు సంఖ్యలు నిర్వచించబడింది.
, తిరిగి కలిసి మా SOLUTIONS విలీనం మా అల్గోరిథం కాబట్టి
మేము బెస్ట్ బై / అమ్మకపు జత గణించడం మీరు
మేము ఎడమ అర్ధభాగంలో కొనుగోలు మరియు కుడి సగం లో అమ్ముటకు పేరు.
మరియు ఆ విధంగా చేయడానికి ఉత్తమ మార్గం, మొదటి సగం లో అత్యల్ప ధర లెక్కించడానికి ఉంది
అత్యధిక కుడి భాగంలో ధర, మరియు వారి తేడా పడుతుంది.
ఫలితంగా మూడు లాభాలు, ఈ మూడు సంఖ్యలు, మీరు, మూడు గరిష్ట పడుతుంది
మరియు మీరు ఈ మొదటి మరియు చివరి రోజులలో చేయవచ్చు ఉత్తమ లాభం ఉంది.
ఇక్కడ ముఖ్యమైన పంక్తులు Red లో ఉన్నాయి.
ఈ ఎడమ భాగంలో సమాధానం లెక్కించడానికి ఒక పునరావృత కాల్ ఉంది.
ఈ కుడి భాగంలో సమాధానం లెక్కించడానికి ఒక పునరావృత కాల్ ఉంది.
ఈ రెండు వలయాలు కోసం వరుసగా ఎడమ మరియు కుడి అర్ధభాగంలో min మరియు మాక్స్ గణించడం.
ఇప్పుడు నేను రెండు భాగాలుగా ఈజిప్టు లాభం గణించడం
మరియు చివరి సమాధానం ఈ మూడు గరిష్ట ఉంది.
సరే.
>> కాబట్టి, ఖచ్చితంగా, మేము ఒక అల్గోరిథం ఉన్నాయి, కాని పెద్ద ప్రశ్న
ఈ సమయం సంక్లిష్టత ఏమిటి?
నేను విలీనంతో విధమైన పేర్కొన్నారు కారణం ఈ రూపం సమాధానం విభజించి ఉంది
రెండు మరియు తర్వాత తిరిగి కలిసి మా SOLUTIONS విలీనం
సరిగ్గా విలీనంతో విధమైన రూపం.
కాబట్టి నాకు వ్యవధి వీలు.
మేము దశలను సంఖ్య ఒక ఫంక్షన్ t (n) నిర్వచించిన ఉంటే
n రోజులు,
మా రెండు పునరావృత కాల్స్
ప్రతి t (n / 2), ఖర్చు వెళ్తున్నారు
మరియు ఈ కాల్స్ రెండు ఉంది.
ఇప్పుడు నేను, ఎడమ భాగంలో కనీసం గణించడం అవసరం
నేను n / 2 సమయం, ప్లస్ కుడి సగం గరిష్ట లో చేయవచ్చు, ఇది.
కాబట్టి ఇది n.
మరియు తర్వాత కొన్ని స్థిరమైన పని ప్లస్.
మరియు ఈ పునరుక్తి సమీకరణం
సరిగ్గా విలీనంతో విధమైన కోసం పునరుక్తి సమీకరణం ఉంది.
మరియు మేము అన్ని విలీనంతో విధమైన n లాగ్ n సమయం అని తెలుసు.
అందువలన, మా అల్గోరిథం కూడా లాగ్ n సమయం n.
ఈ పునరుక్తి సమంజసం లేదు?
ఈ యొక్క ఒక సంక్షిప్త రీక్యాప్:
T (n) గరిష్ట లాభం లెక్కించడానికి దశలను సంఖ్య
n రోజుల వ్యవధిలో.
మేము మా పునరావృత కాల్స్ విడిపోయారు మార్గం
, మొదటి n / 2 రోజులు మా పరిష్కారం కాల్ ఉంది
కాబట్టి ఒక కాల్, యొక్క
మరియు తర్వాత మేము రెండవ సగం మళ్లీ కాల్.
కాబట్టి ఆ రెండు కాల్స్ ఉంది.
మరియు తర్వాత మేము, మేము సరళ సమయంలో చేయవచ్చు, ఇది ఎడమ అర్ధభాగంలో కనీసం కనుగొనడానికి
మేము సరళ సమయంలో చేయవచ్చు ఇది కుడి అర్థ గరిష్ట, కనుగొనండి.
కాబట్టి n / 2 + n / 2 కేవలం n.
అప్పుడు మేము అంకగణితం చేయడం వంటి ఇది కొన్ని స్థిరమైన పని కలిగి.
ఈ పునరావృత సమీకరణం సరిగ్గా విలీనంతో విధమైన కోసం పునరుక్తి సమీకరణం ఉంది.
అందువలన, మా షఫుల్ అల్గోరిథం కూడా n n లాగిన్ అవ్వండి.
కాబట్టి ఎంత ఖాళీ మేము ఉపయోగిస్తున్న?
యొక్క కోడ్ తిరిగి వెళ్ళి తెలపండి.
>> ఒక మంచి ప్రశ్న, ఎన్ని స్టాక్ ఫ్రేములు మనం ఏదైనా సందర్భంలో ఎందుకు చెయ్యాలి ఉంది?
మేము సూత్రం ఉపయోగించి ఉన్నందున,
స్టాక్ ఫ్రేమ్ల సంఖ్య మా స్పేస్ వాడుక నిర్ణయిస్తుంది.
యొక్క n = 8 పరిగణలోకి లెట్.
మేము, 8 న షఫుల్ కాల్
మొదటి నాలుగు ఎంట్రీలు షఫుల్ కాల్ చేస్తుంది,
ఇది మొదటి రెండు ఎంట్రీలు ఒక షఫుల్ కాల్ చేస్తుంది.
మా స్టాక్ ఉంది - ఈ మా స్టాక్ ఉంది.
మరియు తర్వాత మేము, 1 న మళ్లీ షఫుల్ కాల్
మరియు ఆ యొక్క మా బేస్ కేసు ఏమిటి, కాబట్టి మేము వెంటనే తిరిగి.
మనం ఈ అనేక స్టాక్ ఫ్రేముల కన్నా మరింత ఉందా?
నం మేము ఒక ఆవాహన చేయండి ప్రతిసారీ ఎందుకంటే,
షఫుల్ ఒక పునరావృత ఆవాహన,
మేము సగం లో మా పరిమాణం తిరగడానికి.
మనం ఏదైనా సందర్భంలో కలిగి స్టాక్ ఫ్రేములు గరిష్ట సంఖ్య కాబట్టి
లాగ్ n స్టాక్ ఫ్రేములు యొక్క ఆర్డర్ మీద ఉంది.
ప్రతి స్టాక్ ఫ్రేమ్, స్థిరమైన స్థలాన్ని
స్థలం మరియు అందువలన మొత్తం,
మనం ఉపయోగించే స్థలం యొక్క గరిష్ట మొత్తాన్ని O (n లాగ్) స్థలం
పేరు n రోజుల సంఖ్య.
>> ఇప్పుడు, ఎప్పుడూ మిమ్మల్ని మీరే ప్రశ్నించుకోండి, "మేము బాగా చేయగలరని?"
మరియు ముఖ్యంగా, మేము ఇప్పటికే పరిష్కరించవచ్చు చేసిన ఒక సమస్య ఈ తగ్గిస్తుంది?
ఒక సూచన: మేము ఈ ముందు రెండు ఇతర సమస్యలు చర్చించారు, మరియు అది షఫుల్ అని మాత్రం కాదు.
మేము గరిష్ట subarray సమస్య ఈ స్టాక్ మార్కెట్ సమస్య మార్చవచ్చు.
దీన్ని మేము ఎలా చేయగలరు?
మీరు ఒకటి? ఎమ్మి?
(ఎమ్మి, అర్ధం కాని)
[యు] ఖచ్చితంగా.
గరిష్ట subarray సమస్య కాబట్టి,
మేము నిరంతరం subarray పైగా మొత్తానికి ఉన్నాము.
మరియు స్టాక్స్ సమస్య ఎమ్మీ యొక్క సలహా,
మార్పులు, లేదా డెల్టాలు భావిస్తారు.
మరియు ఈ చిత్రాన్ని ఉంది - ఈ ఒక స్టాక్ ధర,
కానీ మేము ప్రతి వరుస రోజు మధ్య వ్యత్యాసం చేపడితే -
కాబట్టి మేము గరిష్ట ధర, గరిష్ట లాభం మేము అని చూడండి
మేము ఇక్కడ కొనుగోలు మరియు అమ్మకం ఇక్కడ ఉంటుంది.
కానీ యొక్క నిరంతర చూద్దాం - యొక్క subarray సమస్య చూద్దాం.
ఇక్కడ, మేము చేయవచ్చు - ఇక్కడ నుండి ఇక్కడ వెళ్ళి,
మేము ఒక మంచి మార్పు ఉండదు, మరియు ఇక్కడ ఇక్కడ నుండి వెళ్లి మేము ప్రతికూల మార్పు ఉండదు.
కానీ, మేము ఒక పెద్ద అనుకూలమైన మార్పును కలిగి ఇక్కడ నుండి ఇక్కడ వెళ్ళడం జరుగుతుంది.
మరియు ఈ మేము మా చివరి లాభం పొందడానికి సైన్ అప్ సంకలనం చేయదలిచిన మార్పులు.
అప్పుడు మేము మరింత ప్రతికూల మార్పులు ఇక్కడ ఉన్నాయి.
మా గరిష్ట subarray సమస్య లోకి మా స్టాక్ సమస్య తగ్గించటం కీ
రోజుల మధ్య డెల్టాలు పరిగణిస్తారు.
కాబట్టి మేము, డెల్టాలు అనే కొత్త శ్రేణి సృష్టించడానికి
, 0 గా మొదటి ఎంట్రీ ప్రారంభించడం
ఆపై ప్రతి డెల్టా కోసం (i), తేడా ఆ తెలియజేయండి
నా ఇన్పుట్ శ్రేణి (i), మరియు శ్రేణి (i - 1).
అప్పుడు మేము ఒక గరిష్ట subarray కోసం మా నియమిత ప్రక్రియగా కాల్
ఒక డెల్టా యొక్క శ్రేణి అక్కడ.
మరియు గరిష్ట subarray సరళ సమయం, ఎందుకంటే
మరియు ఈ తగ్గింపు, ఈ డెల్టా శ్రేణి సృష్టించే ఈ ప్రక్రియ,
, కూడా సరళ సమయం
అప్పుడు నిల్వల కోసం చివరి పరిష్కారం O (n) పని ప్లస్ O (n) రచన, ఇప్పటికీ O (n) రచన.
కాబట్టి మేము మా సమస్యకు ఒక దీర్ఘ సమయం పరిష్కారం ఉంది.
ప్రతి ఒక్కరూ ఈ పరివర్తన అర్థం ఉందా?
>> మీరు ఎల్లప్పుడూ ఉండాలని ఆయన సాధారణంగా, ఒక మంచి ఆలోచన
మీరు చూడటానికి ఒక కొత్త సమస్య తగ్గించడానికి ప్రయత్నించండి.
అది ఒక పాత సమస్య తెలిసిన కనిపిస్తోంది ఉంటే,
పాత సమస్య మార్చడం ద్వారా ప్రయత్నించండి.
మరియు మీరు పాత సమస్య ఉపయోగించే చేసిన అన్ని టూల్స్ ఉపయోగించవచ్చు ఉంటే
కొత్త సమస్యను పరిష్కరించడానికి.
కాబట్టి మూసివేయాలని, సాంకేతిక ఇంటర్వ్యూ సవాలు చేస్తారు.
ఈ సమస్యలు బహుశా మరింత క్లిష్టమైన సమస్యలను కొన్ని
మీరు, ఒక ఇంటర్వ్యూలో చూడవచ్చు ఆ
మీరు నేను కవర్ అన్ని సమస్యలను అర్థం లేదు కాబట్టి, అది సరైందే.
ఇవి సవాలు సమస్యలు ఉన్నాయి.
ప్రాక్టీస్, ప్రాక్టీస్, ప్రాక్టీస్.
నేను హాండ్ ఔట్ లో చాలా సమస్యలను ఇచ్చింది, కాబట్టి ఖచ్చితంగా ఆ తనిఖీ.
మరియు మీ ఇంటర్వ్యూ న అదృష్టం. నా వనరులు, ఈ లింక్ వద్ద పోస్ట్
మరియు నా సీనియర్ ఫ్రెండ్స్ ఒకటి, మాక్ సాంకేతిక ముఖాముఖిలు చేయడానికి అందించింది
మీకు ఆసక్తి అయితే, ఇమెయిల్ ఆ ఇమెయిల్ చిరునామాకు యావో విల్.
మీరు కొన్ని ప్రశ్నలు ఉంటే, మీరు నన్ను అడగవచ్చు.
మీరు అబ్బాయిలు సాంకేతిక ఇంటర్వ్యూ సంబంధించిన నిర్దిష్ట ప్రశ్నలు ఉందా
లేదా మేము ఇప్పటివరకు చూసిన ఏ సమస్యలు?
సరే. Well, మీ ఇంటర్వ్యూ న అదృష్టం.
[CS50.TV]