Manjiri Tapaswi mptap
mptap
/ setLikeDS.java
Last active
October 14, 2018 16:43
Implement a set-like data structure that supports Insert, Remove, and GetRandomElement efficiently. Example: If you insert the elements 1, 3, 6, 8 and remove 6, the structure should contain [1, 3, 8]. Now, GetRandom should return one of 1, 3 or 8 with equal probability
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class SetLikeDS { | |
| private List<Integer> list; | |
| private Map<Integer, Integer> map; | |
| public SetLikeDS() { | |
| list = new ArrayList<>(); | |
| map = new HashMap<>(); | |
| } | |
| public void insert(int num) { |
mptap
/ twoSum.java
Last active
September 26, 2018 08:24
Given an array of integers, determine whether or not there exist two elements in the array (at different positions) whose sum is equal to some target value. Examples: [5, 4, 2, 4], 8 --> true [5, 1, 2, 4], 8 --> false
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import javafx.util.Pair; //available in Java 1.8 | |
| public class Solution { | |
| public static boolean twoSum(int[] a, int target) { | |
| Map<Integer, Pair> map = new HashMap<>(); | |
| for(int i=0; i<a.length; i++) { //O(n) where n=a.length | |
| if (!map.containsKey(a[i])) { //don't insert duplicates | |
| map.put(a[i], new Pair<Integer, Integer>(target-a[i], i)); | |
| //key is every unique element, value is a pair of numberToFind and position of element first found |