CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Alcatel Lucent Interview Question


Country: United States
Interview Type: In-Person
More Questions from This Interview



Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm: Compare quotients and reminders

import java.util.Arrays;
import java.util.Comparator;

public class DictionarySort {
	public static void main(String[] args) {
		Integer[] array = new Integer[] { 1, 2, 10, 20, 100, 110 };
		Arrays.sort(array, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				int quotient1 = o1 / 10;
				int reminder1 = o1 % 10;
				int quotient2 = o2 / 10;
				int reminder2 = o2 % 10;
				if (quotient1 != 0 && quotient2 != 0) {
					if (quotient1 == quotient2)
						return 0;
					int msd1 = 0;
					int msd2 = 0;
					if (quotient1 >= 10)
						msd1 = quotient1 / 10;
					else
						msd1 = quotient1;
					if (quotient2 >= 10)
						msd2 = quotient2 / 10;
					else
						msd2 = quotient2;
					if (msd1 == msd2)
						return quotient1 - quotient2;
					if (msd1 != msd2)
						return msd1 - msd2;

				}

				if (quotient1 == 0 && quotient2 == 0)
					return reminder1 - reminder2;
				if (quotient2 != 0 && quotient1 == 0) {
					while (quotient2 >= 10)
						quotient2 /= 10;
					return reminder1 - quotient2;
				}
				if (quotient1 != 0 && quotient2 == 0) {
					while (quotient1 >= 10)
						quotient1 /= 10;
					return quotient1 - reminder2;
				}

				return 1;
			}

		});
		System.out.println(Arrays.toString(array));
	}
}

- naren December 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Small correction: (when questions are equal)it should return difference of reminders and not 0 although for the example it does not matter.

if (quotient1 == quotient2)
						return reminder1-reminder2;

- naren December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think this will work if there numbers with more than 3 digits

- rizhang December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@rizhang. you are right. There was one glitch in the code which is corrected. Now it works for any length of digits(+ve integers ofcourse). Revised code here with updated inputs for the program

public class DictionarySort {
	public static void main(String[] args) {
		Integer[] array = new Integer[] { 1, 2, 2222, 222222, 10, 20, 100, 110,
				3333, 332,111111111,2222222,233332,66666666,1111111,9090,8880 };
		System.out.println(Arrays.toString(array));
		Arrays.sort(array, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				int quotient1 = o1 / 10;
				int reminder1 = o1 % 10;
				int quotient2 = o2 / 10;
				int reminder2 = o2 % 10;
				if (quotient1 != 0 && quotient2 != 0) {
					if (quotient1 == quotient2)
						return reminder1 - reminder2;
					int msd1 = 0;
					int msd2 = 0;
					if (quotient1 >= 10) {
						msd1 = quotient1 / 10;
						while (msd1 >= 10)
							msd1 = msd1 / 10;
					} else
						msd1 = quotient1;
					if (quotient2 >= 10) {
						msd2 = quotient2 / 10;
						while (msd2 >= 10)
							msd2 = msd2 / 10;
					} else
						msd2 = quotient2;
					if (msd1 == msd2)
						return quotient1 - quotient2;
					if (msd1 != msd2)
						return msd1 - msd2;

				}

				if (quotient1 == 0 && quotient2 == 0)
					return reminder1 - reminder2;
				if (quotient2 != 0 && quotient1 == 0) {
					while (quotient2 >= 10)
						quotient2 /= 10;
					return reminder1 - quotient2;
				}
				if (quotient1 != 0 && quotient2 == 0) {
					while (quotient1 >= 10)
						quotient1 /= 10;
					return quotient1 - reminder2;
				}

				return 1;
			}

		});
		System.out.println(Arrays.toString(array));
	}
}

- naren December 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Java, write a custom Comparator that compares two Integers. The comparator first determines how many digits both numbers has and does a digit by digit comparison. Then, if all digits are equal, the number with the least number of digits is considered "smaller"

