Java Practice

Problem 1

Given an unsorted linked list, delete all duplicates such that each element appear only once.

For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.

Problem 1 - Solution

/** * Definition for singly-linked list. * class ListNode { * public int val; * public ListNode next; * ListNode(int x) { val = x; next = null; } * } */publicclassSolution {
publicListNodedeleteDuplicates(ListNodea) {
ListNodehead = a;
ListNodehold = a;
HashSet<Integer> used = newHashSet<>();
while (a.next != null) {
if (used.contains(a.val)){
hold.next = a.next;
a = hold.next;
} else {
used.add(a.val);
a = a.next;
if (hold.next != a) {
hold = hold.next;
}
}
} if (used.contains(a.val)) {
hold.next = a.next;
a = hold.next;
}
returnhead;
}
}

Problem 2

Write a function that takes an unsigned integer and returns the number of 1 bits it has.

Example:

The 32-bit integer 11 has binary representation

00000000000000000000000000001011

so the function should return 3.

Problem 2 - Solution

publicclassSolution{publicintnumSetBits(longA){intcount=0;while(A>0){if((A&1)!=0)count++;A>>=1;}returncount;}}

Problem 3

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Example :

n = 5
n! = 120 Number of trailing zeros = 1
So, return 1

Problem 3 - Naïve Solution

publicclassSolution {
publicinttrailingZeroes(inta) {
intfactorial = 1;
intcounter = 0;
for (intfactor = 2; factor <= a; factor++)
factorial *= factor;
while (factorial % 10 == 0) {
counter++;
factorial /= 10;
}
returncounter;
}
}

Problem 3 - Fancy Solution

publicclassSolution {
publicinttrailingZeroes(inta) {
intsum=0;
for(inti=5; i <= a; i*=5) sum += a/i;
returnsum;
}
}

Problem 4

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Try solving it using constant additional space.

Example :

Input : ______
| |
\/ |
1 -> 2 -> 3 -> 4
Return the node corresponding to node 3. 

Problem 4 - Solution

/** * Definition for singly-linked list. * class ListNode { * public int val; * public ListNode next; * ListNode(int x) { val = x; next = null; } * } */publicclassSolution{publicListNodedetectCycle(ListNodea){if(a==null){returnnull;}HashSet<ListNode>nodes=newHashSet<>();while(a.next!=null){if(nodes.contains(a)){returna;}else{nodes.add(a);a=a.next;}}returnnull;}}

Problem 5

Given an array A of integers and another non negative integer k, find if there exists 2 indices i and j such that A[i] - A[j] = k, i != j.

Example :

Input :

A : [1 5 3]
k : 2

Output :

1

as 3 - 1 = 2

• Return 0 / 1 for this problem.

Problem 5 - Naïve Solution

publicclassSolution {
publicintdiffPossible(finalList<Integer> a, intb) {
for (inti = 0; i < a.size(); i++) {
for (intj = 0; j < a.size(); j++) {
if (i != j) {
if (a.get(i) - a.get(j) == b)
return1;
}
}
}
return0;
}
}

Problem 5 - Fancy Solution

publicclassSolution {
publicintdiffPossible(finalList<Integer> A, intB) {
HashMap<Integer, Integer> hashMap = newHashMap<>();
for (intnum : A) {
if (hashMap.containsKey(num)) {
intvalue = hashMap.get(num);
value++;
hashMap.put(num, value);
} else {
hashMap.put(num, 1);
}
}
for (intnum : A) {
intn = B + num;
if (hashMap.containsKey(n)) {
if (num == n && hashMap.get(n) > 1)
return1;
elseif (num != n)
return1;
}
n = num - B;
if (hashMap.containsKey(n)) {
if (num == n && hashMap.get(n) > 1)
return1;
elseif (num != n)
return1;
}
}
return0;
}
}

Problem 6

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example :

Input : [1 2 2 3 1]
Output : 3

Problem 6 - SUPER FANCY Solution

publicclassSolution {
// DO NOT MODIFY THE LISTpublicintsingleNumber(finalList<Integer> A) {
intnum = 0;
for (intval : A) {
num ^= val;
}
returnnum;
}
}

Problem 7

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Given s = "Hello World",

return 5 as length("World") = 5.

Please make sure you try to solve this problem without using library functions. Make sure you only traverse the string once.

Problem 7 - Solution

publicclassSolution {
publicintlengthOfLastWord(finalStringa) {
intcount = 0;
booleanfirstWord = true;
for(inti = a.length(); i > 0; i--) {
if (a.charAt(i-1) == ' ' && firstWord) {
;
} else {
firstWord = false;
if (a.charAt(i-1) == ' ') break;
count++;
}
}
returncount;
}
}

