Sachverhalt:
A.
Die Staatsanwaltschaft Zürich-Limmat führte gegen A._ eine Strafuntersuchung wegen Diebstahls, versuchten Diebstahls und Widerhandlungen gegen das Ausländergesetz (AuG; SR 142.20).
Anlässlich der ersten polizeilichen Befragung am 3. Dezember 2014 verlangte A._ den "Anwalt der ersten Stunde". Der beigezogene Verteidiger stellte im Namen des Beschuldigten während der Einvernahme ein Gesuch um Bestellung als amtlicher Verteidiger.
B.
Mit Strafbefehl vom 4. Dezember 2014 wurde A._ wegen Diebstahls eines Fingerrings im Sinne von Art. 139 Ziff. 1 StGB und rechtswidriger Einreise gemäss Art. 115 Abs. 1 lit. a AuG schuldig gesprochen und mit einer Geldstrafe von 45 Tagessätzen zu je Fr. 30.-- bestraft. Der Vollzug der Geldstrafe wurde aufgeschoben, unter Ansetzung einer Probezeit von drei Jahren. Das Strafverfahren wegen versuchten Diebstahls einer Armbanduhr wurde mit Verfügung vom 8. Dezember 2014 eingestellt.
Am 10. Dezember 2014 wies die Oberstaatsanwaltschaft des Kantons Zürich, Büro für amtliche Mandate, das Gesuch um Bestellung einer amtlichen Verteidigung ab. Die dagegen erhobene Beschwerde wies das Obergericht des Kantons Zürich am 5. Februar 2015 ab.
C.
Mit Beschwerde in Strafsachen vom 2. März 2015 an das Bundesgericht beantragt A._, der Beschluss des Obergerichts vom 5. Februar 2015 sei aufzuheben und ihm sei für das bei der Staatsanwaltschaft geführte Strafverfahren in der Person des Rechtsanwalts Patrick Iliev eine amtliche Verteidigung beizugeben und mit Fr. 1'201.40 (inkl. MwSt) zu entschädigen. Eventualiter sei die Sache zur Neubeurteilung an das Obergericht zurückzuweisen. In prozessualer Hinsicht wird um unentgeltliche Prozessführung und Verbeiständung ersucht.
Die Oberstaatsanwaltschaft schliesst auf Abweisung der Beschwerde. Die Staatsanwaltschaft Zürich-Limmat und das Obergericht verzichten auf eine Vernehmlassung.
Der Beschwerdeführer hält in der Replik an seinen Anträgen fest.
D.
Das Bundesgericht hat die Angelegenheit am 12. August 2015 öffentlich beraten.

