Delete Middle Node

problem

Implment an algorithm to delete a node in the middle of a singly linked list. But you can only access to that node.

note

The solution is simply to copy the data from the next node over to the current node.

code

RemoveDups

problem

Write code to remove duplicates from an unsorted linked list without using a temporary buffer.

how to solve

If I can use a temporary buffer, I recommend to use hash table. But in this case, I have to compare two elements to check that they are duplicated or not by using brute force search.

code

Insertion

problem

You are given two 32bit numbers n and m and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i.

how to solve

• Clear the bits j through i in N
• Shift M so that it lines up with bits j through i
• Merge M and N

code

AnimalShelter

Problem

An animal shelter, which holds only dogs and cats. Create the data structures to implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat.

How to solve

My approach is to simply use separate queues for dogs and cats. Then we store some sort of timestamp to mark when each animal was enqueued. When we called dequeueAny, we compare the front of the dog and cat queue and return the oldest.

Code

Rotate Matrix

problem

Given an image represented by an N*N matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

how to solve

We swap on each layer, starting from the outermost layer and working our way inwards.

code

OneAway

Problem

There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

How to solve

Implement three method testing whether the array can be edited by each way. I can check the possibility of each edit by the following way.

• Insert and Remove This means if we compared the strings they would be identical except for one character and the difference of the length is one.

• Replace This means that two strings are different only in one place

Code

SortedMerge

problem

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method B into A in sorted order.

how to solve

In this problem, I can use array A which has a large enough buffer at the end to hold B. So I insert elements into the back of the array in greedy.

code