Subset Sum with a negative number
Problem:
Given a sorted array say int num[10]={-5,1,6,7,9,9,20,25,31,45}, write a function void findsum(int [],int x) that can print out all possible pair of elements in array that can make a sum equal to x. For example if value of x is 26, then function should print {1,25}, {25,1}, {-5,31}, {31,-5}.
private static void findSumFunction() {
//The problem provided me with an already-sorted array
final int[] testData = new int[]{-5,1,6,7,9,9,20,25,31,45};
final int X = 26;
/*first task is to loop through original sorted array and find out where
* searching can stop. If x = 26, then searching can stop once you get
* to numbers > 26 EXCEPT for the fact that there are negative number(s)
* in the test data.
* So first, find out what the lowest number is. If it is negative, adding a
* simple calculation to the algorithm will handle it.
* find lowest number to see if there is a negative number, this is O(1)
*/
if (testData[0] < lowestNumber) {
lowestNumber = testData[0];
}
System.out.println("lowestNumber is " + lowestNumber);
//1st go through array backward & stop before any value + negative num > X
//because those elem(s) are not needed. Worst case, this is O(n)
int rightIndex = testData.length - 1;
while (testData[rightIndex] + lowestNumber > X) {
int answer = testData[rightIndex] + lowestNumber;
System.out.println("don't need " + answer);
rightIndex--;
}
//Now go through the array frontward.Never go past rightIndex
//Simultaneously I am going through the array frontward and backward
int leftIndex = 0;
while (leftIndex < rightIndex) {
if (testData[leftIndex] + testData[rightIndex] == X) {
System.out.println(testData[leftIndex] + " + " + testData[rightIndex]);
leftIndex++;
rightIndex--;
}
else if (testData[leftIndex] + testData[rightIndex] < X) {
leftIndex++;
}
else {
rightIndex--;
}
}
}
Singly Linked List – remove element
Problem:
Given a singly linked list, write a function void DeleteBefore(node **head, data). For example, if the list has values 1->3->6->7->8->9->13, if data is 7, then element with data = 6 will be removed.
As I've said before, Java's LinkedList, which is an implementation of a doubly linked list, would make solving this problem trivial, so that is exactly why I must use a singly linked list.
First, I'll create a Java object that represents an element in a singly linked list.
public class SinglyLinkedListElement {
private int data;
private SinglyLinkedListElement next;
public SinglyLinkedListElement(int data) {
this.data = data;
next = null;
}
public int getValue() {
return this.data;
}
public SinglyLinkedListElement getNext() {
return this.next;
}
public void setNext(SinglyLinkedListElement next) {
this.next = next;
}
}
Next I'll (1) instantiate a SinglyLinkedListElement for each test integer creating a singly linked list and (2) remove the element before the element x (in this case, x is hard-coded to be 9).
public static void removePreviousElementSinglyLinkedList() {
int[] testData = new int[]{1, 3, 6, 7, 8, 9, 13};
int x = 9;
SinglyLinkedListElement head = null;
SinglyLinkedListElement prevElem = null;
for (int i = 0; i < testData.length; i++) {
SinglyLinkedListElement newElem = new SinglyLinkedListElement(testData[i]);
if (head == null) {
head = newElem;
}
else {
prevElem.setNext(newElem);
}
prevElem = newElem;
}
SinglyLinkedListElement curr = head;
SinglyLinkedListElement prevElem = null;
SinglyLinkedListElement prevPrevElem = null;
while (curr != null) {
if (curr.getValue() == x) {
if (prevElem == null) {
System.out.println("No previous element to delete");
}
else {
if (prevPrevElem == null) {
//deleting head elem, so make the curr elem the new head
prevElem.setNext(null);
head = curr;
}
else {
prevPrevElem.setNext(curr);
}
}
break;
}
else {
if (prevElem != null) {
prevPrevElem = prevElem;
}
prevElem = curr;
}
curr = curr.getNext();
}
}
Singly Linked List – mth to the last element
Example Problem:
Given a singly-linked list, devise a time- and space-efficient algorithm to find the mth-to-last element of the list. Implement your algorithm, taking care to handle relevant error conditions. Define mth to last such that when m = 0, the last element of the list is returned. 1->3->6->7->8->9->13
Java's LinkedList class, which is an implementation of a doubly linked list, would make this task trivial, so that is exactly why it must be done in a singly linked list. Here is my implementation in Java.
First I would create a Java object representing an element in a singly linked list.
public class SinglyLinkedListElement {
private int data;
private SinglyLinkedListElement next;
public SinglyLinkedListElement(int data) {
this.data = data;
next = null;
}
public int getValue() {
return this.data;
}
public SinglyLinkedListElement getNext() {
return this.next;
}
public void setNext(SinglyLinkedListElement next) {
this.next = next;
}
}
Now I'll (1) instantiate a SinglyLinkedListElement for each test integer creating a singly linked list and (2) find the element that is mth from the last. In this case, m is hard-coded to be 3 below.
public static void getMthToLastElementInSinglyLinkedList() {
int[] testData = new int[]{1, 3, 6, 7, 8, 9, 13};
SinglyLinkedListElement head = null;
SinglyLinkedListElement prevElem = null;
for (int i = 0; i < testData.length; i++) {
SinglyLinkedListElement newElem = new SinglyLinkedListElement(testData[i]);
if (head == null) {
head = newElem;
}
else {
prevElem.setNext(newElem);
}
prevElem = newElem;
}
final int M = 3;
//advanced the head to at least M
SinglyLinkedListElement curr = head;
for (int i = 0; i < M; i++) {
if (curr.getNext() != null) {
curr = curr.getNext();
}
else {
int listCount = i + 1;
System.out.println("Not enough items in list");
}
}
SinglyLinkedListElement mBehind = head;
while (curr.getNext() != null) {
mBehind = mBehind.getNext();
curr = curr.getNext();
}
System.out.println("Value of mBehind is " + mBehind.getValue());
}
Reference: Programming Interviews Exposed (provides a solution in C)
The Big O (…not that kind of O)
I got this list from a Princeton site, but here's my condensed, I-wasn't-smart-or-rich-enough-for-Princeton version.
O(1): constant
Running time is the same no matter how many inputs you have (N).
O(log N): logarithmic
Gets slightly slower as N grows. When N doubles, the running time increases by a constant.
Example: Binary search, insert/delete on heap or BST
O(N): linear
Running time increases directly proportional to growth of N. When N doubles, so does running time.
O(N log N): linearithmic
When N doubles, the running time slightly more than doubles.
Example: Quicksort, mergesort
O(N2): quadratic
Acceptable for relatively small problems. When N doubles, the running time increases fourfold.
O(N3): cubic
Acceptable only for small problems. When N doubles, running time increases eightfold.
O(2N): exponential
Not typically appropriate for practical use. When N doubles, the running time squares.
O(N!): factorial
When N increases by 1, running time increases by a factor of N.