Showing posts with label Yelp. Show all posts
Showing posts with label Yelp. Show all posts

Saturday, July 15, 2017

126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
  1. Only one letter can be changed at a time
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]
Note:
  • Return an empty list if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.
UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.



Solution:

We first apply BFS to construct a adjacent list storing the mapping of each node and its neighbors.

In the BFS process, we also create a distance map which maps the shortest distance of each node from start.

Having these information, we can then apply DFS to add all valid path.

In each recursion step, we check if the distance of the neighbor of the current node has exactly one steps further than the current node, it is a valid candidate.



Code:


public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> dict = new HashSet<>(wordList);
        HashMap<String, Integer> distance = new HashMap<>();
        HashMap<String, List<String>> adj = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dict.add(beginWord);
        bfs(beginWord, endWord, dict, adj, distance);    
        path.add(beginWord);
        dfs(beginWord, endWord, result, path, dict, adj, distance);
        return result;
    }
    
    public List<String> getNeighbor(String word, HashSet<String> dict) {
        List<String> result = new ArrayList<>();
        char[] arr = word.toCharArray();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == c) {
                    continue;
                }
                char ch = arr[i];
                arr[i] = c;
                if (dict.contains(String.valueOf(arr))) {
                    result.add(String.valueOf(arr));
                }
                arr[i] = ch;
            }
        }
        return result;
    }
    
    public void bfs(String start, 
                    String end, 
                    HashSet<String> dict, 
                    HashMap<String, List<String>> adj, 
                    HashMap<String, Integer> distance) {
        
        for (String word : dict) {
            adj.put(word, new ArrayList<String>());
        }
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        distance.put(start, 0);
        while (!queue.isEmpty()) {
            String curr = queue.poll();
            int level = distance.get(curr);
            List<String> neighbor = getNeighbor(curr, dict);
            for (String nei : neighbor) {
                adj.get(curr).add(nei);
                if (!distance.containsKey(nei)) {
                    distance.put(nei, level + 1);
                    if (!end.equals(nei)) {
                        queue.offer(nei);
                    }
                }
            }
        }
    }
    
    public void dfs(String curr,
                    String end, 
                    List<List<String>> result, 
                    List<String> path, 
                    HashSet<String> dict, 
                    HashMap<String, List<String>> adj, 
                    HashMap<String, Integer> distance) {
        
        if (curr.equals(end)) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (String nei : adj.get(curr)) {
            path.add(nei);
            if (distance.containsKey(nei) && distance.get(nei) == distance.get(curr) + 1) {
                dfs(nei, end, result, path, dict, adj, distance);
            }
            path.remove(path.size() - 1);
        }
    }
}

Saturday, June 10, 2017

207. Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.
Hints:
  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.



Solution:

This is a topological order question.

It asks whether the courses can be formed a topological order.

Therefore we use a count variable to store the number of courses that can form such order.

If it equals to the total number of courses, we return true.



Code:


public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] adj = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        int[] degree = new int[numCourses];
        for (int[] pair : prerequisites) {
            int courseFrom = pair[1];
            int courseTo = pair[0];
            adj[courseFrom].add(courseTo);
            degree[courseTo]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                queue.offer(i);
            }
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for (int nei : adj[course]) {
                degree[nei]--;
                if (degree[nei] == 0) {
                    queue.offer(nei);
                }
            }
        }
        return count == numCourses;
    }
}

Tuesday, June 6, 2017

218. The Skyline Problem

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skylineformed by these buildings collectively (Figure B).
BuildingsSkyline Contour
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
Notes:
  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li. 
  • The output list must be sorted by the x position. 
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]



Solution:

1. Create height coordinates. We use negative value to denote a start point, and positive value to denote an end point.

2. Sort the heights. 3 corner cases: same start, same end, and end == start.

3. Create a max heap with initial value 0.

4. Go through the heights.

a). If it is a start point, put it into the heap. If the top of heap changes, this point with the new heap value (itself) should be in the final result.

b). If it is an end point,  remove it from the heap. If the top of heap changes, this point with the new heap top value should be in the final result.

Detailed explanation check out this Youtube Video.

TreeMap support O(logn) on insert and remove operation.

The time complexity is O(nlogn) and the space complexity is O(n).



Code:


public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> heights = new ArrayList<>();
        for (int[] building : buildings) {
            heights.add(new int[] {building[0], -building[2]});
            heights.add(new int[] {building[1], building[2]});
        }
        Collections.sort(heights, new Comparator<int[]>() {
            public int compare(int[] x, int[] y) {
                if (x[0] == y[0]) {
                    return x[1] - y[1];
                }
                return x[0] - y[0];
            }
        });
        List<int[]> result = new ArrayList<>();
        TreeMap<Integer, Integer> map = new TreeMap<>(Collections.reverseOrder());
        map.put(0, 1);
        int prevHeight = 0;
        for (int[] height : heights) {
            if (height[1] < 0) {
                Integer count = map.get(-height[1]);
                count = count == null ? 1 : count + 1;
                // Use a count to store the frequency of this height.
                // The reason is that map cannot store duplicate items.
                map.put(-height[1], count);
            }
            else {
                Integer count = map.get(height[1]);
                if (count == 1) {
                    map.remove(height[1]);
                }
                else {
                    map.put(height[1], count - 1);
                }
            }
            int currHeight = map.firstKey();
            if (currHeight != prevHeight) {
                result.add(new int[] {height[0], currHeight});
                prevHeight = currHeight;
            }
        }
        return result;
    }
}




public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        List<int[]> heights = new ArrayList<>();
        for (int[] building : buildings) {
            heights.add(new int[] {building[0], -building[2]});
            heights.add(new int[] {building[1], building[2]});
        }
        Collections.sort(heights, new Comparator<int[]>() {
            public int compare(int[] x, int[] y) {
                if(x[0] == y[0]) {
                    return x[1] - y[1];
                }
                return x[0] - y[0];
            }    
        });
        Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(0);
        int prev = 0;
        for (int[] height : heights) {
            if (height[1] < 0) {
                maxHeap.offer(-height[1]);
            }
            else {
                maxHeap.remove(height[1]);
            }
            int curr = maxHeap.peek();
            if (curr != prev) {
                result.add(new int[] {height[0], curr});
                prev = curr;
            }
        }
        return result;
    }
}

Tuesday, May 30, 2017

127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWordto endWord, such that:
  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.
UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.



Solution:

Use BFS.

In each level, we try to find all one edit distance word from the current word.

For each one edit distance word, we check if it is the endWord.

If it is the endWord, we return the level.

If it is not, we check if it is in the word list. If so, we add it in queue.



Code:


public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (beginWord.equals(endWord)) {
            return 1;
        }
        HashSet<String> dict = new HashSet<>();
        for (String word : wordList) {
            dict.add(word);
        }
        if (!dict.contains(endWord)) {
            return 0;
        }
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        dict.remove(beginWord);
        
        int level = 2;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                for (int j = 0; j < word.length(); j++) {
                    char[] chars = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String neighbor = new String(chars);
                        if (neighbor.equals(endWord)) {
                            return level;
                        }
                        if (dict.remove(neighbor)) {
                            queue.offer(neighbor);
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
}

Saturday, May 27, 2017

380. Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.
  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();



Solution:

Use a HashMap and an ArrayList.

ArrayList is to store the elements and the HashMap is to mapping the position of the element.

To insert an element, simply check if its already in the map. If not, we append it to the ArrayList and update the HashMap.

To remove an element, we use HashMap to find its location, swap with the end of the ArrayList, and remove it. Don't forget to update the mapping of the end element which swapped location.



Code:


public class RandomizedSet {

    ArrayList<Integer> list;
    HashMap<Integer, Integer> map;
    java.util.Random rand = new java.util.Random();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int key = list.get(list.size() - 1);
        int index = map.get(val);
        Collections.swap(list, index, list.size() - 1);
        map.put(key, index);
        map.remove(list.get(list.size() - 1));
        list.remove(list.size() - 1);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size())); 
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Monday, May 8, 2017

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.



Solution:

Method 1:

We set the entire string of the first input to be prefix.

Go through the string array, check if the current string has such prefix. If not, decrease the length of prefix and try again.

After going through the string array, the prefix left is the largest common prefix we are looking for.



Code:


public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String pre = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(pre) != 0) {
                pre = pre.substring(0, pre.length() - 1);
            }
        }
        return pre;
    }
}



Method 2: sort

We sort the string array first. Then check the first and last string. The prefix of these two is the longest one we are looking for.



Code:


public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Arrays.sort(strs);
        String first = strs[0];
        String last = strs[strs.length - 1];
        for (int i = 0; i < first.length(); i++) {
            if (i < last.length() && first.charAt(i) == last.charAt(i)) {
                sb.append(first.charAt(i));
            }
            else {
                break;
            }
        }
        return sb.toString();
    }
}

242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.
Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?



Solution:

If two strings are anagram, the frequency of unique characters in string a should be exactly the same with string b.