Problem 8

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Example :

 1
/ \
2 2
/ \ / \
3 4 4 3

The above binary tree is symmetric. But the following is not:

 1
/ \
2 2
\ \
3 3

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

Problem 8 - Solution

/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */publicclassSolution {
publicintisSymmetric(TreeNodea) {
if (a == null)
return0;
if (equal(a.left, a.right)) {
return1;
} else {
return0;
}
}
publicbooleanequal(TreeNodenode1, TreeNodenode2) {
if (node1 == null && node2 == null)
returntrue;
if (node1 == null || node2 == null)
returnfalse;
if (node1.val != node2.val)
returnfalse;
returnequal(node1.left, node2.right) && equal(node1.right, node2.left);
}
}

Problem 9

Reverse bits of an 32 bit unsigned integer

Example 1:

x = 0,

 00000000000000000000000000000000 => 00000000000000000000000000000000

return 0

Example 2:

x = 3,

 00000000000000000000000000000011 => 11000000000000000000000000000000

return 3221225472

Problem 9 - Naïve String Manipulation Solution

importjava.math.BigInteger;
publicclassSolution {
publicstaticlongreverse(longa) {
Stringbs = Long.toBinaryString(a);
StringBuilderbinaryString = newStringBuilder();
while (binaryString.length() + bs.length() < 32){
binaryString.append("0");
}
binaryString.append(bs);
binaryString = binaryString.reverse();
returnparseLong(binaryString.toString(), 2);
}
privatestaticlongparseLong(Strings, intbase) {
returnnewBigInteger(s, base).longValue();
}
}

Problem 9 - Solution

publicclassSolution {
publiclongreverse(longA) {
longreverse = 0;
for (inti = 0; i < 32; i++) {
reverse = reverse << 1;
if ((A & (1 << i)) != 0)
reverse = reverse | 1;
}
returnreverse;
}
}

Problem 10

Remove Element

Given an array and a value, remove all the instances of that value in the array. Also return the number of elements left in the array after the operation.

Example: If array A is [4, 1, 1, 2, 1, 3] and value elem is 1, then new length is 3, and A is now [4, 2, 3]

Try to do it in less than linear additional space complexity.

Problem 10 - Solution

publicclassSolution {
publicintremoveElement(ArrayList<Integer> a, intb) {
for(inti = 0; i < a.size(); i++) {
if (a.get(i) == b) {
a.remove(i);
i--;
}
}
returna.size();
}
}

Problem 11

Remove duplicates from Sorted Array Given a sorted array, remove the duplicates in place such that each element appears only once and return the new length.

Note that even though we want you to return the new length, make sure to change the original array as well in place

Do not allocate extra space for another array, you must do this in place with constant memory.

Example: Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2].

Problem 11 - Solution

publicclassSolution {
publicintremoveDuplicates(ArrayList<Integer> a) {
HashSet<Integer> hash = newHashSet<>();
for (inti = 0; i < a.size(); i++ ) {
if (hash.contains(a.get(i))) {
a.remove(i);
i--;
} else {
hash.add(a.get(i));
}
}
returna.size();
}
}

Problem 12

Reverse digits of an integer.

Example1:

x = 123,

return 321

Example2:

x = -123,

return -321

Return 0 if the result overflows and does not fit in a 32 bit signed integer

Problem 12 - Solution

publicclassSolution {
publicintreverse(intA) {
intsign = (A > 0) ? 1 : -1;
longret = 0;
A *= sign;
while(A > 0) {
ret *= 10;
ret += A%10;
A /= 10;
}
if (ret > 0x7fffffff) return0;
return ((int)ret) * sign;
}
}

Problem 13

Given a column title as appears in an Excel sheet, return its corresponding column number.

Example:

 A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 

Problem 13 - Solution

publicclassSolution {
publicinttitleToNumber(Stringa) {
intresult = 0;
// Base 26 Conversionfor (inti = 0; i < a.length(); i++) {
result *= 26;
result += (a.charAt(i) - 'A') + 1;
}
returnresult;
}
}

Problem 14

Given numRows, generate the first numRows of Pascal’s triangle.

Pascal’s triangle : To generate A[C] in row R, sum up A’[C] and A’[C-1] from previous row R - 1.

Example:

Given numRows = 5,

Return

