Sachverhalt:
A.
Die Regionale Staatsanwaltschaft Bern-Mittelland eröffnete am 26. September 2017 gegen B._ und A._ eine Strafuntersuchung wegen Sachbeschädigung (Farbsprayereien), begangen in der Zeit vom 22. Juli 2017 bis September 2017. Gleichentags ordnete sie eine Hausdurchsuchung am Wohnort der beiden Beschuldigten an, die am frühen Morgen des 17. Oktobers 2017 durchgeführt wurde. Am 1. Februar 2018 wurde B._ gestützt auf <ref-law> mit Wirkung ab 3. Januar 2018 Rechtsanwalt Baumberger als amtlicher Verteidiger beigeordnet. Dieser beantragte am 27. April 2018 die Feststellung, dass spätestens ab 16. Oktober 2017 ein Fall von notwendiger Verteidigung vorgelegen habe, weshalb das Protokoll der delegierten Einvernahme vom 17. Oktober 2017 sowie alle Folgebeweise aus den Akten zu entfernen seien. Zu entfernen bzw. zu schwärzen seien zudem alle weiteren Dokumente in den Akten, in denen aus dem Einvernahmeprotokoll wörtlich oder sinngemäss zitiert oder in denen daraus Schlüsse gezogen würden. Ferner sei die Einvernahme in Anwesenheit der Verteidigung zu wiederholen.
Mit Verfügung vom 1. Mai 2018 stellte die Staatsanwaltschaft fest, es liege nach wie vor ein Fall von gebotener Verteidigung gemäss <ref-law> und nicht ein solcher von notwendiger Verteidigung gemäss <ref-law> vor, und verneinte ein Beweisverwertungsverbot.
Dagegen erhob B._ am 14. Mai 2018 Beschwerde beim Obergericht des Kantons Bern und verlangte, die Verfügung der Staatsanwaltschaft sei aufzuheben. Im Übrigen wiederholte er im Wesentlichen seine gegenüber der Staatsanwaltschaft gestellten Anträge.
Mit Beschluss vom 10. August 2018 hiess das Obergericht die Beschwerde gut, soweit es darauf eintrat, und hob die Verfügung der Staatsanwaltschaft auf. Es ordnete an, dass das Protokoll der Einvernahme von B._ vom 17. Oktober 2017 aus den Akten zu entfernen und bis zum rechtskräftigen Abschluss des Verfahrens unter separatem Verschluss zu halten und danach zu vernichten sei. Ferner seien auch sämtliche Dokumente in den Verfahrensakten, in denen wörtlich oder sinngemäss aus dieser Einvernahme zitiert werde oder aus denen Rückschlüsse auf diese Einvernahme gezogen werden könnten, zu entfernen bzw. zu schwärzen.
B.
Mit Beschwerde in Strafsachen an das Bundesgericht vom 11. September 2018 beantragt die Generalstaatsanwaltschaft des Kantons Bern im Wesentlichen, der Beschluss des Obergerichts sei aufzuheben und das Einvernahmeprotokoll bei den Akten zu belassen. Eventualiter sei die Sache zur neuen Beurteilung an das Obergericht zurückzuweisen.
Das Obergericht hat auf eine Vernehmlassung verzichtet. Der Beschwerdegegner beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei.

