use a map with key = last element in a candidate list and value = list itself.

Traverse the array. Check the element against each element in the map. If the array element is a multiple of the element – and that it’s the longest list satisfying this – put (array element, list appended with array element) to the map. The only other possibility is that the array element is not a multiple of any key, in which case, put (array element, singleton list of the array element)

O(n^2) speed, O(n) space.

Some improvements:

Looks like others’ basic ideas are all the same. One improvement is rather than tracking the whole list, use an array to track the previous index instead.

First attempt: Naive DisjointSet Implementation, with union by rank – in particular, need to go up the forest to find ancestor every time – O(log n) merge and O(log n) query. TLE for most cases.

Second attempt: Optimize by caching index to oldest ancestor. Lazy updates. TLE for most cases.

Third attempt: Go back to attempt 1, but use path compression as well. Used array list to track the visited nodes whose parents have to be updated. TLE for most cases.

Fourth attempt: Use recursion directly to do path compression. Passed.

Conclusion: it looks like the main reason I get TLE was that in merging, I didn’t return when the two sets already have same ancestor. The official solution doesn’t do union by rank or path compression at all.

Fairly straightforward, once you realize that you should think of red edges as non-existent edges, and that you are trying to count the number of unordered triples coming from three distinct connected components (only with the black edges).

Fairly likely that keeping a balanced tree together with number of elements in left/right subtree would be sufficient – O(log n) add/remove/get median.

Redo tomorrow: don’t want to look at AVL deletion right now.

First attempt: recursion, TLE for half the test cases.

Second attempt: key is to build a list of the “smallest” element you can take from the stack each time. Once you build this list, just keep polling until you hit the maximum allowed total. This can be done by tracking two pointers of the respective arrays. Some WA, some TLE

Third attempt: no need to build out that list – you can track the total sum so far in the process of updating the two pointers, and return the answer right away when ready.

Fourth attempt: the above is actually wrong: the greedy way of picking the lowest number at every step is logically wrong… does need recursive ideas, so let’s do memoization. Memoization done by a HashMap<Index Pair, Capacity> TLE for half the test cases.

Fifth attempt: Same as last idea, do bfs on the indices – add index 1 only when permissible, and if this has been calculated before (tracked by a HashSet), don’t do the calculation again. TLE for half of the test cases.

Sixth attempt: two pointer passing solution. Passed

I am reading up on threading and concurrency issues lately. Blogging seems to be an interesting way to write down what I read and to clarify my thoughts a bit.

Prologue: Why concurrency?

We certainly love our devices to process multiple tasks at the same time. If we want to download a file, read a book and play music, we probably don’t want to do them one by one.

For practical purposes though, it is unnecessary for our computer to truly, concurrently download a file, display your book, and play music at the same time.

When I display a pdf for you to read, most of the time the computer sits there waiting for your next instructions, such as next page, previous page and so on. Unless you keep flipping the pages of the book and so on, the computer doesn’t have to do anything, after the first rendering of the page.

If I spend 50% of each second downloading a file, and the other 50% for other tasks, the file would still be downloaded.

To play music, I need to send a number of samples to my speaker every second. For each second, if I can produce and send the number of samples to my speaker needed in 0.01s, then I would have 0.99s for other tasks.

All the figures above are not meant to be accurate, but the idea is that if we can switch between tasks quick enough, practically speaking it would look like the computer is handling several tasks all at once. So practically the real question is then

How can we make process in multiple tasks at the same time?

1. Terminologies

When dealing with concurrency issues, there are several keywords that are used ubiquitously that were a little confusing to me at first. Let us first clarify what they mean.

Multitasking vs multiprocessing

Multitasking means you want to make progress in multiple tasks at the same time. This does not mean that at each instant, we really are executing instructions for separate tasks simultaneously – we can certainly do part of task A, switch to work on part of task B, switch to work on part of task C, come back to task A to finish it up, and so on. Our illustration earlier on downloading a file/displaying a book/playing music is one example of this.

On the other hand, Multiprocessing does mean we are trying to perform several tasks at the same time, by using multiple processors. Most computers these days have multiple-core CPUs, meaning that the CPU itself has multiple processing units/processor. If we execute different processes/tasks on each processor, we are multiprocessing.

Threads vs processes

We were already using the word process, but let us be a bit more precise now.

