1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [సెమినార్: సాంకేతిక ఇంటర్వ్యూ]

2
00:00:02,640 --> 00:00:04,630
[కెన్నీ యు, హార్వర్డ్ విశ్వవిద్యాలయం]

3
00:00:04,630 --> 00:00:08,910
[ఈ CS50 ఉంది.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
హాయ్ అందరూ, నేను కెన్నీ ఉన్నాను. నేను ప్రస్తుతం ఒక జూనియర్ అధ్యయనం చేసే కంప్యూటర్ సైన్స్ am.

5
00:00:12,420 --> 00:00:17,310
నేను ఒక మాజీ CS TF ఉన్నాను, నేను ఒక underclassman ఉన్నప్పుడు నేను ఈ కలిగి అనుకుంటున్నారా

6
00:00:17,310 --> 00:00:19,380
నేను ఈ సదస్సు ఇచ్చి నేను ఎందుకు మరియు ఆ.

7
00:00:19,380 --> 00:00:21,370
నేను మీరు ఆస్వాదిస్తారని భావిస్తున్నాము.

8
00:00:21,370 --> 00:00:23,470
ఈ సదస్సు, సాంకేతిక ఇంటర్వ్యూ గురించి

9
00:00:23,470 --> 00:00:26,650
మరియు నా వనరులు, ఈ లింక్ లో చూడవచ్చు

10
00:00:26,650 --> 00:00:32,350
ఇక్కడే ఈ లింక్ వనరులు జంట.

11
00:00:32,350 --> 00:00:36,550
నేను చాలా కొన్ని సమస్యలు, వాస్తవానికి, సమస్యల యొక్క జాబితా తయారు.

12
00:00:36,550 --> 00:00:40,800
మేము చిట్కాలు వెదుక్కోవచ్చు ఇక్కడ కూడా ఒక సాధారణ వనరులు పేజీ

13
00:00:40,800 --> 00:00:42,870
ఒక ఇంటర్వ్యూలో కోసం సిద్ధం ఎలా,

14
00:00:42,870 --> 00:00:46,470
మీరు ఒక వాస్తవిక ఇంటర్వ్యూలో ఏమి చెయ్యాలి చిట్కాలు,

15
00:00:46,470 --> 00:00:51,910
అలాగే భవిష్యత్ సూచన కోసం సమస్యలు మరియు వనరులను చేరుకోవటానికి ఎలా.

16
00:00:51,910 --> 00:00:53,980
అన్ని ఆన్లైన్ యొక్క.

17
00:00:53,980 --> 00:00:58,290
మరియు ఈ సదస్సు, ఒక డిస్క్లైమర్ ముందుమాటలో

18
00:00:58,290 --> 00:01:00,690
ఈ చేయను - మీ ఇంటర్వ్యూలో తయారీ

19
00:01:00,690 --> 00:01:02,800
ఈ జాబితా పరిమితం కాకుండా ఉండాలి.

20
00:01:02,800 --> 00:01:04,750
ఈ మాత్రమే, ఒక గైడ్ అని అర్థం

21
00:01:04,750 --> 00:01:08,890
మరియు మీరు ఖచ్చితంగా, నేను ఉప్పు ఒక ధాన్యంతో చెప్పే ప్రతీదీ తీసుకోవాలి

22
00:01:08,890 --> 00:01:14,620
కానీ నేను మీ ఇంటర్వ్యూలో తయారీలో మీరు సహాయపడే ప్రతిదీ ఉపయోగిస్తారు.

23
00:01:14,620 --> 00:01:16,400
>> నేను తరువాత కొన్ని స్లయిడ్లను ద్వారా వేగవంతం వెళుతున్న

24
00:01:16,400 --> 00:01:18,650
కాబట్టి మేము అసలు కేస్ స్టడీస్ పొందవచ్చు.

25
00:01:18,650 --> 00:01:23,630
ఒక సాఫ్ట్వేర్ ఇంజినీరింగ్ postion ఒక ఇంటర్వ్యూలో యొక్క నిర్మాణం,

26
00:01:23,630 --> 00:01:26,320
సాధారణంగా 30 నుంచి 45 నిముషాలు,

27
00:01:26,320 --> 00:01:29,810
సంస్థ మీద ఆధారపడి అనేక రౌండ్లు,.

28
00:01:29,810 --> 00:01:33,090
తరచుగా మీరు ఒక వైట్ బోర్డ్ మీద కోడింగ్ వస్తారు.

29
00:01:33,090 --> 00:01:35,960
కాబట్టి ఈ వంటి, కానీ తరచుగా చిన్న పరిమాణంలో తెల్ల బోర్డు.

30
00:01:35,960 --> 00:01:38,540
మీరు ఒక ఫోన్ ఇంటర్వ్యూలో ఉన్నట్లయితే, మీరు బహుశా ఉపయోగించి వస్తుంది

31
00:01:38,540 --> 00:01:44,030
collabedit లేదా Google పత్రాన్ని గాని తద్వారా మీరు కోడింగ్ జీవించాలని చూడగలరు

32
00:01:44,030 --> 00:01:46,500
మీరు ఫోన్ ద్వారా బీయింగ్ ఇంటర్వ్యూడ్ చేస్తున్న సమయంలో.

33
00:01:46,500 --> 00:01:48,490
ఒక ఇంటర్వ్యూలో కూడా సాధారణంగా 2 లేదా 3 సమస్యలు ఉంది

34
00:01:48,490 --> 00:01:50,620
మీ కంప్యూటర్ సైన్స్ జ్ఞానం పరీక్ష.

35
00:01:50,620 --> 00:01:54,490
మరియు అది దాదాపు ఖచ్చితంగా కోడింగ్ కలిగి ఉంటుంది.

36
00:01:54,490 --> 00:01:59,540
మీరు చూస్తారు ఆ రకాల ప్రశ్నలు సాధారణంగా డేటా నిర్మాణాలు మరియు అల్గోరిథంలు.

37
00:01:59,540 --> 00:02:02,210
మరియు సమస్యలను ఈ రకాల చేయడం,

38
00:02:02,210 --> 00:02:07,830
నచ్చిన, మీరు అడుగుతాము, ఏ సమయంలో మరియు అంతరిక్ష సంక్లిష్టత, పెద్ద O ఉంది?

39
00:02:07,830 --> 00:02:09,800
తరచుగా వారు కూడా అధిక స్థాయి ప్రశ్నలు అడగండి

40
00:02:09,800 --> 00:02:12,530
కాబట్టి, ఒక వ్యవస్థ రూపకల్పన

41
00:02:12,530 --> 00:02:14,770
ఎలా మీరు మీ కోడ్ బద్ధం చేస్తుంది?

42
00:02:14,770 --> 00:02:18,370
ఏ ఇంటర్ఫేస్లు, ఏ తరగతులు, మీరు మీ కంప్యూటరు లో ఏం మాడ్యూళ్ళను ఉన్నాయి,

43
00:02:18,370 --> 00:02:20,900
మరియు ఈ ఎలా కలిసి సంకర్షణ చెయ్యాలి?

44
00:02:20,900 --> 00:02:26,130
కాబట్టి డేటా నిర్మాణాలు మరియు క్రమసూత్ర పద్ధతులు మరియు రూపకల్పన వ్యవస్థలు.

45
00:02:26,130 --> 00:02:29,180
>> మేము మా కేస్ స్టడీస్ కు ఈత కొట్టడానికి ముందు కొన్ని సాధారణ చిట్కాలు.

46
00:02:29,180 --> 00:02:32,300
నేను చాలా ముఖ్యమైన నియమం ఎల్లప్పుడూ బిగ్గరగా ఆలోచిస్తూ ఉంటుంది అనుకుంటాను.

47
00:02:32,300 --> 00:02:36,980
ఇంటర్వ్యూ మీ ఆలోచన ప్రక్రియ ఆఫ్ చూపించడానికి ఇది ఒక అవకాశం భావించబడేది.

48
00:02:36,980 --> 00:02:39,820
ఇంటర్వ్యూయర్ కొలవడానికి ఇంటర్వ్యూ యొక్క స్థానం

49
00:02:39,820 --> 00:02:42,660
ఎలా మీరు భావించే మరియు ఎలా మీరు ఒక సమస్య ద్వారా వెళ్లండి.

50
00:02:42,660 --> 00:02:45,210
మీరు చేయవచ్చు నీచమైన మొత్తం ఇంటర్వ్యూ అంతటా ఉంటుంది ఇవ్వలేదు.

51
00:02:45,210 --> 00:02:50,090
అది ఏ బావుంటుంది.

52
00:02:50,090 --> 00:02:53,230
మీరు ఒక ప్రశ్న ఇచ్చిన తర్వాత, మీరు కూడా మీరు ప్రశ్న అర్థం నిర్ధారించుకోవాలి.

53
00:02:53,230 --> 00:02:55,350
మీ స్వంత మాటల్లో తిరిగి ప్రశ్న పునరావృతం

54
00:02:55,350 --> 00:02:58,920
మరియు ప్రయత్నం పరిపూర్ణమైన కొన్ని సులభమైన పరీక్ష కేసులు పని

55
00:02:58,920 --> 00:03:01,530
మీరు ప్రశ్న అర్థం నిర్థారించడానికి.

56
00:03:01,530 --> 00:03:05,510
కొన్ని పరీక్ష కేసులు ద్వారా వర్కింగ్ కూడా మీరు ఈ సమస్యను పరిష్కరించడానికి ఎలా ఒక ఊహ ఇస్తుంది.

57
00:03:05,510 --> 00:03:11,210
మీరు కూడా కొన్ని నమూనాలు మీరు సమస్యను పరిష్కరించడానికి సహాయం కనుగొనడంలో ఉండవచ్చు.

58
00:03:11,210 --> 00:03:14,500
వారి పెద్ద చిట్కా విసుగు పెట్టలేదు ఉంది.

59
00:03:14,500 --> 00:03:17,060
విసుగు పొందలేము.

60
00:03:17,060 --> 00:03:19,060
ఇంటర్వ్యూ సవాలు, కానీ మీరు చేయవచ్చు నీచమైన,

61
00:03:19,060 --> 00:03:23,330
నిశ్శబ్ద కాకుండా, కనిపించే విసుగు ఉంటుంది.

62
00:03:23,330 --> 00:03:27,410
మీరు ఒక ఇంటర్వ్యూయర్ ఆ అభిప్రాయాన్ని ఇవ్వాలని లేదు.

63
00:03:27,410 --> 00:03:33,960
ఒక విషయం మీకు - కాబట్టి, చాలా మంది ప్రజలు, వారు ఒక ఇంటర్వ్యూలో లోకి వెళ్ళినప్పుడు,

64
00:03:33,960 --> 00:03:37,150
వారు, మొదటి ఉత్తమ పరిష్కారం కనుగొనేందుకు ప్రయత్నించండి ప్రయత్నం

65
00:03:37,150 --> 00:03:39,950
ఉన్నప్పుడు నిజంగా, ఒక స్పష్టముగా స్పష్టమైన పరిష్కారం సాధారణంగా ఉంది.

66
00:03:39,950 --> 00:03:43,500
ఇది నెమ్మదిగా ఉంటుంది, అది అసమర్థంగా కావచ్చు, కాని మీరు దాన్ని చెబుతూ ఉండాలి

67
00:03:43,500 --> 00:03:46,210
అందువల్ల మీరు మంచి పని నుండి ప్రారంభ బిందువు కలిగి ఉంటుంది.

68
00:03:46,210 --> 00:03:48,270
అలాగే, పరిష్కారం పై పరంగా, నెమ్మదిగా

69
00:03:48,270 --> 00:03:52,160
పెద్ద O సమయం సంక్లిష్టత లేదా ఖాళీ సంక్లిష్టత,

70
00:03:52,160 --> 00:03:54,450
మీరు అర్థం ఆ ఇంటర్వ్యూ కు ప్రదర్శిస్తారు

71
00:03:54,450 --> 00:03:57,510
ఈ సమస్యలను కోడ్ రాసేటప్పుడు.

72
00:03:57,510 --> 00:04:01,440
కాబట్టి మొదటి సాధారణ అల్గోరిథం పైకి రావటానికి బయపడకండి

73
00:04:01,440 --> 00:04:04,950
తరువాత అక్కడి నుండి పని చేస్తాయి.

74
00:04:04,950 --> 00:04:09,810
ఏదైనా ప్రశ్నలు ఇప్పటివరకు? సరే.

75
00:04:09,810 --> 00:04:11,650
>> కాబట్టి లెట్స్ మా మొదటి సమస్య ప్రవేశిస్తాడు.

76
00:04:11,650 --> 00:04:14,790
"N పూర్ణాంకాల యొక్క వ్యూహం కారణంగా, అర్రే shuffles ఒక చర్యను వ్రాయండి

77
00:04:14,790 --> 00:04:20,209
n పూర్ణాంకాల అన్ని ప్రస్తారణల సమానంగా అవకాశం అలాంటి స్థానంలో. "

78
00:04:20,209 --> 00:04:23,470
మరియు మీరు అందుబాటులో యాదృచ్చిక పూర్ణాంక జనరేటర్ కలిగి ఊహించుకోవటం

79
00:04:23,470 --> 00:04:30,980
సగానికి శ్రేణి, 0 నుండి నేను ఒక పరిధిలో పూర్ణాంకం సృష్టిస్తుంది.

80
00:04:30,980 --> 00:04:32,970
ప్రతి ఒక్కరూ ఈ ప్రశ్న అర్థం ఉందా?

81
00:04:32,970 --> 00:04:39,660
నేను మీరు n పూర్ణాంకాల యొక్క వ్యూహం ఇవ్వండి, నేను మీరు షఫుల్ అది మీరు.

82
00:04:39,660 --> 00:04:46,050
నా డైరెక్టరీ లో నేను వాట్ ఐ మీన్ ప్రదర్శించేందుకు కొన్ని కార్యక్రమాలు రాశారు.

83
00:04:46,050 --> 00:04:48,910
నేను, షఫుల్ 20 మూలకాల యొక్క ఒక అమరిక వెళుతున్న

84
00:04:48,910 --> 00:04:52,490
-10 నుండి +9 కు,

85
00:04:52,490 --> 00:04:57,050
మరియు నేను మీరు ఈ జాబితా అవుట్పుట్ మీరు.

86
00:04:57,050 --> 00:05:02,890
కాబట్టి ఈ నా క్రమబద్ధీకరించబడతాయి ఇన్పుట్ శ్రేణి, మరియు నేను మీరు షఫుల్ అది మీరు.

87
00:05:02,890 --> 00:05:07,070
మేము దీన్ని మళ్లీ చేస్తాను.

88
00:05:07,070 --> 00:05:13,780
ప్రతి ఒక్కరూ ప్రశ్న అర్థం ఉందా? సరే.

89
00:05:13,780 --> 00:05:16,730
కాబట్టి అది మీ ఇష్టం.

90
00:05:16,730 --> 00:05:21,220
కొన్ని ఆలోచనలు ఏమిటి? మీరు n ^ 2, n లాగ్ n, n గా చేయవచ్చు?

91
00:05:21,220 --> 00:05:34,400
సూచనలు ఆహ్వానిస్తుంది.

92
00:05:34,400 --> 00:05:37,730
సరే. ఎమ్మి సూచించారు కాబట్టి ఒక ఆలోచన,

93
00:05:37,730 --> 00:05:45,300
మొదటి 0 నుండి 20 వరకు యాదృచ్చిక సంఖ్య, పూర్ణాంకం యాదృచ్ఛిక, ఒక పరిధిలో గణించడం ఉంది.

94
00:05:45,300 --> 00:05:49,840
మా శ్రేణి 20 యొక్క పొడవు భావిస్తాయి.

95
00:05:49,840 --> 00:05:54,800
20 అంశాల మా రేఖాచిత్రంలో,

96
00:05:54,800 --> 00:05:58,560
ఈ మా ఇన్పుట్ శ్రేణి.

97
00:05:58,560 --> 00:06:04,590
ఇప్పుడు, ఆమె సలహా, ఒక కొత్త శ్రేణి సృష్టించడానికి ఉంది

98
00:06:04,590 --> 00:06:08,440
ఈ ఉత్పత్తి శ్రేణి ఉంటుంది.

99
00:06:08,440 --> 00:06:12,880
నేను RAND ద్వారా తిరిగి ఆధారంగా -

100
00:06:12,880 --> 00:06:17,580
నేను కనుక, 17, యొక్క అని పిలవబడు

101
00:06:17,580 --> 00:06:25,640
మొదటి స్థానం లోకి 17 వ మూలకం కాపీ.

102
00:06:25,640 --> 00:06:30,300
ఇప్పుడు మేము తొలగించాలి - మేము ఇక్కడ అన్ని అంశాలను బదిలీ అవసరం

103
00:06:30,300 --> 00:06:36,920
ఆ విధముగా మేము చివరిలో ఖాళీ మరియు మధ్య ఏ రంధ్రాలు ఉంటాయి.

104
00:06:36,920 --> 00:06:39,860
ఇప్పుడు మేము విధానాన్ని పునరుక్తి.

105
00:06:39,860 --> 00:06:46,360
ఇప్పుడు మేము 0 మరియు 19 మధ్య ఒక కొత్త యాదృచ్ఛిక పూర్ణాంక ఎంచుకోండి.

106
00:06:46,360 --> 00:06:52,510
మేము ఇక్కడ ఒక కొత్త హావ్, మరియు మేము ఈ స్థానాన్ని ఈ మూలకం కాపీ.

107
00:06:52,510 --> 00:07:00,960
అప్పుడు మేము పైగా అంశాలను బదిలీ మరియు మేము మా పూర్తి కొత్త శ్రేణిని కలిగి వరకు మేము విధానాన్ని పునరుక్తి.

108
00:07:00,960 --> 00:07:05,890
ఈ అల్గోరిథం యొక్క రన్ టైం అంటే ఏమిటి?

109
00:07:05,890 --> 00:07:08,110
సరే, ఈ ప్రభావం పరిగణలోకి తెలియజేయండి.

110
00:07:08,110 --> 00:07:10,380
మేము ప్రతి మూలకం బదిలీ చేస్తారు.

111
00:07:10,380 --> 00:07:16,800
మేము ఈ i తొలగించడానికి, మేము ఎడమ దానిని తర్వాత అన్ని అంశాలను బదిలీ చేస్తారు.

112
00:07:16,800 --> 00:07:21,600
మరియు ఒక O (n) ఖర్చు

113
00:07:21,600 --> 00:07:26,100
ఎందుకంటే మనం మొదటి మూలకం తీసివేస్తే?

114
00:07:26,100 --> 00:07:29,670
కాబట్టి ప్రతి తొలగింపు కోసం, మేము తొలగించు -

115
00:07:29,670 --> 00:07:32,170
ప్రతి తొలగింపు, ఒక O (n) ఆపరేషన్ కలిగితే

116
00:07:32,170 --> 00:07:41,520
మేము తొలగింపులు n నుంచి మరియు, ఈ ఒక O (n ^ 2) షఫుల్ దారితీస్తుంది.

117
00:07:41,520 --> 00:07:49,550
సరే. సో గుడ్ ప్రారంభం. మంచి ప్రారంభం.

118
00:07:49,550 --> 00:07:55,290
>> మరో సలహా, క్నుత్ షఫుల్ అని పిలుస్తారు ఏదో ఉపయోగిస్తారు

119
00:07:55,290 --> 00:07:57,540
లేదా FISHER-యేట్స్ షఫుల్.

120
00:07:57,540 --> 00:07:59,630
మరియు అది నిజానికి ఒక సరళ సమయం షఫుల్ ఉంది.

121
00:07:59,630 --> 00:08:02,200
మరియు ఆలోచన చాలా పోలి ఉంటుంది.

122
00:08:02,200 --> 00:08:05,160
మళ్లీ, మేము, మా ఇన్పుట్ శ్రేణి కలిగి

123
00:08:05,160 --> 00:08:08,580
కానీ బదులుగా మా ఇన్పుట్ / అవుట్పుట్ కోసం రెండు శ్రేణుల ఉపయోగించి యొక్క,

124
00:08:08,580 --> 00:08:13,590
మేము, మా దిగి భాగాన్ని ట్రాక్ శ్రేణి యొక్క మొదటి భాగం ఉపయోగించడానికి

125
00:08:13,590 --> 00:08:18,400
మరియు మేము ట్రాక్, మరియు అప్పుడు మేము unshuffled భాగం కోసం మా శ్రేణి యొక్క మిగిలిన వదిలి.

126
00:08:18,400 --> 00:08:24,330
ఇక్కడ నా ఉద్దేశ్యం ఏమిటి. మేము తో మొదలు - మేము ఒక నేను ఎంపిక,

127
00:08:24,330 --> 00:08:30,910
0 నుండి 20 వరకు వ్యూహం.

128
00:08:30,910 --> 00:08:36,150
మా ప్రస్తుత పాయింటర్ మొదటి ఇండెక్స్ కు సూచిస్తుంది.

129
00:08:36,150 --> 00:08:39,590
మేము కొన్ని నేను ఇక్కడ ఎంచుకోండి

130
00:08:39,590 --> 00:08:42,740
మరియు ఇప్పుడు మేము స్వాప్.

131
00:08:42,740 --> 00:08:47,690
, ఈ 5 మరియు ఈ 4 కాబట్టి ఉంటే

132
00:08:47,690 --> 00:08:57,150
ఫలితంగా శ్రేణి ఇక్కడ 5 ఇక్కడ మరియు 4 ఉంటుంది.

133
00:08:57,150 --> 00:09:00,390
ఇప్పుడు మేము ఇక్కడ ఒక మార్కర్ గమనించండి.

134
00:09:00,390 --> 00:09:05,770
ఎడమ ప్రతిదీ, దిగి ఉంది

135
00:09:05,770 --> 00:09:15,160
మరియు కుడివైపున ప్రతిదీ unshuffled ఉంది.

136
00:09:15,160 --> 00:09:17,260
ఇప్పుడు మేము ప్రక్రియ తిరిగి చేయవచ్చు.

137
00:09:17,260 --> 00:09:25,210
మేము ఇప్పుడు 1 మరియు 20 మధ్య ఒక యాదృచ్ఛిక సూచిక ఎంచుకోండి.

138
00:09:25,210 --> 00:09:30,650
నేను ఇక్కడ మా కొత్త అనుకుందాం.

139
00:09:30,650 --> 00:09:39,370
ఇప్పుడు మేము ఇక్కడ మా ప్రస్తుత కొత్త స్థానం ఈ i స్వాప్.

140
00:09:39,370 --> 00:09:44,790
కాబట్టి మేము ఈ వంటి ముందుకు వెనుకకు ఇచ్చిపుచ్చుకోవడంతో లేదు.

141
00:09:44,790 --> 00:09:51,630
నాకు మరింత కాంక్రీటును తయారు చేసేందుకు కోడ్ తీసుకురావటానికి లెట్.

142
00:09:51,630 --> 00:09:55,290
మేము నాకు మా ఎంపిక ప్రారంభం -

143
00:09:55,290 --> 00:09:58,370
నేను 0 సమానం తో మేము ప్రారంభం, మనం ఒక యాదృచ్చిక నగర j ఎంచుకోండి

144
00:09:58,370 --> 00:10:02,420
యెరే యొక్క unshuffled భాగంలో, నేను n-1 కు.

145
00:10:02,420 --> 00:10:07,280
నేను ఇక్కడ ఉన్నాను చేస్తే, ఇక్కడ మరియు యెరే యొక్క మిగిలిన మధ్య ఒక యాదృచ్ఛిక సూచిక ఎంచుకోండి

146
00:10:07,280 --> 00:10:12,410
మరియు మేము స్వాప్.

147
00:10:12,410 --> 00:10:17,550
ఈ షఫుల్ మీ శ్రేణి అవసరమైన అన్ని స్మృతి.

148
00:10:17,550 --> 00:10:21,670
ఏదైనా ప్రశ్నలు?

149
00:10:21,670 --> 00:10:25,530
>> వెల్, ఒక ప్రశ్న అవసరం, ఎందుకు ఈ సరైన ఉంది?

150
00:10:25,530 --> 00:10:28,360
ఎందుకు ప్రతి ప్రస్తారణను సమానంగా అవకాశం ఉంది?

151
00:10:28,360 --> 00:10:30,410
నేను, ఈ నిరూపణ ద్వారా కాదు

152
00:10:30,410 --> 00:10:35,970
కానీ కంప్యూటర్ సైన్స్ లో అనేక సమస్యలు ప్రేరణ ద్వారా నిరూపించబడింది.

153
00:10:35,970 --> 00:10:38,520
ఎలా మీరు చాలా ప్రేరణ తెలిసిన?

154
00:10:38,520 --> 00:10:40,590
సరే. కూల్.

155
00:10:40,590 --> 00:10:43,610
కాబట్టి మీరు, సాధారణ ప్రేరణ ద్వారా ఈ అల్గోరిథం యొక్క సరి నిరూపించవచ్చు

156
00:10:43,610 --> 00:10:49,540
మీ ప్రేరణ పరికల్పన ఉంటుంది, అక్కడ భావిస్తాయి

157
00:10:49,540 --> 00:10:53,290
నా షఫుల్ ప్రతి ప్రస్తారణను సమానంగా అవకాశం తిరిగి

158
00:10:53,290 --> 00:10:56,120
మొదటి నేను అంశాలను.

159
00:10:56,120 --> 00:10:58,300
ఇప్పుడు నేను + 1 భావిస్తారు.

160
00:10:58,300 --> 00:11:02,550
మరియు మేము మా ఇండెక్స్ j స్వాప్ ఎంచుకోవచ్చు ద్వారా,

161
00:11:02,550 --> 00:11:05,230
, మరియు తర్వాత మీరు వివరాలను పని - ఈ దారితీస్తుంది

162
00:11:05,230 --> 00:11:07,390
ఈ అల్గోరిథం తిరిగి ఎందుకు కనీసం ఒక పూర్తి రుజువు

163
00:11:07,390 --> 00:11:12,800
సమానంగా అవకాశం సంభావ్యత ప్రతి ప్రస్తారణను.

164
00:11:12,800 --> 00:11:15,940
>> All right, తర్వాత సమస్య.

165
00:11:15,940 --> 00:11:19,170
కాబట్టి ", ప్రతికూల, సున్నా, అనుకూల పూర్ణాంకాల యొక్క వ్యూహం, ఇచ్చిన

166
00:11:19,170 --> 00:11:21,290
గరిష్ట మొత్తం లెక్క ప్రకారం ఒక ఫంక్షన్ వ్రాయండి

167
00:11:21,290 --> 00:11:24,720
ఇన్పుట్ శ్రేణి ఏ continueous subarray యొక్క. "

168
00:11:24,720 --> 00:11:28,370
ఇక్కడ ఒక ఉదాహరణ, అన్ని సంఖ్యలు అనుకూలంగా ఉంటాయి సందర్భంలో, ఉంది

169
00:11:28,370 --> 00:11:31,320
అప్పుడు ప్రస్తుతం ఉత్తమ ఎంపిక వ్యూహరచనలు పొందాలి.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, 10 సమానం.

171
00:11:34,690 --> 00:11:36,780
మీరు అక్కడ కొన్ని ప్రతికూలతలు ఉన్నప్పుడు,

172
00:11:36,780 --> 00:11:38,690
ఈ సందర్భంలో మనం కేవలం మొదటి రెండు కావలసిన

173
00:11:38,690 --> 00:11:44,590
-1 మరియు / లేదా -3 ఎంచుకోవడం మా మొత్తం దించాలని ఉంటుంది.

174
00:11:44,590 --> 00:11:48,120
కొన్నిసార్లు మేము శ్రేణి మధ్యలో ప్రారంభం ఉంటుంది.

175
00:11:48,120 --> 00:11:53,500
కొన్నిసార్లు మేము అన్ని వద్ద ఏమీ ఎంచుకోవాలనుకుంటే ఇది ఏదీ తీసుకోదు చేయడం ఉత్తమం.

176
00:11:53,500 --> 00:11:56,490
కొన్నిసార్లు, పతనం తీసుకోవాలని ఉత్తమం

177
00:11:56,490 --> 00:12:07,510
అది తర్వాత విషయం సూపర్ పెద్ద ఎందుకంటే. ఏ ఆలోచనలు కాబట్టి?

178
00:12:07,510 --> 00:12:10,970
(విద్యార్థి, అపారదర్శక) >> అవును.

179
00:12:10,970 --> 00:12:13,560
నేను -1 తీసుకోకపోతే అనుకుందాం.

180
00:12:13,560 --> 00:12:16,170
అప్పుడు గాని నేను 1,000 మరియు 20,000, ఎంచుకోండి

181
00:12:16,170 --> 00:12:18,630
లేదా నేను 3 బిలియన్ ఎంచుకోండి.

182
00:12:18,630 --> 00:12:20,760
Well, ఉత్తమ ఎంపిక అన్ని సంఖ్యలు పొందాలి.

183
00:12:20,760 --> 00:12:24,350
ఈ -1, ప్రతికూల ఉన్నప్పటికీ,

184
00:12:24,350 --> 00:12:31,340
మొత్తం మొత్తం నేను -1 తీసుకోకూడదని కంటే మరింత ఉత్తమంగా ఉంది.

185
00:12:31,340 --> 00:12:36,460
నేను ఇదివరకు చెప్పిన చిట్కాలు ఒకటి స్పష్టంగా స్పష్టమైన రాష్ట్రానికి ఉంది

186
00:12:36,460 --> 00:12:40,540
మొదటి మరియు బ్రూట్ ఫోర్స్ పరిష్కారం.

187
00:12:40,540 --> 00:12:44,340
ఈ సమస్య లో బ్రూట్ ఫోర్స్ పరిష్కారం ఏమిటి? Yeah?

188
00:12:44,340 --> 00:12:46,890
[జేన్] నేను బ్రూట్ ఫోర్స్ పరిష్కారం అనుకుంటున్నాను

189
00:12:46,890 --> 00:12:52,600
అన్ని సాధ్యమైన కలయికల (అపారదర్శక) అప్ జోడించడానికి ఉంటుంది.

190
00:12:52,600 --> 00:12:58,250
[యు] సరే. కాబట్టి జానే ఆలోచన ప్రతి సాధ్యం పొందాలి -

191
00:12:58,250 --> 00:13:01,470
నేను paraphrasing ఉన్నాను - ప్రతి సాధ్యం నిరంతర subarray పొందాలి,

192
00:13:01,470 --> 00:13:07,840
దాని మొత్తం గణించడం, మరియు అప్పుడు ఉన్న అన్ని నిరంతర subarrays గరిష్ట పడుతుంది.

193
00:13:07,840 --> 00:13:13,310
ప్రత్యేకంగా నా ఇన్పుట్ శ్రేణిలో subarray గుర్తిస్తుంది?

194
00:13:13,310 --> 00:13:17,380
ఏమి రెండు విషయాలు అవసరం, ఇలా? Yeah?

195
00:13:17,380 --> 00:13:19,970
(విద్యార్థి, అపారదర్శక) >> కుడి.

196
00:13:19,970 --> 00:13:22,130
తక్కువ ఇండెక్స్ మరియు ఒక ఉన్నత బౌండ్ ఇండెక్స్ లో కట్టుబడి

197
00:13:22,130 --> 00:13:28,300
ప్రత్యేకంగా ఒక నిరంతర subarray నిర్ణయిస్తుంది.

198
00:13:28,300 --> 00:13:31,400
[అవివాహిత విద్యార్థి] మేము ఇది ఏకైక సంఖ్యల వ్యూహం యొక్క అంచనా ఆర్?

199
00:13:31,400 --> 00:13:34,280
[యు] నం ఆమె ప్రశ్న కాబట్టి, మేము మా శ్రేణి ఊహిస్తూ ఉంటాయి -

200
00:13:34,280 --> 00:13:39,000
మా శ్రేణి అన్ని ఏకైక సంఖ్యలు, మరియు సమాధానం లేదు ఉంది.

201
00:13:39,000 --> 00:13:43,390
>> మేము అప్పుడు మా బ్రూట్ ఫోర్స్ పరిష్కారం, ప్రారంభ / ముగింపు సూచీలు ఉపయోగిస్తే

202
00:13:43,390 --> 00:13:47,200
ప్రత్యేకంగా మా నిరంతర subarray నిర్ణయిస్తుంది.

203
00:13:47,200 --> 00:13:51,680
మేము అన్ని సాధ్యం ప్రారంభం ఎంట్రీలకు iterate అయితే,

204
00:13:51,680 --> 00:13:58,320
మరియు అన్ని ముగింపు ఎంట్రీలకు> లేదా =, ప్రారంభం, మరియు <n కు

205
00:13:58,320 --> 00:14:05,570
మీరు మొత్తం గణించడం, మరియు అప్పుడు మేము ఇప్పటివరకు చూసిన గరిష్ట మొత్తం పడుతుంది.

206
00:14:05,570 --> 00:14:07,880
ఈ స్పష్టం?

207
00:14:07,880 --> 00:14:12,230
ఈ పరిష్కారం యొక్క పెద్ద O ఏమిటి?

208
00:14:12,230 --> 00:14:16,660
Timewise.

209
00:14:16,660 --> 00:14:18,860
చాలా ^ 2 n Not.

210
00:14:18,860 --> 00:14:25,250
, మేము 0 నుండి N వరకు iterate గమనించండి

211
00:14:25,250 --> 00:14:27,520
కాబట్టి లూప్ ఒకటి.

212
00:14:27,520 --> 00:14:35,120
మేము లూప్, దాదాపు ప్రారంభం నుండి చివరి వరకు మరొక iterate.

213
00:14:35,120 --> 00:14:37,640
ఇప్పుడు, ఆ లోపల, మేము ప్రతి ఎంట్రీ అప్ సంకలనం కలిగి

214
00:14:37,640 --> 00:14:43,810
కాబట్టి లూప్ ఇంకొక. కాబట్టి మేము మూడు ఉచ్చులు కోసం సమూహం, n ^ 3 ఉంటాయి.

215
00:14:43,810 --> 00:14:46,560
సరే. ఈ ప్రారంభ బిందువుగా వెళుతుంది.

216
00:14:46,560 --> 00:14:53,180
మా పరిష్కారం n ^ 3 కంటే దారుణంగా ఉంది.

217
00:14:53,180 --> 00:14:55,480
ప్రతి ఒక్కరూ బ్రూట్ ఫోర్స్ పరిష్కారం అర్థం ఉందా?

218
00:14:55,480 --> 00:14:59,950
>> సరే. ఉత్తమ పరిష్కారం డైనమిక్ ప్రోగ్రామింగ్ అని ఒక ఆలోచన ఉపయోగిస్తోంది.

219
00:14:59,950 --> 00:15:03,040
మీరు CS124 తీసుకోకపోతే, ఇది ఆల్గోరిథమ్స్ మరియు డేటా స్ట్రక్చర్స్ ఉంది

220
00:15:03,040 --> 00:15:05,680
మీరు ఈ టెక్నిక్ తో బాగా తెలిసిన అవుతుంది.

221
00:15:05,680 --> 00:15:12,190
మరియు ఆలోచన, మొదటి చిన్న సమస్యలకు పరిష్కారాలను నిర్మించటానికి ప్రయత్నించండి.

222
00:15:12,190 --> 00:15:17,990
ప్రారంభ మరియు ముగింపు: ఈ ద్వారా వాట్ ఐ మీన్, మేము ప్రస్తుతం రెండు విషయాల గురించి ఆందోళన.

223
00:15:17,990 --> 00:15:29,340
మరియు ఆ బాధించే ఉంది. మేము ఆ పారామితులు ఒకటి వదిలించుకోవటం కాలేదు ఏమి?

224
00:15:29,340 --> 00:15:32,650
మేము మా అసలు సమస్య ఇచ్చిన, - ఒక ఆలోచన ఉంది

225
00:15:32,650 --> 00:15:37,470
ఒక పరిధిలో ఏ subarray గరిష్ట మొత్తం [O, n-1] చూడండి.

226
00:15:37,470 --> 00:15:47,400
ఇప్పుడు మేము, మా ప్రస్తుత సూచిక నేను, మేము తెలిసిన ఒక కొత్త subproblem కలిగి

227
00:15:47,400 --> 00:15:52,520
మేము అక్కడ ముగించారు ఉండాలి తెలుసు. మా subarray ప్రస్తుత సూచిక వద్ద ముగుస్తాయి.

228
00:15:52,520 --> 00:15:57,640
మిగిలిన సమస్య కాబట్టి, అక్కడ మా subarray ప్రారంభం కావాలి?

229
00:15:57,640 --> 00:16:05,160
ఈ కోణంలో రాబడుతుంది? సరే.

230
00:16:05,160 --> 00:16:12,030
నేను ఈ అప్ కోడ్ చేసిన, మరియు దీని అర్థం చూద్దాం యొక్క.

231
00:16:12,030 --> 00:16:16,230
Codirectory లో subarray అని పిలిచే ఒక కార్యక్రమం ఉంది

232
00:16:16,230 --> 00:16:19,470
మరియు ఇది అంశాల సంఖ్య పడుతుంది

233
00:16:19,470 --> 00:16:25,550
మరియు అది నా దిగి జాబితాలో గరిష్ట subarray మొత్తం తిరిగి.

234
00:16:25,550 --> 00:16:29,920
కాబట్టి ఈ సందర్భంలో, మా గరిష్ట subarray 3.

235
00:16:29,920 --> 00:16:34,850
మరియు కేవలం 2 మరియు 1 ఉపయోగించి తీసుకువెళ్లారు.

236
00:16:34,850 --> 00:16:38,050
యొక్క మళ్లీ అమలు లెట్. ఇది 3 యొక్క.

237
00:16:38,050 --> 00:16:40,950
కానీ ఈ సమయంలో, మేము 3 ఎలా గమనించండి.

238
00:16:40,950 --> 00:16:46,690
మేము పట్టింది - మేము 3 స్వయంగా పడుతుంది

239
00:16:46,690 --> 00:16:49,980
ఇది రెండు వైపులా ప్రతికూలతలు చుట్టూ ఎందుకంటే,

240
00:16:49,980 --> 00:16:55,080
మొత్తానికి <3 తెచ్చే.

241
00:16:55,080 --> 00:16:57,820
యొక్క 10 అంశాలను అమలు లెట్.

242
00:16:57,820 --> 00:17:03,200
ఇది 7 యొక్క ఈ సమయం, మేము ప్రధాన 3 మరియు 4 పడుతుంది.

243
00:17:03,200 --> 00:17:09,450
ఈ సమయంలో అది 8, మరియు మేము 1, 4 మరియు 3 తీసుకొని ఆ పొందటానికి.

244
00:17:09,450 --> 00:17:16,310
కాబట్టి మీరు ఎలా ఒక ఊహ ఇవ్వాలని మేము ఈ రూపాంతరం సమస్య పరిష్కరించగల,

245
00:17:16,310 --> 00:17:18,890
యొక్క ఈ subarray పరిశీలించి అనుమతిస్తుంది.

246
00:17:18,890 --> 00:17:23,460
మేము ఈ ఇన్పుట్ శ్రేణి ఇచ్చిన, మరియు మేము సమాధానం 8 తెలుసు చేస్తున్నారు.

247
00:17:23,460 --> 00:17:26,359
మేము 1, 4, 3 మరియు పడుతుంది.

248
00:17:26,359 --> 00:17:29,090
కానీ యొక్క మేము నిజంగా ఆ సమాధానం ఎలా చూద్దాం.

249
00:17:29,090 --> 00:17:34,160
యొక్క ఈ సూచికలకు ప్రతి వద్ద ముగిసింది గరిష్ట subarray చూద్దాం.

250
00:17:34,160 --> 00:17:40,780
మొదటి స్థానం వద్ద ముగిసింది కలిగి గరిష్ట subarray ఏమిటి?

251
00:17:40,780 --> 00:17:46,310
[స్టూడెంట్] జీరో. >> జీరో. జస్ట్ -5 తీసుకోరు.

252
00:17:46,310 --> 00:17:50,210
ఇక్కడ అది 0 చేస్తాడు. Yeah?

253
00:17:50,210 --> 00:17:56,470
(విద్యార్థి, అర్ధం కాని)

254
00:17:56,470 --> 00:17:58,960
[యు] ఓహ్, క్షమించండి, -3 ఉంది.

255
00:17:58,960 --> 00:18:03,220
ఈ ఒక 2 కాబట్టి, ఈ ఒక -3 ఉంది.

256
00:18:03,220 --> 00:18:08,690
సరే. కాబట్టి -4, ఆ స్థానం ముగించడానికి గరిష్ట subarray ఏది

257
00:18:08,690 --> 00:18:12,910
-4 లో ఎప్పుడు? జీరో.

258
00:18:12,910 --> 00:18:22,570
ఒక? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
ఇప్పుడు నేను -2 వద్ద ఉన్న నగర వద్ద ముగుస్తాయి.

260
00:18:28,060 --> 00:18:39,330
కాబట్టి 6, 5, 7, మరియు చివరి 4 ఉంటుంది.

261
00:18:39,330 --> 00:18:43,480
ఈ నా ప్రవేశాలు తెలుసుకొని

262
00:18:43,480 --> 00:18:48,130
నేను ఈ సూచికలకు ప్రతి వద్ద ముగుస్తాయి పేరు రూపాంతరం సమస్య కోసం,

263
00:18:48,130 --> 00:18:51,410
నా చివరి సమాధానం ఉంది, అంతటా స్వీప్ పడుతుంది

264
00:18:51,410 --> 00:18:53,580
మరియు గరిష్ట సంఖ్య పడుతుంది.

265
00:18:53,580 --> 00:18:55,620
కాబట్టి ఈ విషయంలో అది 8 ఉంది.

266
00:18:55,620 --> 00:19:00,010
ఇది గరిష్ట subarray ఈ ఇండెక్స్ వద్ద ముగుస్తుంది సూచిస్తుంది

267
00:19:00,010 --> 00:19:04,970
మరియు అది ముందు ఎక్కడో ప్రారంభించారు.

268
00:19:04,970 --> 00:19:09,630
ప్రతి ఒక్కరూ ఈ రూపాంతరం subarray అర్థం ఉందా?

269
00:19:09,630 --> 00:19:22,160
>> సరే. సరే, ఈ కోసం పునరుక్తి గుర్తించడానికి అనుమతిస్తాయి.

270
00:19:22,160 --> 00:19:27,990
యొక్క కేవలం మొదటి కొన్ని ఎంట్రీలను పరిగణలోకి లెట్.

271
00:19:27,990 --> 00:19:35,930
ఇక్కడ అది, 8 0, 0, 0, 1, 5 ఉంది.

272
00:19:35,930 --> 00:19:39,790
మరియు తరువాత ఇక్కడ ఒక -2 ఉంది, మరియు ఆ 6 దానిని తగ్గిపోయాయి.

273
00:19:39,790 --> 00:19:50,800
నేను స్థానంలో ఎంట్రీ కాల్ అయితే నేను subproblem (i),

274
00:19:50,800 --> 00:19:54,910
ఎలా మునుపటి subproblem సమాధానం ఉపయోగించవచ్చు

275
00:19:54,910 --> 00:19:59,360
ఈ subproblem సమాధానం?

276
00:19:59,360 --> 00:20:04,550
నేను విషయంలో చూస్తే, ఈ ఎంట్రీ, సే తెలియజేయండి.

277
00:20:04,550 --> 00:20:09,190
నేను చూడటం ద్వారా సమాధానం 6 గణించాలి

278
00:20:09,190 --> 00:20:18,780
ఈ శ్రేణి మరియు ఈ శ్రేణి గత ఉప సమస్యలను సమాధానాలు కలయిక? అవును?

279
00:20:18,780 --> 00:20:22,800
[అవివాహిత విద్యార్థి] మీరు మొత్తాలను యొక్క శ్రేణి పడుతుంది

280
00:20:22,800 --> 00:20:25,430
స్థానం లో కుడి అది ముందు, 8 కాబట్టి

281
00:20:25,430 --> 00:20:32,170
మరియు తర్వాత మీరు ప్రస్తుత subproblem జోడించండి.

282
00:20:32,170 --> 00:20:36,460
[యు], ఆమె సలహా ఈ రెండు సంఖ్యలను కు ఉంది కాబట్టి

283
00:20:36,460 --> 00:20:40,090
ఈ సంఖ్య మరియు ఈ సంఖ్య.

284
00:20:40,090 --> 00:20:50,130
కాబట్టి ఈ 8 subproblem కోసం సమాధానం (- 1 i) సూచిస్తుంది.

285
00:20:50,130 --> 00:20:57,300
మరియు నా ఇన్పుట్ శ్రేణి A. కాల్ తెలియజేయండి

286
00:20:57,300 --> 00:21:01,470
స్థానం i వద్ద ముగుస్తుంది ఒక గరిష్ట subarray కనుగొనేందుకు చేయడానికి,

287
00:21:01,470 --> 00:21:03,980
నేను రెండు ఎంపికలు ఉన్నాయి: నేను గాని subarray కొనసాగించవచ్చు

288
00:21:03,980 --> 00:21:09,790
ఆ మునుపటి సూచిక వద్ద ముగిసింది, లేదా ఒక కొత్త శ్రేణి ప్రారంభించండి.

289
00:21:09,790 --> 00:21:14,190
నేను గత సూచిక వద్ద ప్రారంభించారు subarray కొనసాగించదలిస్తే

290
00:21:14,190 --> 00:21:19,260
అప్పుడు నేను సాధించింది గరిష్ట మొత్తం మునుపటి subproblem సమాధానం ఉంది

291
00:21:19,260 --> 00:21:24,120
ప్లస్ ప్రస్తుత శ్రేణి ఎంట్రీ.

292
00:21:24,120 --> 00:21:27,550
కానీ, నేను కూడా, ఒక కొత్త subarray మొదలు ఎంపిక

293
00:21:27,550 --> 00:21:30,830
ఈ సందర్భంలో మొత్తం 0.

294
00:21:30,830 --> 00:21:42,860
1, ప్లస్ ప్రస్తుత శ్రేణి ఎంట్రీ - కాబట్టి సమాధానం 0 యొక్క మాక్స్, subproblem ఐ.

295
00:21:42,860 --> 00:21:46,150
ఈ పునరుక్తి సమంజసం లేదు?

296
00:21:46,150 --> 00:21:50,840
మా పునరుక్తి, మేము కనుగొనగా, subproblem ఐ

297
00:21:50,840 --> 00:21:54,740
గత subproblem గరిష్ట ప్లస్ నా ప్రస్తుత శ్రేణి ఎంట్రీ సమానంగా ఉంటుంది

298
00:21:54,740 --> 00:22:01,490
ఇది గత subarray కొనసాగుతుంది అర్థం

299
00:22:01,490 --> 00:22:07,250
లేదా 0, నా ప్రస్తుత సూచిక ఒక కొత్త subarray ప్రారంభించండి.

300
00:22:07,250 --> 00:22:10,060
మరియు ఒకసారి మేము మా చివరి సమాధానం అప్పటి, పరిష్కారాలను ఈ పట్టికలో పైకి నిర్మించారు,

301
00:22:10,060 --> 00:22:13,950
కేవలం subproblem శ్రేణి అంతటా సరళ స్వీప్ చేయండి

302
00:22:13,950 --> 00:22:19,890
మరియు గరిష్ట సంఖ్య పడుతుంది.

303
00:22:19,890 --> 00:22:23,330
ఈ నేను మాట్లాడుతూ యొక్క ఒక ఖచ్చితమైన అమలు ఉంది.

304
00:22:23,330 --> 00:22:27,320
కాబట్టి మేము ఒక కొత్త subproblem అర్రే, ఉప సమస్యలను సృష్టించవచ్చు.

305
00:22:27,320 --> 00:22:32,330
మొదటి ఎంట్రీ 0 లేదా మొదటి ఎంట్రీ, ఆ రెండు గరిష్ట ఉంటుంది.

306
00:22:32,330 --> 00:22:35,670
మరియు ఉప సమస్యలను మిగిలిన

307
00:22:35,670 --> 00:22:39,810
మేము కేవలం కనుగొన్నారు ఖచ్చితమైన పునరుక్తి ఉపయోగించండి.

308
00:22:39,810 --> 00:22:49,960
ఇప్పుడు మేము మా ఉపసమస్యలను శ్రేణి యొక్క గరిష్ట గణించడం, మరియు మా చివరి సమాధానం ఉంది.

309
00:22:49,960 --> 00:22:54,130
>> కాబట్టి ఎంత ఖాళీ మేము ఈ అల్గోరిథం లో ఉపయోగిస్తున్నారు?

310
00:22:54,130 --> 00:23:01,470
మీరు మాత్రమే CS50 తీసుకున్నారు, అప్పుడు మీరు చాలా స్పేస్ చర్చించారు ఉండకపోవచ్చు.

311
00:23:01,470 --> 00:23:07,750
Well, గమనించదగ్గ ఒక మాట పరిమాణం n ఇక్కడ malloc అనే ఉంది.

312
00:23:07,750 --> 00:23:13,590
మీరు ఏమి సూచిస్తున్నాయి లేదు?

313
00:23:13,590 --> 00:23:17,450
ఈ అల్గోరిథం సరళ ప్రదేశాన్ని ఉపయోగించుకుంటుంది.

314
00:23:17,450 --> 00:23:21,030
మేము బాగా చేయగలరని?

315
00:23:21,030 --> 00:23:30,780
మీరు తుది సమాధానం గణించడం అనవసరమైన ఉంది అని గుర్తించలేకపోతే ఆ ఏదైనా ఉందా?

316
00:23:30,780 --> 00:23:33,290
నేను ఊహిస్తున్నాను మరింత మంచి ప్రశ్న, ఏ సమాచారం

317
00:23:33,290 --> 00:23:40,680
మేము చివరి వరకు అన్ని మార్గం కలిగి లేదు?

318
00:23:40,680 --> 00:23:44,280
ఇప్పుడు మేము ఈ రెండు పంక్తులు చూస్తే,

319
00:23:44,280 --> 00:23:47,720
మేము మాత్రమే గత subproblem శ్రద్ధ

320
00:23:47,720 --> 00:23:50,910
మరియు మేము మాత్రమే మనం ఇప్పటివరకు చూసిన గరిష్ట పట్టించుకోనట్లు.

321
00:23:50,910 --> 00:23:53,610
మా చివరి సమాధానం లెక్కించడానికి, మేము మొత్త అవసరం లేదు.

322
00:23:53,610 --> 00:23:57,450
మేము గత సంఖ్య గత రెండు సంఖ్యలు మాత్రమే అవసరం.

323
00:23:57,450 --> 00:24:02,630
గరిష్టంగా subproblem శ్రేణి, మరియు గత సంఖ్య చివరి సంఖ్య.

324
00:24:02,630 --> 00:24:07,380
కాబట్టి, నిజానికి, మేము కలిసి ఈ వలయాలు కరుగుతాయి

325
00:24:07,380 --> 00:24:10,460
మరియు సరళ స్పేస్ నుండి స్థిరమైన స్పేస్ వెళ్ళండి.

326
00:24:10,460 --> 00:24:15,830
ప్రస్తుత మొత్తం ఇప్పటివరకు, ఇక్కడ, subproblem, మా subproblem శ్రేణి యొక్క పాత్ర తొలగించబడుతాయి.

327
00:24:15,830 --> 00:24:20,020
కాబట్టి ప్రస్తుత మొత్తం ఇప్పటివరకు మునుపటి subproblem సమాధానం ఉంది.

328
00:24:20,020 --> 00:24:23,450
ఈ మొత్తం ఇప్పటివరకు మా మాక్స్ యొక్క జరుగుతుంది.

329
00:24:23,450 --> 00:24:28,100
మేము సహకరించు వంటి మేము గరిష్ట గణించడం.

330
00:24:28,100 --> 00:24:30,890
కాబట్టి మేము, స్థిరమైన స్పేస్ సరళ స్పేస్ నుంచి

331
00:24:30,890 --> 00:24:36,650
మరియు మేము కూడా మా subarray సమస్యకు పరిష్కారం సరళ ఉన్నాయి.

332
00:24:36,650 --> 00:24:40,740
>> ప్రశ్నలు ఈ రకాల మీరు ఇచ్చిన ఇంటర్వ్యూలో పొందుతారు.

333
00:24:40,740 --> 00:24:44,450
సమయం సంక్లిష్టత ఏమిటి; స్పేస్ సంక్లిష్టత ఏమిటి?

334
00:24:44,450 --> 00:24:50,600
మీరు బాగా చేయగలరని? చుట్టూ ఉంచడానికి అనవసరమైన అంశాలు ఉన్నాయి?

335
00:24:50,600 --> 00:24:55,270
నేను మీరు మీ సొంత తీసుకోమని విశ్లేషణలు హైలైట్ ఈ చేశాడు

336
00:24:55,270 --> 00:24:57,400
మీరు ఈ సమస్యలపై పని చేస్తున్నపుడు.

337
00:24:57,400 --> 00:25:01,710
ఎల్లప్పుడూ "నేను బాగా చేయగలరని?", మీరే అడుగుతూ కూడా

338
00:25:01,710 --> 00:25:07,800
నిజానికి, మేము ఈ కంటే మెరుగైన చేయగలరు?

339
00:25:07,800 --> 00:25:10,730
ఒక ట్రిక్ ప్రశ్న అబ్బాయి. మీరు అవసరం ఎందుకంటే మీరు, కాదు

340
00:25:10,730 --> 00:25:13,590
కనీసం సమస్య ఇన్పుట్ చదవండి.

341
00:25:13,590 --> 00:25:15,570
మీరు అవసరం వాస్తవం కనీసం సమస్య ఇన్పుట్ చదవండి కాబట్టి

342
00:25:15,570 --> 00:25:19,580
మీరు, సరళ సమయం కంటే బాగా అర్థం ఏమిటంటే

343
00:25:19,580 --> 00:25:22,870
మరియు మీరు స్థిరమైన ప్రదేశం కంటే బాగా లేదు.

344
00:25:22,870 --> 00:25:27,060
కాబట్టి ఇది నిజానికి, ఈ సమస్య ఉత్తమ పరిష్కారం.

345
00:25:27,060 --> 00:25:33,040
ప్రశ్నలు? సరే.

346
00:25:33,040 --> 00:25:35,190
>> స్టాక్ మార్కెట్ సమస్య:

347
00:25:35,190 --> 00:25:38,350
"అనుకూల, సున్నా, లేదా ప్రతికూల n పూర్ణ, ఒక వరుస కారణంగా,

348
00:25:38,350 --> 00:25:41,680
ఆ, n రోజులలో స్టాక్ ధర ప్రాతినిధ్యం

349
00:25:41,680 --> 00:25:44,080
మీరు చేయవచ్చు గరిష్ట లాభం లెక్కించడానికి ఒక ఫంక్షన్ వ్రాయండి

350
00:25:44,080 --> 00:25:49,350
మీరు ఈ n రోజుల్లో ఖచ్చితంగా 1 స్టాక్ కొనుగోలు మరియు విక్రయించే ఇచ్చిన. "

351
00:25:49,350 --> 00:25:51,690
ముఖ్యంగా, మేము, తక్కువ కొనుగోలు అధిక విక్రయించదలిచాను.

352
00:25:51,690 --> 00:25:58,580
మరియు మేము చేయవచ్చు ఉత్తమ లాభం గుర్తించడానికి కావలసిన.

353
00:25:58,580 --> 00:26:11,500
నా చిట్కా కు వెళుతున్నారు, ఏ వెంటనే స్పష్టమైన, సరళమైన సమాధానం, కానీ నెమ్మదిగా ఉంది?

354
00:26:11,500 --> 00:26:17,690
అవును? (విద్యార్థి, అపారదర్శక) >> అవును.

355
00:26:17,690 --> 00:26:21,470
>> కాబట్టి మీరు అయితే వెళ్ళి స్టాక్ ధరలు పరిశీలిస్తాడు

356
00:26:21,470 --> 00:26:30,550
సమయం లో ప్రతి పాయింట్, (అపారదర్శక).

357
00:26:30,550 --> 00:26:33,990
[యు] సరే, తన పరిష్కారం - కంప్యూటింగ్ ఆమె సలహా

358
00:26:33,990 --> 00:26:37,380
అత్యల్ప మరియు అత్యధిక కంప్యూటింగ్ తప్పనిసరిగా పని లేదు

359
00:26:37,380 --> 00:26:42,470
అత్యధిక అత్యల్ప ముందే కాబట్టి.

360
00:26:42,470 --> 00:26:47,340
కాబట్టి ఈ సమస్యకు బ్రూట్ ఫోర్స్ పరిష్కారం ఏమిటి?

361
00:26:47,340 --> 00:26:53,150
నేను ప్రత్యేకంగా నేను తయారు లాభం గుర్తించేందుకు అవసరమైన రెండు విషయాలు ఏమిటి? కుడి.

362
00:26:53,150 --> 00:26:59,410
బ్రూట్ ఫోర్స్ పరిష్కారం - OH, కాబట్టి, జార్జ్ యొక్క సలహా మేము కేవలం రెండు రోజులు అవసరం

363
00:26:59,410 --> 00:27:02,880
ప్రత్యేకంగా ఆ రెండు రోజులు లాభం గుర్తించడానికి.

364
00:27:02,880 --> 00:27:06,660
కాబట్టి మేము, కొనుగోలు / అమ్మే ఇష్టం, ప్రతి జంట గణించడం

365
00:27:06,660 --> 00:27:12,850
ప్రతికూల లేదా అనుకూల లేదా సున్నా చేసే ఆ లాభం, గణించడం.

366
00:27:12,850 --> 00:27:18,000
మేము రోజుల అన్ని జతల పై iterating తర్వాత చేసే గరిష్ట లాభం కంప్యూట్.

367
00:27:18,000 --> 00:27:20,330
మా చివరి సమాధానం ఉంటుంది.

368
00:27:20,330 --> 00:27:25,730
ఆ పరిష్కారం ఉంది ఎందుకంటే, O (n ^ 2) ఉంటుంది n రెండు జతల ఎన్నుకుంటుంది -

369
00:27:25,730 --> 00:27:30,270
మీరు ముగింపు రోజులు ఎంపిక చేసే రోజులు.

370
00:27:30,270 --> 00:27:32,580
సరే, నేను ఇక్కడ బ్రూట్ ఫోర్స్ పరిష్కారం వెళ్ళి వెళుతున్న కాదు.

371
00:27:32,580 --> 00:27:37,420
నేను ఒక n లాగ్ n పరిష్కారం అక్కడ మీరు చెప్పండి వెళుతున్న.

372
00:27:37,420 --> 00:27:45,550
మీరు ప్రస్తుతం n లాగ్ n అని అంటే అల్గోరిథం తెలుసు?

373
00:27:45,550 --> 00:27:50,730
ఇది ఒక ట్రిక్ ప్రశ్న కాదు.

374
00:27:50,730 --> 00:27:54,790
>> క్రమీకరించు విలీనం. విలీనం విధమైన, n లాగ్ n ఉంది

375
00:27:54,790 --> 00:27:57,760
నిజానికి, ఈ సమస్య పరిష్కరించేందుకు ఒక మార్గం ఉపయోగిస్తారు

376
00:27:57,760 --> 00:28:04,400
అని ఆలోచన యొక్క ఒక విలీనంతో విధమైన రకం సాధారణంగా, విభజించి జయించటానికి.

377
00:28:04,400 --> 00:28:07,570
మరియు ఈ విధంగా ఆలోచన.

378
00:28:07,570 --> 00:28:12,400
మీరు బెస్ట్ బై గణించడం / ఎడమ భాగంలో జత విక్రయించదలిచాను.

379
00:28:12,400 --> 00:28:16,480
మీరు రెండు రోజుల పాటు మొదటి n తో, చేయవచ్చు ఉత్తమ లాభం కనుగొనండి.

380
00:28:16,480 --> 00:28:19,780
అప్పుడు మీరు, బెస్ట్ బై oompute / కుడి అర్ధభాగంలో జత విక్రయించదలిచాను

381
00:28:19,780 --> 00:28:23,930
రెండు రోజుల పాటు గత n.

382
00:28:23,930 --> 00:28:32,400
ఇప్పుడు ప్రశ్న ఎలా మేము తిరిగి కలిసి ఈ పరిష్కారాలను విలీనం లేదు, ఉంది?

383
00:28:32,400 --> 00:28:36,320
అవును? (విద్యార్థి, అర్ధం కాని)

384
00:28:36,320 --> 00:28:49,890
సరే >>. నాలో ఒక చిత్రాన్ని డ్రా తెలియజేయండి.

385
00:28:49,890 --> 00:29:03,870
అవును? (జార్జ్, అర్ధం కాని)

386
00:29:03,870 --> 00:29:06,450
ఖచ్చితంగా >>. జార్జ్ యొక్క పరిష్కారం సరిగ్గా హక్కు.

387
00:29:06,450 --> 00:29:10,040
తన సలహా కాబట్టి, మొదటి, బెస్ట్ బై / అమ్మకపు జత గణించడం

388
00:29:10,040 --> 00:29:16,050
మరియు ఎడమ భాగంలో సంభవిస్తుంది, అందుచే యొక్క ఎడమ, ఎడమ ఆ కాల్ తెలియజేయండి.

389
00:29:16,050 --> 00:29:20,790
ఉత్తమ కుడి భాగంలో సంభవించే జత కొనుగోలు / అమ్మే.

390
00:29:20,790 --> 00:29:25,180
మేము మాత్రమే ఈ రెండు సంఖ్యలను పోల్చి అయితే, మేము కేసు లేదు చేస్తున్నారు

391
00:29:25,180 --> 00:29:30,460
మేము ఇక్కడ కొనుగోలు మరియు కుడి భాగంలో ఎక్కడో అమ్మే పేరు.

392
00:29:30,460 --> 00:29:33,810
మేము ఎడమ భాగంలో కొనుగోలు, కుడి భాగంలో అమ్మే.

393
00:29:33,810 --> 00:29:38,490
మరియు రెండు భాగాలుగా ఈజిప్టు బెస్ట్ బై / అమ్మకపు జత గణించడం ఉత్తమ మార్గం

394
00:29:38,490 --> 00:29:43,480
ఇక్కడ కనీస గణించడం మరియు ఇక్కడ గరిష్ట లెక్కించడానికి ఉంది

395
00:29:43,480 --> 00:29:45,580
మరియు వారి తేడా పడుతుంది.

396
00:29:45,580 --> 00:29:50,850
కొనుగోలు / అమ్మకపు జంట మాత్రమే ఇక్కడ సంభవించే రెండు కేసులు కాబట్టి,

397
00:29:50,850 --> 00:30:01,910
మాత్రమే ఇక్కడ, లేదా రెండూ విభజించటం ఈ మూడు సంఖ్యలు నిర్వచించబడింది.

398
00:30:01,910 --> 00:30:06,450
, తిరిగి కలిసి మా SOLUTIONS విలీనం మా అల్గోరిథం కాబట్టి

399
00:30:06,450 --> 00:30:08,350
మేము బెస్ట్ బై / అమ్మకపు జత గణించడం మీరు

400
00:30:08,350 --> 00:30:13,120
మేము ఎడమ అర్ధభాగంలో కొనుగోలు మరియు కుడి సగం లో అమ్ముటకు పేరు.

401
00:30:13,120 --> 00:30:16,740
మరియు ఆ విధంగా చేయడానికి ఉత్తమ మార్గం, మొదటి సగం లో అత్యల్ప ధర లెక్కించడానికి ఉంది

402
00:30:16,740 --> 00:30:20,360
అత్యధిక కుడి భాగంలో ధర, మరియు వారి తేడా పడుతుంది.

403
00:30:20,360 --> 00:30:25,390
ఫలితంగా మూడు లాభాలు, ఈ మూడు సంఖ్యలు, మీరు, మూడు గరిష్ట పడుతుంది

404
00:30:25,390 --> 00:30:32,720
మరియు మీరు ఈ మొదటి మరియు చివరి రోజులలో చేయవచ్చు ఉత్తమ లాభం ఉంది.

405
00:30:32,720 --> 00:30:36,940
ఇక్కడ ముఖ్యమైన పంక్తులు Red లో ఉన్నాయి.

406
00:30:36,940 --> 00:30:41,160
ఈ ఎడమ భాగంలో సమాధానం లెక్కించడానికి ఒక పునరావృత కాల్ ఉంది.

407
00:30:41,160 --> 00:30:44,760
ఈ కుడి భాగంలో సమాధానం లెక్కించడానికి ఒక పునరావృత కాల్ ఉంది.

408
00:30:44,760 --> 00:30:50,720
ఈ రెండు వలయాలు కోసం వరుసగా ఎడమ మరియు కుడి అర్ధభాగంలో min మరియు మాక్స్ గణించడం.

409
00:30:50,720 --> 00:30:54,970
ఇప్పుడు నేను రెండు భాగాలుగా ఈజిప్టు లాభం గణించడం

410
00:30:54,970 --> 00:31:00,530
మరియు చివరి సమాధానం ఈ మూడు గరిష్ట ఉంది.

411
00:31:00,530 --> 00:31:04,120
సరే.

412
00:31:04,120 --> 00:31:06,420
>> కాబట్టి, ఖచ్చితంగా, మేము ఒక అల్గోరిథం ఉన్నాయి, కాని పెద్ద ప్రశ్న

413
00:31:06,420 --> 00:31:08,290
ఈ సమయం సంక్లిష్టత ఏమిటి?

414
00:31:08,290 --> 00:31:16,190
నేను విలీనంతో విధమైన పేర్కొన్నారు కారణం ఈ రూపం సమాధానం విభజించి ఉంది

415
00:31:16,190 --> 00:31:19,200
రెండు మరియు తర్వాత తిరిగి కలిసి మా SOLUTIONS విలీనం

416
00:31:19,200 --> 00:31:23,580
సరిగ్గా విలీనంతో విధమైన రూపం.

417
00:31:23,580 --> 00:31:33,360
కాబట్టి నాకు వ్యవధి వీలు.

418
00:31:33,360 --> 00:31:41,340
మేము దశలను సంఖ్య ఒక ఫంక్షన్ t (n) నిర్వచించిన ఉంటే

419
00:31:41,340 --> 00:31:50,010
n రోజులు,

420
00:31:50,010 --> 00:31:54,350
మా రెండు పునరావృత కాల్స్

421
00:31:54,350 --> 00:32:00,460
ప్రతి t (n / 2), ఖర్చు వెళ్తున్నారు

422
00:32:00,460 --> 00:32:03,540
మరియు ఈ కాల్స్ రెండు ఉంది.

423
00:32:03,540 --> 00:32:10,020
ఇప్పుడు నేను, ఎడమ భాగంలో కనీసం గణించడం అవసరం

424
00:32:10,020 --> 00:32:17,050
నేను n / 2 సమయం, ప్లస్ కుడి సగం గరిష్ట లో చేయవచ్చు, ఇది.

425
00:32:17,050 --> 00:32:20,820
కాబట్టి ఇది n.

426
00:32:20,820 --> 00:32:25,050
మరియు తర్వాత కొన్ని స్థిరమైన పని ప్లస్.

427
00:32:25,050 --> 00:32:27,770
మరియు ఈ పునరుక్తి సమీకరణం

428
00:32:27,770 --> 00:32:35,560
సరిగ్గా విలీనంతో విధమైన కోసం పునరుక్తి సమీకరణం ఉంది.

429
00:32:35,560 --> 00:32:39,170
మరియు మేము అన్ని విలీనంతో విధమైన n లాగ్ n సమయం అని తెలుసు.

430
00:32:39,170 --> 00:32:46,880
అందువలన, మా అల్గోరిథం కూడా లాగ్ n సమయం n.

431
00:32:46,880 --> 00:32:52,220
ఈ పునరుక్తి సమంజసం లేదు?

432
00:32:52,220 --> 00:32:55,780
ఈ యొక్క ఒక సంక్షిప్త రీక్యాప్:

433
00:32:55,780 --> 00:32:59,170
T (n) గరిష్ట లాభం లెక్కించడానికి దశలను సంఖ్య

434
00:32:59,170 --> 00:33:02,750
n రోజుల వ్యవధిలో.

435
00:33:02,750 --> 00:33:06,010
మేము మా పునరావృత కాల్స్ విడిపోయారు మార్గం

436
00:33:06,010 --> 00:33:11,980
, మొదటి n / 2 రోజులు మా పరిష్కారం కాల్ ఉంది

437
00:33:11,980 --> 00:33:14,490
కాబట్టి ఒక కాల్, యొక్క

438
00:33:14,490 --> 00:33:16,940
మరియు తర్వాత మేము రెండవ సగం మళ్లీ కాల్.

439
00:33:16,940 --> 00:33:20,440
కాబట్టి ఆ రెండు కాల్స్ ఉంది.

440
00:33:20,440 --> 00:33:25,310
మరియు తర్వాత మేము, మేము సరళ సమయంలో చేయవచ్చు, ఇది ఎడమ అర్ధభాగంలో కనీసం కనుగొనడానికి

441
00:33:25,310 --> 00:33:29,010
మేము సరళ సమయంలో చేయవచ్చు ఇది కుడి అర్థ గరిష్ట, కనుగొనండి.

442
00:33:29,010 --> 00:33:31,570
కాబట్టి n / 2 + n / 2 కేవలం n.

443
00:33:31,570 --> 00:33:36,020
అప్పుడు మేము అంకగణితం చేయడం వంటి ఇది కొన్ని స్థిరమైన పని కలిగి.

444
00:33:36,020 --> 00:33:39,860
ఈ పునరావృత సమీకరణం సరిగ్గా విలీనంతో విధమైన కోసం పునరుక్తి సమీకరణం ఉంది.

445
00:33:39,860 --> 00:33:55,490
అందువలన, మా షఫుల్ అల్గోరిథం కూడా n n లాగిన్ అవ్వండి.

446
00:33:55,490 --> 00:33:58,520
కాబట్టి ఎంత ఖాళీ మేము ఉపయోగిస్తున్న?

447
00:33:58,520 --> 00:34:04,910
యొక్క కోడ్ తిరిగి వెళ్ళి తెలపండి.

448
00:34:04,910 --> 00:34:09,420
>> ఒక మంచి ప్రశ్న, ఎన్ని స్టాక్ ఫ్రేములు మనం ఏదైనా సందర్భంలో ఎందుకు చెయ్యాలి ఉంది?

449
00:34:09,420 --> 00:34:11,449
మేము సూత్రం ఉపయోగించి ఉన్నందున,

450
00:34:11,449 --> 00:34:23,530
స్టాక్ ఫ్రేమ్ల సంఖ్య మా స్పేస్ వాడుక నిర్ణయిస్తుంది.

451
00:34:23,530 --> 00:34:29,440
యొక్క n = 8 పరిగణలోకి లెట్.

452
00:34:29,440 --> 00:34:36,889
మేము, 8 న షఫుల్ కాల్

453
00:34:36,889 --> 00:34:41,580
మొదటి నాలుగు ఎంట్రీలు షఫుల్ కాల్ చేస్తుంది,

454
00:34:41,580 --> 00:34:46,250
ఇది మొదటి రెండు ఎంట్రీలు ఒక షఫుల్ కాల్ చేస్తుంది.

455
00:34:46,250 --> 00:34:51,550
మా స్టాక్ ఉంది - ఈ మా స్టాక్ ఉంది.

456
00:34:51,550 --> 00:34:54,980
మరియు తర్వాత మేము, 1 న మళ్లీ షఫుల్ కాల్

457
00:34:54,980 --> 00:34:58,070
మరియు ఆ యొక్క మా బేస్ కేసు ఏమిటి, కాబట్టి మేము వెంటనే తిరిగి.

458
00:34:58,070 --> 00:35:04,700
మనం ఈ అనేక స్టాక్ ఫ్రేముల కన్నా మరింత ఉందా?

459
00:35:04,700 --> 00:35:08,880
నం మేము ఒక ఆవాహన చేయండి ప్రతిసారీ ఎందుకంటే,

460
00:35:08,880 --> 00:35:10,770
షఫుల్ ఒక పునరావృత ఆవాహన,

461
00:35:10,770 --> 00:35:13,950
మేము సగం లో మా పరిమాణం తిరగడానికి.

462
00:35:13,950 --> 00:35:17,020
మనం ఏదైనా సందర్భంలో కలిగి స్టాక్ ఫ్రేములు గరిష్ట సంఖ్య కాబట్టి

463
00:35:17,020 --> 00:35:28,460
లాగ్ n స్టాక్ ఫ్రేములు యొక్క ఆర్డర్ మీద ఉంది.

464
00:35:28,460 --> 00:35:42,460
ప్రతి స్టాక్ ఫ్రేమ్, స్థిరమైన స్థలాన్ని

465
00:35:42,460 --> 00:35:44,410
స్థలం మరియు అందువలన మొత్తం,

466
00:35:44,410 --> 00:35:49,240
మనం ఉపయోగించే స్థలం యొక్క గరిష్ట మొత్తాన్ని O (n లాగ్) స్థలం

467
00:35:49,240 --> 00:36:03,040
పేరు n రోజుల సంఖ్య.

468
00:36:03,040 --> 00:36:07,230
>> ఇప్పుడు, ఎప్పుడూ మిమ్మల్ని మీరే ప్రశ్నించుకోండి, "మేము బాగా చేయగలరని?"

469
00:36:07,230 --> 00:36:12,390
మరియు ముఖ్యంగా, మేము ఇప్పటికే పరిష్కరించవచ్చు చేసిన ఒక సమస్య ఈ తగ్గిస్తుంది?

470
00:36:12,390 --> 00:36:20,040
ఒక సూచన: మేము ఈ ముందు రెండు ఇతర సమస్యలు చర్చించారు, మరియు అది షఫుల్ అని మాత్రం కాదు.

471
00:36:20,040 --> 00:36:26,200
మేము గరిష్ట subarray సమస్య ఈ స్టాక్ మార్కెట్ సమస్య మార్చవచ్చు.

472
00:36:26,200 --> 00:36:40,100
దీన్ని మేము ఎలా చేయగలరు?

473
00:36:40,100 --> 00:36:42,570
మీరు ఒకటి? ఎమ్మి?

474
00:36:42,570 --> 00:36:47,680
(ఎమ్మి, అర్ధం కాని)

475
00:36:47,680 --> 00:36:53,860
[యు] ఖచ్చితంగా.

476
00:36:53,860 --> 00:36:59,940
గరిష్ట subarray సమస్య కాబట్టి,

477
00:36:59,940 --> 00:37:10,610
మేము నిరంతరం subarray పైగా మొత్తానికి ఉన్నాము.

478
00:37:10,610 --> 00:37:16,230
మరియు స్టాక్స్ సమస్య ఎమ్మీ యొక్క సలహా,

479
00:37:16,230 --> 00:37:30,720
మార్పులు, లేదా డెల్టాలు భావిస్తారు.

480
00:37:30,720 --> 00:37:37,440
మరియు ఈ చిత్రాన్ని ఉంది - ఈ ఒక స్టాక్ ధర,

481
00:37:37,440 --> 00:37:42,610
కానీ మేము ప్రతి వరుస రోజు మధ్య వ్యత్యాసం చేపడితే -

482
00:37:42,610 --> 00:37:45,200
కాబట్టి మేము గరిష్ట ధర, గరిష్ట లాభం మేము అని చూడండి

483
00:37:45,200 --> 00:37:50,070
మేము ఇక్కడ కొనుగోలు మరియు అమ్మకం ఇక్కడ ఉంటుంది.

484
00:37:50,070 --> 00:37:54,240
కానీ యొక్క నిరంతర చూద్దాం - యొక్క subarray సమస్య చూద్దాం.

485
00:37:54,240 --> 00:38:02,510
ఇక్కడ, మేము చేయవచ్చు - ఇక్కడ నుండి ఇక్కడ వెళ్ళి,

486
00:38:02,510 --> 00:38:08,410
మేము ఒక మంచి మార్పు ఉండదు, మరియు ఇక్కడ ఇక్కడ నుండి వెళ్లి మేము ప్రతికూల మార్పు ఉండదు.

487
00:38:08,410 --> 00:38:14,220
కానీ, మేము ఒక పెద్ద అనుకూలమైన మార్పును కలిగి ఇక్కడ నుండి ఇక్కడ వెళ్ళడం జరుగుతుంది.

488
00:38:14,220 --> 00:38:20,930
మరియు ఈ మేము మా చివరి లాభం పొందడానికి సైన్ అప్ సంకలనం చేయదలిచిన మార్పులు.

489
00:38:20,930 --> 00:38:25,160
అప్పుడు మేము మరింత ప్రతికూల మార్పులు ఇక్కడ ఉన్నాయి.

490
00:38:25,160 --> 00:38:29,990
మా గరిష్ట subarray సమస్య లోకి మా స్టాక్ సమస్య తగ్గించటం కీ

491
00:38:29,990 --> 00:38:36,630
రోజుల మధ్య డెల్టాలు పరిగణిస్తారు.

492
00:38:36,630 --> 00:38:40,630
కాబట్టి మేము, డెల్టాలు అనే కొత్త శ్రేణి సృష్టించడానికి

493
00:38:40,630 --> 00:38:43,000
, 0 గా మొదటి ఎంట్రీ ప్రారంభించడం

494
00:38:43,000 --> 00:38:46,380
ఆపై ప్రతి డెల్టా కోసం (i), తేడా ఆ తెలియజేయండి

495
00:38:46,380 --> 00:38:52,830
నా ఇన్పుట్ శ్రేణి (i), మరియు శ్రేణి (i - 1).

496
00:38:52,830 --> 00:38:55,530
అప్పుడు మేము ఒక గరిష్ట subarray కోసం మా నియమిత ప్రక్రియగా కాల్

497
00:38:55,530 --> 00:39:01,500
ఒక డెల్టా యొక్క శ్రేణి అక్కడ.

498
00:39:01,500 --> 00:39:06,440
మరియు గరిష్ట subarray సరళ సమయం, ఎందుకంటే

499
00:39:06,440 --> 00:39:09,370
మరియు ఈ తగ్గింపు, ఈ డెల్టా శ్రేణి సృష్టించే ఈ ప్రక్రియ,

500
00:39:09,370 --> 00:39:11,780
, కూడా సరళ సమయం

501
00:39:11,780 --> 00:39:19,060
అప్పుడు నిల్వల కోసం చివరి పరిష్కారం O (n) పని ప్లస్ O (n) రచన, ఇప్పటికీ O (n) రచన.

502
00:39:19,060 --> 00:39:23,900
కాబట్టి మేము మా సమస్యకు ఒక దీర్ఘ సమయం పరిష్కారం ఉంది.

503
00:39:23,900 --> 00:39:29,610
ప్రతి ఒక్కరూ ఈ పరివర్తన అర్థం ఉందా?

504
00:39:29,610 --> 00:39:32,140
>> మీరు ఎల్లప్పుడూ ఉండాలని ఆయన సాధారణంగా, ఒక మంచి ఆలోచన

505
00:39:32,140 --> 00:39:34,290
మీరు చూడటానికి ఒక కొత్త సమస్య తగ్గించడానికి ప్రయత్నించండి.

506
00:39:34,290 --> 00:39:37,700
అది ఒక పాత సమస్య తెలిసిన కనిపిస్తోంది ఉంటే,

507
00:39:37,700 --> 00:39:39,590
పాత సమస్య మార్చడం ద్వారా ప్రయత్నించండి.

508
00:39:39,590 --> 00:39:41,950
మరియు మీరు పాత సమస్య ఉపయోగించే చేసిన అన్ని టూల్స్ ఉపయోగించవచ్చు ఉంటే

509
00:39:41,950 --> 00:39:46,450
కొత్త సమస్యను పరిష్కరించడానికి.

510
00:39:46,450 --> 00:39:49,010
కాబట్టి మూసివేయాలని, సాంకేతిక ఇంటర్వ్యూ సవాలు చేస్తారు.

511
00:39:49,010 --> 00:39:52,280
ఈ సమస్యలు బహుశా మరింత క్లిష్టమైన సమస్యలను కొన్ని

512
00:39:52,280 --> 00:39:54,700
మీరు, ఒక ఇంటర్వ్యూలో చూడవచ్చు ఆ

513
00:39:54,700 --> 00:39:57,690
మీరు నేను కవర్ అన్ని సమస్యలను అర్థం లేదు కాబట్టి, అది సరైందే.

514
00:39:57,690 --> 00:40:01,080
ఇవి సవాలు సమస్యలు ఉన్నాయి.

515
00:40:01,080 --> 00:40:03,050
ప్రాక్టీస్, ప్రాక్టీస్, ప్రాక్టీస్.

516
00:40:03,050 --> 00:40:08,170
నేను హాండ్ ఔట్ లో చాలా సమస్యలను ఇచ్చింది, కాబట్టి ఖచ్చితంగా ఆ తనిఖీ.

517
00:40:08,170 --> 00:40:11,690
మరియు మీ ఇంటర్వ్యూ న అదృష్టం. నా వనరులు, ఈ లింక్ వద్ద పోస్ట్

518
00:40:11,690 --> 00:40:15,220
మరియు నా సీనియర్ ఫ్రెండ్స్ ఒకటి, మాక్ సాంకేతిక ముఖాముఖిలు చేయడానికి అందించింది

519
00:40:15,220 --> 00:40:22,050
మీకు ఆసక్తి అయితే, ఇమెయిల్ ఆ ఇమెయిల్ చిరునామాకు యావో విల్.

520
00:40:22,050 --> 00:40:26,070
మీరు కొన్ని ప్రశ్నలు ఉంటే, మీరు నన్ను అడగవచ్చు.

521
00:40:26,070 --> 00:40:28,780
మీరు అబ్బాయిలు సాంకేతిక ఇంటర్వ్యూ సంబంధించిన నిర్దిష్ట ప్రశ్నలు ఉందా

522
00:40:28,780 --> 00:40:38,440
లేదా మేము ఇప్పటివరకు చూసిన ఏ సమస్యలు?

523
00:40:38,440 --> 00:40:49,910
సరే. Well, మీ ఇంటర్వ్యూ న అదృష్టం.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]