public static void dictionarySort(List<Integer> numbers) {
		Collections.sort(numbers, new Comparator<Integer>() {
			@Override
			public int compare(Integer n, Integer m) {
				if(n == m) return 0;
				
				int nDigits = 0;
				int mDigits = 0;
				
				while(n/Math.round(Math.pow(10, ++nDigits)) > 0);
				while(m/Math.round(Math.pow(10, ++mDigits)) > 0);
				
				int digitsToCompare = Math.min(nDigits, mDigits);
				for(int i = 1; i <= digitsToCompare; i++) {
					int nDigit = n/(int) Math.round(Math.pow(10, nDigits - i));
					int mDigit = m/(int) Math.round(Math.pow(10, mDigits - i));
					if(nDigit < mDigit) return -1;
					if(mDigit < nDigit) return 1;
				}
				
				if(nDigits < mDigits) return -1;
				else return 1;
			}
			
		});
	}

	public static void main(String[] args) {
		List<Integer> numbers = new ArrayList<>();
		numbers.add(1);
		numbers.add(2);
		numbers.add(10);
		numbers.add(20);
		numbers.add(100);
		numbers.add(110);
		System.out.println(numbers);
		dictionarySort(numbers);
		System.out.println(numbers);
	}

Input: 1, 2, 10, 20, 100, 110
Output: 1, 10, 100, 110, 2, 20

- JRS December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think we need any kinds of loops for that:

final static Comparator<Integer> DICT_COMP = new Comparator<Integer>() {
		@Override
		public int compare(Integer o1, Integer o2) {
			int v1 = o1.intValue();
			int v2 = o2.intValue();
			int len1 = getDigits(v1);
			int len2 = getDigits(v2);
			// make them the same length
			if(len1 < len2) 
				v1 = v1 * (int)Math.pow(10, len2 - len1);
			else 
				v2 = v2 * (int)Math.pow(10, len1 - len2);
			// if values are unequal, compare by value, otherwise shorter numbers go first
			if(v1 != v2) return v1 - v2;
			else return len1 - len2;
		}
		
		// return # of dezimal (non-0) digits of number
		int getDigits(int number) {
			int len = 0;
			while(number != 0) {
				number /= 10;
				len++;
			}
			return len;
		}
	};
	
	public static final void main(String[] args) {
		List<Integer> vals = Arrays.asList(10, 2, 1, 20, 100, 110);
		Collections.sort(vals, DICT_COMP);
		System.out.println(vals);
	}

- Flo January 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hmm, this will lead to problems with very big numbers...

- Flo January 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
int[] arr = { 1, 2, 10, 20, 100, 110 };
HashMap<Integer, Integer> map = find(arr);

for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length - i; j++) {
if (map.get(arr[j - 1]) > map.get(arr[j])) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
} else if (map.get(arr[j - 1]) == map.get(arr[j])) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
for (int item : arr) {
System.out.println(item);
}
}

private static HashMap<Integer, Integer> find(int[] input) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer element : input) {
int item = element;
int length = (int) (Math.log10(element) + 1);
if (length > 1) {
while (element > 0) {
int length1 = (int) (Math.log10(element) + 1);
if (length1 == 1)
break;
element = element / 10;
}
map.put(item, element);
} else {
map.put(element, element);
}
}
return map;
}

- Anonymous January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		int[] arr = { 1, 2, 10, 20, 100, 110 };
		HashMap<Integer, Integer> map = getQuotientAsMapValue(arr);

		for (int i = 0; i < arr.length; i++) {
			for (int j = 1; j < arr.length - i; j++) {
				if (map.get(arr[j - 1]) > map.get(arr[j])) {
					int temp = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = temp;
				} else if (map.get(arr[j - 1]) == map.get(arr[j])) {
					if (arr[j - 1] > arr[j]) {
						int temp = arr[j - 1];
						arr[j - 1] = arr[j];
						arr[j] = temp;
					}
				}
			}
		}
		for (int item : arr) {
			System.out.println(item);
		}
	}

	//method which accepts the input array and returns the map with the number as key and quotient as value
	private static HashMap<Integer, Integer> getQuotientAsMapValue(int[] input) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (Integer element : input) {
			int item = element;
			//find the number of digits in the number
			int length = (int) (Math.log10(element) + 1);
			if (length > 1) {
				while (element > 0) {
					int length1 = (int) (Math.log10(element) + 1);
					//break if the number of digits is 1
					if (length1 == 1)
						break;
					element = element / 10;
				}
				map.put(item, element);
			} else {
				map.put(element, element);
			}
		}
		return map;
	}