A process is basically an executable program loaded in the memory. Think of each process as a separate container – it has its own address space, memory, and so on. Nonetheless, processes can still talk to each other, for example by files, sockets, and so on. (Remark: processes can actually share memory, typically when one process is forked by another. As a first iteration of the picture though, this point can probably be ignored.)

Within one process though, we may still want to multi-task. Look at any multiplayer game – the computer needs to process what your character does, as well as talking to the server to see what other characters do. This leads us to threading.

A thread is an execution context ( reads: a sequence of instructions, together with the context of when/with what are these instructions executed ), that can be scheduled. A thread lives in a process, and a process can have multiple threads. All these threads will share the same resources as the process itself. Nonetheless, each threads may still maintain its own call stack to store context, local variables, and so on.

2. Multithreading

Multithreading is a way to achieve multitasking, by coordinating several threads of instructions to execute a task. In a multi-player game situation, we may have three threads in the most naive case:

One thread handling user input

One thread communicates with server to get the latest version of the whole game

One thread renders the latest version of the game.

Even if we have only one CPU, if we can coordinate these three threads well – so that we switch between threads at suitable time – it would look as if we handle these three tasks at the same time.

A basic model for coordinating threads is:

Each thread has a runnable task, and a state.

New: an initialized thread which is not started yet.

Runnable: A thread which is ready to run.

Running: A thread which is running/being executed right now.

Blocked: A thread which is waiting for completion of another thread to continue.

Dead: A thread is terminated, either because it has finished execution, or it gets interrupted.

The thread states can be modeled as below:

Thread scheduling

An important part of this process is scheduling, which is the step of deciding which thread to run when the CPU is available.

Some concerns scheduling have to take into account include:

Fairness. If multiple threads are trying to run, it is possible that one thread never actually runs (sometimes called starving), because another thread gets selected each time. Fairness means we try to avoid this situation.

Priority. Different threads may have different priorities that we should account for.

Deadlines. Must a thread be executed before a certain time?

Throughput, i.e. the number of threads that finish running per unit time.

Efficiency – e.g. minimizing overhead of scheduler, context switching etc.

The two most basic categories for scheduling algorithms are

Non-preemptive scheduling. This means that once a thread starts to execute, it would end unless the thread finishes running and terminate/voluntarily yields the control of CPU.This can be a bad thing – if a time-intensive task is running while a higher-priority task comes up, we will not be able to stop the running thread to execute the higher-priority task first.

Pre-emptive scheduling. This means that the current executing thread may be interrupted.

There are many scheduling algorithms available, see here for a general introduction.

3. Some issues with multi-threading

There are some issues/tools we need to be aware of when we use multiple threads.

Data Race/Race conditions. Since multiple threads within a process share data, they may try to modify same data at the same time, and that could be a problem.

Thread signaling. If we try to split up a task among several threads, a situation like this may happen:

thread A does something, and pass the result to thread B.

thread B processes whatever it gets from thread A, and passes back to thread A.

thread A continues its execution.
This means that thread B would need to signal thread A that the task is done, so that thread A wakes up and continues the process.

We will look at strategies to deal with these two issues in a future post.

Your attempt: have a maxPointer that tracks the index with maximum value. The very bad case, is when the whole array is decreasing, and so you need to linearly search for maxPointer every time. This makes it O(n^2) in that case, but on average it looks like O(n). (AC, 97.53%)

Some ideas from solution:

A two pass solution, where you split up the array into blocks of k. For each block, store the accumulating maximum from the left, and from the right. Given a length k interval, you can then split it into the right half of a block + the left half of an adjacent block. Just output the max( max of right half block, max of left half adjacent block)

A queueing solution. Use a queue to track the possible maximum indices.

If current index is i, keep polling head of queue until the index >= i – k + 1. This makes us focus on the index range [i-k+1, i]

We want to add nums[i]. Before we do so, poll from the back of the queue until nums[index] > nums[i]. This removes the elements in the queue that has no chance to be a max in any range.

Add nums[i] to the queue.

If the index is at least k-1, peek at the head of the queue – that would give you the max in the range [i-k+1, i].

Your attempt: use recursion: try hitting the farthest point you can get to without hitting snake/ladder, and try all the snake/ladder you can reach in one roll.

Also track the visited vertices, in case there is a dead loop.