[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

Problem 14 - Solution

publicclassSolution {
publicArrayList<ArrayList<Integer>> generate(inta) {
ArrayList<ArrayList<Integer>> pascal = newArrayList<>();
ArrayList<Integer> firstRow = newArrayList<>();
intprevRow = 1;
intind1 = 0;
intind2 = 1;
if (a == 0) returnpascal;
firstRow.add(1);
pascal.add(firstRow);
if (a == 1) returnpascal;
ArrayList<Integer> secondRow = newArrayList<>();
secondRow.add(1);
secondRow.add(1);
pascal.add(secondRow);
for (inti = 0; i < (a - 2); i++) {
ArrayList<Integer> newRow = newArrayList<>();
newRow.add(1);
for(intj = 0; j < prevRow; j++)
newRow.add(pascal.get(prevRow).get(ind1++) + pascal.get(prevRow).get(ind2++));
newRow.add(1);
pascal.add(newRow);
prevRow++;
ind1 = 0;
ind2 = 1;
} returnpascal;
}
}

Problem 15

Given a non-negative number represented as an array of digits,

add 1 to the number ( increment the number represented by the digits ).

The digits are stored such that the most significant digit is at the head of the list.

Example:

If the vector has [1, 2, 3]

the returned vector should be [1, 2, 4]

as 123 + 1 = 124.

NOTE: Certain things are intentionally left unclear in this question which you should practice asking the interviewer. For example, for this problem, following are some good questions to ask :

• Q : Can the input have 0’s before the most significant digit. Or in other words, is 0 1 2 3 a valid input?
• A : For the purpose of this question, YES
• Q : Can the output have 0’s before the most significant digit? Or in other words, is 0 1 2 4 a valid output?
• A : For the purpose of this question, NO. Even if the input has zeroes before the most significant digit.

Problem 15 - Solution

publicclassSolution {
publicArrayList<Integer> plusOne(ArrayList<Integer> a) {
for(inti = a.size() - 1; i >= 0; i--) {
// If the digit is not 9, just increment by 1if (a.get(i) != 9) {
a.set(i, a.get(i) + 1);
break;
// Otherwise, set digit to 0 and move back one digit// to increment
} else {
// Edge case: [9, 9, ..., 9]if (i == 0){
a.set(0, 1);
a.add(0);
} else {
a.set(i, 0);
}
}
}
// Remove leading zerosfor(inti = 0; a.get(i) == 0; i++)
a.remove(i--);
returna;
}
}

Problem 16

Given a linked list, remove the nth node from the end of list and return its head.

For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: * If n is greater than the size of the list, remove the first node of the list.

Try doing it using constant additional space.

Problem 16 - Solution (With test driver)

importjava.io.*;
importjava.util.*;
classListNode {
publicintval;
publicListNodenext;
ListNode (inta) {
this.val = a;
this.next = null;
}
}
classSolution {
publicstaticvoidmain(String[] args) {
ListNodea = newListNode(1);
ListNodeb = newListNode(2);
ListNodec = newListNode(3);
ListNoded = newListNode(4);
ListNodee = newListNode(5);
a.next = b;
b.next = c;
c.next = d;
d.next = e;
a = removeNthFromEnd(a, 5);
while (a != null) {
System.out.println(a.val);
a = a.next;
}
}
publicstaticListNoderemoveNthFromEnd(ListNodea, intb) {
intlistSize = 0;
ListNodetemp = a;
if (b == 0) {
returna;
}
while (temp != null) {
listSize++;
temp = temp.next;
}
temp = a;
if (listSize <= b) {
temp = a.next;
a.next = null;
returntemp;
} else {
for(inti = 0; i < (listSize - (b + 1)); i++){
temp = temp.next;
}
temp.next = temp.next.next;
}
returna;
}
}

Problem 17 - Asked During Interview

Given a String, determine if it is a palindrome or not.

For example, A man, a plan, a canal. Panama!, and race ecar should return true.

chicken, and gravy should return false.

Problem 17 - Solution

publicclassJavaTest
{
publicstaticbooleanfoo (Stringa) {
intx = a.length() - 1; inti = 0;
a = a.toLowerCase();
while (i != x) {
while (!Character.isLetter(a.charAt(i)) && (i != x))
i++;
while (!Character.isLetter(a.charAt(x)) && (i != x))
x--;
if (i != x) {
if ((a.charAt(i) == a.charAt(x))) {
x--;
i++;
} else {
returnfalse;
}
}
}
returntrue;
}
publicstaticvoidmain(String [] args)
{
Stringstr = "A man, a plan, a canal. Panama!";
System.out.println(foo(str));
}
}