Erwägungen:
1.
Der Beschluss des Obergerichts ist ein kantonal letztinstanzlicher Entscheid über die Gewährung der amtlichen Verteidigung in einem Strafverfahren. Dagegen ist die Beschwerde in Strafsachen zulässig (Art. 78 Abs. 1 und Art. 80 BGG). Es handelt sich um einen selbstständig eröffneten Zwischenentscheid, der einen nicht wieder gutzumachenden Nachteil bewirken kann (Art. 93 Abs. 1 lit. a BGG; <ref-ruling> E. 4 S. 338; <ref-ruling> E. 1.1 S. 283 f.; je mit Hinweisen). Obwohl das Strafverfahren inzwischen rechtskräftig abgeschlossen worden ist, hat der Beschwerdeführer ein aktuelles und praktisches Interesse an der Behandlung der Beschwerde, da die Frage der Entschädigung der bereits geleisteten anwaltlichen Leistungen noch offen ist (Art. 81 Abs. 1 BGG; <ref-ruling> E. 1.3.1 S. 77; <ref-ruling> E. 1.3 S. 276 mit Hinweisen). Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
2.
Der Beschwerdeführer macht geltend, der angefochtene Entscheid verletze Art. 132 Abs. 1 lit. b und Abs. 2 StPO, Art. 29 Abs. 3 BV sowie Art. 6 Ziff. 3 lit. c EMRK. Da er einen "Anwalt der ersten Stunde" verlangt habe, liege ein Anwendungsfall der Gebotenheit sui generis vor, weshalb sein Gesuch um Beigabe einer amtlichen Verteidigung bewilligt werden müsse. Im Übrigen handle es sich nicht um einen Bagatellfall und die besonderen tatsächlichen und rechtlichen Schwierigkeiten des Falls erforderten die Beigabe eines Rechtsbeistands.
2.1. Liegt kein Fall notwendiger Verteidigung gemäss Art. 130 StPO vor, ordnet die Verfahrensleitung eine amtliche Verteidigung an, wenn die beschuldigte Person nicht über die erforderlichen Mittel verfügt und die Verteidigung zur Wahrung ihrer Interessen geboten ist (Art. 132 Abs. 1 lit. b StPO). Zur Wahrung der Interessen der beschuldigten Person ist die Verteidigung namentlich geboten, wenn es sich nicht um einen Bagatellfall handelt und (kumulativ) der Straffall in tatsächlicher oder rechtlicher Hinsicht Schwierigkeiten bietet, denen die beschuldigte Person allein nicht gewachsen wäre (Art. 132 Abs. 2 StPO). Wie sich aus dem Wortlaut dieser Bestimmung ("namentlich") ergibt, ist nicht ausgeschlossen, dass die Gewährung der amtlichen Verteidigung aus anderen als den genannten Gründen geboten sein kann (Urteile 1B_746/2012 vom 5. März 2013 E. 2.5; 1B_477/2011 vom 4. Januar 2012 E. 2.2; 1B_605/2011 vom 4. Januar 2012 E. 2.2; je mit Hinweisen). Nach Art. 132 Abs. 3 StPO liegt ein Bagatellfall jedenfalls dann nicht mehr vor, wenn eine Freiheitsstrafe von mehr als 4 Monaten, eine Geldstrafe von mehr als 120 Tagessätzen oder gemeinnützige Arbeit von mehr als 480 Stunden zu erwarten ist.
2.2. Mit Art. 132 StPO wurde die bisherige bundesgerichtliche Rechtsprechung zu Art. 29 Abs. 3 BV und Art. 6 Ziff. 3 lit. c EMRK kodifiziert (<ref-ruling> E. 4.3 S. 119; Urteile 1B_170/2013 vom 30. Mai 2013 E. 4.3; 1B_448/2012 vom 17. Oktober 2012 E. 2.2; je mit Hinweisen). Demnach hat die bedürftige Partei Anspruch auf unentgeltliche Verbeiständung, wenn ihre Interessen in schwerwiegender Weise betroffen sind und der Fall in tatsächlicher und rechtlicher Hinsicht Schwierigkeiten bietet, die den Beizug eines Rechtsvertreters erforderlich machen. Falls das in Frage stehende Verfahren besonders stark in die Rechtsposition des Betroffenen eingreift, ist die Bestellung eines unentgeltlichen Rechtsvertreters grundsätzlich geboten. Droht zwar eine erhebliche, nicht aber eine besonders schwere Freiheitsbeschränkung, müssen zur relativen Schwere des Eingriffs besondere tatsächliche oder rechtliche Schwierigkeiten hinzukommen, denen der Betroffene - auf sich allein gestellt - nicht gewachsen wäre. Als besondere Schwierigkeiten, die eine Verbeiständung rechtfertigen können, fallen auch in der betroffenen Person liegende Gründe in Betracht, insbesondere deren Unfähigkeit, sich im Verfahren zurechtzufinden (<ref-ruling> E. 2.5.2 S. 232 f.; <ref-ruling> E. 2c/bb S. 51 f.; 275 E. 3a S. 276; je mit Hinweisen; Urteile 1B_257/2013 vom 28. Oktober 2013 E. 2.1; 1B_448/2012 vom 17. Oktober 2012 E. 2.3). Auch Sprachschwierigkeiten, mangelnde Vertrautheit mit dem schweizerischen Rechtssystem oder heikle Abgrenzungsfragen können tatsächliche oder rechtliche Schwierigkeiten begründen, welche, insgesamt betrachtet, für die sachliche Notwendigkeit einer amtlichen Verteidigung sprechen (<ref-ruling> E. 6.3 f. S. 38 f. mit Hinweisen; Urteile 1B_263/2013 vom 20. November 2013 E. 4.5; 1B_257/2013 vom 28. Oktober 2013 E. 2.2 f.; 1B_448/2012 vom 17. Oktober 2012 E. 2.3; 1B_195/2012 vom 7. Mai 2012 E. 2.4).
2.3. Der Beizug eines sog. Anwalts der ersten Stunde ist in der StPO speziell geregelt. Nach Art. 158 Abs. 1 lit. c StPO weisen die Polizei oder die Staatsanwaltschaft die beschuldigte Person zu Beginn der ersten Einvernahme in einer ihr verständlichen Sprache darauf hin, dass sie berechtigt ist, eine Verteidigung zu bestellen oder gegebenenfalls eine amtliche Verteidigung zu beantragen. Der Anspruch auf einen Anwalt der ersten Stunde wird in Art. 159 StPO gewährleistet: Die beschuldigte Person hat bei polizeilichen Einvernahmen im Ermittlungsverfahren das Recht, dass ihre Verteidigung anwesend sein und Fragen stellen kann (Abs. 1); bei polizeilichen Einvernahmen einer vorläufig festgenommenen Person hat diese zudem das Recht, mit ihrer Verteidigung frei zu verkehren (Abs. 2). Die Geltendmachung dieser Rechte gibt aber keinen Anspruch auf Verschiebung der Einvernahme (Abs. 3).
Bei der Beurteilung, ob der beigezogene Anwalt der ersten Stunde gegebenenfalls als amtlicher Verteidiger im Sinne von Art. 132 Abs. 1 lit. b StPO eingesetzt werden kann, ist es unerlässlich, eine ex ante Perspektive einzunehmen. Mit anderen Worten hat diese Beurteilung unter Würdigung der Umstände zu erfolgen, wie sie sich im Zeitpunkt der Aufbietung des Anwalts der ersten Stunde präsentierten. Steht nicht bereits zu Beginn fest, dass es sich klarerweise bloss um einen leichten und einfachen Straffall handelt, ist der aufgebotene Anwalt der ersten Stunde als amtlicher Verteidiger beizugeben. Sollte sich in einem späteren Verfahrensstadium herausstellen, dass die in den Abs. 2 und 3 des Art. 132 StPO genannten Voraussetzungen nicht erfüllt werden, ist das Mandat im Sinne von Art. 134 Abs. 1 StPO aufzuheben.
Wie nachfolgend aufgezeigt wird (vgl. E. 2.5), handelt es sich beim vorliegenden Fall nicht um einen leichten und einfachen Straffall: Nicht nur liessen die Verhältnisse im Zeitpunkt der Aufbietung des Anwalts der ersten Stunde mit einer gewissen Wahrscheinlichkeit darauf schliessen, dass kein Bagatellfall vorliegt; der Straffall warf darüber hinaus auch besondere Schwierigkeiten auf.
2.4. Die Vorinstanz beurteilte den vorliegenden Fall weder als einen solchen der notwendigen Verteidigung noch als Bagatellfall, womit die Verfahrensbeteiligten - jedenfalls vor Bundesgericht - übereinstimmen. Ebenso wurde die Bedürftigkeit des Beschwerdeführers im Rahmen der unentgeltlichen Verbeiständung für das Beschwerdeverfahren bejaht. Die Vorinstanz erwog indessen, die amtliche Verteidigung sei zur Wahrung der Interessen des Beschwerdeführers nicht geboten, weil der Straffall in tatsächlicher und rechtlicher Hinsicht keine Schwierigkeiten biete, denen der Beschwerdeführer alleine nicht gewachsen wäre. Die Vorwürfe seien beweismässig unproblematisch und auch für einen Laien leicht zu erfassen. Trotz einer teilweise einschlägigen Vorstrafe sei die Festlegung der Sanktion klar. Zwar könne die Frage nach dem Beginn der Ausführung der Tat im Sinne der "Schwellentheorie" in gewissen Fallkonstellationen durchaus Schwierigkeiten bereiten, jedoch seien diese vorliegend nicht ersichtlich, da es um einen einfachen Sachverhalt gehe. Ob dem Beschwerdeführer bei Anklageerhebung ein entsprechender Vorsatz hätte nachgewiesen werden können sei eine Frage der Beweiswürdigung, wobei er durchaus alleine hätte geltend machen können, dass er die Armbanduhr nicht habe stehlen wollen. Ferner könnten sprachliche Probleme mit Hilfe eines Dolmetschers ausgeräumt werden. Der Umstand, dass der Beschwerdeführer in der Lage gewesen sei, zu Beginn der polizeilichen Einvernahme einen Verteidiger einzufordern, spreche für seine Fähigkeit, sich im Justizsystem der Schweiz zurechtzufinden. Sein Argument, es handle sich um einen Anwendungsfall der Gebotenheit sui generis, weil er einen "Anwalt der ersten Stunde" verlangt habe und bedürftig sei, verfange nicht, könnten damit doch die gesetzlichen Voraussetzungen für die Bestellung einer amtlichen Verteidigung ausgehebelt werden. Dasselbe gelte für das Vorbringen, bei einer Nichtgenehmigung der amtlichen Verteidigung würde das Kostenrisiko auf den Pikettstrafverteidiger abgewälzt.
2.5. Es ist unbestritten, dass der Beschwerdeführer nicht über die erforderlichen Mittel verfügt und dass es sich um keinen Bagatellfall handelt. Strittig ist dagegen, ob das Strafverfahren in tatsächlicher oder rechtlicher Hinsicht Schwierigkeiten bietet, denen der Beschwerdeführer allein nicht gewachsen wäre. In dieser Hinsicht trifft zu, dass nicht davon ausgegangen werden kann, beim Vorwurf des (versuchten) Diebstahls und der rechtswidrigen Einreise liege generell ein komplexer Fall vor, der eine amtliche Verteidigung erforderlich macht. Vielmehr ist im Einzelfall auf die Schwierigkeiten des Straffalls und auf die persönlichen Fähigkeiten der beschuldigten Person abzustellen.
Beim Beschwerdeführer handelt es sich um einen georgischen Staatsangehörigen, der mit dem schweizerischen Justizsystem nicht vertraut ist, über keine juristischen Fachkenntnisse verfügt und der Verfahrenssprache nicht mächtig ist. Zwar trifft es zu, dass sprachliche Schwierigkeiten mit einem Dolmetscher überwunden werden können, weshalb diese für sich allein nicht für eine amtliche Verteidigung sprechen (vgl. Urteil 1B_500/2012 vom 3. Dezember 2012 E. 3.2.3). Entgegen der Auffassung der Vorinstanz kann aber aus dem Umstand, dass der Beschwerdeführer zu Beginn der polizeilichen Einvernahme sein Recht auf Beizug eines Verteidigers geltend gemacht hatte, nicht ohne Weiteres geschlossen werden, dieser vermöge sich im Justizsystem der Schweiz zurechtzufinden. Wie sich aus den Akten ergibt, ist vielmehr anzunehmen, dass er dieses Recht eingefordert hatte, weil er zuvor von der Kantonspolizei darauf aufmerksam gemacht worden war. Angesichts der persönlichen Fähigkeiten ist somit bereits bei geringen tatsächlichen oder rechtlichen Schwierigkeiten davon auszugehen, dass der Beschwerdeführer diesen, auf sich selbst gestellt, nicht gewachsen gewesen wäre.
Dem Obergericht ist insoweit zuzustimmen, als die Vorwürfe des (versuchten) Diebstahls und der rechtswidrigen Einreise in tatsächlicher Hinsicht für den Beschwerdeführer verständlich und die Beweiserhebungen erfassbar waren. Nicht gefolgt werden kann indessen seiner Auffassung, der Fall biete in rechtlicher Hinsicht keine Schwierigkeiten. Immerhin wurden dem Beschwerdeführer mehrere Vorfälle zur Last gelegt, was für sich alleine bereits eine nicht unerhebliche Komplexität darstellt. Einer davon umfasste den Vorwurf des versuchten Diebstahls einer Armbanduhr im Wert von Fr. 39'500.--. Der Beschwerdeführer wurde beschuldigt, die Uhr in einem Geschäft anprobiert und ständig belanglose Fragen gestellt zu haben, wohl in der Hoffnung, die Verkäuferin werde vergessen, dass er die Uhr noch am Handgelenk trage. Er habe sodann telefonieren müssen und dabei Anstalten gemacht, das Geschäft verlassen zu wollen, bevor er von der Verkäuferin auf die Uhr angesprochen worden sei. Daraufhin habe er sich noch einmal nach dem Preis erkundigt und gesagt, er müsse es sich überlegen, ehe er das Geschäft verlassen habe. Dass es sich hierbei - wie von der Vorinstanz ausgeführt - klarerweise um eine einfache Fallkonstellation handle, ist nicht offenkundig. Bei dieser Sachlage ist die Abgrenzung zwischen einer straflosen Vorbereitungshandlung und dem Beginn des Versuchsstadiums für einen juristischen Laien nicht leicht zu erfassen. Zudem wurde der subjektive Tatbestand bestritten, zu welchem neben dem Vorsatz ein Aneignungswille und eine Bereicherungsabsicht gehören. Dass diesbezüglich Unklarheiten bestanden, lässt sich auch aus dem Tathergang schliessen und ist im Übrigen der Einstellungsverfügung zu entnehmen, in der die Staatsanwaltschaft bemerkte, dem Beschuldigten könne trotz gewichtiger Verdachtsmomente letztlich nicht rechtsgenügend nachgewiesen werden, einen Diebstahlsversuch unternommen zu haben. Es ist daher nur schwerlich nachvollziehbar, wie der Beschwerdeführer, der über kein juristisches Fachwissen verfügt und mit dem hiesigen Justizsystem nicht vertraut ist, zu diesen für den Ausgang des Verfahrens entscheidenden Fragen kompetent hätte Stellung nehmen können. Im Übrigen kann aus dem Hinweis der Vorinstanz, der Nachweis des Vorsatzes bilde eine Frage der Beweiswürdigung - welche von Amtes wegen vorzunehmen ist - nicht abgeleitet werden, der Beschuldigte brauche keinen Anwalt (Urteil 1B_102/2012 vom 24. März 2012 E. 2.2 mit Hinweisen).
2.6. Nach dem Gesagten ist der Anspruch des Beschwerdeführers auf amtliche Verteidigung zu bejahen. Die Rüge der Verletzung von Art. 132 Abs. 1 lit. b StPO bzw. Art. 29 Abs. 3 BV und Art. 6 Ziff. 3 lit. c EMRK ist begründet. Wird die amtliche Verteidigung gewährt, erfolgt die Beigabe des Rechtsvertreters rückwirkend auf den Mandatsantritt hin (vgl. Urteil 1B_263/2013 vom 20. November 2013 E. 5) und erfasst somit auch die Leistungen als Anwalt der ersten Stunde (ebenso GUNHILD GODENZI, in: Kommentar zur Schweizerischen Strafprozessordnung, 2. Aufl. 2014, N. 23b zu Art. 159; DONATSCH/CAVEGN, Der Anspruch auf einen Anwalt zu Beginn der Strafuntersuchung, forumpoenale 2/2009, S. 107; NIKLAUS RUCKSTUHL, in: Basler Kommentar zur StPO, 2. Aufl. 2014, N. 31 zu Art. 159). Dies entspricht im Übrigen auch der Praxis im Kanton Zürich ( SCHLEGEL/WOHLERS, Der "Anwalt der ersten Stunde" in der Schweiz, StV 5/2012 S. 316; STEFAN HEIMGARTNER, Amtliche Mandate im Vorverfahren - Zürcher Praxis, forumpoenale 3/2012, S. 168).
Es kann folglich offen bleiben, ob ein Anwendungsfall der Gebotenheit sui generis vorliegt.
3.
Die Beschwerde ist gutzuheissen und der angefochtene Entscheid aufzuheben. Das Bundesgericht entscheidet reformatorisch (Art. 107 Abs. 2 BGG) und setzt Rechtsanwalt Patrick Iliev (rückwirkend auf den Mandatsantritt) als amtlichen Verteidiger ein.
Dem Ausgang des bundesgerichtlichen Verfahrens entsprechend sind keine Gerichtskosten zu erheben (Art. 66 Abs. 4 BGG). Der Kanton Zürich hat dem Beschwerdeführer für das kantonale Verfahren, einschliesslich der Leistungen des Anwalts der ersten Stunde, und für das Verfahren vor dem Bundesgericht eine angemessene Parteientschädigung zu bezahlen, die aus prozessökonomischen Gründen gesamthaft zu erheben ist (Art. 68 Abs. 2 und 5 BGG). Der betreffende Honoraranspruch wird dem amtlichen Verteidiger persönlich zugesprochen (vgl. Art. 64 Abs. 2 Satz 2 BGG). Damit wird das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und der angefochtene Entscheid vom 5. Februar 2015 des Obergerichts des Kantons Zürich, III. Strafkammer, wird aufgehoben. Rechtsanwalt Patrick Iliev wird für das Verfahren vor der Staatsanwaltschaft Zürich-Limmat als amtlicher Verteidiger des Beschwerdeführers bestellt.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zürich hat Rechtsanwalt Patrick Iliev für das kantonale Verfahren und das Verfahren vor Bundesgericht mit insgesamt Fr. 4'000.-- zu entschädigen.
4.
Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft Zürich-Limmat, der Oberstaatsanwaltschaft und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 12. August 2015
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Pedretti