Skip to content

Commit a850103

Browse files
ChevTechChevTech
committed
Practicing LC arrays & hashing problems
1 parent d3fc991 commit a850103

6 files changed

Lines changed: 339 additions & 1 deletion

File tree

‎JavaScript/Array Partition.js‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,4 @@
11
var arrayPairSum = function(nums) {
2-
debugger;
32
if(nums.length === 2){
43
return Math.min(nums[0], nums[1]);
54
}

‎python/arrays_hashing/contains_duplicate.py‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
import unittest
2+
from typing import List
3+
4+
class Solution:
5+
def containsDuplicate(self, nums: List[int]) -> bool:
6+
if len(nums) == 0:
7+
return False
8+
9+
seen = set()
10+
11+
for num in nums:
12+
if num in seen:
13+
return True
14+
15+
seen.add(num)
16+
17+
return False
18+
19+
class TestContainsDuplicate(unittest.TestCase):
20+
def setUp(self):
21+
self.solution = Solution()
22+
23+
def test_empty_array(self):
24+
nums = []
25+
result = self.solution.containsDuplicate(nums)
26+
self.assertFalse(result)
27+
28+
def test_no_duplicates(self):
29+
nums = [1, 2, 3, 4, 5]
30+
result = self.solution.containsDuplicate(nums)
31+
self.assertFalse(result)
32+
33+
def test_with_duplicates(self):
34+
nums = [1, 2, 3, 1]
35+
result = self.solution.containsDuplicate(nums)
36+
self.assertTrue(result)
37+
38+
def test_all_duplicates(self):
39+
nums = [1, 1, 1, 1]
40+
result = self.solution.containsDuplicate(nums)
41+
self.assertTrue(result)
42+
43+
def test_single_element(self):
44+
nums = [1]
45+
result = self.solution.containsDuplicate(nums)
46+
self.assertFalse(result)
47+
48+
def test_negative_numbers(self):
49+
nums = [-1, -1, 2, 3]
50+
result = self.solution.containsDuplicate(nums)
51+
self.assertTrue(result)
52+
53+
if __name__ == '__main__':
54+
unittest.main()

‎python/arrays_hashing/group_anagrams.py‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
import unittest
2+
from typing import List
3+
4+
class Solution:
5+
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
6+
groups = {}
7+
8+
for word in strs:
9+
anagramKey = self.getAnagramKey(word)
10+
11+
if anagramKey not in groups:
12+
groups[anagramKey] = []
13+
groups[anagramKey].append(word)
14+
15+
return list(groups.values())
16+
17+
def getAnagramKey(self, s: str) -> tuple:
18+
freq = [0] * 26 # fixed length array of 26 (all lowercase letters)
19+
20+
for i in range(0, len(s)):
21+
index = ord(s[i]) - ord('a')
22+
freq[index] = freq[index] + 1
23+
24+
25+
return tuple(freq)
26+
27+
class TestGroupAnagrams(unittest.TestCase):
28+
def setUp(self):
29+
self.solution = Solution()
30+
31+
def test_basic_anagrams(self):
32+
strs = ["eat","tea","tan","ate","nat","bat"]
33+
result = self.solution.groupAnagrams(strs)
34+
# Sort each group and the overall result for consistent comparison
35+
result = [sorted(group) for group in result]
36+
result.sort(key=lambda x: x[0])
37+
38+
expected = [["ate","eat","tea"], ["bat"], ["nat","tan"]]
39+
expected = [sorted(group) for group in expected]
40+
expected.sort(key=lambda x: x[0])
41+
42+
self.assertEqual(result, expected)
43+
44+
def test_single_string(self):
45+
strs = ["a"]
46+
result = self.solution.groupAnagrams(strs)
47+
self.assertEqual(result, [["a"]])
48+
49+
def test_empty_strings(self):
50+
strs = ["", ""]
51+
result = self.solution.groupAnagrams(strs)
52+
self.assertEqual(result, [["", ""]])
53+
54+
def test_no_anagrams(self):
55+
strs = ["cat", "dog", "pig"]
56+
result = self.solution.groupAnagrams(strs)
57+
# Each string should be in its own group
58+
self.assertEqual(len(result), 3)
59+
self.assertTrue(all(len(group) == 1 for group in result))
60+
61+
def test_all_same_anagrams(self):
62+
strs = ["aaa", "aaa"]
63+
result = self.solution.groupAnagrams(strs)
64+
self.assertEqual(result, [["aaa", "aaa"]])
65+
66+
def test_getAnagramKey(self):
67+
# Test the key generation
68+
result1 = self.solution.getAnagramKey("eat")
69+
result2 = self.solution.getAnagramKey("tea")
70+
self.assertEqual(result1, result2)
71+
72+
result3 = self.solution.getAnagramKey("bat")
73+
self.assertNotEqual(result1, result3)
74+
75+
if __name__ == '__main__':
76+
unittest.main()

‎python/arrays_hashing/top_k_frequent_elements.py‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
2+
import unittest
3+
from typing import List
4+
5+
6+
class Solution:
7+
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
8+
freqMap = {}
9+
for num in nums:
10+
freqMap[num] = freqMap.get(num, 0) + 1
11+
12+
buckets = []
13+
for i in range(len(nums) + 1):
14+
buckets.append([])
15+
16+
for num, freq in freqMap.items():
17+
buckets[freq].append(num)
18+
19+
res = []
20+
for i in range(len(buckets)-1, -1, -1):
21+
for num in buckets[i]:
22+
if len(res) < k:
23+
res.append(num)
24+
25+
return res
26+
27+
class TestTopKFrequent(unittest.TestCase):
28+
def setUp(self):
29+
self.solution = Solution()
30+
31+
def test_basic_case(self):
32+
nums = [1,1,1,2,2,3]
33+
k = 2
34+
result = self.solution.topKFrequent(nums, k)
35+
# Sort for consistent comparison since order doesn't matter
36+
self.assertEqual(sorted(result), [1,2])
37+
38+
def test_single_element(self):
39+
nums = [1]
40+
k = 1
41+
result = self.solution.topKFrequent(nums, k)
42+
self.assertEqual(result, [1])
43+
44+
def test_all_same_frequency(self):
45+
nums = [1,1,2,2,3,3]
46+
k = 3
47+
result = self.solution.topKFrequent(nums, k)
48+
self.assertEqual(sorted(result), [1,2,3])
49+
50+
def test_multiple_frequencies(self):
51+
nums = [1,1,1,2,2,3,3,3,3]
52+
k = 2
53+
result = self.solution.topKFrequent(nums, k)
54+
self.assertEqual(sorted(result), [1,3])
55+
56+
def test_negative_numbers(self):
57+
nums = [-1,-1,-2,-2,-2]
58+
k = 1
59+
result = self.solution.topKFrequent(nums, k)
60+
self.assertEqual(result, [-2])
61+
62+
def test_k_equals_array_length(self):
63+
nums = [1,2,3]
64+
k = 3
65+
result = self.solution.topKFrequent(nums, k)
66+
self.assertEqual(sorted(result), [1,2,3])
67+
68+
def test_frequencies_in_order(self):
69+
nums = [1,1,1,2,2,3]
70+
k = 3
71+
result = self.solution.topKFrequent(nums, k)
72+
self.assertEqual(len(result), 3)
73+
# First element should have highest frequency
74+
self.assertEqual(result[0], 1)
75+
76+
if __name__ == '__main__':
77+
unittest.main()

‎python/arrays_hashing/two_sum.py‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
import unittest
2+
from typing import List
3+
4+
class Solution:
5+
def twoSum(self, nums: List[int], target: int) -> List[int]:
6+
if len(nums) == 0:
7+
return []
8+
9+
map = {}
10+
11+
for i in range(0, len(nums)):
12+
num = nums[i]
13+
if num in map:
14+
return [map[num], i]
15+
16+
map[target-num] = i
17+
18+
return []
19+
20+
class TestTwoSum(unittest.TestCase):
21+
def setUp(self):
22+
self.solution = Solution()
23+
24+
def test_basic_case(self):
25+
nums = [2,7,11,15]
26+
target = 9
27+
result = self.solution.twoSum(nums, target)
28+
self.assertEqual(sorted(result), [0,1]) # Sort since order doesn't matter
29+
30+
def test_multiple_solutions_returns_first(self):
31+
nums = [3,3,3,3]
32+
target = 6
33+
result = self.solution.twoSum(nums, target)
34+
# Should return first valid pair
35+
self.assertEqual(len(result), 2)
36+
self.assertEqual(nums[result[0]] + nums[result[1]], target)
37+
38+
def test_no_solution(self):
39+
nums = [1,2,3,4]
40+
target = 10
41+
result = self.solution.twoSum(nums, target)
42+
self.assertEqual(result, [])
43+
44+
def test_empty_array(self):
45+
nums = []
46+
target = 5
47+
result = self.solution.twoSum(nums, target)
48+
self.assertEqual(result, [])
49+
50+
def test_negative_numbers(self):
51+
nums = [-1,-2,-3,-4]
52+
target = -5
53+
result = self.solution.twoSum(nums, target)
54+
self.assertEqual(sorted(result), [1,2])
55+
56+
def test_zero_target(self):
57+
nums = [1,0,-1]
58+
target = 0
59+
result = self.solution.twoSum(nums, target)
60+
self.assertEqual(nums[result[0]] + nums[result[1]], target)
61+
62+
if __name__ == '__main__':
63+
unittest.main()

‎python/arrays_hashing/valid_anagram.py‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
import unittest
2+
3+
class Solution:
4+
def isAnagram(self, s: str, t: str) -> bool:
5+
if len(s) != len(t):
6+
return False
7+
8+
freq = [0] * 26 # fixed length array of 26 (all lowercase letters)
9+
10+
for i in range(0, len(s)):
11+
self.increment(freq, s[i])
12+
self.decrement(freq, t[i])
13+
14+
for char in freq:
15+
if char != 0:
16+
return False
17+
18+
return True
19+
20+
def increment(self, freq, char):
21+
index = ord(char) - ord('a')
22+
freq[index] = freq[index] + 1
23+
24+
def decrement(self, freq, char):
25+
index = ord(char) - ord('a')
26+
freq[index] = freq[index] - 1
27+
28+
class TestIsAnagram(unittest.TestCase):
29+
def setUp(self):
30+
self.solution = Solution()
31+
32+
def test_valid_anagram(self):
33+
s = "anagram"
34+
t = "nagaram"
35+
result = self.solution.isAnagram(s, t)
36+
self.assertTrue(result)
37+
38+
def test_not_anagram(self):
39+
s = "rat"
40+
t = "car"
41+
result = self.solution.isAnagram(s, t)
42+
self.assertFalse(result)
43+
44+
def test_different_lengths(self):
45+
s = "abc"
46+
t = "abcd"
47+
result = self.solution.isAnagram(s, t)
48+
self.assertFalse(result)
49+
50+
def test_empty_strings(self):
51+
s = ""
52+
t = ""
53+
result = self.solution.isAnagram(s, t)
54+
self.assertTrue(result)
55+
56+
def test_same_letters_different_count(self):
57+
s = "aabc"
58+
t = "abcc"
59+
result = self.solution.isAnagram(s, t)
60+
self.assertFalse(result)
61+
62+
def test_repeated_letters(self):
63+
s = "aaaa"
64+
t = "aaaa"
65+
result = self.solution.isAnagram(s, t)
66+
self.assertTrue(result)
67+
68+
if __name__ == '__main__':
69+
unittest.main()

0 commit comments

Comments
 (0)