Questions & Solutions

February 10, 2020

Discussion Session

Topic:

C++ in a UNIX Environment

January 27, 2020

Advanced Session
Lead - Harsha

Starter code

Show

Problem:

Given a node that represents the head of a linked list, find where there exists a circular loop. Note: The linked list need not necessarily wrap to back to the head node.

Solution: O(max(N,M))

Show


public static boolean isCircular(Node node) {

	Node pointer1 = node;
	Node pointer2 = node;

	while (pointer1 != null || pointer2 != null || pointer1 != pointer2) {
		pointer1 = pointer1.getNextNode();
		pointer2 = pointer2.getNextNode();
		if (pointer2 != null) {
			pointer2 = pointer2.getNextNode();
		}
	}
	return false;
}

Problem:

Given two nodes that represent that heads of two different linked lists, identify whether the linked lists are connected at any point.

Solution: O(max(M,N))

Show


public static boolean isConnected(Node node, Node node2) {
	if(isCircular(node) || isCircular(node2)) {
		return false;
	}
	Node pointer1 = node;
	Node pointer2 = node2;
	while(pointer1.getNextNode() != null) {
		pointer1 = pointer1.getNextNode();
	}
	while(pointer2.getNextNode() != null) {
		pointer2 = pointer2.getNextNode();
	}
	if(pointer1.equals(pointer2)) {
		return true;
	}
	return false;
}

November 21, 2019

Advanced Session
Lead - Harsha

Problem:

Given a two dimensional ArrayList of boolean values that represent a maze where false represents a wall and true represents an open space, write a function that returns whether a path exists from the start to the end. Assume index (0,0) is the start of the maze and (n,n) represents the end. Assume that there only exists one path from start to end. Use the following code to initialize your arrayList. Diagonals do not count as a path.

Starter code for ArrayList

Show


List< List< Boolean>> list = new ArrayList<>() {
	{
		add(new ArrayList<>() {
			{
				add(true);
				add(false);
				add(false);
				add(false);
				add(true);
			}
		});
		add(new ArrayList<>() {
			{
				add(true);
				add(true);
				add(true);
				add(true);
				add(true);
			}
		});
		add(new ArrayList<>() {
			{
				add(false);
				add(true);
				add(false);
				add(false);
				add(true);
			}
		});
		add(new ArrayList<>() {
			{
				add(true);
				add(true);
				add(false);
				add(false);
				add(false);
			}
		});
		add(new ArrayList<>() {
			{
				add(false);
				add(true);
				add(true);
				add(true);
				add(true);
			}
		});
	}
};

Solution: Recursive O(MN)

Show


public static boolean doesPathExist(List< List< Boolean>> list, int i, int j) {
		if(i < 0 || i >= list.size()) {
			return false;
		}
		if(j < 0 || j >= list.get(i).size()) {
			return false;
		}
		if(!list.get(i).get(j)) {
			return false;
		}
		if(i == list.size()-1 && j == list.get(i).size()-1) {
			return true;
		}

		List< Boolean> lst = list.get(i);
		lst.set(j, false);
		list.set(i, lst);
		
		boolean left = doesPathExist(list, i, j-1);
		boolean right = doesPathExist(list, i, j+1);
		boolean up = doesPathExist(list, i-1, j);
		boolean down = doesPathExist(list, i+1, j);

		return left || right || up || down;
	}

November 14, 2019

Advanced Session
Lead - Atharv

Activity: The Pie of Life

Draw one large circle on a piece of paper to represent a typical day in your life
Divide the circle into different slices
Each slice represents the amount of time you spend doing different activities
Ex: Sleeping, playing an instrument, studying, hanging with friends, physical activity
Share and guess which pie belongs to whom

Problem:

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

Solution: O(n²)

Show


/**
* Use two for loops to iterate through every possible combination of indicies
* to find the maximum area in O(n^2)
*
* @param array of numbers that represent height
* @return maxArea that can be held by the container
*/
public static int getMaxAreaSlowly(int[] array) {

	int maxArea = 0;
	for (int i = 0; i < array.length; i++) {
		for (int j = 0; j < array.length; j++) {
			int height1 = array[i];
			int height2 = array[j];

			int area = Math.min(height1, height2) * (Math.abs(j - i));
			if (area > maxArea) {
				maxArea = area;
			}
		}
	}
	return maxArea;
}

Solution: O(N)

Show


