Scribd
Upload
5 views4 pages

Java Trie and Interval Intersection

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
5 views4 pages

Java Trie and Interval Intersection

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

Mod 6 Assignment 2

Problem Statement 3: Interval Intersection


import [Link].*;

public class IntervalIntersection {


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

while (i < [Link] && j < [Link]) {


int start = [Link](intervals1[i][0], intervals2[j][0]);
int end = [Link](intervals1[i][1], intervals2[j][1]);

if (start <= end) {


[Link](new int[]{start, end});
}

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


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

return [Link](new int[[Link]()][]);


}

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) {


[Link]([Link](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 : [Link]()) {
int index = c - 'a';
if ([Link][index] == null) {
[Link][index] = new TrieNode();
}
node = [Link][index];
}
[Link] = true;
}

public boolean search(String word) {


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

public boolean startsWith(String prefix) {


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

public static void main(String[] args) {


Trie trie = new Trie();
[Link]("apple");
[Link]([Link]("apple")); // Output: true
[Link]([Link]("app")); // Output: false
[Link]([Link]("app")); // Output: true
[Link]("app");
[Link]([Link]("app")); // Output: true
}
}

You might also like