- Anonymous January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		int[] arr = { 1, 2, 10, 20, 100, 110 };
		HashMap<Integer, Integer> map = getQuotientAsMapValue(arr);

		for (int i = 0; i < arr.length; i++) {
			for (int j = 1; j < arr.length - i; j++) {
				if (map.get(arr[j - 1]) > map.get(arr[j])) {
					int temp = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = temp;
				} else if (map.get(arr[j - 1]) == map.get(arr[j])) {
					if (arr[j - 1] > arr[j]) {
						int temp = arr[j - 1];
						arr[j - 1] = arr[j];
						arr[j] = temp;
					}
				}
			}
		}
		for (int item : arr) {
			System.out.println(item);
		}
	}

	//method which accepts the input array and returns the map with the number as key and quotient as value
	private static HashMap<Integer, Integer> getQuotientAsMapValue(int[] input) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (Integer element : input) {
			int item = element;
			//find the number of digits in the number
			int length = (int) (Math.log10(element) + 1);
			if (length > 1) {
				while (element > 0) {
					int length1 = (int) (Math.log10(element) + 1);
					//break if the number of digits is 1
					if (length1 == 1)
						break;
					element = element / 10;
				}
				map.put(item, element);
			} else {
				map.put(element, element);
			}
		}
		return map;
	}

- Shridhar January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		int[] arr = { 1, 2, 10, 20, 100, 110 };
		HashMap<Integer, Integer> map = getQuotientAsMapValue(arr);

		for (int i = 0; i < arr.length; i++) {
			for (int j = 1; j < arr.length - i; j++) {
				if (map.get(arr[j - 1]) > map.get(arr[j])) {
					int temp = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = temp;
				} else if (map.get(arr[j - 1]) == map.get(arr[j])) {
					if (arr[j - 1] > arr[j]) {
						int temp = arr[j - 1];
						arr[j - 1] = arr[j];
						arr[j] = temp;
					}
				}
			}
		}
		for (int item : arr) {
			System.out.println(item);
		}
	}

	//method which accepts the input array and returns the map with the number as key and quotient as value
	private static HashMap<Integer, Integer> getQuotientAsMapValue(int[] input) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (Integer element : input) {
			int item = element;
			//find the number of digits in the number
			int length = (int) (Math.log10(element) + 1);
			if (length > 1) {
				while (element > 0) {
					int length1 = (int) (Math.log10(element) + 1);
					//break if the number of digits is 1
					if (length1 == 1)
						break;
					element = element / 10;
				}
				map.put(item, element);
			} else {
				map.put(element, element);
			}
		}
		return map;
	}

- Shridhar January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
int[] arr = { 1, 2, 10, 20, 100, 110 };
HashMap<Integer, Integer> map = getQuotientAsMapValue(arr);

for (int i = 0; i < arr.length; i++) {
for (int j = 1; j < arr.length - i; j++) {
if (map.get(arr[j - 1]) > map.get(arr[j])) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
} else if (map.get(arr[j - 1]) == map.get(arr[j])) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
for (int item : arr) {
System.out.println(item);
}
}

//method which accepts the input array and returns the map with the number as key and quotient as value
private static HashMap<Integer, Integer> getQuotientAsMapValue(int[] input) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer element : input) {
int item = element;
//find the number of digits in the number
int length = (int) (Math.log10(element) + 1);
if (length > 1) {
while (element > 0) {
int length1 = (int) (Math.log10(element) + 1);
//break if the number of digits is 1
if (length1 == 1)
break;
element = element / 10;
}
map.put(item, element);
} else {
map.put(element, element);
}
}
return map;
}

- Anonymous January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		int[] arr = { 1, 2, 10, 20, 100, 110 };
		HashMap<Integer, Integer> map = getQuotientAsMapValue(arr);

		for (int i = 0; i < arr.length; i++) {
			for (int j = 1; j < arr.length - i; j++) {
				if (map.get(arr[j - 1]) > map.get(arr[j])) {
					int temp = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = temp;
				} else if (map.get(arr[j - 1]) == map.get(arr[j])) {
					if (arr[j - 1] > arr[j]) {
						int temp = arr[j - 1];
						arr[j - 1] = arr[j];
						arr[j] = temp;
					}
				}
			}
		}
		for (int item : arr) {
			System.out.println(item);
		}
	}

	//method which accepts the input array and returns the map with the number as key and quotient as value
	private static HashMap<Integer, Integer> getQuotientAsMapValue(int[] input) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (Integer element : input) {
			int item = element;
			//find the number of digits in the number
			int length = (int) (Math.log10(element) + 1);
			if (length > 1) {
				while (element > 0) {
					int length1 = (int) (Math.log10(element) + 1);
					//break if the number of digits is 1
					if (length1 == 1)
						break;
					element = element / 10;
				}
				map.put(item, element);
			} else {
				map.put(element, element);
			}
		}
		return map;
	}

- Shridhar January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

radix sort

- tmp December 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Radix sort is for strings

- mohit December 25, 2014 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More