Sachverhalt:
A.
Die Regionale Staatsanwaltschaft Bern-Mittelland eröffnete am 26. September 2017 gegen A._ und B._ 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 A._ gestützt auf <ref-law> mit Wirkung ab 4. Januar 2018 Rechtsanwalt Braunschweig als amtlicher Verteidiger beigeordnet. Dieser beantragte am 27. April 2018 die Feststellung, dass vor den Beweiserhebungen vom 17. Oktober 2017 ein Fall von notwendiger Verteidigung vorgelegen habe, weshalb die erhobenen Beweise (Ergebnisse der Hausdurchsuchung und Einvernahmeprotokoll vom 17. Oktober 2017 sowie allfällige Folgebeweise) als unverwertbar zu erklären und aus den Akten zu entfernen seien. Ferner seien die Untersuchungshandlungen, insbesondere 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 A._ am 14. Mai 2018 Beschwerde beim Obergericht des Kantons Bern und verlangte, die Verfügung der Staatsanwaltschaft sei aufzuheben und es sei festzustellen, dass ab dem 17. Oktober 2017 bzw. vor der Hausdurchsuchung von jenem Datum bis zum 3. Januar 2017 [recte: 2018] die Voraussetzungen der notwendigen Verteidigung erfüllt gewesen seien. Das Einvernahmeprotokoll vom 17. Oktober 2017, die Ergebnisse der Hausdurchsuchung sowie allfällige Folgebeweise und damit verbundene Schlussfolgerungen seien als unverwertbar zu erklären sowie in geeigneter Form aus den Akten zu weisen, eventuell zu schwärzen, und bis zum Abschluss des Verfahrens separat unter Verschluss zu halten.
Mit Beschluss vom 10. August 2018 hiess das Obergericht die Beschwerde teilweise gut und hob die Verfügung der Staatsanwaltschaft auf. Es ordnete an, dass das Protokoll der Einvernahme von A._ 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. Im Übrigen wies es die Beschwerde ab, soweit es darauf eintrat.
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, in 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 18 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 (z.B. eine kleine Frischhaltebox mit dem Schriftzug "3110", eine kleine Flasche Farbe, ein Paar schwarze Handschuhe mit Farbrückständen sowie ein Buch mit Skizzen, u.a. mit den Schriftzügen "3110" und "OGRS") 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 100 Sprayereien abgebildet seien. Aufgrund der Meldung eines Hauswarts und einer nachfolgenden Personenkontrolle des Beschwerdegegners und seines Kollegen B._ 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 das anlässlich der Hausdurchsuchung sichergestellte Skizzenbuch Motive enthalte, die den in der Fotodokumentation enthaltenen Sprayereien glichen, 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 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, was er anlässlich der Einvernahme zugegeben haben solle. Massgebend sei, dass er als beschuldigte Person einvernommen und ihm vorgehalten worden sei, als mutmasslicher (Mit-) Verursacher für 123 Sprayereien verantwortlich zu sein. Erforderlich sei somit eine ex-ante-Betrachtung. Entgegen der Auffassung der Staatsanwaltschaft sei von einer natürlichen Handlungseinheit auszugehen. Vermutlich seien in einer einzigen Nacht 61 Sprayereien entstanden, die darüber hinaus einen engen örtlichen Zusammenhang hätten. Zudem gehe es auch um Mittäterschaft oder Teilnahme. Wenn die Staatsanwaltschaft vorbringe, der Vorhalt des Fotodossiers dürfe nicht mit einem Tatverdacht in Bezug auf alle darin abgebildeten Graffitis gleichgesetzt werden, rüge sie die Sachverhaltsfestellung durch die Vorinstanz, die allerdings verbindlich sei. Er folge zudem der bundesgerichtlichen Auffassung in <ref-ruling> nicht. Im Übrigen habe das Bundesgericht auch als zulässig erkannt, verschiedene Straftaten in einem Gesamtzusammenhang zu betrachten und anstelle einer Geld- eine Freiheitsstrafe als Gesamtstrafe zu verhängen (Urteil 6B_157/2014 vom 26. Januar 2015 E. 3.1 mit Hinweisen). Folglich habe der Sachrichter die Möglichkeit, die kriminelle Energie trotz fehlender Handlungseinheit in einen Zusammenhang zu stellen.
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 B._ 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 Thierry Braunschweig, 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