Classical Dijkstra – note that Java Priority Queue has O(n) runtime for remove – so don’t use Priority Queue to choose the next vertex to visit. Otherwise Test case 7 will TLE. (Naive linear search for minimum will pass test case 7)

Without solutions it’s hard to see where my ideas can improve.

Track:

Naive O(n^2) per query solution: 5.97 points

Better O(n) per query solution: 20.31 points

What can I cache so that I can do better than O(n) per query? q >> n so presumably I should be caching things. Your O(n) per query solution depends on the pair, not the individual x,y though.

Read about Disjoint Set Data Structure and Kruskal’s algorithm – not hard to prove but still a little counter intuitive to me that naive greedy algorithm actually works.

Question is weird though – if you only care about minimizing sum of weights, then it doesn’t matter which smallest-weight edge you pick at every stage. The specification of which edge to choose is not tested at all any way.

size of each connected components. Still doable by dfs.

Initially brute force compute sum of pairwise product of connected component size. That results in TLE in one test case, so change it to half of square of sum – sum of squares.

I still don’t understand what went wrong with previous solution – since it gave me WA rather than TLE. Nonetheless, implemented bucket sort solution anyway.

Your attempt: sort. Start from the lowest element, set the center to be the farthest possible element that can still cover your current low. Increment counter and update.

Store the accumulative frequency of A,C,G,T up to i.

In particular, the last such array counts the frequency of A,C,G,T in whole array. If all of them equals n/4, return 0.

If not, this gives us the discrepancy vector between each alphabet and n/4. For each index i, we seek the smallest index > i such that the number of alphabets in this range, is bigger than the discrepancy vector in every component.

Since accumulative frequency is increasing in each component, we can do the last step by binary search.

Your attempt: Keep [0,i] sorted so that we can binary search for the index/update answer. When we get to i+1, bubble down the latest element to make it sorted. O(n^2) (TLE)

Failed

Your idea is okay, as in you know that you should do something in [0,i] progressively to facilitate searching. Bad thing is bubble things down is too slow for this purpose – having some data structure would help.

Binary search tree would work, with average time O(log n) insertion and searching. This brings the average run time down to O(n log n). (Tried to implement naive unbalanced search tree – TLE)

Of course you may worry about unbalanced trees, so you can use any balanced binary search trees to make it actually O(n log n).

I don’t understand how Fenwick tree can be applied here.

Your attempt: DP, track two double arrays: (Memory limit exceeded)

max profit, at most k transactions, holding at the end of n-th day ( bought but not sold yet is not counted as a transaction)

max profit, at most k transactions, not holding at the end of n-th day

Second attempt: to calculate the arrays at (k,n), only need data for (k, <n) and (k-1, <n) – so just two rows is fine, rather than int[k][n]; (Time limit exceeded)

Third attempt: clearly k <= n/2. also note that notHolding array doesn’t need to cache the last k at all. O(kn), all test cases passed but still TLE

Fourth attempt: note also that the precomputation you need for (k,n) depends on (k, n-1) or (k-1, n-1) – in particular the window n-k never increases. This means as you iterate j up to k, you only need to look up to (j, j + n-k) rather than up to n. TLE

Failed, nonetheless

public int maxProfit(int k, int[] prices) {
int n = prices.length;
if( n == 0 ) return 0;
k = Math.min( n/2, k );
int[] holding = new int[n]; // max profit, for at most j transactions and holding at the end of n-th day, j up to k
int[] notHolding = new int[n]; // max profit, for at most j transactions and not holding at the end of n-th day, j up to k
//initialize
int min = Integer.MAX_VALUE;
for(int i = 0; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; n; i++){
min = ( prices[i] &amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; min ) ? prices[i] : min;
holding[i] = -min;
}
int window = n-k;
//recurrence
for(int j = 1; j &amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;= k; j++){
int[] newHold = new int[n];
newHold[0] = -prices[0]; // max profit, for at most k transactions and holding at the end of 0-th day = bought stock the first day
for(int i = 1; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; j + window; i++ ){
newHold[i] = Math.max( newHold[i-1], notHolding[i-1] - prices[i] );
notHolding[i] = Math.max( holding[i-1] + prices[i], notHolding[i-1] );
}
holding = newHold;
}
return notHolding[n-1];
}