/**
* Two pointer solution that finds maximum area in O(n)
* Move the pointer that has the short height
*
* @param array of numbers that represent height
* @return maxArea that can be held by the container
*/
public static int getMaxArea(int[] array) {
	int startIndex = 0;
	int endIndex = array.length - 1;

	int maxArea = 0;

	while (startIndex != endIndex) {
		int height1 = array[startIndex];
		int height2 = array[endIndex];

		int minimumHeight = Math.min(height1, height2);
		int area = minimumHeight * (endIndex - startIndex);
		if (area > maxArea) {
			maxArea = area;
		}


		if (height1 > height2) {
			endIndex--;
		} else {
			startIndex++;
		}
	}

	return maxArea;
}

November 12, 2019

Novice Session
Leads - Ifrit & Harsha

Activity: Who Knows Who Best?

Split in 2 teams. Every person on the other team has 30 seconds to write down their answer on a piece of paper. Crumble the paper up. The other team tries to guess who wrote what answer down as a team by writing down their guesses on the whiteboard. After guesses are made for the round the answers are revealed. At the end of every round the points are tallied up. After 5 rounds, whichever team has the most amount of points win.

Tutorial: Time & Space Complexity

Problem:

Given a list of Integers with n elements and a target, find the set of factors that multiply to the target. Challenge: And if none exist then provide the closest.


public static void findMultiple(List< Integer> list, int target) { 

}

Solution: O(N²)

Show


/**
* O(n^2) solution by brute force checking all combinations by iterating through two for loops
*
* @param list   contains the list of all numbers
* @param target is the value that the factors need to multiply out to or be the closest to
*/
public static void findClosestFactor(List< Integer> list, int target) {

	int num1 = 0;
	int num2 = 0;

	int diffVal = Integer.MAX_VALUE;

	boolean exactMatch = false;
	for (int i = 0; i < list.size(); i++) {
		for (int j = 0; j < list.size(); j++) {
			if (j != i) {
				int multiple = list.get(i) * list.get(j);

				if (Math.abs(target - multiple) < diffVal) {
					diffVal = Math.abs(target - multiple);
					num1 = list.get(i);
					num2 = list.get(j);
				}
				if (multiple == target) {
					System.out.println(list.get(i) + " * " + list.get(j) + " = " + target);
					exactMatch = true;
				}
			}
		}
	}
	if (!exactMatch) {
		System.out.println(num1 + " * " + num2 + " = " + num1 * num2 + " ~ " + target);
	}
}

Solution: O(N)

Show


/**
* O(n) solution for finding the exact match using hashmap, implement V2 for most efficient closest factor calculation in O(nlogn)
*
* @param list contains the list of all numbers
* @param target is the value that the factors need to multiply out to or be the closest to
*/
public static void findClosestFactorV3(List< Integer> list, int target) {
	Map< Integer, Integer> map = new HashMap<>();
	for (int i = 0; i < list.size(); i++) {
		if (map.get(list.get(i)) == null) {
			map.put(list.get(i), 1);
		} else {
			map.replace(list.get(i), map.get(list.get(i)) + 1);
		}
	}

	for (int i = 0; i < list.size(); i++) {
		int div = target / list.get(i);
		if (div * list.get(i) == target) {
			if(map.get(div) != null) {
				if(div == list.get(i) && map.get(div) > 1) {
					System.out.println(list.get(i) + " * " + div + " = " + target);
				}

				if(div != list.get(i)) {
					System.out.println(list.get(i) + " * " + div + " = " + target);
				}
			}
		}
	}
}

October 24, 2019

Advanced Session
✭ Lead - Sanjeev ✭

Activity: Turning Over A New Leaf

Based on the number of people in this activity, make sure you use a cloth big enough for everyone to fit one. The challenge in this game is that with everyone standing on the piece of cloth must work together to flip the piece of cloth completely. There are only 2 rules that you must obey! One is no one can step outside the piece of cloth area. And finally, no one can climb up on top of each other, to preserve space. Everyone’s feet must be touching the piece of cloth at all times!

Problem:

Design a stack that supports push, pop, top and retrieving the minimum element in constant time

push(x) → Push element x onto stack
pop() → Removes the element at the top of the stack
top() → Return the top element
getMin/90 → Retrieve the minimum element in the stack

Starter Code

Given a string containing just the characters (, ), {, }, [, ] determine if the input string is valid by checking if all open brackets have a closing bracket and that they are present in the right order

Solution

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window

Solution

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle. You need to return the lease number of intervals the CPU will take to finish all the given tasks.

Solution

October 10, 2019

Advanced Session
Lead - Gautam

Problem:

Given a linked list, find the middle element of the linked list


public void middle(String str) {

}

