Scribd
Upload
32 views4 pages

Mod6 Assignment 2

The document contains two Java programming problems: the first is about finding the intersection of two intervals, implemented in the 'IntervalIntersection' class, which outputs overlapping intervals. The second problem involves creating a Trie data structure with methods to insert words, search for exact matches, and check for prefixes, implemented in the 'Trie' class. Both classes include main methods demonstrating their functionality with example inputs.

Uploaded by

fathima ashref
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views4 pages

Mod6 Assignment 2

The document contains two Java programming problems: the first is about finding the intersection of two intervals, implemented in the 'IntervalIntersection' class, which outputs overlapping intervals. The second problem involves creating a Trie data structure with methods to insert words, search for exact matches, and check for prefixes, implemented in the 'Trie' class. Both classes include main methods demonstrating their functionality with example inputs.

Uploaded by

fathima ashref
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Mod 6 Assignment 2

Problem Statement 3: Interval Intersection


import java.util.*;

public class IntervalIntersection {


public static int[][] intervalIntersection(int[][] intervals1, int[][] intervals2) {
List<int[]> result = new ArrayList<>();
int i = 0, j = 0;

while (i < intervals1.length && j < intervals2.length) {


int start = Math.max(intervals1[i][0], intervals2[j][0]);
int end = Math.min(intervals1[i][1], intervals2[j][1]);

if (start <= end) {


result.add(new int[]{start, end});
}

if (intervals1[i][1] < intervals2[j][1]) {


i++;
} else {
j++;
}
}

return result.toArray(new int[result.size()][]);


}

public static void main(String[] args) {


int[][] intervals1 = {{1, 3}, {5, 6}, {7, 9}};
int[][] intervals2 = {{2, 5}, {7, 8}};

int[][] result = intervalIntersection(intervals1, intervals2);

for (int[] interval : result) {


System.out.println(Arrays.toString(interval));
}
}
}

Problem Statement 4: Trie Data Structure

class TrieNode {
TrieNode[] children;
boolean isEndOfWord;

public TrieNode() {
children = new TrieNode[26];
isEndOfWord = false;
}
}

public class Trie {


private final TrieNode root;

public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true;
}

public boolean search(String word) {


TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return node.isEndOfWord;
}

public boolean startsWith(String prefix) {


TrieNode node = root;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return true;
}

public static void main(String[] args) {


Trie trie = new Trie();
trie.insert("apple");
System.out.println(trie.search("apple")); // Output: true
System.out.println(trie.search("app")); // Output: false
System.out.println(trie.startsWith("app")); // Output: true
trie.insert("app");
System.out.println(trie.search("app")); // Output: true
}
}

You might also like