Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Please test your code for input char arr []={'a','c','e','g','i','j'}; and char c='f'.
O/p should be 'g' but your code gives o/p as 'i'
Here is my solution:
char getSmallestLarge(char [] list,char c)
{
SmallestCharacter sc=new SmallestCharacter();
return sc.BinarySearchChar(list,c,0,list.length-1);
}
char BinarySearchChar(char[] list,char c,int low,int high)
{
if(low>high)
return ' ';
if(high-low+1==2)
{
if(list[low]<=c && list[high]>c)
return list[high];
return list[0];
}
if(high-low+1==3)
{
if(list[low]==c)
return list[low+1];
if(list[low+1]==c)
return list[low+2];
if(list[low]<c && list[low+1]>c)
return list[low+1];
if(list[low+1]<c && list[low+2]>c)
return list[low+2];
//default case
return list[0];
}
int mid=low+high/2;
if(list[mid]==c)
return list[mid+1];
else if (list[mid-1]<c && list[mid]>c)
return list[mid];
else if(list[mid]<c && list[mid+1]>c)
return list[mid+1];
else if(list[mid]>c)
return BinarySearchChar(list,c,0,mid-1);
else if(list[mid]<c)
return BinarySearchChar(list,c,mid+1,high);
return list[0];
}
Actually it doesn't make much difference even if duplicates are allowed.
public char nextChar2(char[] list, char c) {
if (list == null || list.length == 0)
throw new IllegalArgumentException("Null or empty list!");
int start = 0;
int end = list.length - 1;
if (c < list[0] || c >= list[list.length - 1])
return list[0];
while (start < end) {
int mid = (start + end) / 2;
if (c == list[mid]) {
if (list[mid + 1] > c)
return list[mid + 1];
else
start = mid + 1;
}
else if (c < list[mid]) {
end = mid - 1;
}
else
start = mid + 1;
}
if (list[start] == c)
return list[start + 1];
return list[start];
}
keep two variables, one that stores the smallest character and another that stores the smallest character that is also strictly larger than the given character.
char smallest_of_strictly_larger(char* str, char c)
{
char s = 'z'; // the smallest char
char sl = c; // the smallest char that is strictly larger than the given c
int i=0;
while( str[i]!='\0' ) {
if( str[i]<s )
s = str[i];
if( str[i]>c && (sl==c || str[i]<sl) )
sl = str[i];
i++;
}
return sl==c ? s : sl;
}
public static char find(char [] chs , char target){
int left = 0;
int right = chs.length - 1;
while(left<=right){
int mid = (left+right)/2;
if (chs[mid] == target){
if (mid<chs.length - 1){
return chs[mid+1];
}else{
return chs[0];
}
} else if (target > chs[mid]){
left = mid+1;
}else{
right = mid -1 ;
}
}
return left == 0? chs[0]:left==chs.length? chs[left-1]:chs[left];
}
In Python,
def smallest_strictly_larger(list, target):
list.sort(reverse=True)
found = list[-1] #needed for wrap-around case
for e in list:
if e > target:
found = e
else:
break #end prematurely
return found
list = ["c", "f", "j", "p", "v"]
target = "d"
print smallest_strictly_larger(list, target)
This works but it's not the most efficient as it's the brute force methodology. Like all of the others above, you should use binary search.
from types import ListType
def getNext(sorted_array, char):
left = 0
right = len(sorted_array) - 1
result = sorted_array[0]
assert len(sorted_array) > 0
assert ListType(sorted_array)
if len(sorted_array) == 1:
return result
while left < right:
middle = left + (right - left) / 2
if sorted_array[middle] == char:
if middle < len(sorted_array) - 1:
return sorted_array[middle+1]
else:
return result
elif sorted_array[middle] < char:
left = middle + 1
else:
right = middle - 1
result = sorted_array[middle]
return result
list = ["c", "f", "j", "p", "v"]
target = "d"
do a modified binary search O(logn)
public char modBS(char[]input,int left, int right, char target){
if(left > right){
return input[left%input.length];
}
int mid = (left + right)/2;
if(input[mid] == target){
return input[(mid+1)%input.length];
}else if(input[mid] < target){
return modBS(input,mid+1,right,target);
}else{
return modBS(input,left,mid-1,target);
}
}
public char findCharacter(char[] input, char target){
return modBS(input,0,input.length-1,target);
}
In scala
object SmallestChar extends App {
def smallestChar(chars:Seq[Char], char:Char):Char = {
if (char>=chars.last) return chars(0)
def search(lower:Int, upper:Int):Char = {
var middle = (lower+upper)/2
val c = chars(middle)
if (c==char) return chars(middle+1)
if (upper-lower<=1) {
if (chars(lower)<char) return chars(upper)
else return chars(lower)
}
if (c<char) search(middle, upper)
else search(lower, middle)
}
search(0, chars.length)
}
"acfkvz".foreach(c=>println(smallestChar("cfjpv", c)))
println
"ackz".foreach(c=>println(smallestChar("cfjpv", c)))
println
"fcd".foreach(c=>println(smallestChar("cfk", c)))
}
#include <iostream>
#include <vector>
using namespace std;
char getSmallest(vector<char>& chars, char c, int l, int h, int n) {
int m = (l+h)/2;
if (chars[m] > c) {
if (m > 0 && chars[m-1] > c) {
return getSmallest(chars, c, l, m-1,n);
} else {
return chars[m];
}
} else if (chars[m] < c) {
if (m == n-1) {
return chars[0];
} else {
return getSmallest(chars, c, m+1,h,n);
}
} else {
if (m == n-1) {
return chars[0];
} else {
return chars[m+1];
}
}
}
int main() {
vector<char> chars;
chars.push_back('c');
chars.push_back('f');
chars.push_back('j');
chars.push_back('p');
chars.push_back('v');
cout << "Smallest : " << getSmallest(chars, 'c',0,4,5) << "\n";
cout << "Smallest : " << getSmallest(chars, 'z',0,4,5) << "\n";
cout << "Smallest : " << getSmallest(chars, 'k',0,4,5) << "\n";
cout << "Smallest : " << getSmallest(chars, 'a',0,4,5) << "\n";
cout << "Smallest : " << getSmallest(chars, 'v',0,4,5) << "\n";
cout << "Smallest : " << getSmallest(chars, 'j',0,4,5) << "\n";
vector<char> chars2;
chars2.push_back('c');
cout << "Smallest : " << getSmallest(chars2, 'j',0,0,1) << "\n";
cout << "Smallest : " << getSmallest(chars2, 'a',0,0,1) << "\n";
cout << "Smallest : " << getSmallest(chars2, 'c',0,0,1) << "\n";
chars2.push_back('d');
cout << "Smallest : " << getSmallest(chars2, 'c',0,1,2) << "\n";
cout << "Smallest : " << getSmallest(chars2, 'd',0,1,2) << "\n";
}
Assuming the list doesn't contain duplicates. It's just a simple variation of binary search.
Test Case:
Output:
- chriscow January 31, 2014