Google Interview Question
SDE1sTeam: Google Search
Country: United States
Interview Type: In-Person
There is something called cycle leader iteration which can be used for this.
The pre-requisite for this is that the size array should be in 3^k+1 format. If the input array is not of that length then the array need to be broken in multiple subarrays to get this format for all arrays.
Once that is done cycle leader iteration can be applied on each array individually and then merge them to get final output.
Who asked you this at Google? We need to notify the hiring committee of this interviewer.
Yes it's stupid and useless interview question.
30 min. to invent something while nervous, yet the answers are pointing to published papers.......
You are good enough for Google Research (or Google X) though.
Evidenced by the loads of useless non-interview questions you've posted on cc:
careercup.com/user?id=5728613638864896
Have to agree with BigK.
The question with time and space complexity requirements will be thrown out by the hiring committee.
Without the complexity requirements, it is a decent interview question (permits multiple levels of solutions).
Ayush, if you are preparing for Google interview, I think you are going about it all wrong. Please don't reduce the signal/noise ratio of this site in the process. Thanks.
The folowing solution is, possibly, the simplest and cheapest (in terms of memory and space) that can be!
The characters in odd positions must be moved to the last half and that's what the solution shown in geeksforgeeks does. However the problem also states that those characters are digits. This is not required for the geeksforgeeks solution to work but using this fact allows a much simpler solution (this one here).
Here is the function:
#include <algorithm>
#include <cassert>
#include <cctype>
void transform(char* const begin, char* const end) {
assert(begin <= end);
const unsigned h = (static_cast<unsigned>(end - begin) + 1) / 2;
for (unsigned i = 1; i < h; ++i) {
if (std::isdigit(begin[i])) {
unsigned j = i;
while ((j = j / 2 + (j % 2) * h) != i)
std::swap(begin[i], begin[j]);
}
}
}
Here is a testing code:
#include <cstring>
#include <iostream>
void transform(char* begin, char* end);
int main() {
char src[] = "a0b1c2d3e4f5g6h7i8j9k";
const unsigned n = sizeof(src) / sizeof(char);
char str[n];
for (unsigned i = 1; i < n; ++i) {
std::strcpy(str, src);
str[i] = 0;
transform(str, str + i);
std::cout << str << '\n';
const unsigned half = (i + 1) / 2;
for (unsigned j = 0; j < half; ++j)
assert(str[j] == 'a' + static_cast<int>(j) && "Failed!");
for (unsigned j = half; j < i; ++j)
assert(str[j] == '0' + static_cast<int>(j - half) && "Failed!");
}
}
public class NumAlpha implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
if(o1.matches("\\d") && o2.matches("[a-zA-Z]")) {
System.out.println("o1" + o1);
System.out.println("o1" + o2);
return 1;
} else if (o2.matches("\\d") && o1.matches("[a-zA-Z]")) {
return -1;
}
else
return o1.compareTo(o2);
}
}
Test t = new Test();
NumAlpha na = t.new NumAlpha();
TreeSet<String> set = new TreeSet<String>(na);
set.add("a");
set.add("1");
set.add("b");
set.add("2");
set.add("c");
set.add("3");
set.add("d");
set.add("4");
System.out.println(set.toString());
package com.google.practice;
public class SortItOut {
public static void main(String[] arg){
char[] mix = {'a','1','b','2','c','3','d','4'};
sortItOut(mix);
System.out.println(String.copyValueOf(mix).toString());
}
//since every alphabet is at odd position, making sure j points to odd location
// for every swap will ensure the alphabets to be placed before digits.
public static void sortItOut(char[] mix){
int skip = 0;
for(int i=1;i<mix.length;i++){
int j = i+skip+1;
if(j>=mix.length)
skip = 0;
else{
char tmp = mix[i];
mix[i] = mix[j];
mix[j] = tmp;
skip++;
}
}
}
}
Need a little help here. I am able to place all alphabets before digits, before the skip is reset. When I apply the same logic again for the numeric part, it isn't working for all inputs. Trying to figure that out, but I think I am almost there.
Let A be the input char array and N be its size. One can easly verify that the char in position i should go to position
j = i / 2 + (i % 2) * (N / 2 + N % 2).
Using this formula makes very easy to implement a O(n) solution in time and space by copying from A[i] to B[j] where B is an auxiliary array with size N. However, we are constraint to O(1) in space.
We can workaround this limitation in a way that works for this particular problem because the ASCIIs for a-z, A-Z and 0-9 are all in [0, 127] and the range of a char is [-128, 127] (for simplicity, I'm considering a machine where char is signed but a similar argument holds for machines with unsigned char). We can mark A[i] as "dirty" if it's not in the right position by changing it's sign.
Here is the code:
bool is_dirty(char c) {
if (std::is_signed<char>::value)
return c < 0;
else
return c >= 128;
}
// Toggle c's dirtyness
char toggle(char c) {
if (std::is_signed<char>::value)
return -c;
else
return c + 128;
}
void transform(char* begin, char* end) {
const unsigned n = end - begin;
for (unsigned i = 0; i < n; ++i)
begin[i] = toggle(begin[i]);
const unsigned half = n / 2 + n % 2;
for (unsigned i = 0; i < n; ++i) {
unsigned j = i;
char c = begin[j];
while (is_dirty(c)) {
j = j / 2 + (j % 2) * half;
std::swap(c, begin[j]);
begin[j] = toggle(begin[j]);
}
}
}
I think this solution might works!
The common idea is use only even positions end replace it with index = even_position / 2
For example a1b2c3d4
1) ab12c3d4 n = 2, i = 1 (i+1 = 2, 2==2 then n += 2, i = 0)
2) abc213d4 n = 4, i = 2 (i+1 = 3, 3 < 4 then continue)
3) abc123d4 n = 4, i = 3 (i+1 = 4, 4==4 then n += 2, i = 0)
4) abcd2314 n = 6, i = 3 (i+1 = 4, 4 < 6 then continue)
5) abcd1324 n = 6, i = 4 (i+1 = 5, 5 < 6 then continue)
6) abcd1234 n = 6, i = 5 (i+1 = 6, 6 ==6 then n+=2, n >= stringArray.lengh() then it's over)
private void sort (String[] str) {
int n = 2;
int i = 0;
while (true) {
String tmpStr;
if (i == 0) {
i = n / 2;
}
tmpStr = str[i];
str[i] = str[n];
str[n] = tmpStr;
i++;
if (i == n) {
n += 2;
i = 0;
if (n >= str.length) {
break;
} else
continue;
}
}
}
}
public static String rearrange(String str){
// indexes of str: 0 1 2 3 4 5 6 7
// indexes of new: 0 2 4 6 1 3 5 7
// indexes of str: 0 1 2 3 4 5 6 7 8 9
// indexes of new: 0 2 4 6 8 1 3 5 7 9
char[] arr =str.toCharArray(); // convert to array of chars
int lastIndex = arr.length - 1; // last index
int middle = lastIndex/2;
int startIndex = 1;
char startChar = arr[startIndex];
int currIndex = startIndex;
int nextIndex ;
for (int i = 1 ; i < lastIndex; i++){
if (currIndex <= middle){
nextIndex = currIndex * 2;
}else {
nextIndex = 2 * currIndex - lastIndex;
}
if (nextIndex == startIndex){
arr[currIndex] = startChar;
if (i < lastIndex){
startIndex += 2;
startChar = arr[startIndex];
currIndex = startIndex;
continue;
}else {
break;
}
}
arr[currIndex] = arr[nextIndex];
currIndex = nextIndex;
}
return new String(arr);
}
public static void main(String[] a){
String str = "a1b2c3d4e5f6g7k8l9m0";
System.out.println(rearrange(str));
//abcdefgklm1234567890
}
public class Main {
public static void main(String args[]){
String temp = "a1b2c3d4";
int indexL=2;
int indexN = 1;
while(indexL<temp.length()){
temp = temp.substring(0,indexN)+temp.substring(indexL,indexL+1)+temp.substring(indexN,indexL)+temp.substring(indexL+1,temp.length());
indexN++;indexL++;indexL++;
}
System.out.println(temp);
}
}
My solution works without recursion, in O(n) time and O(1) memory.
It proceeds as follows, by steps
Consider the string "a1b2c3d4e5f6g7h8"
1) Handle groups of 2 -> ab12cd34ef56gh78
2) Handle groups of 4 -> abcd1234efgh5678
3) Handle groups of 8 -> abcdefgh12345678
My code works only for sizes of strings power of 2 and would require some additional code to handle any size but the main idea is there
public static void rearrange( String[] tab ){
int l = tab.length;
for( int i = 2 ; i <= log2( l ) ; i++){
int kmax = (int)Math.floor( l/(Math.pow(2,i))-1/4)-1;
for( int k = 0 ; k <= kmax ; k++ ){
for( int j = (int) Math.pow( 2, i-2 ) ; j < Math.pow( 2, i-1 ) ; j++ ){
int idx1 = (int) Math.pow( 2, i ) * k + j ;
int idx2 = (int)(Math.pow( 2, i ) * k + Math.pow( 2, i-2 ) + j);
if( idx2 < l ){
swap( tab , idx1 , idx2 );
}
}
}
}
}
#include <iostream>
#include <string>
using namespace std;
string str="zzzzzzzzzzzzz999999999999999999";
int main()
{
cout << str << endl;
int siz=str.size();
int i, char_pos=-1, num_pos=-1;
long long int int_val=0;
long long int char_val=0;
for(i=siz-1;i>=0;i--)
{
//cout << int(str[i]) << endl;
if(str[i]>47&&str[i]<58)
{
if(num_pos==-1)
{
int_val=str[i]-48;
num_pos=i;
}
else
int_val=int_val*10+(str[i]-48);
//cout << num_pos << endl;
}
else
{
if(char_pos==-1)
{
char_val=str[i]-97;
char_pos=i;
}
else
char_val=char_val*26+(str[i]-97);
}
//cout << str << endl;
}
cout << int_val << endl;
cout << char_val << endl;
i=0;
while(char_val!=0)
{
str[i]=char_val%26+97;
char_val=char_val/26;
cout << str[i] << endl;
i++;
}
while(int_val!=0)
{
str[i]=int_val%10+48;
int_val=int_val/10;
cout << str[i] << endl;
i++;
}
cout << str << endl;
}
The above code will only work for maximum of 13 characters and 18 numbers in any combination.
So it would work for 31 size of minimum (of which maximum characters are 13 and maximum numbers are 18). This can be improvised.
For example say array is:
a 2 3 b c 5 d e 4 6
Start traversing from left side of array (0th index)
find the next sequence of numbers and sequence of char and exchange those in case numeric sequence is before char sequence
[Exchange the place of '2 3' to 'b c']
a b c 2 3 5 d e 4 6
apply same logic
[Exchange the place of '2 3' 5 to 'd e']
a b c d e 2 3 5 4 6
Solution written in C++, both recursive and iterative versions. The recursive version also allows tail-call optimization by the compiler.
Output:
x3y4z6 -> xyz346 (iterative)
x3y4z6 -> xyz346 (recursive)
x3y4z6a7 -> xyza3467 (iterative)
x3y4z6a7 -> xyza3467 (recursive)
a1b2c3d4 -> abcd1234 (iterative)
a1b2c3d4 -> abcd1234 (recursive)
Code:
#include <iostream>
static void transform_recursive(std::string& str, size_t pos = 0) {
if (str.empty())
return;
if (str.size() - pos == 2) {
return;
}
if (str.size() - pos == 3) {
std::swap(str[pos], str[pos+1]);
return;
}
size_t mid = (str.size() - pos) / 2;
for (size_t i = pos + 1, j = 1; i+j < str.size(); ++i, ++j) {
std::swap(str[i], str[i+j]);
}
// tail-call recursion, can be optimized by the compiler
transform_recursive(str, pos + mid);
}
static void transform_iterative(std::string& str) {
if (str.empty())
return;
size_t pos = 0;
while (true) {
if (str.size() - pos == 2) {
break;
}
if (str.size() - pos == 3) {
std::swap(str[pos], str[pos+1]);
break;
}
size_t mid = (str.size() - pos) / 2;
for (size_t i = pos + 1, j = 1; i+j < str.size(); ++i, ++j) {
std::swap(str[i], str[i+j]);
}
pos += mid;
}
}
int main() {
std::string s1_a = "x3y4z6";
std::cout << s1_a << " -> ";
transform_iterative(s1_a);
std::cout << s1_a << " (iterative)" << std::endl;
std::string s1_b = "x3y4z6";
std::cout << s1_b << " -> ";
transform_recursive(s1_b);
std::cout << s1_b << " (recursive)" << std::endl;
std::string s2_a = "x3y4z6a7";
std::cout << s2_a << " -> ";
transform_iterative(s2_a);
std::cout << s2_a << " (iterative)" << std::endl;
std::string s2_b = "x3y4z6a7";
std::cout << s2_b << " -> ";
transform_recursive(s2_b);
std::cout << s2_b << " (recursive)" << std::endl;
std::string s3_a = "a1b2c3d4";
std::cout << s3_a << " -> ";
transform_iterative(s3_a);
std::cout << s3_a << " (iterative)" << std::endl;
std::string s3_b = "a1b2c3d4";
std::cout << s3_b << " -> ";
transform_recursive(s3_b);
std::cout << s3_b << " (recursive)" << std::endl;
}
Since the input to be segregated is a String like "a5b6c7d8" we can use String's substring method to hand pick numbers from the string and append them at the end of the string in a single for loop.
Time complexity: O(n)
space complexity: O(1)
Example:
i here denotes the index of the character in the string
i=1 -- input: a5b6c7d8 (Append 5 to the end of string) output: ab6c7d85
i=2 -- input: ab6c7d85 (Append 6 to the end of string) output: abc7d856
i=3 -- input: abc7d856 (Append 7 to the end of string) output: abcd8567
i=4 -- input: abcd8567 (Append 8 to the end of string) output: abcd5678
package stringManipulation;
public class SegregateCharAndNumbers {
private static String input="a1b2c3d4e5f6g7h8i9j1k2l3m4";
public static void main(String[] args) {
System.out.println("String before change = " + input);
for(int i=1; i<input.length()/2+1;i++) {
input = input.substring(0,i) + input.substring(i+1, input.length()) + input.charAt(i);
}
System.out.println("String after change = " + input);
}
}
I'm making use of the fact that two digits can be stored in a single character using 10*d1 + d2.
static void relocate(char[] arr) {
int n = arr.length/2;
char firstDigit = arr[1];
//Replacing each digit char in 2nd half with INTEGER that combines two
//consecutive digits as 10*(digit at pos-2) + digit
//For example, if input is a0b1c2d3e4f5,
// char[11]=45,char[9]=23,char[7]=1 (integer equivalent)
for(int i=2*n-1;i>n;i-=2) {
arr[i] = (char)((arr[2*i-2*n+1]-'0') + 10*(arr[2*i-2*n-1]-'0'));
}
for(int i=1;i<n;i++) {//Move all letters to correct pos
arr[i]=arr[2*i];
}
//From integers constructed above, extract the digits
for(int i=2*n-1;i>n;i-=2) {
arr[i-1] = (char)(arr[i]/10 + '0');
arr[i] = (char)(arr[i]%10 + '0');
}
if(n%2 == 1) arr[n] = firstDigit;
}
#include <iostream>
#include <string.h>
void trans(char* a, int size)
{
if (size <= 2) return;
for (int i = 1; i <= size - 3; i += 2)
{
// swap a[i] and a[i + 1]
a[i] ^= a[i + 1];
a[i + 1] ^= a[i];
a[i] ^= a[i + 1];
}
trans(a + 1, size - 2);
}
int main(int argc, char* argv[])
{
int length = strlen(argv[1]);
trans(argv[1], length);
std::cout << argv[1] << "\n";
return 0;
}
public static String inPlaceSeparation(String str) {
if (str == null || str.length() <= 2) {
return str;
}
char[] arr = str.toCharArray();
BitSet bs = new BitSet(arr.length);
for (int head = 1; head < arr.length - 1; ++head) {
if (bs.get(head)) {
continue;
}
char hValue = arr[head];
int to = head;
while (true) {
int from = to < arr.length / 2 ? to * 2 : 1 + 2 * (to - arr.length / 2);
if (from == head) {
arr[to] = hValue;
bs.set(to);
break;
}
arr[to] = arr[from];
bs.set(to);
to = from;
}
}
return new String(arr);
}
public static void main(String[] args) {
String str = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
System.out.println(str);
System.out.println(inPlaceSeparation(str));
}
Though theoretically, it's not O(1) space complexity (n bits space cost for array of length n), but it minimizes the number of element movement with simple logic.
Feedback appreciated
public String fixMe (String a) {
int l = a.length() ;
HashMap<Integer,String> m = new HashMap<Integer,String>(1);
for (int i=0; i < l; i++)
if (i%2==0) {
char g = a.charAt(i);
if(m.containsKey(0))
m.put(0,m.get(0)+g);
else
m.put(0,""+g);
}
for (int i=0;i<l;i++)
if(i%2 != 0)
m.put(0, m.get(0)+a.charAt(i));
return m.get(0);
}
Actually, my apologies for HashMap, a simple String object would suffice.
public String fixMe (String a) {
int l = a.length() ;
String m = new String("");
for (int i=0; i < l; i++)
if (i%2==0) {
char g = a.charAt(i);
m = m + g;
}
for (int i=0;i<l;i++)
if(i%2 != 0)
m = m + a.charAt(i);
return m;
}
I think this would be O(n) time and O(1) space. Don't get confused by the fact that it has one loop inside the other, it'd still be O(n).
void swap(string & str, int pos1, int pos2)
{
char tmp = str[pos1];
str[pos1] = str[pos2];
str[pos2] = tmp;
}
void TransformString(string & str)
{
int letterPointer = (str.size() % 2 == 0) ? str.size() - 2 : str.size() - 1;
int count = 1;
int numPointer = letterPointer - count;
while (numPointer > 0)
{
while (numPointer < letterPointer)
{
swap(str, numPointer, numPointer + 1);
numPointer++;
}
letterPointer--;
count++;
numPointer = letterPointer - count;
}
}
#include<stdio.h>
void changeString(char *string1)
{
int start;
int end;
// get string size
int stringSize = 0;
while(string1[stringSize] != '\0')
{
stringSize += 1;
}
start = 1;
end = stringSize - 2;
while(start < end)
{
for(int i = start; i <= end; i += 2)
{
int temp = string1[i];
string1[i] = string1[i + 1];
string1[i + 1] = temp;
}
start += 1;
end -= 1;
}
}
int main(void)
{
char string1[100];
printf("Enter Input: ");
scanf("%s", string1);
changeString(string1);
printf("%s\n", string1);
return 0;
}
#include<stdio.h>
void changeString(char *string1)
{
int start;
int end;
// get string size
int stringSize = 0;
while(string1[stringSize] != '\0')
{
stringSize += 1;
}
start = 1;
end = stringSize - 2;
while(start < end)
{
for(int i = start; i <= end; i += 2)
{
int temp = string1[i];
string1[i] = string1[i + 1];
string1[i + 1] = temp;
}
start += 1;
end -= 1;
}
}
int main(void)
{
char string1[100];
printf("Enter Input: ");
scanf("%s", string1);
changeString(string1);
printf("%s\n", string1);
return 0;
}
import java.util.Scanner;
public class Test {
Scanner x=new Scanner(System.in);
String s;
public static void main(String[] args) {
Test t=new Test();
t.get();
}
private void get()
{
StringBuilder builder1 = new StringBuilder();
StringBuilder builder2 = new StringBuilder();
s=x.next();
String tempChar[]=s.split("[0-9]");
String tempNum[]=s.split("[a-z]");
int i=0,j=0;
while(i<tempChar.length||j<tempNum.length)
{
if(i<tempChar.length)
{
builder1.append(tempChar[i++]);
}
else if(j<tempNum.length)
{
builder2.append(tempNum[j++]);
}
}
System.out.println(String.valueOf(builder1)+String.valueOf(builder2));
}
}
just use String instead of String builder ... space allocated for str='ab' and str ='abcd' is the same, in your case your space will be o(2) for the two strings which is the same as 0(1)
public class IsolateCharInt {
String val = "";
public IsolateCharInt(String val) {
this.val = val;
}
String printIn() {
String nums = "";
String chars = "";
for(int i=0 ; i<val.length(); i++) {
if((i % 2) == 0) {
nums += val.charAt(i);
}else
chars += val.charAt(i);
}
val = nums + chars;
return val;
}
public static void main(String[] args) {
IsolateCharInt i = new IsolateCharInt("1a2b3c4");
System.out.println(i.printIn());
}
}
This question is carefully described at geeksforgeeks org
- GK March 09, 2014Search for an-in-place-algorithm-for-string-transformation there.
Base64 encoded url: aHR0cDovL3d3dy5nZWVrc2ZvcmdlZWtzLm9yZy9hbi1pbi1wbGFjZS1hbGdvcml0aG0tZm9yLXN0cmluZy10cmFuc2Zvcm1hdGlvbi8=