Erwägungen:
1.
1.1. Beim angefochtenen Urteil handelt es sich um einen kantonal letztinstanzlichen Entscheid in einer Strafsache (Art. 78 Abs. 1 und Art. 80 BGG).
1.2. Der Staatsanwaltschaft steht das Beschwerderecht in Strafsachen nach Art. 81 Abs. 1 lit. b Ziff. 3 BGG grundsätzlich ohne Einschränkung zu (<ref-ruling> E. 1.4 S. 39 ff. mit Hinweisen). Sie hat insbesondere auch dann ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids, wenn sie sich gegen die Entfernung von Beweismitteln aus den Akten zur Wehr setzt (Urteil 1B_363/2013 vom 12. Mai 2015 E. 1, nicht publ. in <ref-ruling>). Allerdings ist das Beschwerderecht nur in dem Umfang zu bejahen, als das Obergericht das Rechtsmittel des Beschwerdegegners gutgeheissen hat. Insoweit, als die Beschwerdeführerin mit ihrem Antrag darüber hinausgeht, ist darauf nicht einzutreten.
1.3. In Kantonen, bei denen eine staatsanwaltliche Behörde für die Strafverfolgung aller Straftaten im ganzen Kantonsgebiet zuständig ist, hat nur diese Behörde die Beschwerdeberechtigung gemäss Art. 81 Abs. 1 lit. b Ziff. 3 BGG (<ref-ruling> E. 1.5.2 S. 200). Dies trifft für die hier beschwerdeführende Berner Generalstaatsanwaltschaft zu (Urteil 1B_160/2017 vom 19. Juli 2017 E. 1.2 mit Hinweis).
1.4. Beim angefochtenen Entscheid handelt es sich um einen Zwischenentscheid gemäss <ref-law>, gegen den die Beschwerde nur zulässig ist, wenn er unter anderem einen nicht wieder gutzumachenden Nachteil bewirken kann (Abs. 1 lit. a). Dabei muss es sich im Bereich der Beschwerde in Strafsachen um einen Nachteil rechtlicher Natur handeln. Ein lediglich tatsächlicher Nachteil, wie die Verlängerung oder Verteuerung des Verfahrens, genügt nicht (<ref-ruling> E. 2.2 S. 287; 289 E. 1.2 S. 291; <ref-ruling> E. 1.3.1 S. 318 mit Hinweisen).
Wenn die kantonale Beschwerdeinstanz während des Vorverfahrens ein Beweismittel als unverwertbar erachtet und nach <ref-law> seine Entfernung aus den Akten anordnet, droht der Staatsanwaltschaft praxisgemäss dann ein nicht wieder gutzumachender Nachteil, wenn dadurch die Weiterführung des Strafverfahrens verunmöglicht oder zumindest stark erschwert wird. Dies trifft nicht zu, wenn der Staatsanwaltschaft andere Untersuchungsmassnahmen zur Weiterführung des Strafverfahrens und gegebenenfalls Anklageerhebung zur Verfügung stehen. In jedem Fall ist es Sache der Staatsanwaltschaft darzutun, dass die Voraussetzungen von <ref-law> erfüllt sind (<ref-ruling> E. 2.4 S. 287 f.; 289 E. 1.4 S. 292; Urteil 1B_5/2016 vom 23. Mai 2016 E. 2.3; je mit Hinweisen).
Die Staatsanwaltschaft legt dar, der Beschwerdegegner habe in der Einvernahme vom 17. Oktober 2017 zugegeben, für 21 Graffitis verantwortlich zu sein. Mit dem Verlust dieser belastenden Aussagen werde die Weiterführung des Strafverfahrens in ganz erheblichem Ausmass erschwert. Andere Untersuchungsmassnahmen stünden nicht zur Verfügung. Die bei der Hausdurchsuchung sichergestellten Gegenstände (Spraydosen, Tag-Stifte, Handschuhe und Skizzen) reichten nicht aus, um nachzuweisen, dass der Beschwerdegegner illegal gesprayt habe. Auch die Wiederholung der Einvernahme könne nicht als erfolgversprechende Untersuchungsmassnahme angesehen werden. Nachdem sich der Beschwerdegegner mit Nachdruck für die Entfernung des Einvernahmeprotokolls aus den Akten eingesetzt habe, sei nicht anzunehmen, dass er seine Aussagen wiederhole.
Gestützt auf diese Darlegungen, die vom Beschwerdegegner nicht bestritten werden, ist von einem nicht wieder gutzumachenden Nachteil auszugehen. Zwar erscheint nicht völlig ausgeschlossen, dass die Staatsanwaltschaft mit anderen Untersuchungsmassnahmen die Delikte ebenfalls aufklären könnte, doch sind solche gegenwärtig nicht konkret erkennbar. Insbesondere scheint in dieser Hinsicht die von der Polizei erstellte Fotodokumentation mit über 100 Sprayereien nicht erfolgversprechend. Durch den Verlust der belastenden Aussagen würde die Weiterführung des Strafverfahrens deshalb stark erschwert.
1.5. Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
2.
2.1. Die beschuldigte Person muss unter anderem verteidigt werden, wenn ihr eine Freiheitsstrafe von mehr als einem Jahr droht (<ref-law>). Ausschlaggebend ist nicht das abstrakt höchstmögliche, sondern das konkret zu erwartende Strafmass (<ref-ruling> E. 2.4.3 S. 170). Liegt ein Fall notwendiger Verteidigung vor, so achtet die Verfahrensleitung darauf, dass unverzüglich eine Verteidigung bestellt wird (<ref-law>). Sind die Voraussetzungen notwendiger Verteidigung bei Einleitung des Vorverfahrens erfüllt, so ist die Verteidigung nach der ersten Einvernahme durch die Staatsanwaltschaft, jedenfalls aber vor Eröffnung der Untersuchung, sicherzustellen (<ref-law>). Wurden in Fällen, in denen die Verteidigung erkennbar notwendig gewesen wäre, Beweise erhoben, bevor eine Verteidigerin oder ein Verteidiger bestellt worden ist, so ist die Beweiserhebung nur gültig, wenn die beschuldigte Person auf ihre Wiederholung verzichtet (<ref-law>; vgl. zum Ganzen Urteil 6B_178/2017 vom 25. Oktober 2017 E. 2.2.1 und 2.6 mit Hinweisen, in: Pra 2018 Nr. 21 S. 192).
2.2. Das Obergericht hielt fest, die Polizei habe dem Beschwerdegegner am 17. Oktober 2017 eine Fotodokumentation vorgelegt, in der über 120 Sprayereien abgebildet seien. Aufgrund der Meldung eines Hauswarts und einer nachfolgenden Personenkontrolle des Beschwerdegegners und seines Kollegen A._ am 25. Juli 2017 könne angenommen werden, dass die Polizei ein besonderes Augenmerk auf die beiden gerichtet hatte. Angesichts der sich im Fotodossier wiederholenden Schriftzüge ("OGRS" und "3110") und derer auffallenden Ähnlichkeiten sei gar davon auszugehen, dass sie minutiös über Monate hinweg die Sprayereien in Münsingen dokumentiert und analysiert habe. Da die anlässlich der Hausdurchsuchung sichergestellten Skizzen Motive enthielten, die auch auf den in der Fotodokumentation enthaltenen Sprayereien zu sehen seien, und aufgrund der zeitlichen Abfolge von Hausdurchsuchung und anschliessender Einvernahme könne nicht ernsthaft bezweifelt werden, dass die Polizei den Beschwerdeführer schon vor den Beweiserhebungen vom 17. Oktober 2017 im Verdacht gehabt hatte, eine Vielzahl von Sachbeschädigungen begangen zu haben. Sie habe ihm bereits Schriftzüge zugeordnet gehabt. Die Polizei habe ihn somit verdächtigt, (Mit-) Verursacher von über 100 Farbsprayereien gewesen zu sein. Ob die von der Staatsanwaltschaft angenommene durchschnittliche Schadenshöhe von Fr. 1'000.-- pro Fall zu tief sei, könne offenbleiben. Ausgehend von den staatsanwaltschaftlichen Annahmen habe sich der Deliktsvorwurf bereits vor den Beweiserhebungen vom 17. Oktober 2017 auf einen Gesamtschaden von über Fr. 100'000.-- belaufen. Somit sei schon vor jenem Zeitpunkt objektiv erkennbar gewesen, dass eine Strafe von mindestens einem Jahr zur Diskussion stehen könnte, zumal bereits eine relativ entfernte Möglichkeit der Verurteilung zu einer Freiheitsstrafe von mehr als einem Jahr genüge. Dass der Beschwerdegegner jung und nicht vorbestraft sei, ändere daran nichts.
2.3. Die Staatsanwaltschaft rügt eine Verletzung von <ref-law>. Sie bringt vor, die Schadensbeträge dürften nur dann zusammengezählt werden, wenn die einzelnen Sachbeschädigungen in einer natürlichen Handlungseinheit begangen worden wären. Dies sei hier nicht der Fall. Die vom Beschwerdegegner in unregelmässigen Abständen an willkürlich ausgewählten Standorten angebrachten Zahlen- und Buchstabenkombinationen könnten nicht als einheitliches Geschehen betrachtet werden. Ihm drohe also höchstens eine Verurteilung wegen mehrfacher Sachbeschädigung (<ref-law>). Selbst wenn einzelne Sprayereien als Einheitstat zu betrachten seien, so würde sich diese höchstens im Grenzbereich zum qualifizierenden Merkmal des grossen Schadens im Sinne von <ref-law> bewegen. Von der blossen Anzahl abgelichteter Graffitis im von der Polizei zusammengestellten und dem Beschwerdegegner vorgehaltenen Fotodossier könne nicht per se auf einen Fall der notwendigen Verteidigung geschlossen werden. Insbesondere könne daraus nicht abgeleitet werden, dass die Polizei vor der Einvernahme davon ausgegangen sei, der Beschwerdegegner komme als alleiniger Urheber dieser 125 Graffitis in Betracht. Sprayer würden meist in losen Gruppen operieren, die mit Vorzug bestimmte für sie typische Zeichen verwendeten. So hätten die beiden Beschuldigten vor allem "OGRS" und "3110" (die Postleitzahl von Münsingen) verwendet. Es sei gut denkbar, dass noch weitere Sprayer zur "OGRS/3110"-Gruppe zählten und zur Verbreitung dieser Erkennungszeichen beitrugen. Auch die Vorinstanz habe anerkannt, dass der Beschwerdegegner bloss als " (Mit-) Verursacher" in Frage komme. Den beiden Beschuldigten sei zudem dasselbe Fotodossier vorgehalten worden, insofern relativiere sich dessen Umfang.
Zu berücksichtigen sei die Art der polizeilichen Ermittlungstätigkeit bei der Bekämpfung von Sprayereien. Anzeigen gegen unbekannte Täterschaft würden gesammelt und nach spezifischen Erkennungsmerkmalen der Graffitis gruppiert und geordnet. Werde ein Sprayer erwischt, so könne anhand der im konkreten Fall festgestellten Eigenheiten (z.B. verwendete Zahlen- oder Buchstabenfolge, kombiniert mit örtlicher und zeitlicher Eingrenzung) ein auf den jeweiligen Fall abgestimmtes Fotodossier zusammengestellt werden. Dies erkläre, warum ein solches Fotodossier je nach Fall umfangreicher ausfallen könne, insbesondere wenn es sich um in der Sprayerszene beliebte und häufig verwendete Buchstaben- und Zahlenkombinationen handle, wie z.B. "A.C.A.B.", die Postleitzahl oder die Telefonvorwahl. In einem ersten Schritt gehe es dann bei der Befragung vor allem um eine Eingrenzung. Der Vorhalt des Fotodossiers dürfe deshalb nicht mit einem gegenüber dem Beschwerdegegner gehegten Tatverdacht für alle darin abgebildeten Graffitis gleichgesetzt werden.
Vor diesem Hintergrund und angesichts des Umstands, dass der Beschwerdegegner noch jung, in Ausbildung (3. Lehrjahr) und nicht vorbestraft sei, werde nur eine Geldstrafe in Betracht kommen. Dabei sei auch zu berücksichtigen, dass es gemäss der Praxis des Bundesgerichts unter dem geltenden Recht nicht möglich sei, eine Gesamtfreiheitsstrafe aus mehreren Geldstrafen zu bilden (<ref-ruling> E. 3.6 S. 237 f. mit Hinweisen).
2.4. Der Beschwerdegegner bringt vor, es sei unerheblich, ob er als "alleiniger Urheber" in Betracht komme. Bei einer Mittäterschaft erfolge eine wechselseitige Zurechnung der Tatbeiträge. Vorliegend reiche es deshalb, wenn der Verdacht auf eine (Mit-) Urheberschaft an den vorgehaltenen Sprayereien bestanden habe. Soweit das Obergericht einen konkreten Tatverdacht zum relevanten Zeitpunkt bejaht habe, sei diese Sachverhaltsfeststellung für das Bundesgericht verbindlich. Es käme einer Umgehung der Bestimmungen zur notwendigen Verteidigung gleich, wenn die Strafverfolgungsbehörden Verfahrensbeteiligte zu konkreten Vorwürfen zwar formell als beschuldigte Person befragen könnten, ihnen aber nicht alle damit einhergehenden Rechte gewähren müssten. Statt als Auskunftsperson habe die Staatsanwaltschaft ihn als Beschuldigten befragt und bei jeder einzelnen Sprayerei die Frage gestellt, ob er der Urheber sei. Damit habe sie zum Ausdruck gebracht, dass sie ihn als Urheber tatsächlich in Betracht ziehe. Weiter deuteten die Akten auf eine natürliche Handlungseinheit hin. Vermutlich seien in einer einzigen Nacht 65 Sprayereien entstanden, die darüber hinaus einen engen örtlichen Zusammenhang hätten. Im Übrigen sei die Polizei selber ausdrücklich von einem grossen Schaden im Sinne von <ref-law> ausgegangen, als sie am 17. Oktober 2017 eine erkennungsdienstliche Erfassung und die Erstellung eines DNA-Profils beantragte. Weiter sei die Annahme eines durchschnittlichen Schadens von Fr. 1'000.-- mit grosser Wahrscheinlichkeit zu tief, wie auch der Rechtsprechung entnommen werden könne (z.B. Urteil 1P.216/2006 vom 3. Juli 2006 E. 3.4). Selbst bei der Annahme einer mehrfachen Sachbeschädigung im Sinne von <ref-law> komme eine Freiheitsstrafe von über einem Jahr in Betracht. Im Übrigen habe das Bundesgericht auch als zulässig erkannt, die verschiedenen Straftaten in einem Gesamtzusammenhang zu betrachten und anstelle einer Geld- eine Freiheitsstrafe als Gesamtstrafe zu verhängen (Urteil 6B_523/2018 vom 23. August 2018 E. 1.2.2 mit Hinweisen).
2.5. Nach <ref-law> wird, wer eine Sache, an der ein fremdes Eigentums-, Gebrauchs- oder Nutzniessungsrecht besteht, beschädigt, zerstört oder unbrauchbar macht, auf Antrag mit Freiheitsstrafe bis zu drei Jahren oder Geldstrafe bestraft. Hat der Täter einen grossen Schaden verursacht, so kann gemäss Abs. 3 Satz 1 auf Freiheitsstrafe von einem Jahr bis zu fünf Jahren erkannt werden. Gemäss der Rechtsprechung ist es sachgerecht, einen Schaden von mindestens Fr. 10'000.-- als gross im Sinne dieser Bestimmung zu bezeichnen (<ref-ruling> E. 4.3.1 S. 118 f. mit Hinweisen).
2.6. Angesichts des Umstands, dass die Staatsanwaltschaft bereits am 26. September 2017 eine Strafuntersuchung gegen den Beschwerdegegner und A._ wegen Sachbeschädigung eröffnet und vor der fraglichen Einvernahme eine Hausdurchsuchung durchgeführt hatte, kann ohne Weiteres davon ausgegangen werden, dass grundsätzlich ein objektiver Tatverdacht auf Sachbeschädigung bestand. Umstritten ist, auf welche Sprayereien sich dieser erstreckte. Die Staatsanwaltschaft ist der Auffassung, die Erstellung einer Fotodokumentation bedeute nicht, dass ein Tatverdacht für alle darin abgebildeten Graffitis bejaht werden könne, weil Sprayer meist in losen Gruppen operierten und mit Vorzug bestimmte für sie typische Zeichen verwendeten. Dabei lässt sie ausser Betracht, dass die in den Akten befindliche Fotodokumentation klarerweise für das vorliegende Strafverfahren zusammengestellt und der Beschwerdegegner als beschuldigte Person aufgefordert wurde, zu jeder darin abgebildeten Sprayerei Auskunft zu geben. Dazu hätte sie keinen Anlass gehabt, wenn nicht angesichts der gemeinsamen Merkmale der Sprayereien und des örtlichen Zusammenhangs ein objektiver Tatverdacht bestanden hätte.
2.7. Zu prüfen bleibt, ob aufgrund des Schadens und der weiteren Umstände anzunehmen war, dass dem Beschwerdegegner eine Freiheitsstrafe von über einem Jahr drohte. Das Obergericht hat sich nicht mit der von den Parteien in diesem Zusammenhang aufgeworfenen Frage befasst, ob bzw. inwiefern bezüglich der einzelnen Sprayereien von einer natürlichen Handlungseinheit auszugehen ist bzw. im Zeitpunkt der Einvernahme auszugehen war. Es hat stattdessen von einem Gesamtschaden in der Höhe von mehr als Fr. 100'000.-- automatisch auf eine drohende Freiheitsstrafe von mehr als einem Jahr geschlossen (vgl. zur Berechnung des grossen Schadens bei natürlicher Handlungseinheit PHILIPPE WEISSENBERGER, in: Basler Kommentar, Strafrecht II, 3. Aufl. 2013, N. 104-107 zu <ref-law>). Dies ist insoweit nachvollziehbar, als der Richter auch im Rahmen des Grundtatbestands von <ref-law> eine Freiheitsstrafe von über einem Jahr aussprechen kann, wenn Unrechts- und Schuldgehalt der Tat dies erfordern (<ref-ruling> E. 4.3.1 S. 119). Angesichts der grossen Anzahl der Sprayereien und des damit verbundenen, ausserordentlich grossen Schadens ist die Einschätzung des Obergerichts jedenfalls nicht zu beanstanden. Immerhin kann aber zusätzlich festgehalten werden, dass gestützt auf die in der Fotodokumentation enthaltenen Datumsangaben anzunehmen ist, dass jeweils mehrere Sprayereien in einem eigentlichen Streifzug entstanden sind. Dass der Beschwerdegegner jung und nicht vorbestraft ist, erachtete das Obergericht schliesslich zu Recht als nicht ausschlaggebend.
2.8. Das Obergericht hat somit kein Bundesrecht verletzt, wenn es davon ausging, dass im Zeitpunkt der Einvernahme des Beschwerdegegners eine Freiheitsstrafe von über einem Jahr drohte. Die Rüge der Verletzung von <ref-law> ist unbegründet.
3.
Die Beschwerde ist aus diesen Gründen abzuweisen, soweit darauf einzutreten ist.
Bei diesem Verfahrensausgang sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Dem Rechtsvertreter des Beschwerdegegners ist eine angemessene Parteientschädigung zuzusprechen (Art. 68 Abs. 1-2 BGG). Dessen Gesuch um unentgeltliche Rechtspflege wird damit hinfällig.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Bern hat den Rechtsvertreter des Beschwerdegegners, Rechtsanwalt Silvano Baumberger, mit Fr. 1'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, Beschwerdekammer in Strafsachen, schriftlich mitgeteilt.
Lausanne, 6. Dezember 2018
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Merkli
Der Gerichtsschreiber: Dold