After reading solution – key point is to handle the corner case k >= n/2, i.e. you can do any number of transactions directly. You don’t need DP for that!

Your attempt: look ahead k dudes to see if reverse is necessary. If it is, use two pointers (one faster one slower) to swap next node one by one.

public ListNode reverseKGroup(ListNode head, int k) {
ListNode pre = new ListNode( 0 );
pre.next = head;
ListNode stopper = pre;
while( stopper != null ){
ListNode checker = stopper; //checker used to look ahead to see if there is k nodes remaining
for(int i = 0; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; k; i++ ){
checker = checker.next;
if( checker == null ) return pre.next;
}
ListNode tail = checker.next; // the supposedly "next" node; the initial value is the element right after the k elements we want to reverse order. In particular, the very first node in the block of k would have next pointing to this node
ListNode mover = stopper.next; // start of the k-block
for(int i = 0; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; k; i++ ){
ListNode tmp = mover.next;
mover.next = tail; // adjust next node for our current target
tail = mover; // move tail node
mover = tmp; // move node
}
ListNode nextStopper = stopper.next; // the next stopper node in next while loop
stopper.next = tail;
stopper = nextStopper;
}
return pre.next;
}

Your attempt: basic sieve, using hashset (exceed memory)

Second attempt: basic sieve, using array

public int countPrimes(int n) {
if( n &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; 2) return 0;
boolean[] composite = new boolean[n];
int ans = 0;
for(int i = 2; i &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; n; i++ ){
if( !composite[i] ){
ans++;
int count = 2*i;
while( count &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt; n ){
composite[count] = true;
count += i;
}
}
}
return ans;
}

Optimization: for inner loop you don’t need to start with 2*i, since for a composite number with the smallest prime factor p, the flag is set already if we start from p^2. This reduces number of operations.

Your attempt: straightforward rotation. Why do they like tedious problems..

import java.io.*;
import java.util.*;
public class Solution {
public static void rotate( int[][] matrix, int r ){
int m = matrix.length;
int n = matrix[0].length;
for(int i = 0; i < Math.min(m,n)/2; i++ ){
// rotate i-th layer
int perimeter = 2*(m+n-4*i) - 4;
int shellR = r % perimeter;
int[] array = shellToArray( matrix, i ); // clockwise
int[] shiftedArray = cyclicShift( array, r );
updateShellByArray( matrix, i, shiftedArray );
}
}
public static int[] shellToArray( int[][] matrix, int layer ){ //copying i-th layer in clockwise direction
int m = matrix.length;
int n = matrix[0].length;
int perimeter = 2*(m+n-4*layer) - 4;
int[] ans = new int[perimeter];
int count = 0;
for(int i = layer; i < n - layer-1; i++ ){
ans[count++] = matrix[layer][i];
}
for(int i = layer; i < m - layer-1; i++ ){ ans[count++] = matrix[i][n-layer-1]; } for(int i = n-layer-1; i > layer; i-- ){
ans[count++] = matrix[m-layer-1][i];
}
for(int i = m-layer-1; i > layer; i-- ){
ans[count++] = matrix[i][layer];
}
return ans;
}
public static int[] cyclicShift( int[] array, int shift ){
int[] ans = new int[array.length];
for(int i = 0; i < array.length; i++){
ans[i] = array[(i + shift) % array.length ];
}
return ans;
}
public static void updateShellByArray( int[][] matrix, int layer, int[] array ){
int m = matrix.length;
int n = matrix[0].length;
int count = 0;
for(int i = layer; i < n - layer-1; i++ ){
matrix[layer][i] = array[count++];
}
for(int i = layer; i < m - layer-1; i++ ){ matrix[i][n-layer-1] = array[count++]; } for(int i = n-layer-1; i > layer; i-- ){
matrix[m-layer-1][i] = array[count++];
}
for(int i = m-layer-1; i > layer; i-- ){
matrix[i][layer] = array[count++];
}
}
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner( System.in );
int m = in.nextInt();
int n = in.nextInt();
int r = in.nextInt();
int[][] matrix = new int[m][n];
for(int i = 0; i < m; i++ ){
for(int j = 0; j < n; j++ ){
matrix[i][j] = in.nextInt();
}
}
rotate(matrix, r);
for(int i = 0; i < m; i++ ){
for(int j = 0; j < n; j++ ){
System.out.print( matrix[i][j] );
if( j < n-1 ) System.out.print( " " );
}
if( i < m-1 ) System.out.print( "\n" );
}
}
}

