tsg1zzn

Amazon Coding Interview - firstNonRepeatingCharacter

Mar 1st, 2020
579
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. ; Purebasic 5.72
  4.  
  5. ; Go through input string
  6. ; Cases
  7. ;   Unseen character    ; Pigeonhole is 0, not in ll.
  8. ;   Seen character      ; Pigeonhole is *ptr to ll element
  9. ;   Seen again character ; Pigeonhole is 1
  10. ;   End of input
  11.  
  12. Procedure FirstUniqueCharacterO1n(s.s)
  13.   NewList Found.c()
  14.   Dim *Pigeonholes.Character(26)
  15.  
  16.   Protected L = Len(S)
  17.   For I = 0 To L-1
  18.     Pigeon.c = PeekC(@S+I*2) - 'a'
  19.     P = *Pigeonholes(Pigeon)
  20.     Select P
  21.       Case 0  ; Not seen before
  22.         LastElement(Found()) ; O(1)
  23.         *Pigeonholes(Pigeon) = AddElement(Found())
  24.         Found() = Pigeon + 'a'
  25.       Case 1  ; Known to be a duplicate, so out of the game
  26.       Default ; This is a new duplicate
  27.         ChangeCurrentElement(Found(), P) ; O(1)
  28.         DeleteElement(Found())
  29.         *Pigeonholes(Pigeon) = 1
  30.     EndSelect
  31.   Next
  32.   If FirstElement(Found()) ; O(1)
  33.     ProcedureReturn Found()
  34.   Else
  35.     ProcedureReturn '_'
  36.   EndIf
  37. EndProcedure
  38.  
  39. Debug Chr(FirstUniqueCharacterO1n("abcdef"))  ; a
  40. Debug Chr(FirstUniqueCharacterO1n("abcdefa"))  ; b
  41. Debug Chr(FirstUniqueCharacterO1n("bbcdcdefa"))  ; e
  42. Debug Chr(FirstUniqueCharacterO1n("aabb"))  ; _
  43. Debug Chr(FirstUniqueCharacterO1n(""))  ; _
  44.  
  45. Debug "----------------------------------"
  46.  
  47.  
  48. Procedure FirstUniqueCharacter(s.s)
  49.   Dim Pigeonholes.i(26)
  50.   Protected L = Len(S)
  51.   For I = 0 To L-1
  52.     Pigeon.c = PeekC(@S+I*2) - 'a'
  53.     Pigeonholes(Pigeon) + 1
  54.   Next
  55.   For I = 0 To L-1
  56.     Pigeon.c = PeekC(@S+I*2) - 'a'
  57.     If Pigeonholes(Pigeon) = 1
  58.       ProcedureReturn Pigeon + 'a'
  59.     EndIf
  60.   Next
  61.   ProcedureReturn '_'
  62. EndProcedure
  63.  
  64. Debug Chr(FirstUniqueCharacter("abcdef"))  ; a
  65. Debug Chr(FirstUniqueCharacter("abcdefa"))  ; b
  66. Debug Chr(FirstUniqueCharacter("bbcdcdefa"))  ;
  67. Debug Chr(FirstUniqueCharacter("aabb"))  ; _
  68. Debug Chr(FirstUniqueCharacter(""))  ; _
RAW Paste Data