Given a linked list, an int m, and an int n, return the sum of the mth element from beginning of the list and the nth element from the end of the list


public void sumMN(int m, int n) {

}

Given a linked list, segregate the list into evens and odds in such a way that the evens are listed before odds


public void seperateOddEven() {

}

October 8, 2019

Novice Session
Lead - Sivam

Return an integer array of the values in the matrix in spiral order


public int[] spiral(int[][] matrix) {

}

Find the longest consecutive sequence of numbers in an integer array


public int longestConsecutive(int[] nums) {

}

If you are given a sorted array of integers, return the sorted array of the squares of all values


public int sortedSquares(int[] A) {

}

Given a 2d array of characters, check if the given word exists


public boolean wordSearch(char[][] board, String word) {

}

October 3, 2019

Novice Session
Lead - Atharv

Problem:

Write a function to print the number of occurrences of a character in a string


public void listCountsOfCharacters(String str) {

}

Write a function that rotates an array k times to the right


public int[] rotated(int[] array, int k) {

}

Given two 2-D arrays, write a function that multiplies them


public int[][] multiplyMatrix(int[][] a, int[][] b) {

}

October 1, 2019

Novice Session
Lead - Harsha

Problem:

Write a function to compute the sum of all prime numbers less than equal to a given integer N


public int getPrimeSum (int n) { {

}

Solution: O(√N)

Show


public int getPrimeSum (int n) {
	if( n== 0 || n==1) {
		return 0;
	} 
	List< Boolean> numbers = new ArrayList<>();
	for (int i = 0; i < limit + 1; i++) {
	numbers.add(true);
	}
	for (int i = 2; i < Math.sqrt(numbers.size()); i++) {
		if (numbers.get(i)) {
			int multiple = i * i;
			while (multiple < numbers.size()) {
				numbers.set(multiple, false);
				multiple += i;
			}
			numbers.set(i, true);
		}
	}
	int sum = 0;
	for (int i = 2; i < numbers.size(); i++) {
		if (numbers.get(i)) {
			sum+=i;
		}
	}
	return sum;
}

Write a function that returns if two strings are anagrams


public boolean isAnagram (String a, String b) {

}

Solution: O(N)

Show


public boolean isAnagram (String a, String b) {
	int n1 = a.length;
	int n2 = b.length;
	if (n1!= n2) {
		return false;
	}
	Map< String, Integer> str1 = new HashMap<>();
	//add letters and frequency to hashmap
	for(int i = 0;i < a.length;i++) {
		String letter1 = a.charAt(i) + "";
		if(str1.get(letter1) == null) {
			str1.put(letter1, 1);
		}
		else {
			str1.replace(letter1, str1.get(i) + 1);
		}
	}
	//check if letters are present
	for(int i =0;i < b.length;i++) {
		String letter1 = b.charAt(i) + "";
		if(str1.get(letter1) == null || str1.get(letter1) == 0) {
			return false;
		}
		else {
			str1.replace(letter1, str1.get(letter1) - 1);
		}
	}
	return true;
}

Solution: O(Nlog(N))

Show


public boolean isAnagram (String a, String b) {
	int n1 = a.length;
	int n2 = b.length;
	if (n1!= n2) {
		return false;
	}
	char [] str1 = a.toCharArray();
	char [] str2 = b.toCharArray();
	Arrays.sort(str1);
	Arrays.sort(str2);

	// Compare sorted strings
	for (int i = 0; i < str1.length; i++)
		if (str1[i] != str2[i]) {
			return false;
		}
	}
	return true;
}

Suppose you had N identical balls. One of them is slightly heavier and you are given a balance scale. Write a function to return the fewest number of times you have to use the scale to find the heavier ball


public int getMinUses (int n) {

}

Solution: O(1)

Show


public int getMinUses (int n) {
	return (int) Math.ceil(Math.log(n)/Math.log(3));
}

Topic:

Starter code

Problem:

Solution: O(max(N,M))

Problem:

Solution: O(max(M,N))

Problem:

Starter code for ArrayList

Solution: Recursive O(MN)

Activity: The Pie of Life

Problem:

Solution: O(n2)

Solution: O(N)

Activity: Who Knows Who Best?

Tutorial: Time & Space Complexity

Problem:

Solution: O(N2)

Solution: O(N)

Activity: Turning Over A New Leaf

Problem:

Problem:

Problem:

Problem:

Solution: O(√N)

Solution: O(N)

Solution: O(Nlog(N))

Solution: O(1)

Solution: O(n²)

Solution: O(N²)