Your attempt: naive multiplication (yeah yeah I know there are quicker ways like Karatsuba’s algorithm, but let’s not bother during interview)

import java.io.*;
import java.util.*;
public class Solution {
public static String factorial( int n ){
StringBuilder sb = new StringBuilder();
int[] arr = {1} ;
int count = 1;
while( count <= n ){ arr = multiply( count++, arr ); // arr is in reverse order } for(int i = arr.length-1; i >= 0; i-- ){
sb.append( arr[i] );
}
return sb.toString();
}
public static int[] multiply( int n, int[] arr ){
int[] digits = getDigits( n );
int[] ans = new int[ arr.length + digits.length ];
int carry = 0;
for(int i = 0; i < arr.length + digits.length - 1; i++ ){
int step = carry;
for(int j = Math.max( 0, i + 1 - digits.length) ; j < Math.min( i+1, arr.length ); j++ ){ step += arr[j] * digits[ i - j ]; } ans[i] = step % 10; carry = step / 10; } int index = arr.length + digits.length - 1 ; while( carry > 0 ){
ans[index++] = carry % 10;
carry /= 10;
}
return Arrays.copyOfRange( ans, 0, index );
}
public static int[] getDigits( int n ){ // reverse order
if( n == 0 ) return new int[] {0};
List<Integer> ans = new ArrayList<Integer>();
while( n > 0 ){
ans.add( n % 10 );
n /= 10;
}
return listToArray( ans );
}
public static int[] listToArray( List<Integer> list ){
int[] ans = new int[ list.size() ];
for( int i = 0; i < list.size(); i++ ){
ans[i] = list.get(i);
}
return ans;
}
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner( System.in );
System.out.println( factorial( in.nextInt() ) );
}
}

public int checkRecord(int n) {
//count is an array counting [ 1 abs, last 2 is L; 1 abs, last one is L; 1 abs, last one not L; 0 abs, last one is L; 0 abs, last 1 is L; 0 abs, last one not L ]
long[] count = {0,0,1,0,1,1};
long a,b,c,d,e,f;
int big = 1000000007;
for(int i = 1; i &lt; n; i++ ){
a = count[1];
b = count[2];
c = (count[0] + count[1] + count[2] + count[3] + count[4] + count[5]) % big;
d = count[4];
e = count[5];
f = ( count[3] + count[4] + count[5] ) % big;
count[0] = a;
count[1] = b;
count[2] = c;
count[3] = d;
count[4] = e;
count[5] = f;
}
return (int) ( ( count[0] + count[1] + count[2] + count[3] + count[4] + count[5] ) % big );
}

Your attempt: iterate from the end of array, and see if it’s in descending order; when it’s not, arrange the descending order part in ascending order, and swap the new element with the one just larger than it. (86.5% just bubble sort)

Tried to clean code up – turned out that using library to sort slows things down a lot here (24% lol)

public void nextPermutation(int[] nums) {
int n = nums.length;
if( n == 1 ) return;
int max = nums[n-1];
int i = n-2;
for(; i &amp;gt;= 0; i-- ){
if( nums[i] &amp;gt;= max ){
max = nums[i];
} else {
int j = findNextLargerNumberIndex( nums, i+1, nums[i] );
swap( nums, i, j );
break;
}
}
Arrays.sort( nums, i+1, n);
}
public int findNextLargerNumberIndex( int[] nums, int startIndex, int search ){
for(int i = nums.length-1; i &amp;gt;= startIndex; i--){
if( nums[i] &amp;gt; search ) return i;
}
return startIndex;
}
public void swap( int[] nums, int index1, int index2 ){
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}

Your attempt: DP – find maximum scores of each player in each position. (45%)