Therefore, we use a HashMap to count the frequency of each character in string a first.

Then we check string b. When we meet a character, we decrease its frequency by 1 in the HashMap.

If we find the frequency of a character in the HashMap is less than 0, we know the number of this character in string b is more that that in string a. So they are not anagram.

The time complexity is O(n). We can treat the space complexity as O(1).



Code:


public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] check = new int[256];
        for (char c : s.toCharArray()) {
            check[c]++;
        }
        for (char c : t.toCharArray()) {
            check[c]--;
            if (check[c] < 0) {
                return false;
            }
        }
        return true;
    }
}

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note: 
  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm's time complexity must be better than O(n log n), where n is the array's size.



Solution:

The idea is to count the frequency of each number. Then we use a bucket array and put all the numbers that appear x times to index x.

Hence, we add the most frequent number to the result until reach k elements.

Both time complexity and space complexity are O(n).



Code:


public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result = new ArrayList<>();
        List<Integer>[] bucket = new List[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            }
            else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        
        for (int key : map.keySet()) {
            int frequency = map.get(key);
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            bucket[frequency].add(key);
        }
        
        for (int i = bucket.length - 1; i >= 0 && k > 0; i--) {
            if (bucket[i] != null) {
                for (int num : bucket[i]) {
                    result.add(num);
                    k--;
                    if (k == 0) {
                        break;
                    }
                }
            }
        }
        return result;
    }
}

Friday, May 5, 2017

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.



Solution:

We keep two pointers i and j and a HashMap to keep track of substring.

The HashMap maintains a character to index map.

We set i to be the start of a substring and j to be the end.

For each j, we check if the character is in the substring by checking the HashMap.

If it has not appeared before, we simply add j + 1 (the next position to this character) to the HashMap. This indicates that if we found a repeat at some point, we need to set i (start of the substring) to skip this character to its next position.

If there is a repeat, we set i to skip the repeated character.



Code:


public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0, j = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(i, map.get(s.charAt(j)));
            }
            max = Math.max(max, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return max;
    }
}




public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] check = new int[256];
        int max = 0;
        for (int i = 0, j = 0; j < s.length(); j++) {
            i = Math.max(i, check[s.charAt(j)]);
            max = Math.max(max, j - i + 1);
            check[s.charAt(j)] = j + 1;
        }
        return max;
    }
}




public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0;
        int end = 0;
        int max = 0;
        int count = 0;
        while (end < s.length()) {
            char c = s.charAt(end);
            if (!map.containsKey(c)) {
                map.put(c, 1);
            }
            else {
                map.put(c, map.get(c) + 1);
            }
            if (map.get(c) > 1) {
                count++;
            }
            end++;
            while (count > 0) {
                char ch = s.charAt(start);
                if (map.containsKey(ch)) {
                    map.put(ch, map.get(ch) - 1);
                    if (map.get(ch) > 0) {
                        count--;
                    }
                }
                start++;
            }
            max = Math.max(max, end - start);
        }
        return max;
    }
}

Thursday, May 4, 2017

49. Group Anagrams

Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]
Note: All inputs will be in lower-case.



Solution:

If two strings s1 and s2 are anagram, sort(s1) will be equal to sort(s2). So we can use sorted element as a key to the HashMap.

We go through the input array. For each s, we sort it and check if the HashMap has this key. If so, s is an anagrams and we put it to corresponding value list.



Code:


public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<List<String>>();
        }
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArr = str.toCharArray();
            Arrays.sort(charArr);
            String s = new String(charArr);
            if (!map.containsKey(s)) {
                map.put(s, new ArrayList<String>());
            }
            map.get(s).add(str);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

Wednesday, May 3, 2017

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].



Solution:

The idea is to sort the List by Interval.start. (write a comparator)

Then we go through the list and compares the start of current interval with the previous interval's end.

If the start of current interval <= end of previous interval, there is an overlap, we update the end of this overlap.

If the start of current interval > end of previous interval, we know there is no overlap and the current interval can be added to the result.

The sorting takes O(nlogn) and the merge takes O(n). So the overall time complexity is O(n).



Code:


/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return result;
        }
        
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval x, Interval y) {
                if (x.start != y.start) {
                    return x.start - y.start;
                }
                return x.end - y.end;
            }
        });
        
        result.add(intervals.get(0));
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals.get(i).start <= result.get(result.size() - 1).end) {
                result.get(result.size() - 1).end = 
                    Math.max(result.get(result.size() - 1).end, intervals.get(i).end);
            }
            else {
                result.add(intervals.get(i));
            }
        }

        return result;
    }
}