Scribd
Upload
21 views5 pages

Amarnath Java 9

The document contains code solutions for four programming problems: finding the longest substring without repeating characters, determining the next greater element for an array, displaying a table of food orders in a restaurant, and finding minimum height trees in a graph. Each solution is presented in Java, demonstrating the use of data structures like HashSet, HashMap, and Queue. The document includes the code and a brief description of each problem's approach.

Uploaded by

Ɯԋιƚҽ Ԃҽʋιʅ
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
21 views5 pages

Amarnath Java 9

The document contains code solutions for four programming problems: finding the longest substring without repeating characters, determining the next greater element for an array, displaying a table of food orders in a restaurant, and finding minimum height trees in a graph. Each solution is presented in Java, demonstrating the use of data structures like HashSet, HashMap, and Queue. The document includes the code and a brief description of each problem's approach.

Uploaded by

Ɯԋιƚҽ Ԃҽʋιʅ
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

Day-9

Name –Amarnath Choudhary

Uid-21BCS9971

Sub - Java

Section- CC-627 / B

Q.1 Longest Substring Without Repeating Characters


Code:
class Solution {
public int lengthOfLongestSubstring(String s)
{int n = [Link]();
int maxLength = 0;
Set<Character> charSet = new
HashSet<>(); int left = 0;
for (int right = 0; right < n; right++) {
if (![Link]([Link](right)))
{ [Link]([Link](right));
maxLength = [Link](maxLength, right - left + 1); }
else { while
([Link]([Link](right))) {
[Link]([Link](left)); left++;
}
[Link]([Link](right));
}
}

return maxLength;
}
}
Output:
Q.2 Next Greater Element I
Code:
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2)
{HashMap<Integer, Integer> hMap = new HashMap<>();
Stack<Integer> st = new Stack<>(); for (int i =
[Link] - 1; i >= 0; i--) { while (![Link]()
&& [Link]() <= nums2[i]) [Link](); if
(![Link]()) [Link](nums2[i], [Link]());
else [Link](nums2[i], -1);
[Link](nums2[i]);
} for (int i = 0; i < [Link]; i++)
{nums1[i] =
[Link](nums1[i]);
}
return nums1;
}
}
Output:
Q.3 Display Table of Food Orders in a Restaurant
Code:
class Solution { public List<List<String>> displayTable(final
List<List<String>> orders) { final TreeMap<Integer, Map<String,
Integer>> tables = new TreeMap<>(); final TreeSet<String> meals =
new TreeSet<>();
for(final List<String> order : orders) { final int
tableNum = [Link]([Link](1));
[Link](tableNum, new
HashMap<>());
final Map<String, Integer> table = [Link](tableNum);

[Link]([Link](2), [Link]([Link](2), 0) + 1);

[Link]([Link](2));
}

final List<List<String>> result = new ArrayList<>();

[Link](new ArrayList<>());
[Link](0).add("Table");
[Link](0).addAll(meals);

for(final int tableNum : [Link]()) {


final List<String> tableOrders = new ArrayList<>();
[Link]([Link](tableNum)); final
Map<String, Integer> table =
[Link](tableNum);

for(int i = 1; i < [Link](0).size(); ++i) {


final String meal = [Link](0).get(i);
[Link]([Link](meal) ?
[Link]([Link](meal)) : "0");
}

[Link](tableOrders);
}

return result;
}
}
Output:

Q.4 Minimum Height Trees


Code:
class Solution { public List<Integer> findMinHeightTrees(int
n, int[][] edges)
{if(n == 1) return [Link](0);

int ind[] = new int[n];


Map<Integer, List<Integer>> map = new HashMap();
for(int[] edge: edges) {
ind[edge[0]]++; ind[edge[1]]++;
[Link](edge[0], new
ArrayList()); [Link](edge[1],
new ArrayList());
[Link](edge[0]).add(edge[1]);
[Link](edge[1]).add(edge[0]);
}

Queue<Integer> queue = new


LinkedList(); for(int
i=0;i<[Link];i++) { if(ind[i] == 1) {
[Link](i);
}
}

int processed = 0;
while(n - processed > 2)
{int size = [Link]();
processed += size;
for(int i=0;i<size;i++) {
int poll =
[Link](); for(int
adj: [Link](poll))
{if(--ind[adj] == 1) {
[Link](adj);
}
}
}
}

List<Integer> list = new


ArrayList(); [Link](queue);
return list;
}
}
Output:

You might also like