public boolean PredictTheWinner(int[] nums) {
int n = nums.length;
if(n == 1) return true;
int[][] playerOneScore = new int[n][n]; //player one's max score if we play the game in range from i to j, inclusive.
int[][] playerTwoScore = new int[n][n];
for(int i = 0; i &lt; n; i++ ){
playerOneScore[i][i] = nums[i];
}
for(int d = 1; d &lt; n; d++ ){
for( int i = 0; i &lt; n-d; i++ ){
playerOneScore[i][i+d] = Math.max( nums[i] + playerTwoScore[i+1][i+d], nums[i+d] + playerTwoScore[i][i+d-1] );
playerTwoScore[i][i+d] = ( nums[i] + playerTwoScore[i+1][i+d] &lt; nums[i+d] + playerTwoScore[i][i+d-1] ) ? playerOneScore[i][i+d-1] : playerOneScore[i+1][i+d];
}
}
return ( playerOneScore[0][n-1] &gt;= playerTwoScore[0][n-1] );
}

Your attempt: scan from left to right, if the next numeral is bigger than current one in value, update current value and next index accordingly. (74.86%)

Optimization:

Actually take O(n) time to convert each digit into numeral (rather than calling hash map every time) is actually much quicker.

Your attempt: track frequency of the “breakpoints”, and the answer is number of rows – maximum frequency. (43%)

Optimization:

Using a classical for loop for each row rather than for(Integer : row) rises it to 86%, wtf? The biggest reason is probably removing an element is taking time.

Your attempt: (80.06%, O(log n) get and put – actually not quite, apparently removal in PriorityQueue uses a linear search to look for things you are removing, so eviction is O(n) time )

A priority queue to track the next element to evict

a map to track the (key, Node) pair.

a Node class that tracks key, value, frequency, and last used time.

get:

If key exists in the map, use map to retrieve the necessary node, and remove from the queue. Add a new node to the map/queue with updated frequency and last used time.

put:

If key exists in the map, use map to retrieve the necessary node, and remove from the queue. Add a new node to the map/queue with updated value, frequency and last used time.

If key doesn’t exist in the map and capacity is not reached, add Node to the map and the priority queue.

If key doesn’t exist in the map and capacity is reached, evict the key from the priority queue, and remove corresponding (key, Node) pair from the map. Add a new node to map/queue with the new key, value, freq and current time.

Better solution: (O(1) time, 86.25%)

Form a Map<Key, Frequency>, and Map<Frequency, LinkedHashSet>, and Map<Key, Value>

get:

If key exists in map, increment frequency, as well as updating the corresponding key set for the affected frequencies.

put:

If key exists in map, increment frequency, as well as updating the corresponding key set for the affected frequencies, and the new value.

If key doesn’t exist in the map and capacity is not reached, update the three maps accordingly.

If key doesn’t exist in the map and capacity is reached, evict the first key for the lowest frequency, update accordingly.

Your attempt: use a Priority Queue, initialized with (nums1[i], nums2[0]). Each time, poll an element; and add back a new one with nums2 index incremented. O(klog k) time, 65%

Your attempt: use a Deque (i.e. stack + queue) O(n) (95%)

First pass:

Go through nums once. When you get to index i, for existing elements j in Deque, mark nums[j]’s next greatest integer is nums[i] and pop it out whenever nums[j] < nums[i].

After going through nums once, you are left with a stack where the bottommost element is the largest element, and the indices in stack would have descending nums values.

Mark the max element’s next greatest integer to be -1.

Go through nums for the second time, up to the max element’s index, do step 1 again.

For the remaining things in the stack, they must have the same value as the max element. Mark all of them to have next greatest integer -1.

Your attempt: calculate frequency (for each alphabet) of p. Do the same for each continuous block in s that has same length as p. You can update the frequency of the block as you move one step to the right. (88%)

Optimization: The sliding window solution is very clean! You are using the same idea, but his way of writing is much cleaner than yours.

First attempt: cache pairwise midpoint and target slope, check if point is on the line. TLE. (O(n^3))

Second attempt: for each point, create a map, and store (distance^2, multiplicity) pair. Then sum up. O(n^2), 35%

Third attempt: same as second, except caching the distance^2 for i < j so that I only need to calculate half the distance O(n^2), 19% (Huge memory overhead, and honestly doesn’t seem to save time)

Optimization ideas:

Use second attempt as skeleton

Rather than going through the values and sum freq*(freq-1) afterwards, move this into the first for loop – i.e. whenever the map already contains the key, add 2*map.get(key) (58.72% – fastest try 98%, variance too huge)

First attempt: recursive buildup by nCr = (n-1)Cr + (n-1)C(r-1) (2ms, 59.7%)

