havanagrawal
BAN USERYes, this can be done with a few lines of bash on the console. It is O(n^2 log(n)) in time where n is the #lines in the file, with O(1) in space. The nlog(n) is only because uniq does not work without the sort.
It can be optimized in time, by trading off space and using a hash. At that point, you will need a higher-level scripting language like Python or Bash (or Perl), which is trivial to write. By using a hash, you can have O(n) time complexity, with O(n) space.
for ip in $(sort IP.txt | uniq)
do
count=$(grep -c "$ip" IP.txt);
# 5 is just an arbitrary number, you could ask your interviewer for the limit
if [[ count -ge 5 ]]; then
echo "BLOCK $ip"
fi
done
Input text file:
121.132.133.141
121.231.12.41
121.132.133.141
121.231.12.41
121.132.133.141
121.231.12.41
121.132.133.141
12.39.80.1
121.132.133.141
14.15.16.19
15.14.119.10
1.10.102.12
12.39.80.1
121.132.133.141
121.132.133.141
Output:
BLOCK 121.132.133.141
Solution for the first part.
Follow-up: Yes, it will be simpler to solve, since searching for the node in the forest will be faster. In the case of the BST, only the find_node function needs to be changed in the below implementation, everything else remains the same.
class TreeNode():
def __init__(self, x, left = None, right = None):
self.val = x
self.left = left
self.right = right
def print_tree(self, level=0):
print(level*" " + str(self.val))
if self.left:
self.left.print_tree(level+1)
if self.right:
self.right.print_tree(level+1)
def T(x, l=None, r=None):
"""Convenience function for TreeNodes"""
return TreeNode(x, l, r)
def main():
print("TEST 1: Erasing [1, 5]")
test1()
print("TEST 2: Erasing [2, 3]")
test2()
def test1():
# 1
# 2 3
# 4 5 6 7
root = T(1, T(2, T(4), T(5)), T(3, T(6), T(7)))
to_be_erased = [1, 5]
forest = break_tree(root, to_be_erased)
print_forest(forest)
def test2():
# 1
# 2 3
# 4 5 6 7
root = T(1, T(2, T(4), T(5)), T(3, T(6), T(7)))
to_be_erased = [2, 3]
forest = break_tree(root, to_be_erased)
print_forest(forest)
def print_forest(forest):
for i, f in enumerate(forest):
print("Forest #" + str(i + 1))
f.print_tree()
print()
def break_tree(root, to_be_erased):
forest = [root]
for num in to_be_erased:
for i, rt in enumerate(forest):
n, parent, which = find_node(rt, num)
if n:
forest.append(n.left)
forest.append(n.right)
# If this node has no parent, it means it was a root in the forest
# and we need to remove it from our list
if not parent:
forest[i] = None
else:
if which == "left":
parent.left = None
elif which == "right":
parent.right = None
return [f for f in forest if f]
def find_node(root, num):
def find_node_and_parent(root, num, parent, which):
if root:
if root.val == num:
return root, parent, which
else:
n, p, w = find_node_and_parent(root.left, num, root, "left")
if n:
return n, p, w
n, p, w = find_node_and_parent(root.right, num, root, "right")
if n:
return n, p, w
return None, None, None
return find_node_and_parent(root, num, None, None)
if __name__ == "__main__":
main()
Output:
TEST 1: Erasing [1, 5]
Forest #1
2
4
Forest #2
3
6
7
TEST 2: Erasing [2, 3]
Forest #1
1
Forest #2
4
Forest #3
5
Forest #4
6
Forest #5
7
Same logic as the other answer, but correct implementation. The other answer will result in multiple answers being printed in certain cases, and will in fact give an incorrect answer for certain cases as well.
Eg:
GOOD,11,12
BAD,11,13
BAD,12,14
will give multiple mapping in the other code, where as there is a distinct answer.
def main():
n = int(input())
good_nums = set([])
bad_nums = set([])
maybe_bad_nums = []
all_nums = set([])
for _ in range(n):
s = input().strip().split(",")
tag = s[0]
nums = [int(k) for k in s[1:]]
all_nums.update(nums)
if tag == "GOOD":
for k in nums:
good_nums.add(k)
else:
maybe_bad_nums.append(nums)
ans = solve(good_nums, maybe_bad_nums)
if ans:
print(ans)
else:
for i in sorted(all_nums):
final_tag = "GOOD" if i in good_nums else "BAD"
print(str(i) + ": " + final_tag)
def solve(good_nums, maybe_bad_nums):
ans = None
for maybe_bad_num_list in maybe_bad_nums:
maybe_bad = set(maybe_bad_num_list)
definitely_bad = list(maybe_bad - good_nums)
if len(definitely_bad) > 1:
# We don't return from here because it is possible that
# some other tagging makes the answer "NO CONSISTENT"
# which is stronger than multiple mapping
ans = "MULTIPLE MAPPING"
elif len(definitely_bad) == 0:
# We can return from here since a solution does not exist
return "NO CONSISTENT"
return ans
if __name__ == "__main__":
main()
Output:
2
BAD,10,11
BAD,11,12
MULTIPLE MAPPING
2
GOOD,10,11,12
BAD,10,11
NO CONSISTENT
2
GOOD,10,11
BAD,11,12
10: GOOD
11: GOOD
12: BAD
3
GOOD,11,12
BAD,11,13
BAD,12,14
11: GOOD
12: GOOD
13: BAD
14: BAD
Time Complexity: O(n) if the problem is limited to the current month, otherwise O(mn), where m is the length of the longest period.
Space Complexity: O(n)
A little overkill with the SalePeriod class, but it makes the start and end times easier to handle. You could just as well do it with plain arrays.
import java.io.*;
import java.util.*;
class SalePeriod {
public int startDay;
public int endDay;
public double price;
public SalePeriod(int startDay, int endDay, double price) {
this.startDay = startDay;
this.endDay = endDay;
this.price = price;
}
@Override
public String toString() {
return "(" + startDay + ", " + endDay + ", $" + price + ")";
}
}
class SaleSchedule {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
SalePeriod[] sales = new SalePeriod[t];
int minStart = Integer.MAX_VALUE;
int maxEnd = Integer.MIN_VALUE;
for (int i = 0; i < t; i++) {
String[] s = br.readLine().split(" ");
int start = Integer.parseInt(s[0]);
int end = Integer.parseInt(s[1]);
double price = Integer.parseInt(s[2]);
minStart = Math.min(minStart, start);
maxEnd = Math.max(maxEnd, end);
sales[i] = new SalePeriod(start, end, price);
}
List<SalePeriod> nonConflictingSchedule = getNonConflictingSchedule(sales, minStart, maxEnd);
nonConflictingSchedule.forEach(System.out::println);
}
public static List<SalePeriod> getNonConflictingSchedule(SalePeriod[] sales, int minStart, int maxEnd) {
// This will contain the minimum price on the ith day at the ith index
double[] prices = new double[maxEnd + 1];
for (int i = 0; i <= maxEnd; i++) {
prices[i] = Integer.MAX_VALUE;
}
for (SalePeriod sp : sales) {
for (int i = sp.startDay; i <= sp.endDay; i++) {
prices[i] = Math.min(sp.price, prices[i]);
}
}
List<SalePeriod> nonConflictingSchedule = new ArrayList<>();
int i = minStart;
while(i <= maxEnd) {
int start = i;
while (i <= maxEnd - 1 && prices[i + 1] == prices[i]) {
i += 1;
}
int end = i;
i += 1;
nonConflictingSchedule.add(new SalePeriod(start, end, prices[i - 1]));
}
return nonConflictingSchedule;
}
}
Output:
5
1 5 20
3 6 15
2 8 25
7 12 18
1 31 22
(1, 2, $20.0)
(3, 6, $15.0)
(7, 12, $18.0)
(13, 31, $22.0)
Disclaimer: For finding the 3 largest numbers, the other solution is fine, and the one I am giving will be overkill. However, for solving k largest numbers, you can use a min heap:
import java.util.Arrays;
class KLargestNumbers {
public static void makeMinHeap(int arr[]) {
int n = arr.length / 2;
for (int i = n; i >= 1; i--) {
fixHeap(arr, i);
}
}
public static void fixHeap(int[] arr, int i) {
// Executes a top-down heapify, starting from the index i
int left = 2*i;
int right = 2*i + 1;
int smallest = i;
if (left < arr.length && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < arr.length && arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest != i) {
int t = arr[smallest];
arr[smallest] = arr[i];
arr[i] = t;
fixHeap(arr, smallest);
}
}
public static void insertIntoHeap(int[] heap, int i) {
// If the number is larger than the smallest number in the heap
// Replace it with the root, and then heapify top-down
if (i > heap[1]) {
heap[1] = i;
fixHeap(heap, 1);
}
}
public static int[] kLargest(int[] arr, int k) {
int[] minHeap = new int[k + 1];
for (int i = 0; i < k; i++) {
minHeap[i + 1] = arr[i];
}
makeMinHeap(minHeap);
for (int i = k; i < arr.length; i++) {
insertIntoHeap(minHeap, arr[i]);
}
int[] kLargestNums = new int[k];
for (int i = 0; i < k; i++) {
kLargestNums[i] = minHeap[i + 1];
}
return kLargestNums;
}
public static void main(String[] args) {
int[] arr = new int[args.length];
for (int i = 0; i < args.length; i++) {
arr[i] = Integer.parseInt(args[i]);
}
System.out.println(Arrays.toString(kLargest(arr, 3)));
}
}
java KLargestNumbers 8 0 2 3 1 11 0 -5 18 21 25
[18, 25, 21]
java KLargestNumbers 0 -10 -100 -25 -8 -11
[-10, -8, 0]
class StringMultiplier {
public static void main(String[] args) {
String s1 = args[0];
String s2 = args[1];
String ans = multiplyStringsAsIntegers(s1, s2);
System.out.println(ans);
}
public static String multiplyStringsAsIntegers(String s1, String s2) {
int[] results = new int[s1.length() + s2.length() + 1];
// Bytes because each digit will never exceed 0-9, so ints will be a waste
byte[] a1 = toByteArray(s1);
byte[] a2 = toByteArray(s2);
for (int i = 0; i < a1.length; i++) {
for (int j = 0; j < a2.length; j++) {
results[i + j] += a1[i] * a2[j];
}
}
processCarryOvers(results);
return toString(results);
}
public static void processCarryOvers(int[] results) {
int carry = 0;
for (int i = 0; i < results.length; i++) {
results[i] += carry;
carry = results[i] / 10;
results[i] = results[i] % 10;
}
}
public static byte[] toByteArray(String s) {
byte[] bArr = new byte[s.length()];
for (int i = 0; i < s.length(); i++) {
// Convert each character into its corresponding integer representation
bArr[i] = (byte)(s.charAt(s.length() - i - 1) - '0');
}
return bArr;
}
public static String toString(int[] arr) {
// This appends the values in arr in reverse order,
// Since we multiply right to left, so the result in arr is reversed
StringBuilder s = new StringBuilder();
for (int i = arr.length - 1; i >= 0; i--) {
s.append(arr[i]);
}
return s.toString();
}
}
If there are going to be multiple queries against the same string, it would be wiser to first calculate all the matching pairs in a hash, and then have amortized O(1) time complexity for a query.
On the other hand, if there are going to be multiple queries against different strings, then you can use the approach below.
Potential things to consider:
1. How should the code behave when the input index is not an opening bracket? (raise exception vs return some sentinel value)
2. How would you handle more types of bracket pairs (, [, {, <, etc.?
3. Can you do it without a stack for one-time queries? (yes)
- havanagrawal November 15, 2017