Second attempt: recursively build up by computing nCr from nC(r-1) – casting is needed (1ms, 88.46%) (if you do this more carefully, you can get it down to 0ms)

Solution 1 : O(n^2) – DP, by tracking the array of “Longest Increasing Subsequence ending at i”. Then l[i] = 1 + max_{j < i, a[j] < a[i]} l[i]

Solution 2: O(n log n) – DP, by tracking the array of “Smallest possible number of longest Increasing Subsequence of length i-1”. For a new element, we can do a binary search; if it’s larger than all the tails, increasing length of array by 1, and attach the new tail. Otherwise if tail[i] < x <= tail[i+1], update tail[i+1]=x.

Your attempt: form a graph – vertex = envelope, edge from a to b if a can be contained in b. Then run bfs to find longest edge in the graph. O(n^2), TLE

Second attempt: Optimize by only tracking immediate neighbor – TLE.

A possible solution:

Sort the sequence in ascending order by width, and descending order by height for same width.

The problem is then the Longest-Increasing-Subsequence Problem for height.

Your attempt: sort the dictionary in descending order of length then ascending lexicographical order. Then check linearly to see if dictionary dude is subsequence of my word.

Possible optimization: don’t need to sort – you need to find the longest only, so just do one pass linear time.

First attempt: DFS via recursion. Minor optimization: don’t track the direction you came from. Still very slow (127ms – 3.88%)

Second attempt: DFS via stack. Slower – TLE

Big optimization:

You do NOT have to track visited vertices separately using a set every single time. Observe that when you use dfs, when you have to withdraw from the dfs child, you can mark the parent unvisited again!

Your attempt: naive O(nlog n) solution, by tracking one array of starting point, one array of endpoint, sort the start array, and for each endpoint, search for least starting point larger than it.

First attempt: TreeMap.

Second attempt: Implement it yourself – sort the start array, and write a binary search from scratch.

First attempt: use an array to track frequency, a second pass to track down elements with frequency 0. Drawback: O(n) space.

Second attempt: In place “cycle” solution, i.e. take an element n out, mark a[n] = -1 for visited, and repeat for the original a[n]. Loop over the whole thing once for that, and track out the unvisited ones. O(1) space.

Some other nice ideas:

For visited index n, flip the sign of a[n] if a[n] is positive – so that after one pass, only non-visited indices have positive values.

For visited index n, add n to a[n]; so that after one pass, only non-visited indices have values <= n.

Your attempt: Extremely unclean brute force code, essentially by dealing with the previous block expression right away whenever you see + or – and update the answer.

Your attempt: one pass track frequency of characters, sort characters in descending order by frequency, then write the String.

Possible Optimization:

Do not use HashMap – in standard encoding Java characters is 2 bytes long (unsafe! Should not make this assumption in general) – so can do bucket sort using an array of length 256.

Do not sort – Just build buckets. (O(n) vs O(nlog n))

Your attempt: backtrack ancestor, then traverse the ancestor to find first intersection.

Your attempt would work for any binary tree – this one is a binary SEARCH tree – which means you can take advantage of the fact that lowest common ancestor is the first node whose value is between the two target nodes.

Your initial idea was great: a^b is sum without carry, and (a&b) << 1 is precisely the carry. But you didn’t note that this gives you a recursive solution!

BFS is fine, although one actually doesn’t need BFS (!) Note that for a 1-cell and a 0-cell, you can either use left/top or right/down to reach the 0-cell from the 1-cell.

In particular, that means you can start from the top left corner, sweep to the bottom right by right/down, and update answer using only top or left neighbor. Then you can sweep back from bottom right to top left by left/top, and updates the answer by considering the bottom or right neighbor too.

This saves on the number of updates you need to do.

Your attempt: naive map of index list: O(n) memory, O( length of list ) retrieval.

One improvement: O(n) memory (with smaller constant – since no manipulation on input is needed), O( length of list ) retrieval. The technique is Reservoir sampling, a technique of doing uniform sampling on an finite stream of numbers of unknown size, given a random number generator.

The basic question is: given a finite stream (but unknown size) of numbers, figure out a way to keep/replace the number as the stream passes along so that we are uniformly sampling the whole stream.

This is your very first post. Click the Edit link to modify or delete it, or start a new post. If you like, use this post to tell readers why you started this blog.